Формулы алгебры высказываний

Логика высказываний интересуется единственным свойством элементарных высказываний – их значением истинности; составные же высказывания изучаются ею со стороны их логической структуры, отражающей способ, которым они образованы. Структура составных высказываний определяет зависимость их значений истинности от значений истинности составляющих элементарных высказываний.

Так как смысл высказываний математическую логику не интересует, их вполне можно заменить переменными.

Пусть X, Y,…, Z,…, X_i, Y_i,…, Z_i – переменные, вместо которых можно подставить любые элементарные высказывания (или их значения истинности). Такие переменные называют пропозициональными или высказывательными переменными. С помощью высказывательных переменных и символов логических операций любое высказывание можно формализовать, т.е. заменить формулой, отражающей его логическую структуру.

Начнем с того, что уточним понятие формулы логики высказываний. Для этого зададим алфавит, т.е. набор символов, которые мы будем употреблять в логике высказываний:

1. Х, Y,…, Z,…, Xi, Yi,…, Zi (i – натуральное число) – символы для обозначения высказывательных переменных;

2. И, Л, 1, 0 – символы, обозначающие логические константы «истина» и «ложь»;

3. – символы логических операций;

4. (,), [, ] – скобки (вспомогательные символы, служащие для указания порядка выполнения операций).

Дадим теперь строгое определение формулы логики высказываний (будем говорить формула ЛВ):

1. Всякая высказывательная переменная – формула ЛВ.

2. Символы И, Л, 1, 0 – формулы ЛВ.

3. Если F – формула ЛВ, то – формула ЛВ.

4. Если F₁ и F₂ – формулы ЛВ, то , , и – формулы ЛВ.

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

Определение такого вида называется индуктивным. В п.п. 1 и 2 определены элементарные формулы, в п.п. 3 и 4 даны правила образования новых формул из любых двух данных формул.

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

Опишем процедуру формализации высказываний:

1. Если высказывание – простое, то ему ставится в соответствие элементарная формула.