Равносильные формулы алгебры логики

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

Равносильность формул будем обозначать знаком , а запись A В означает, что формулы A и В рав­носильны.

Например, равносильны формулы:

,

,

.

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

Например, тожественно истинны формулы , .

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

Например, тождественно ложна формула .

Ясно, что отношение равносильности рефлексивно, симметрично и транзитивно.

Между понятиями равносильности и эквивалентно­сти существует следующая связь: если формулы А и В равносильны, то формула А В - тавтология, и обрат­но, если формула А В - тавтология, то формулы А и В равносильны.

Важнейшие равносильности алгебры логики можно разбить на три группы.

1. Основные равносильности:

Докажем один из законов поглощения. Рассмотрим формулу . Если в этой формуле а = 1 то, очевидно, и тогда как конъюнк­ция двух истинных высказываний. Пусть теперь вфор­муле А x = 0. Но тогда по определению операции конъ­юнкции будет ложной и конъюнкция . Итак, во всех случаях значения формулы А совпадают со зна­чениями а, а поэтому А x.

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

Ясно, что равносильности 5 и 6 получаются из равносильностей 3 и 4 соответственно, если от обеих частей последних взять отрицания и воспользоваться законом снятия двойного отрицания. Таким образом, в доказатель­стве нуждаются первые четыре равносильности. Докажем две из них: первую и третью.

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

Пусть теперь х и у имеют различные логические значе­ния. Тогда будут ложными эквивалентность и одна из двух импликаций или . То при этом

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

Рассмотрим равносильность 3. Если х и у принима­ют одновременно истинные значения, то будет истинной конъюнкция х&у и ложным отрицание конъюнкции . В то же время будут ложными и и , а поэто­му будет ложной и дизъюнкция .

Пусть теперь хотя бы одна из переменных х или у принимает значение ложь. Тогда будет ложной конъюн­кция х&у и истинной ее отрицание. В то же время от­рицание хотя бы одной из переменных будет истинным, а поэтому будет истинной и дизъюнкция .

Следовательно, во всех случаях обе части равносиль­ности 3 принимают одинаковые логические значения.

Аналогично доказываются равносильности 2 и 4.

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

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

Однако существуют операции, с помощью которых может быть выражена любая из пяти логических опера­ций, которыми мы пользуемся. Такой операцией являет­ся, например, операция «Штрих Шеффера». Эта опера­ция обозначается символом х|у и определяется следую­щей таблицей истинности:

x	y	x|у

Очевидно, имеют место равносильности:

1) .

2) х&у (х|у)|(х|у).

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

Отметим, что .

Аналогично может быть введена операция .

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

1. х& у у&х - коммутативность конъюнкции.

2. x у y х - коммутативность дизъюнкции.

3. х& (у& г) (х& у)& z - ассоциативность конъюнк­ции.

4. х (y z ) (х у) z- ассоциативность дизъюнк­ции.

5. х& (у z) (х& у) (х&z) - дистрибутивность конъ­юнкции относительно дизъюнкции.

6. х (y&z) (х y)& (x z ) - дистрибутивность дизъ­юнкции относительно конъюнкции.

 

Докажем последний из перечисленных законов. Если х = 1, то будут истинными формулы х (у& z), х у, x z. Но тогда будет истинной и конъюнкция (х y)& (x z ). Таким образом, при х = 1 обе части равносильности 6 принимают одинаковые логические значения (истинные).

Пусть теперь х = 0. Тогда х (у& z) y&z, x у у и x z z, а поэтому и конъюнкция х (y&z) y&z. Следовательно, здесь обе части равносильности 6 равно­сильны одной и той же формуле у&z, и поэтому прини­мают одинаковые логические значения.

 

§ 5. Равносильные преобразования формул

Используя равносильности I, II и III групп можно часть формулы или формулу заменить равносильной ей форму­лой. Такие преобразования формул называются равносиль­ными.

Равносильные преобразования используются для доказательства равносильностей, для приведения формул к заданному виду, для упрощения формул.

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

1. Доказать равносильность .

Используя равносильности I, II и III групп запишем цепочку равносильных формул:

.

 

2. Упростить формулу .

Запишем цепочку равносильных формул:

.

 

3. Доказать тождественную истинность формулы

.

Запишем цепочку равносильных формул:

 

Алгебра Буля

Равносильности III группы говорят о том, что алгебра логики обладает коммутативными и ассоциативными за­конами относительно операций конъюнкции и дизъюнк­ции и дистрибутивным законом конъюнкции относитель­но дизъюнкции, эти же законы имеют место и в алгебре чисел. Поэтому над формулами алгебры логики можно производить те же преобразования, которые проводятся в алгебре чисел (раскрытие скобок, заключение в скобки, вынесение за скобки общего множителя).

Но в алгебре логики возможны и другие преобразова­ния, основанные на использовании равносильностей:

Эта особенность позволяет прийти и к далеко иду­щим обобщениям.

Рассмотрим непустое множество М элементов любой природы { x,y,z,... }, в котором определены отношение «=» (равно) и три операции: «+» (сложение), «» (умно­жение) и «-» (отрицание), подчиняющиеся следующим аксиомам:

Коммутативные законы:

1а. х + у = у + х, 1б. х у = у х.

Ассоциативные законы:

2а. х + (у + г) = (х + у) + z, 2б. х (у z) = (x y) z.

Дистрибутивные законы:

3а. (х + у) z = (х z ) + (у г) 3б. (x y) + z = (x + z) (y + z).

Законы идемпотентности:

4а. х + х = х, 4б. х х = х.

Закон двойного отрицания:

5. .

Законы де-Моргана:

6а. , 6б. .

Законы поглощения:

7а. х + (у х) = х, 7б. х (у + х) = х.

Такое множество М называется булевой алгеброй.

Если под основными элементами х, у, z,... подразу­мевать высказывания, под операциями «+», «», «-» дизъюнкцию, конъюнкцию, отрицание соответственно, а знак равенства рассматривать как знак равносильнос­ти, то, как следует из равносильностей I, II и III групп, все аксиомы булевой алгебры выполняются.

В тех случаях, когда для некоторой системы аксиом удается подобрать конкретные объекты и конкретные соотношения между ними так, что все аксиомы выпол­няются, говорят, что найдена интерпретация (или мо­дель) данной системы аксиом.

Значит, алгебра логики является интерпретацией бу­левой алгебры. Алгебра Буля имеет и другие интерпрета­ции. Например, если под основными элементами х, у, z,... множества М подразумевать множества, под операци­ями «+», «», «-» объединение, пересечение, дополнение соответственно, а под знаком равенства - знак равенства множеств, то мы приходим к алгебре множеств. Нетруд­но убедиться, что в алгебре множеств все аксиомы алгеб­ры Буля выполняются.

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

Функции алгебры логики

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

Например, формула является функцией

трех переменных f(x,y,z). Особенностью этой функции является то обстоятельство, что ее аргументы принима­ют одно из двух значений: ноль или единицу, и при этом функция также принимает одно из двух значений: ноль или единицу.

Определение. Функцией алгебры логики га перемен­ных (или функцией Буля) называется функция га пере­менных, где каждая переменная принимает два значе­ния: 0 и 1, и при этом функция может принимать толь­ко одно из двух значений: 0 или 1.

Ясно, что тождественно истинные и тождественно ложные формулы алгебры логики представляют собой постоянные функции, а две равносильные формулы вы­ражают одну и ту же функцию.

Выясним, каково число функций n переменных. Оче­видно, каждую функцию алгебры логики (как и формулу алгебры логики) можно задать с помощью таблицы ис­тинности, которая будет содержать 2ⁿ строк. Следователь­но, каждая функция n переменных принимает 2ⁿзначе­ний, состоящих из нулей и единиц. Таким образом, фун­кция n переменных полностью определяется набором зна­чений из нулей и единиц длины 2ⁿ.(Общее же число на­боров, состоящих из нулей и единиц, длины 2ⁿ равно . Значит, число различных функций алгебры логики п переменных равно .

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

Рассмотрим таблицу истинности для различных функций одной переменной. Она, очевидно, имеет вид:

x	f1(x)	f2(x)	f3(x)	f3(x)
1

Из этой таблицы следует, что две функции одной пе­ременной будут постоянными: f₁(x)= 1, f₄(x) = 0, а f₂(x) х, и f₃(x) .

Таблица истинности для всевозможных функций двух переменных имеет вид:

f_i = f_i (x,y)

x

y

f1

f2

f3

f4

f5

f6

f7

f8

f9

f10

f11

f12

f13

f14

f15

f16

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

f1 1	f5	f9	f13
f2	f6 x	f10	f14
f3	f7	f11 y	f15 x&y
f4	f8	f12	f16 0