Таблицы истинности составных высказываний

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

Таблица истинности высказывания, составленного из двух простых высказываний, состоит из четырех строк; а таблица истинности высказывания, составленного из трех простых высказывания - из восьми строк. Сколько строк должна иметь таблица истинности высказывания, составленного из четырех простых высказываний? Сколько – из пяти? Сколько из n?

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

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

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

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

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

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

x1	x2	x3
0	0	0
		1
	1	0
		1
1	0	0
		1
	1	0
		1

 

x1	x2	x3
0
1

x1	x2	x3
0	0
	1
1	0
	1

 

    

      

 

        

 

рис.1

 

Пример 1. Построить таблицу истинности формулы: x₁  (x₁  x₂)

1. Определим порядок действий в формуле:

1)

2)  x₁ ×

3)  (x₁  x₂)

4)

5)  (x₁  x₂)×

6) x₁ ×  (x₁  x₂)×

 

2. Пользуясь определениями логических операций Ø, &, Ú и ® заполним таблицу.

 

Таблица.

x1	x2	x3		x1×	x1  x2		(x1 x2)	x1 (x1  x2)
0 0 0 0 1 1 1 1	0 0 1 1 0 0 1 1	0 1 0 1 0 1 0 1	1 1 0 0 1 1 0 0	0 0 0 0 1 1 0 0	0 0 1 1 1 1 1 1	1 0 1 0 1 0 1 0	0 0 1 0 1 0 1 0	1 1 1 1 1 0 1 1