Лабораторная работа № 125.
Равносильность формул.
Цель работы. Изучить логические операции и основные равносильности алгебры логики, научиться преобразовывать формулы, используя основные равносильности и правила поглощения.
Логические операции
- отрицание, Ú - дизъюнкция, Ù (&) - конъюнкция,
«(~) - эквиваленция, ® - импликация
Приоритет операций:
конъюнкция, дизъюнкция, эквиваленция и импликация
Таблица истинности
| A | B |
| A Ú B | A & B | A «B | A ® B |
| 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 |
Основные равносильности алгебры логики:
1. º A 2. A & B º B & A
3. A Ú B º B Ú A 4. (A & B) & C º A & (B & C)
5. (A Ú B) Ú C º A Ú (B Ú C) 6. A & (B Ú C) º (A & B) Ú (A & C)
7. A Ú (B & C) º (A Ú B) & (A Ú C) 8. A & A º A
9. A Ú A º A 10. (A & B) Ú A º A
11. (A Ú B) & A º A 12. A & B º Ú 
13. A Ú B º & 14. A & 1 º A
15. A & 0 º 0 16. A Ú 1 º 1
17. A Ú 0 º A 18. A Ú º 1
19. A & º 0 20. A ® B º Ú B
21. A «B º (A ® B) & (B ® A) º AB Ú
22. A Ú B º A Ú B
Студенты с четными номерами по списку группы выполняют 2, 4, 6, 8, 10 задания, с нечетными номерами выполняют задания 1, 3, 5, 7, 9.
Задание 1. Используя основные равносильности алгебры логики, упростить формулы:
1) 
; 2) 
; 3) 
; 4) 
;
5) 
; 6) 
; 7) 
;
8) 
;
9) 
.
Методические указания.
Пример 1. Используя основные равносильности алгебры логики, а также равносильности 
и 
,
упростить формулу: 
.
Решение.
Ответ: 
Логическую операцию конъюнкция в формулах алгебры логики можно опускать, т.е. выражение A&B можно записывать в виде АВ.
Пример 2. Для заданного высказывания 
1) построить таблицу истинности;
2) упростить высказывание, используя равносильные преобразования;
3) полученный результат проверить, построив для него таблицу истинности.
Решение.
1) Таблица истинности. Пусть 
| Х | Y | Z | 
| YZ | 
| 
| U |
| 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
2) Выполним равносильные преобразования, используя 
и , имеем:
в последнем преобразовании для первого и третьего слагаемых использовали правило поглощения АВÚАºА, далее используем другое правило поглощения 
, получаем
Еще раз использовали правило поглощения.
3) Для полученного выражения 
построим таблицу истинности
| Х | Y | Z | 
| 
|
|
| 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 | 1 |
Результирующие (последние) столбцы в двух таблицах совпали, следовательно, выполненные преобразования верны.
Задания для самостоятельной работы
Для заданного логического выражения (высказывания):
1) построить таблицу истинность;
2) упростить высказывание, используя равносильные преобразования;
3) полученный результат проверить, построив для него таблицу истинности.
| Вариант | Вариант | ||
| 1 | (A «C) Ú A Ú B
| 2 | (A ® B) Ú A  Ú BC
|
| 3 | (AB ® C) Ú A
| 4 | C Ú (AB «C)
|
| 5 | ( ® C) (B Ú AC)
| 6 | (A ~ B) Ú C Ú AB
|
| 7 | (A ® B) Ú A Ú AC
| 8 | (A ~ B) Ú A Ú AC
|
| 9 | (AC ® B) Ú B
| 10 | (AC ® B) Ú A
|
| 11 | ( ® B) ( Ú AC)
| 12 | ( «C) (A ® BC)
|
| 13 | (A ® C) Ú A Ú B
| 14 | (C ® A ) Ú Ú BC
|
| 15 | (BC ® ) ÚAB
| 16 | C Ú (AB «C) Ú B
|
| 17 | (AB ® C) Ú AB
| 18 | ( ~ B) (A ® CB)
|
| 19 | (B ® AC) Ú (AB ® C) | 20 | ( B ® C) Ú B Ú C
|
| 21 | (A «B) Ú (A ® BC)
| 22 | ( C ® ) Ú BC
|
| 23 | (AB ® C) Ú A
| 24 | ( B ® C) (A ~ C)
|
| 25 | ( «BC) (A ® BC)
| 26 | (A ® B) ( B ® C)
|
| 27 | (A «C) Ú A C Ú B
| 28 | (A ® B) Ú A Ú BC
|
| 29 | ( ® AC) Ú A
| 30 | C Ú (AB «C)
|
| 31 | ( ® BC) ( Ú AB)
| 32 | (A ~ B) Ú C Ú AB
|
| 33 | (A ® BC) Ú C Ú AB
| 34 | (A ~ B) Ú A Ú AC
|
Контрольные вопросы.
1. Какие основные логические операции вам известны?
2. Перечислите основные равносильности алгебры логики.
