Некоторые применения алгебры высказываний

I. Анализ логических рассуждений. Рассмотрим несколько примеров, которые используют понятие логического следования.

Примеры: 1. Правильно ли следующее логическое рассуждение: “Когда выпадает снег, птицы улетают на юг. Если птицы улетели на юг, то скоро наступит зима. Зима наступила. Следовательно, либо выпал снег, либо птицы улетели на юг”.

a	b	c	a ® b	b ® c	b Ú a
0	0	0	1	1	0
0	0	1	1	1
0	1	0	1	0	1
0	1	1	1	1	1
1	0	0	0	1	1
1	0	1	0	1	1
1	1	0	1	0	1
1	1	1	1	1	1

Обозначим элементарные высказывания буквами: a := “Выпал снег”, b := “Птицы улетели на юг”, c := “Наступила зима”. Тогда получим схему рассуждения: a ® b, b ® c, с b Ú a. Проверим, так ли это, по таблице истинности. Как видно из таблицы, формула b Ú a не является логическим следствием формул a ® b, b ® c, с: именно, она ложна при a = 0 = b, c = 1, когда все посылки рассматриваемого логического следования истинны. Другими словами, в ситуации, когда зима наступила, но снег не выпал и птицы не улетели на юг, приведённый вывод не корректен.

2. Оцените правильность логического вывода: “Если a < b, то b – a > 0. Если a ³ b, то a – b ³ 0. Либо a < b, либо a – b ³ 0. Следовательно, либо неверно, что a – b < 0, либо неверно, что b – a £ 0”.

Обозначая элементарные высказывания буквами, получим: x := “a < b”, y := “b – a > 0”, z := “a ³ b”, t := “a – b ³ 0”. Тогда = “a – b < 0”, = “b – a £ 0”, и нужно схема рассуждения x ® y, z ® t, x Ú t Ú , т.е. x ® y, z ® t, x Ú t t Ú y. Формула t Ú y ложна только при t = 0 = y, но при этих значениях все три формулы x ® y, z ® t, x Ú t не могут быть одновременно истинны: для формулы x Ú t условие истинности при t = 0 означает x = 1, что влечёт ложность значения формулы x ® y. Итак, заключение не может быть ложным при истинности всех посылок, т.е. рассуждение правильное.

Замечание: С точки зрения математики в целом все посылки и заключение в исследованном рассуждении истинны.

3. Оцените правильность логического вывода: “Если число, составленное из двух младших цифр числа чётно, то само число делится на 2. Если сумма всех цифр числа делится на 3, то само число делится на 3. Сумма цифр трёхзначного числа равна 27. Число 27 делится на 3. Значит, это трёхзначное число не делится на 2”.

Аналогично предыдущему, a := “число, составленное из двух младших цифр числа n чётно”, b := “число n делится на 2”, c := “сумма всех цифр числа n делится на 3”, d := “число n делится на 3”, e := “число n трёхзначно”, f := “сумма цифр числа n равна 27”, g := “27 делится на 3”.

Исследуем логическое следование a ® b, c ® d, e Ù f, g e Ù . Очевидно, что в таком общем виде оно не имеет места (?!), хотя рассматриваемое рассуждение верно с общематематической точки зрения: если при сформулированных условиях M 2, то цифра z чётна, и x + y + z = 27 влечёт x = y = z = 9 – противоречие.

Однако, с точки зрения логики, в этом верном математическом рассуждении есть пробелы: заключение невозможно вывести из сформулированных посылок, используя только правила логического вывода – мы привлекли для обоснования заключения арифметическое свойство трёхзначных чисел. Этот пример показывает, что математика не сводится к логике, хотя и не может без неё обойтись. Придумайте более простые примеры, иллюстрирующие этот вывод.

II. Оптимизация логики условных переходов в программах. В сложных программах может использоваться много логических переменных, которые, причудливо сплетаясь и нагромождаясь друг на друга в условных операторах, способны запутать даже опытного программиста.

Примеры. 1. Следующий фрагмент программы чудовищен:

if (not(a and b) or (a or b)) then

P

else

if (not(a or b) and not(b)) then

Q

else

R;

Действительно, стоит только упростить логическое выражение

Ú (a Ú b) º Ú Ú a Ú b º Ú a Ú b Ú º 1,

как выяснится, что никаких условных операторов вообще не нужно: приведённый фрагмент программы равносилен просто выполнению группы операторов P.

2. Не лучше и такой фрагмент:

if (not(a and b) or (not(a or с) and not(b) and c)) then

P

else

if (not(a or b) and not(b or c)) then

Q

else

R;

Первое условие – для группы операторов P – оптимизируется так:

Ú (ÙÙ c) º Ú Ú (Ù Ù Ù c) º

º Ú Ú (ÙÙ Ù c) º Ú º .

Условие для группы операторов Q таково:

Ù Ù º a Ù b Ù Ù º a Ù b Ù Ù Ù º 0,

так что операторы группы Q не выполняются никогда, а условие для группы операторов R принимает вид a Ù b. Поэтому весь рассматриваемый фрагмент программы равносилен такому:

if not(a and b) then

P

else

R;

Однако его лучше (?!) переписать следующим образом:

if (a and b) then

R

else

P;

Упражнения: 1. Почему в программах лучше писать not(a and b), нежели not(a) or not(b), хотя по закону де Моргана эти операторы равносильны ?

2.Оптимизируйте фрагмент программы:

if (not(a or b and c) or not(b or c)) then

P

else

if (b and not(a and c)) then

Q

else

R;

3.Приведите ещё пару-тройку логических несуразностей из собственных программ.

III. Автоматизированный логический вывод формул. Пусть заданы формулы A₁ , … , A_n , A от некоторого набора пропозициональных переменных и нужно понять, верно ли, что A₁ , … , A_n A. Оказывается, что для машинной проверки удобно использовать правило резолюций в виде или в терминах логического следования A Ú B , Ú C B Ú C.

Привычное человеку правило modus ponens является частным случаем этого правила резолюций при B º 0 : ввиду A Ú B º A , Ú C º A ® C , B Ú CºC правило резолюций принимает знакомый вид – modus ponens.

Как было доказано, логическое следование A₁ , … , A_n A имеет место тогда и только тогда, когда (A₁ Ù … Ù A_n ® A) º 1. Удобнее перейти к отрицаниям:

0 º .

Значит нужно понять, что A₁ Ù … Ù A_n Ùº 0, т.е. A₁ Ù … Ù A_n Ùº Ф Ùдля некоторой формулы Ф, т.е. A₁ , … , A_n , (этого достаточно ?!).

Запишем посылки A₁ , … , A_n , в КНФ и обозначим множество всех элементарных дизъюнкций, участвующих в этих КНФ через D = {D₁ , … , D_m}. Тогда каждая посылка, будучи конъюнкцией некоторых элементов множества D, является логическим следствием множества формул D (по правилу введения конъюнкции), т.е. D A₁ , … , D A_n , D . Поэтому D A₁ Ù … Ù A_n Ù и D Ф Ù . Обратно, если D Ф Ù , то D₁ Ù … Ù D_m ® Ф Ù – закон логики, причём D₁ Ù … Ù D_m º A₁ Ù … Ù A_n Ù , т.к. каждая формула в правой части является конъюнкцией некоторых элементарных дизъюнкций из левой части, а каждая дизъюнкция из левой части встречается в одной из формул правой части. Итак, задача о проверке следования A₁ , … , A_n , Ф Ù сводится к проверке следования D Ф Ù для заданного конечного множества D элементарных дизъюнкций.

Возникшую редуцированную задачу будем решать методом резолюций, который можно описать так:

· перебираем дизъюнкции из множества D , пока не найдём пару вида , где e_l , d_m Î {0, 1, Æ} (1 £ £ s), а запись означает, что переменная x_l не участвует в соответствующей дизъюнкции. Таким образом, в D_i и D_j переменная x_k (для некоторого k) встречается в одной дизъюнкции с отрицанием, а в другой – без отрицания.

· к этой паре применяем правило резолюций: если обозначить

,

то , причём , т.е. дизъ­юнкция d_i Ú d_j будет логическим следствием формул D_i , D_j , а значит и следствием множества D .

Возможен случай, когда , т.е. дизъюнкции d_i и d_j пустые. Тогда очевидно, что D x_k Ù , т.е. можно взять Ф = x_k .

Если же d_i Ú d_j º 1, то рассматриваемое следствие тривиально и такую резолюцию можно не делать. Так будет, например, когда e_l = Î {0, 1}. Таким образом, можно ограничиться рассмотрением дизъюнкций D_i и D_j , в которых x_k – единственная переменная, встречающаяся в одной из них с отрицанием, а в другой – без отрицания. Это ограничение существенно сокращает перебор возможных резолюций.

· расширяем множество D до D¢ , присоединяя к D все дизъюнкции д₁ , … , д_m из КНФ для d_i Ú d_j : D¢ = D È {д₁ , … , д_m}, d_i Ú d_j º д₁ Ù … Ù д_m . Теперь D Ф Ùтогда и только тогда, когда D¢ Ф Ù. Действительно, если противоречие Ф Ùследует из множества D, то оно следует и из большего множества D¢. Если же это противоречие следует из множества D¢, то оно следует и из D , т.к. каждый элемент D¢ является логическим следствием множества D .

· процесс построения резолюций можно ещё более сократить, если учесть, что

при появлении во множестве D¢ двух дизъюнкций вида Д и Д Ú D можно оставить только одну из них – более короткую Д, т.к. Д Д Ú D.

Описанный алгоритм последовательного расширения множества D называется замыканием этого множества относительно резолюций.На некотором шаге ввиду конечности числа всех дизъюнкций (от фиксированного конечного числа переменных) либо получится вывод искомого противоречия D x_k Ù , либо множество дизъюнкций, замкнутое относительно резолюций,т.е. такое множество, которое описанный выше процесс не расширяет: дизъюнкций D_i , D_j описанного выше вида в нём нет. В первом случае получим A₁ , … , A_n A для исходных формул, а во втором формула A не является логическим следствием формул A₁ , … , A_n .

Примеры: 1.Проверить,следует ли формула A = y из

A₁ = (x Ú y Ú ) Ù (Ú y Ú z), A₂ = (x Ú Ú ) Ù (Ú Ú z) .

Имеем = , D = {x Ú y Ú , Ú y Ú z, x Ú Ú , Ú Ú z, }.

Из этого множества сразу можно удалить все дизъюнкции, строго содержащие (они следуют из ). Таким образом, D = { x Ú y Ú , Ú y Ú z, }.

Процесс замыкания относительно резолюций таков:

· x Ú y Ú , x Ú , и D¢ = { x Ú y Ú , Ú y Ú z, , x Ú }.

Из этого множества можно удалить все дизъюнкции, строго содержащие x Ú , т.е. оставить D¢ = {Ú y Ú z, , x Ú }.

· Ú y Ú z, Ú z, так что D¢¢ = { Ú y Ú z, , x Ú , Ú z } и после удаления дизъюнкций, строго содержащих Ú z, D¢¢ = {, x Ú , Ú z }.

Других нетривиальных резолюций нет, D¢¢ замкнуто относительно резолюций, поэтому формула А не является логическим следствием формул A₁ и A₂ .

Этот результат можно, конечно, получить, построив таблицы истинности:

 

x	y	z	x Ú y Ú	Ú y Ú z	Ú Ú z	x Ú Ú	A1	A2	A
0	0	0	1	1	1	1	1	1	0
0	0	1	0	1	1	1	0	1	0
0	1	0	1	1	1	1	1	1	1
0	1	1	1	1	1	0	1	0	1
1	0	0	1	0	1	1	0	1	0
1	0	1	1	1	1	1	1	1	0
1	1	0	1	1	0	1	1	0	1
1	1	1	1	1	1	1	1	1	1

 

2. Верно ли, что (x Ú y Ú ) Ù (Ú y Ú z), x ® y Ù z y Ú Ù ?

Здесь A = y Ú Ù , A₁ = (x Ú y Ú ) Ù (Ú y Ú z), A₂ = x ® y Ù z º º Ú (y Ù z) º (Ú y) Ù (Ú z) . При этом º Ù (x Ú z). Поэтому

D = { x Ú y Ú , Ú y Ú z , Ú y, Ú z, , x Ú z },

и после удаления всех дизъюнкций, строго содержащих Ú z, получим

D = { x Ú y Ú , Ú y, Ú z, , x Ú z }.

Теперь считаем нетривиальные резолюции:

· x Ú y Ú , Ú y (y Ú ) Ú y º y Ú , поэтому

D¢ = { x Ú y Ú , Ú y, Ú z, , x Ú z, y Ú },

D¢ = { Ú y, Ú z, , x Ú z, y Ú }.

· Ú y , , и D¢¢ = { , x Ú z, y Ú , } .

· , y Ú , т.е. D¢¢¢ = { , x Ú z, , }.

· x Ú z , z, поэтому D⁽⁴⁾ = { , , , z }, и D⁽⁴⁾ z Ù .

Итак, А₁ , A₂ A . Проверьте этот результат с помощью таблиц истинности.

Изложенный алгоритм допускает программную реализацию, эффективность которой зависит от удобства организации представления данных в ЭВМ и порядка вычисления резолюций.

IV. Проектирование, анализ и оптимизация релейно-контактных и больших интегральных схем.Рассмотрим лишь некоторые модельные задачи, иллюстрирующие методы этой важной и необъятной области современных технологий.

Задача 1. Разработать схему для предварительного отбора участников соревнований в следующий тур. Перед каждым из четырёх членов жюри находится выключатель, который включается, если этот член жюри считает участника достойным прохождения в следующий тур. На табло должна загораться лампочка, если большинством голосов, обязательно включая председателя, имеющего два голоса, жюри высказалось за прохождение участника в следующий тур.

Решение. Процесс проектирования проведём в несколько шагов:

1. Анализ логики задачи. Составим таблицу всех случаев, в которых должна загораться лампочка:

x1	x2	x3	x4	Л
0	0	0	0	0
0	0	0	1	0
0	0	1	0	0
0	0	1	1	0
0	1	0	0	0
0	1	0	1	0
0	1	1	0	0
0	1	1	1	0
1	0	0	0	0
1	0	0	1	1
1	0	1	0	1
1	0	1	1	1
1	1	0	0	1
1	1	0	1	1
1	1	1	0	1
1	1	1	1	1

Здесь x₁ , x₂ , x₃ , x₄ – члены жюри, причём x₁ – председатель, а равенство x_i = 1 означает, что i-й судья нажал свою кнопку. Лампочка же включается тогда и только тогда, когда Л = 1, что происходит только при условии (x₁ = 1) Ù (x₂ + x₃ + x₄) ³ 1.

2. Получение функции проводимости схемы.По таблице истинности напишем логическую функцию – функцию проводимости схемы:

Л(x₁ , x₂ , x₃ , x₄ ) = (x₁ Ù Ù Ù x₄ ) Ú

Ú (x₁ Ù Ù x₃ Ù ) Ú (x₁ Ù Ù x₃ Ù x₄ ) Ú

Ú (x₁ Ù x₂ Ù Ù ) Ú (x₁ Ù x₂ Ù Ù x₄ ) Ú

Ú (x₁ Ù x₂ Ù x₃ Ù ) Ú (x₁ Ù x₂ Ù x₃ Ù x₄ ).

3. Упрощение функции проводимости. Для того, чтобы схема получилась более компактной, эту функцию нужно упростить с помощью равносильных преобразований:

Л(x₁ , x₂ , x₃ , x₄ ) = (x₁ Ù Ù Ù x₄ ) Ú (x₁ Ù Ù x₃ Ù ) Ú

Ú (x₁ Ù Ù x₃ Ù x₄ ) Ú (x₁ Ù x₂ Ù Ù ) Ú

Ú (x₁ Ù x₂ Ù Ù x₄ ) Ú (x₁ Ù x₂ Ù x₃ Ù ) Ú (x₁ Ù x₂ Ù x₃ Ù x₄ ) º

º x₁ Ù [(Ù Ù x₄) Ú (Ù x₃ Ù ) Ú (Ù x₃ Ù x₄) Ú (x₂ Ù Ù ) Ú

Ú (x₂ Ù Ù x₄) Ú (x₂ Ù x₃ Ù ) Ú (x₂ Ù x₃ Ù x₄ )] º

º x₁ Ù [(Ù Ù x₄) Ú (Ù x₃) Ú (x₂ Ù ) Ú (x₂ Ù x₃)] º

º x₁ Ù [(Ù Ù x₄) Ú x₃ Ú (x₂ Ù )] º

º x₁ Ù [(Ù Ù x₄) Ú (x₂ Ú x₃)] º x₁ Ù [(Ù x₄) Ú (x₂ Ú x₃)] º

º x₁ Ù (x₂ Ú x₃ Ú x₄ ).

Конечно, о таком результате в этой простейшей задаче можно было бы догадаться, внимательно прочитав условие. В случае сложных схем этапы генерации и упрощения логической функции можно автоматизировать.

4. Изображение схемы. Теперь можно нарисовать искомую релейно-кон­тактную схему, используя следующие условные обозначения, позволяющие строить электрическую схему по логической функции:

 

Обозначения
логические	релейно-контактные
	цепь разомкнута
	цепь замкнута
	инверсия
x Ù y	последовательное соединение
x Ú y	параллельное соединение

 

Таким образом, проектируемая схема выглядит так:

Задача 2. Упростить релейно-контактную схему, приведённую ниже.

Учитывая реализацию последовательных и параллельных соединений в электрической схеме логическими связками конъюнкции и дизъюнкции соответственно, получаем функцию проводимости

f(x, y, z) = x Ú [(Ú x) Ù (Ú y)]Ú Ú z .

После упрощения f(x, y, z) = x Ú [(Ú x) Ù (Ú y)] Ú Ú z º

º xÚ [ÙÚ x ÙÚ Ù y Ú x Ù y]Ú Ú z º

º xÚ (Ù )Ú (x Ù)Ú (x Ù y)Ú Ú z º

º (xÚ x ÙÚ x Ù y) Ú (ÙÚ )Ú z º

º x Ù (1 Ú Ú y) Ú Ù (Ú 1) Ú z º x Ú Ú z

рисуем новую схему:

Отличие электронных интегральных схемот обычных электрических состоит, во-первых, в том, что они позволяют использовать транзисторы, с помощью которых более просто и компактно проектируются стандартные электронные устройства (вентили), реализующие те или иные логические функции. Во-вторых, технология изготовления интегральных схем позволяет размещать на малой площади изготавливаемого кристалла большое количество элементов, обеспечивающих его многофункциональность.

С логической точки зрения процесс разработки интегральной схемы ничем не отличается от этапов построения электрической схемы: вначале выписывается булева функция проводимости, которая минимизируется и реализуется в схеме с использованием доступной элементной базы. Конечно, при этом необходимо ещё учесть технологические ограничения, которые, грубо говоря, не позволяют “лепить” слишком много элементов и “проводов” на ограниченном участке печатной платы. Эти ограничения здесь рассматриваться не будут, хотя и очень важны при реальном проектировании интегральных схем.

Обозначения
логические	интегральных схем
	сигнал низкого уровня
	сигнал высокого уровня
	вентиль “НЕ”
x Ù y	вентиль “И”
x Ú y	вентиль “ИЛИ”

Рассмотрим пример проектирования сумматора– реального электронного устройства, складывающего два n-разрядных двоичных числа. При сложении чисел “в столбик” цифры результата получаются последовательно: справа налево. Для получения очередной цифры нужно сложить две текущие цифры слагаемых и учесть полученный на предыдущем шаге перенос. Таким образом, сумматор можно проектировать на основе конвейерной технологии, часто используемой при создании разнообразных сложных интегральных схем. Именно, достаточно создать более простое устройство – одноразрядный сумматор:

получающий на входах очередные суммируемые цифры x, y а также бит переноса T, и дающий на выходах очередную цифру результата R и новый бит переноса S. Если такое устройство создано, то n-разрядный сумматор можно построить в соответствии со следующей схемой. Здесь начальный бит переноса S_–1 равен 0, и вырабатываемые в дальнейшем биты переноса передаются “по конвейеру”. Последний бит переноса S_n–1 даёт информацию о переполнении: он равен единице в том и только том случае, если результат сложения не помещается в n разрядов.

x	y	T	S	R
0	0	0	0	0
1	0	0	0	1
0	1	0	0	1
1	1	0	1	0
0	0	1	0	1
1	0	1	1	0
0	1	1	1	0
1	1	1	1	1

Итак, спроектируем одноразрядный сумматор. Его естественная логика работы реализована в следующей таблице, из которой получаем дизъюнктивные формы логических функций S(x, y, T) и R(x, y, T):

S(x, y, T) = (x Ù y Ù) Ú (x ÙÙ T) Ú

Ú (Ù y Ù T) Ú (x Ù y Ù T),

R(x, y, T) = (x ÙÙ)Ú (Ù y Ù) Ú

Ú (ÙÙ T) Ú (x Ù y ÙT).

Теперь эти функции нужно упростить. Оказывается,

S(x, y, T) º (x Ù y) Ú (x Ù T) Ú (y Ù T),

R(x, y, T) º (x Ù y Ù T) Ú Ù (x Ú y Ú T),

что следует из таблицы истинности правых частей r и s этих равенств.

x	y	T	R	S		x Ù y Ù T	x Ú y Ú T	r	x Ù y	x Ù T	y Ù T	s
0	0	0	0	0	1	0	0	0	0	0	0	0
1	0	0	1	0	1	0	1	1	0	0	0	0
0	1	0	1	0	1	0	1	1	0	0	0	0
1	1	0	0	1	0	0	1	0	1	0	0	1
0	0	1	1	0	1	0	1	1	0	0	0	0
1	0	1	0	1	0	0	1	0	0	1	0	1
0	1	1	0	1	0	0	1	0	0	0	1	1
1	1	1	1	1	0	1	1	1	1	1	1	1

Таким образом, можно построить следующую схему одноразрядного сумматора, где вентили конъюнкции и дизъюнкции трёх величин можно получить, два раза выполнив соответствующие операции с двумя аргументами.