Элементы математической логики. Исчисление высказываний

Рефераты / Математика / Элементы математической логики. Исчисление высказываний

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

пока в итоге не найдут истинностное значение всей формулы.

Так, пользуясь указанным алгоритмом можно легко вычислить истинностное значение формулы:

((p→q)Ù(q→r))→(p→r)

p	q	r	p→q	q→r	p→r	(p→q)Ù(q→r)	((p→q)Ù(q→r))→(p→r)
0	0	0	1	1	1	1	1
0	0	1	1	0	0	0	1
0	1	0	1	1	0	1	1
1	0	0	0	1	0	0	1
0	1	1	1	1	1	1	1
1	0	1	0	1	1	0	1
0	1	1	1	0	0	0	1
1	1	1	1	1	1	1	1

Итак, каждой формуле исчисления высказываний соответствует определенная функция, аргументы которой принимают значение из множества {0,1} и сама она принимает значение из этого множества. Эту функцию называют функцией исчисления высказываний. Проблема разрешимости в алгебре высказываний заключается в решении вопроса, является ли сложная формула тождественно истинной, т.е. истинной при всех значениях входящих в нее переменных, выполнимой, т.е. истинной лишь для некоторого набора значений переменных, или тождественно ложной, т.е. ложной при всех значениях переменных. Это проблема полностью решается посредствам вычисления значения функции, представленной данной формулой, с помощью таблиц истинности.

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