Таблицы истинности

Все возможные логические значения формулы, в зависимости от значений входящих в нее элементарных высказываний, могут быть описаны полностью с помощью таблицы истинности. Таблица истинности логической формулы выражает соответствие между всевозможными наборами значений переменных и значениями формулы. Для формулы, которая содержит две переменные, таких наборов значений переменных всего четыре:

(0, 0), (0, 1), (1, 0), (1, 1).

 

Таблица 12 – Сводная таблица истинности для двух сложных высказываний

 

х	у	х& у	х v у	х→ у	х↔ у	х

 

Удобной формой записи при нахождении значений формулы является таблица, содержащая кроме значений переменных и значений формулы также и значения промежуточных формул.

Например, для формулы х v у→ х& у таблица истинности имеет вид (таблица 2):

Таблица 13 – Таблица истинности для формулы х v у→ х& у

х	у	х	у	х v у	х& у	х v у → х& у

 

Если формула содержит три переменные, то возможных наборов значений переменных восемь:

(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1).

Количество наборов для формулы с четырьмя переменными равно шестнадцати и т.д. Легко видеть, что если формула содержит n элементарных высказываний, то она принимает 2ⁿ значений, состоящих из нулей и единиц, т.е. таблица истинности содержит 2ⁿ строк.

Например, для формулы a & b v c таблица истинности имеет вид (таблица 3):

 

Таблица 14 – Таблица истинности для формулы a & b v c

 

a	b	c	a & b	a & b v c