Практическая работа «Равносильные формулы. Составление таблиц истинности»
Теоретическая часть
Равносильные формулы. Основные равносильности
Определение. Формула называется тождественно истинной, или тавтологией, если эта формула принимает значение 1 при всех наборах значений переменных.
Определение. Формула называется тождественно ложной, или противоречием, если эта формула принимает значение 0 при всех наборах значений переменных.
Основные тавтологии
1. 
| Закон исключенного третьего |
2. 
| |
3. 
| |
4. 
| Цепное рассуждение |
5. 
| |
6. 
|
Определение. Формулы P и Q называются равносильными (обозначается 
), если при любых значениях переменных значение формулы P совпадает со значением Q.
Основные равносильности
1.  2. 
| Коммутативность  и 
|
3. 
4. 
| Ассоциативность и
|
5. 
6. 
| Дистрибутивность и
|
7.  8. 
| Идемпотентность и
|
9.  10. 
| Законы исключенного третьего и противоречия |
11. 
12. 
| Законы де Моргана |
13. 
14. 
| Законы поглощения |
15. 
| Правило склеивания |
16.  17. 
18.  19. 
| |
20. 
| Закон двойного отрицания |
21. 
22. 
23. 
24. 
| |
25. 
| Коммутативность 
|
26. 
| Ассоциативность
|
27. 
| Дистрибутивность и
|
28.  29. 
30. 
|
Замечание. Здесь P, Q и R —пропозициональные формулы.
Понятие двойственной функции
Определение. Функцией, двойственной к булевой функции 
, называется функция 
.
Определение. Функция называется самодвойственной, если 
.
Теорема. (Принцип двойственности.) Пусть 
,…, 
и 
— булевы функции и пусть 
= 
- сложная булева функция. Тогда
= 
Следствие. Пусть P и Q —формулы. Если , тогда 
.
Принцип двойственности позволяет получать из доказанных равносильностей целый ряд новых. Кроме того, СКНФ(f)= 
.
Некоторые двойственные функции
| 
| |
| 1. | 
| 
|
| 2. | 
|
|
| 3. | 
|
|
| 4. | 
| 
|
| 5. |
|
|
Замечание.  .
|
Практическая часть
Составим таблицы истинности для логических функций.
Пример.1. Составьте таблицу истинности для формулы 
Решение.
| X | Y | Z | Z ^ X | Y → Z ^ X | (Y → Z ^ X) → Z | ((Y → Z ^ X) → Z) |
Пример. 2. Рассмотрим решение этой задачи на примере. Пусть формула F = F(A1, A2, A3) от трёх переменных задана таблицей истинности
Таблица истинности формулы от трёх высказывательных переменных.
| A1 | А2 | А3 | F(A1, A2, A3) |
Понятно, что существует бесконечно много равносильных формул алгебры высказываний, имеющих эту таблицу истинности. Укажем способ нахождения двух таких формул.
Помечаем те строки таблицы, в которых F(A1, A2, A3) принимает значение, равное 1. Это строки 1, 3, 7. Для каждой строки (логической возможности) составим формулу, истинную только в этой логической возможности и ложную во всех остальных логических возможностях
1-я строка — А1 ^ А2 ^ А3
3-я строка — А1 ^ А2 ^ А3
7-я строка — А1 ^ А2 ^ А3.
Если возьмём теперь дизъюнкцию всех этих формул, то это и будет искомой формулой:
Рассмотрим другое решение этой задачи. Помечаем те строки таблицы, в которых F(A1, A2, A3) принимает значение, равное 0. Это строки 2, 4, 5, 6, 8. Для каждой логической возможности составим формулу, ложную только в этой логической возможности и истинную во всех остальных логических возможностях
2-я строка — А1 v А2 v А3
4-я строка — А1 v А2 v А3
5-я строка — А1 v А2 v А3
6-я строка — А1 v А2 v А3
8-я строка — А1 v А2 v А3.
Если теперь возьмём конъюнкцию этих формул, то это также будет искомой, то есть имеющей заданную таблицу истинности, формулой:
Формулы (1) и (2) равносильны, так как имеют одну и ту же таблицу истинности. В данном случае удобнее строить формулу (1).