Таблицы истинности
Все возможные логические значения формулы, в зависимости от значений входящих в нее элементарных высказываний, могут быть описаны полностью с помощью таблицы истинности. Таблица истинности логической формулы выражает соответствие между всевозможными наборами значений переменных и значениями формулы. Для формулы, которая содержит две переменные, таких наборов значений переменных всего четыре: (0, 0), (0, 1), (1, 0), (1, 1).
Таблица 12 – Сводная таблица истинности для двух сложных высказываний
Удобной формой записи при нахождении значений формулы является таблица, содержащая кроме значений переменных и значений формулы также и значения промежуточных формул. Например, для формулы х v у→ х& у таблица истинности имеет вид (таблица 2): Таблица 13 – Таблица истинности для формулы х 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 элементарных высказываний, то она принимает 2n значений, состоящих из нулей и единиц, т.е. таблица истинности содержит 2n строк. Например, для формулы a & b v c таблица истинности имеет вид (таблица 3):
Таблица 14 – Таблица истинности для формулы a & b v c
|
х
