Равносильные логические выражения
Логические выражения, у которых последние столбцы таблиц истинности совпадают, называются равносильными. Для обозначения равносильных логических выражений используется знак «=».
Докажем,
что логические выражения
равносильны.
Построим
сначала таблицу истинности логического
выражения
(таблица 9).
Таблица
9 – Таблица истинности логического
выражения
-
А
В
0
0
1
1
1
0
1
1
0
0
1
0
0
1
0
1
1
0
0
0
Теперь
построим таблицу истинности логического
выражения
(таблица
10).
Таблица
10
– Таблица
истинности логического выражения
-
А
В
А v В
0
0
0
1
0
1
1
0
1
0
1
0
1
1
1
0
Значения в последних столбцах таблиц истинности совпадают, следовательно, логические выражения равносильны:
=
.
Построение таблиц истинности для сложных выражений
Согласно определению, таблица истинности логической формулы выражает соответствие между всевозможными наборами значений переменных и значениями формулы.
Для формулы, которая содержит две переменные, таких наборов значений переменных всего четыре:
(0, 0), (0, 1), (1, 0), (1, 1).
Если формула содержит три переменные, то возможных наборов значений переменных восемь:
(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1).
Количество наборов для формулы с четырьмя переменными равно шестнадцати и т.д.
Удобной формой записи при нахождении значений формулы является таблица, содержащая кроме значений переменных и значений формулы также и значения промежуточных формул.
Пример 1
Составим таблицу истинности для формулы, которая содержит две переменные X иY. В первых двух столбцах таблицы запишем четыре возможных пары значений этих переменных, в последующих столбцах — значения промежуточных формул и в последнем столбце — значение формулы. В результате получим таблицу 11:
Таблица 11 – Таблица истинности для формулы с переменными Х и У
Пример 2
Cоставить таблицу истинности сложного логического выражения: D = неA & (B+C).
А, В, С – три простых высказывания, поэтому:
количество строк = 23 +2 = 10 (n=3, т.к. на входе три элемента А, В, С)
количество столбцов (таблица 12):
1) А,
2) В,
3) С,
4) не A – это инверсия А (обозначим Е),
5) B + C – это операция дизъюнкции (обозначим F),
6) D = неA & (B+C), т.е. D = E & F – это операция конъюнкции.
Таблица 12 – Таблица истинности логического выражения D = неA & (B+C)
