Определение. Две формулы алгебры логики А и В называются равносильными, если они принимают одинаковые логические значения на любом наборе значений входящих в формулы элементарных высказываний.
Равносильность формул будем обозначать знаком , а запись A
В означает, что формулы А и В равносильны.
Например, равносильны формулы:
Формула А называется тождественно истинной (или тавтологией), если она принимает значение 1 при всех значениях входящих в нее переменных.
Например, тожественно истинны формулы ,
.
Формула А называется тождественно ложной, если она принимает значение 0 при всех значениях входящих в нее переменных. Например, тождественно ложна формула х& .
Между понятиями равносильности и эквивалентности существует следующая связь: если формулы А и В равносильны, то формула А В - тавтология, и обратно, если формула А
В - тавтология, то формулы А и В равносильны.
Важнейшие равносильности алгебры логики можно разбить на три группы.
I. Основные равносильности:
|
2.
3.
4.
5.
6.
7. - закон противоречия.
8. - закон исключенного третьего.
9. - закон снятия двойного отрицания.
10.
|
11.
Докажем один из законов поглощения. Рассмотрим формулу . Если в этой формуле х = 1, то, очевидно,
и тогда
как конъюнкция двух истинных высказываний. Пусть теперь в формуле А х = 0. Но тогда по определению операции конъюнкции будет ложной и конъюнкция
. Итак, во всех случаях значения формулы А совпадают со значениями х, а поэтому А
х.
II. Равносильности, выражающие одни логические операции через другие:
1. ;
2. ;
3. ;
4. ;
5. ;
6. .
Ясно, что равносильности 5 и 6 получаются из равносильностей 3 и 4 соответственно, если от обеих частей последних взять отрицания и воспользоваться законом снятия двойного отрицания. Таким образом, в доказательстве нуждаются первые четыре равносильности. Докажем две из них: первую и третью.
Так как при одинаковых логических значениях х и у истинными являются формулы , то истинной будет и конъюнкция
. Следовательно, в этом случае обе части равносильности имеют одинаковые истинные значения.
Пусть теперь х и у имеют различные логические значения. Тогда будут ложными эквивалентность х↔у и одна из двух импликаций х ® у или у х. Но при этом будет ложной и конъюнкция . Таким образом, в этом случае обе части равносильности имеют одинаковые логические значения.
Рассмотрим равносильность 3. Если х и у принимают одновременно истинные значения, то будет истинной конъюнкция х&у и ложным отрицание конъюнкции . В то же время будут ложными
и
, а поэтому будет ложной и дизъюнкция
.
Пусть теперь хотя бы одна из переменных х или у принимает значение ложь. Тогда будет ложной конъюнкция х&у и истинной ее отрицание. В то же время отрицание хотя бы одной из переменных будет истинным, а поэтому будет истинной и дизъюнкция .
Следовательно, во всех случаях обе части равносильности 3 принимают одинаковые логические значения.
Аналогично доказываются равносильности 2 и 4.
Из равносильностей этой группы следует, что всякую формулу алгебры логики можно заменить равносильной ей формулой, содержащей только две логические операции: конъюнкцию и отрицание или дизъюнкцию и отрицание.
Дальнейшее исключение логических операций невозможно. Так, если мы будем использовать только конъюнкцию, то уже такая формула как отрицание х не может быть выражена с помощью операции конъюнкции.
Однако существуют операции, с помощью которых может быть выражена любая из пяти логических операций, которыми мы пользуемся. Такой операцией является, например, операция «Штрих Шеффера». Эта операция обозначается символом и определяется следующей таблицей истинности:
х | у | х\у |
1 | 1 | 0 |
1 | 0 | 1 |
0 | 1 | 1 |
0 | 0 | 1 |
Очевидно, имеют место равносильности:
1) .
2) .
Из этих двух равносильностей следует, что всякая формула алгебры логики может быть заменена равносильной формулой, содержащей только операцию «Штрих Шеффера». Отметим, что .
Аналогично может быть введена операция .
III. Равносильности, выражающие основные законы алгебры логики:
1. х&у≡у&х - коммутативность конъюнкции.
2. - коммутативность дизъюнкции.
3. - ассоциативность конъюнкции.
4. - ассоциативность дизъюнкции.
5. -дистрибутивность конъюнкции относительно дизъюнкции.
6. -дистрибутивность дизъюнкции относительно конъюнкции.
Докажем последний из перечисленных законов. Если х = 1, то будут истинными формулы .
Но тогда будет истинной и конъюнкция . Таким образом, при х = 1 обе части равносильности 6 принимают одинаковые логические значения (истинные).
Пусть теперь х=0. Тогда и
, а поэтому и конъюнкция
. Следовательно, здесь обе части равносильности 6 равносильны одной и той же формуле у& z и поэтому принимают одинаковые логические значения.
1.5. Равносильные преобразования формул
Используя равносильности I, II и III групп, можно часть формулы или формулу заменить равносильной ей формулой. Такие преобразования формул называются равносильными.
Равносильные преобразования используются для доказательства равносильностей, для приведения формул к заданному виду, для упрощения формул.
Формула А считается проще равносильной ей формулы В, если она содержит меньше букв, меньше логических операций. При этом обычно операции эквивалентность и импликация заменяются операциями дизъюнкции и конъюнкции, а отрицание относят к элементарным высказываниям. Рассмотрим ряд примеров.
1. Доказать равносильность .
Используя равносильности I, II и III групп, запишем цепочку равносильных формул:
2. Упростить формулу .
Запишем цепочку равносильных формул:
3. Доказать тождественную истинность формулы:
Запишем цепочку равносильных формул:
Дата: 2019-02-19, просмотров: 247.