- •Элементы математической логики
- •Алгебра высказываний.
- •1. Высказывания и операции над ними
- •1.2 Логические операции над высказываниями.
- •2. Формулы алгебры логики.
- •3. Равносильные формулы алгебры логики
- •3.1 Классификация формул алгебры высказываний.
- •3.3 Равносильные преобразования формул.
- •Решение логических задач методами алгебры логики.
3. Равносильные формулы алгебры логики
3.1 Классификация формул алгебры высказываний.
Формула Хназываетсятождественно истинной (или тавтологией),если она превращается в истинное высказывание, то есть принимает значение 1, при всех наборах значений входящих в нее переменных. Тавтологии представляют собой схемы построения истинных высказываний, независимо от содержания и истинности составляющих элементарных высказываний.
Формула Хназываетсятождественно ложной,если она принимает значение 0 при всех наборах значений входящих в нее переменных.
Две формулы алгебры логики XиYназываютсяравносильными, если при любых значениях входящих в них высказывательных переменных логические значения высказываний, получающихся из формулXиY, совпадают. Для указания равносильности формул используют обозначение.
Существует тесная связь между понятием равносильности формул и понятием тавтологии.
Признак равносильности формул.Две формулыXиYалгебры высказываний равносильны тогда и только тогда, когда формулаявляется тавтологией, и обратно, если формула– тавтология, то формулыXиYравносильны.
Отношение равносильности между формулами алгебры высказываний:
а) рефлексивно: ;
б) симметрично: если , то ;
в) транзитивно: если и, то.
3.2 Примеры равносильных формул.Равносильности формул алгебры логики часто называютзаконами логики.
Вот наиболее важные из них:
–закон тождества.
–закон противоречия.
–закон исключенного третьего.
–закон двойного отрицания.
.
.
.
.
; – законы идемпотентности.
; – законы поглощения.
; – законы склеивания.
законы коммутативности (переместительности):
–коммутативность конъюнкции;
–коммутативность дизъюнкции.
законы ассоциативности (сочетательности):
–ассоциативность конъюнкции;
–ассоциативность дизъюнкции.
законы дистрибутивности (распределительности):
–дистрибутивность конъюнкции относительно дизъюнкции;
–дистрибутивность дизъюнкции относительно конъюнкции.
; – законы де Моргана.
Доказать эти равносильности можно, например, с помощью таблиц истинности.
Пример.
Докажем равносильность – закон де Моргана. При любых комбинациях значений, от которых зависят формулыXиY, эти формулы принимают некоторые логические значения. Всего будет четыре способа распределения логических значенийXиY. Надо показать, что в каждом из этих случаев значения левой и правой части равносильностисовпадают.
X |
Y |
| |||||
0 |
0 |
|
1 |
1 |
0 |
1 |
1 |
0 |
1 |
|
1 |
0 |
0 |
1 |
1 |
1 |
0 |
|
0 |
1 |
0 |
1 |
1 |
1 |
1 |
|
0 |
0 |
1 |
0 |
0 |
Логические значения в последних двух столбцах совпадают, следовательно, закон де Моргана справедлив.
Имеют место равносильности, выражающие одни логические операции через другие.
Импликация выражается через:
–дизъюнкцию и отрицание;
–конъюнкцию и отрицание.
Эквиваленциявыражается через:
–конъюнкцию и импликацию;
–конъюнкцию, дизъюнкцию и отрицание;
–конъюнкцию и отрицание.
Из этих равносильностей следует вывод, что любую формулу алгебры логики можно заменить равносильной ей формулой, которая будет содержать только две логические операции: конъюнкцию и отрицание или дизъюнкцию и отрицание. Дальнейшее исключение логических операций невозможно.
Существует логическая операция, через которую можно выразить любую из пяти логических операций, которыми мы пользуемся: отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция. Эта операция называется «штрих Шеффера», обозначается символом и определяется таблицей истинности
X |
Y | |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
Согласно таблице, имеем: ;.