Матлогика(Лагодинский)

2. Алгебра (логика) высказываний

Алгебра или логика высказываний – это простейшая теория математической логики. Основное понятие этой теории – высказывание. Высказывание – это повествовательное предложение, о котором, хотя бы в принципе, можно сказать, истинно оно или ложно (конечно, эта фраза не является математически корректным определением: основные понятия любой теории не определяются, иначе они определялись бы через другие понятия, т. е. не были бы основными). Например: ‘‘Волга впадает в Каспийское море’’, ‘‘2=3’’ – высказывания, причем первое – истинное, а второе – ложное, Но фраза: ‘‘Сумма корней приведенного квадратного уравнения равна свободному члену’’ высказыванием не является, поскольку бывают уравнения этого типа, для которых это справедливо, но для других это неправильно. Математическая логика не интересуется конкретным содержанием высказывания, высказывания рассматриваются как переменные x, y, z, …, которые могут принимать только два значения: истина (и) и ложь (л) или 1 и 0 соответственно.

Логические связки и логические функции

Из одного или нескольких высказываний можно получить другое высказывание, используя логические связки: (конъюнкция, логическое умножение, и), (дизъюнкция, логическое сложение, неисключающее или), ¬ (отрицание, не), → (импликация), ↓(стрелка Пирса), | (штрих Шеффера), (символ Жегалкина, исключаю-

щее или, сложение по модулю 2), ~ (эквиваленция), \ (логическое вычитание) и это высказывание называется логической функцией исходных высказываний. Таким образом, логическая функция n исходных высказываний является отображением множества Fn во множество F, где F – множество, состоящее из двух элементов: F={0; 1}. Нетрудно установить, что всего таких функций может

быть 22n (доказательство предоставляется читателю в качестве упражнения).

Рассмотрим все логические функции одной логической переменной f(x). Их удобно представить в виде следующей таблицы (табли-

цы истинности):

11

Функция f0 называется тождественно ложной или тожде-

ственно нулевой: f0(x)≡0, функция f1 осуществляет тождественное отображение множества F: f1(x)=x при всех значениях x, функция f2 переставляет элементы множества F, она является отрицанием: f2(x) =x при всех значениях x, функция f3 называется тожде-

ственно истинной или тождественно единичной: f3(x)≡1.

Теперьрассмотримвсевозможныефункциидвухлогическихпе-

ременных fi(x,y), i=0,1,...,15 (число таких функций равно 222 =16). Будем придерживаться определенного порядка как для наборов значений переменных, так и в нумерации логических функций. Этот порядок соответствует двоичной системе счисления. Получаем следующую таблицу:

Таблица 1

Каждая из этих функций имеет свой логический смысл. Функция f0(x,y) – тождественно ложная функция. Функция f1(x,y) истинна в том и только том случае, когда истинны и x, и y – это конъюнкция: f1(x,y)=x y. Функция f2(x,y) истинна в том и только том случае, когда истинно x, а y ложно – это логическая разность этих высказываний: f2(x,y)=x\y. Функция f3(x,y) истинна в том и только том случае, когда истинно x, независимо от y: f3(x,y)=x. Функция f4(x,y) истинна в том и только том случае, когда истинно y, а x ложно – это логическая разность этих высказываний: f4(x,y)=y\x. Функция f5(x,y) истинна в том и только том случае, когда истинно y, независимо от x: f5(x,y)=y. Функция f6(x,y) истинна в том и только том случае, когда либо x истинно, а y ложно, либо, наоборот, y истинно, а x ложно: это сумма по модулю 2 x и y: f6(x,y)=x y. Функция f7(x,y) ложна в том и только том случае, когда ложны и x, и y, это дизъюнкция: f7(x,y)=x y. Функция f8(x,y) истинна в том и только том случае, когда x и y принимают одинаковые значения, это – эквиваленция: f9(x,y)=x~y. Функция f10(x,y) истинна в том и только том случае, когда ложно y, это отрицание y: f10(x,y) =y. Функция f11(x,y) ложна в том и только том случае, когда x ложно, а y истинно, это импликация: f11(x,y)=y→x. Функция f12(x,y)

12

истинна в том и только том случае, когда ложно x, это отрицание

x: f12(x,y) =x. Функция f13(x,y) ложна в том и только том случае, когдаxистинно,аyложно,это–импликация:f13(x,y)=x→y.Функ-

ция f14(x,y) ложна в том и только том случае, когда истинны и x,

и y, это – штрих Шеффера: f14(x,y)=x|y. Функция f15(x,y) истинна при любых x и y, это – тождественно истинная функция.

Два первых столбца табл. 1 вместе со столбцом, соответствующим функции fn(x,y) (n=0, 1, …, 15), составляют таблицу истинности функции fn(x,y). Например, таблица истинности импликации f13(x,y)=x→y имеет вид:

Это определение импликации следует обсудить особо. С точки зрения логики импликация означает: ``Если x, то y’’. Очевидно, это истинно, если из истинности x следует истинность y, а из ложности x ложность y, и ложно, если из истинности x следует ложность y. Но совсем не очевидна третья строчка таблицы, которая гласит, что импликация истинна, если из ложности x следует истинность y. Можно привести такой шуточный пример: если крокодилы летают, то дважды два – пять. Тут действует своеобразная презумпция истинности: высказывание считается истинным, пока не доказана его ложность. А чтобы доказать ложность нашего высказывания, необходимо доказать, во-первых, что крокодилы летают, во-вторых, что дважды два не равно пяти. Но первое доказать невозможно.

Парадоксальный вывод логики: из лжи следует все, что угодно. Из неправильных посылок можно получить правильные заключения. В термодинамике известна формула Карно для предельного коэффициента полезного действия тепловой машины. Эта формула правильна, хотя Карно получил ее из неверных предположений. Неправильная теория может приводить к результатам, согласующимся с экспериментом. Поэтому эксперимент не может подтвердить теорию, он может лишь ее опровергнуть. Если какой-либо вывод теории не согласуется с экспериментом – теория неверна.

13

По номеру N(f)=n функции fn(x,y) легко определить ее таблицу истинности и наоборот. Для этого надо представить номер n в двоичной системе счисления, например, 7=4+2+1 в этой системе изображается в виде 0111 (добавляется 0 слева, чтобы число цифр было равно четырем). Самая правая цифра соответствует значению функции при x=1, y=1, вторая справа – при x=1, y=0 и так далее. Таким образом, простейшая теория математической логики – логика высказываний – основана на определении логических операций (отрицания, конъюнкции, дизъюнкции, импликации и т. д.) с помощью таблиц истинности.

Можно пойти дальше и определить новые логические функции трех переменных с помощью таблиц истинности, каждая из которых содержит 9 строк и 4 столбца, например:

Порядок следования наборов значений переменных (строк) здесь по-прежнему определяется в соответствии с двоичной системой счисления: 000 соответствует нулю, 001 – единице, 010 – двум и так далее. Функции нумеруются аналогично: f0(x,y,z) – тождественный нуль, в четвертом столбце ее таблицы истинности нули во всех строках. Чтобы получить таблицу истинности для функции fn(x,y,z), надо число n представить в виде:

8

n= åαk2k-1, k=1

где αk – либо нуль, либо единица. αk и есть то число, которое должно стоять на пересечении четвертого столбца и k-й строки в таблице истинности функции fn(x,y,z). Тождественная единица, или тождественно истинная функция имеет индекс 255:

14

f255(x,y,z)≡1. Но любую такую функцию можно определить с помощью суперпозиции функций одной или двух переменных. Например, пусть f(x,y) =xÚy,g(x) =x, h(y,z) =y®z. Суперпозицию этих функций получим, подставив в функцию f(x,y) вместо x g(x) =x, вместо y h(y,z)=y→z. В результате получим:

ϕ(x,y,z) =f(g(x),h(y,z))=xÚ(y®z) – формулу. Формула может представлять собой только одну букву (независимую переменную) – такие формулы называются пропозициональными. Если A – формула, то A – тоже формула. Если A и B – формулы, то A B, A B, A→B, A B, A↓B, A|B, A\B, A~B –тоже формулы. Других формул в логике высказываний нет. Таким образом, любое выражение, содержащее пропозициональные формулы, разделенные логическими связками, представляет собой формулу, которая представляет собой некоторое сложное высказывание. Для определения логического смысла этого высказывания необходимо учитывать правила приоритета логических операций. Именно, вначале выполняются операции, находящиеся под знаком отрицания, конъюнкции, штрихи Шеффера и стрелки Пирса, затем дизъюнкции, потом импликации, после них сложения по модулю 2 и эквиваленции. Для обеспечения другого порядка вычисления операций используются скобки. Составим таблицу истинности функции xÚ(y®z) :

Любойформулеможносопоставитьтаблицуистинности,ноодна и та же таблица истинности сопоставляется разным формулам. Формулы, имеющие одинаковые таблицы истинности, называются равносильными. На множестве формул это определяет отношение эквивалентности.

15

Основные равносильности (легко проверяемые по таблицам ис-

пления).

Равносильности, выражающие одни логические операции через другие.

1)  A ~ Bº( A ® B) Ù(B® A) º( AÙB) Ú( AÙB) º( AÚB) Ù(BÚ A). 2)  A ® Bº AÚBº AÙB.

3)  AÚBº A ® Bº AÙB.

4)  AÙBº A ® Bº AÚB.

5)  AÙBº AÚB – первый закон де Моргана. 6)  AÚBº AÙB – второй закон де Моргана.

7)  AÙBº AÚB, AÚBº AÙB.

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

Равносильности, выражающие основные законы алгебры ло-

Используя равносильности, можно упрощать выражения.

16

Пример 1. Упростить выражение для f(x,y,z) =(y| z) \ (xÚy) Å

Å(yÚz).

Решение.

f(x,y,z) =(y| z) \ (xÚy) Å(yÚz) =((y| z) ®(xÚy))Å(yÚz) = =(yÙz®(xÚy))Å(yÚz) =(yÙzÚ(xÚy))Å(yÚz) =

=((yÙzÚy)Úx)Å(yÚz) =æççççç(yÚy)Ù(zÚy) Úxö÷÷÷÷÷÷Å(yÚz) = ççè 1 ÷ø

=(xÚyÚz) Å(yÚz) =xÚyÚzÅyÚz=xÙyÙzÅyÙz=

=yÙzÙ(xÅ1) =yÙzÙx=yÚzÙx=(y| z) Ùx.

Формула называется тавтологией (тождественно истинной),

если она принимает значение 1 при всех значениях входящих в нее переменных. Формула называется противоречивой или тождественно ложной, если она принимает значение 0 при всех значениях входящих в нее переменных. Формула называется выполнимой, если хотя бы при одном наборе значений переменных она принимает значение 1.

Основные тавтологии (логические законы):

1)  AÚ A – закон исключенного третьего (tertium nondatum). 2)  A® A.

3)  A®(B® A).

4) ( A® B) ®((B®C) ®( A®C)) – цепное рассуждение.

Итак, в математической логике все множество высказываний отображается на множество, состоящее из двух элементов: 0 и 1, и на этом множестве определяются три операции: одна унарная (отрицание) и две бинарных (конъюнкция и дизъюнкция), которые не выводят элементы из этого множества.

Булевы алгебры

Любое множество M, содержащее (может быть, наряду с другими) два выделенных элемента 0 и 1, на котором определены одна унарная операция (обозначим ее через ¬) и две бинарные операции (обозначим их через + и ×), такие, что справедливы следующие равенства:

17

a+(b+c) =(a+b) +c

2. a´(b´c) =(a´b)´c – ассоциативные законы,

3. (a+b)´c=(a´c) +(b´c) – дистрибутивные законы,

(a´b) +c=(a+c)´(b+c)

a+a=a

4. a´a=a – законы идемпотентности,

5. a+b=a´b – законы де Моргана, a´b=a+b

6. a=a – закон двойного отрицания,

a+(a´b) =a

7. a´(a+b) =a – законы поглощения,

8. a+0=a, a+1=1, a´0=0, a´1=a – особые свойства элементов 0 и 1, называется алгеброй Буля или булевой алгеброй.

Поскольку все эти законы справедливы для логических операций ¬, , , алгебра логики является интерпретацией булевой алгебры. Но у последней есть и другие интерпретации. Рассмотрим, например, множество M подмножеств какого-либо множества E. В множестве M содержится элемент Ø (пустое множество), играющий роль нуля, множество E, играющее роль единицы, и определены операции C (дополнение), ∩ (пересечение множеств) и (объединение множеств), для которых справедливы перечисленные законы. Следовательно, множество M с операциями C, , ∩ представляет собой булеву алгебру.

Двойственность

На множестве логических функций можно ввести отношение

двойственности: функция f(x, y, z, …) называется двойственной

функции g(x, y, z,…) (это обозначается: f(x, y, z, …)≡g*(x, y, z, …)),

если справедлива равносильность: f(x, y, z, ) º g(x, y, z, ). Отношение двойственности симметрично: если f(x, y, z,…)≡g*(x, y, z, …), то и g(x, y, z, …)≡f*(x, y, z, …), но не транзитивно. В следующей таблице друг под другом расположены двойственные друг другу функции.

18

Из таблицы видно, что существуют функции, двойственные сами себе. Такие функции называют самодвойственными.

Пример 2. Найти выражение для f*(x,y,z), если f(x,y,z) =((x~

~ (y®z)) Ù(yÚz).

Решение. f* (x,y,z) =((xÅy) Å(z\ y)) Ú(yÙz).

где σ={σ1, σ2,..., σn} – какой-нибудь двоичный набор, а среди переменных xi могут быть совпадающие, называется элементарной конъюнкцией, или конъюнктом. Всякая дизъюнкция элементар-

ных конъюнкций называется дизъюнктивной нормальной формой

(ДНФ). Если ДНФ удовлетворяет следующим условиям совершенства: все логические слагаемые в ДНФ различны, каждое слагаемое содержит все переменные, ни одно логическое слагаемое не содержит xi и x одновременно и ни одно логическое слагаемое не содержит одно и то же переменное дважды, такая ДНФ называет-

ся совершенной дизъюнктивной нормальной формой (СДНФ). Для всякой функции алгебры логики f(x1, x2,..., xn), не равной тождественно нулю, справедливо ее представление в виде СДНФ:

(дизъюнкция по всем наборам переменных, при которых функция принимает значение 1). Тождественно ложная функция не имеет СДНФ.

Формула x1σ1 Úx2σ2 Ú Úxnσn , называетсяэлементарнойдизъюнк-

цией, или дизъюнктом. Всякая конъюнкция элементарных дизъ-

юнкций называется конъюнктивной нормальной формой (КНФ).

Если КНФ удовлетворяет следующим условиям совершенства: все логические сомножители в КНФ различны, каждый сомножитель содержит все переменные, ни один логический сомножитель не содержит xi и x одновременно и ни один логический сомножитель не содержит одно и то же переменное дважды, такая КНФ называет-

ся совершенной конъюнктивной нормальной формой (СКНФ). Для всякой функции алгебры логики f(x1, x2,..., xn), не равной тождественно единице, справедливо ее представление в виде СКНФ:

19

ÑÊÍÔf = Ù xσ1 Úxσ2 Ú Úxσn

(конъюнкция по всем наборам переменных, при которых функция принимает значение 0). Тождественно истинная функция не имеет СКНФ.

Значение СДНФ и СКНФ состоит в том, что равносильные формулы имеют одинаковые СДНФ и СКНФ (с точностью до порядка следования конъюнктов и дизъюнктов). Для получения СДНФ и СКНФ строится таблица истинности функции, например:

Из таблицы видно, что значение 1 эта функция принимает, если x=y=0, или x=1, y=z=0 или x=y=1, z=0. Для всех остальных наборов значений переменных эта функция принимает значение 0. Отсюда получаем:

СДНФf =(xÙyÙz) Ú(xÙyÙz) Ú(xÙyÙz) Ú(xÙyÙz),

СКНФ f =(xÚyÚz) Ù(xÚyÚz) Ù(xÚyÚz) Ù(xÚyÚz).

Но среди ДНФ могут быть и такие, которые содержат меньше переменных, чем СДНФ. Такие ДНФ целесообразно использовать при реализации логических функций в виде переключательных устройств или в машинных программах. Будем называть импликантой формулы A такую элементарную конъюнкцию B, которая, во-первых, содержит каждую из переменных не более чем один раз (т. е. является правильной), во-вторых, удовлетворяет уравнению AÙB=B. Импликанта называется простой, если после удаления из нее любой переменной она перестает быть импликантой. Дизъюнкция простых импликант называется сокращенной ДНФ. Со-

20