Книги-online
Глава 5 — Логические основы компьютеров
5.10. Как составить таблицу истинности?
Согласно определению, таблица истинности логической формулы выражает
соответствие между всевозможными наборами значений переменных и значениями
формулы.
Для формулы, которая содержит две переменные, таких наборов значений
переменных всего четыре:
(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. В первых двух столбцах таблицы запишем четыре возможных
пары значений этих переменных, в последующих столбцах — значения
промежуточных формул и в последнем столбце — значение формулы.
В результате получим таблицу:
| Переменные |
Промежуточные логические формулы |
Формула |
 |
 |
 |
 |
 |
 |
 |
|
| 0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
| 0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
| 1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
| 1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
Из таблицы видно, что при всех наборах значений переменных x и y формула
принимает значение 1, то есть
является тождественно истинной.
2. Таблица истинности для формулы 
:
| Переменные |
Промежуточные логические формулы |
Формула |
|
|
|
 |
 |
 |
|
| 0 |
0 |
0 |
1 |
1 |
0 |
0 |
| 0 |
1 |
1 |
0 |
0 |
0 |
0 |
| 1 |
0 |
1 |
0 |
1 |
1 |
0 |
| 1 |
1 |
1 |
0 |
0 |
0 |
0 |
Из таблицы видно, что при всех наборах значений переменных x и y
формула принимает значение
0, то есть является тождественно ложной.
3. Таблица истинности для формулы 
:
| Переменные |
Промежуточные логические формулы |
Формула |
|
|
 |
|
 |
 |
 |
 |
|
| 0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
| 0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
| 0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
| 0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
| 1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
| 1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
| 1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
| 1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
Из таблицы видно, что формула
в некоторых случаях принимает значение 1, а в некоторых — 0,
то есть является выполнимой.
