Алгебра высказываний, исчисление высказываний

Повествовательное предложение, записанное на естественном или формализованном языке, для которого имеет смысл говорить о его истинности или ложности, называется высказыванием. Другими словами, высказывание – это предложения, которые могут принимать значения “истина” - 1, или “ложь” - 0. Пример: 5>10 - ложно; 5<10 - истинно.

Высказывания представляют булевыми константами (булевыми переменными 0,1), в дальнейшем обозначаемыми малыми буквами латинского алфавита. Такие высказывания называют элементарными (простыми).

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

Составное высказывание называется тождественно истинным (ложным) или тавтологией (противоречием), если оно истинно при всех значениях входящих в него элементарных высказываний.

В аксиоматической теории исчисления высказываний под высказыванием понимается формула для булевой функции, но понятие “истина” (тавтология) не определяются. Вместо них задаётся набор некоторых высказываний, объявленных аксиомами. Из аксиом и исходных высказываний (допущений), с помощью правил вывода строится последовательность высказываний, называемая выводом из допущений. Этот вывод из допущений называется доказательством, а высказывание в его конце – формально доказуемым или теоремой (╞). Выводимые и доказуемые высказывания являются истинами “аксиоматической” теории. Выбирая аксиомы и различные выводы можно построить различные логики.

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

Тавтологиями являются основные правила алгебры логики:

1. Х + 0=Х. 2) Х + 1=1. 3) Х+Х+Х=Х. 4) Х+ неХ = 1. 5) Х·0=0.

6)X · 1 = X. 7) Х·Х·Х = Х. 8) Х умножить на не Х=0. 9) Х = Х.

Примеры: