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

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

Таблица истинности формулы алгебры высказываний содержит столько строк, сколько всевозможных наборов значений истинности переменных можно образовать. Так как каждая высказывательная переменная может принимать только два значения (0 и 1), то в случае n переменных таблица истинности содержит 2ⁿ строк.

При построении таблицы истинности наборы значений переменных располагают сверху вниз в лексикографическом порядке (каждый набор понимают как двоичную запись неотрицательного целого числа и располагают в порядке возрастания от (000…0) до (111…1)).

Если возникают трудности с использованием двоичной системы счисления, можно применить метод «последовательного половинного деления столбцов» - столбец первой переменной делят пополам и заполняют верхнюю половину нулями, а нижнюю половину – единицами, затем каждую половину второго столбца делят пополам и опять заполняют полученные половины нулями и единицами, и т.д. Последовательность такого заполнения приведена на рис. 1.

Затем в соответствии с порядком действий последовательно заполняют столбцы значений подформул, из которых образуется формула. Последним заполняется столбец значений истинности формулы.

 

x1	x2	x3

x1	x2	x3

x1	x2	x3

 

рис.1

 

Пример 1. Построить таблицу истинности формулы: ï.

Решение. Порядок действий при построении таблицы исттинности совпадает с порядком столбцов таблицы 9.

 

 

Таблица 9.

								ï	(ï)	(ï)