§ 2. Формулы алгебры высказываний и их истинностное значение.

Пусть А,В,С, ... простые высказывания, принимающие одно из двух значений И или Л.

С помощью логических операций из них можно образовать более сложные высказывания: , АВ, ВС, АВ и так далее. Из этих высказываний с помощью тех же логических операций можно образовать еще более сложные высказывания, например, ((АВ) ВС)), (АВ)( ВС), ((ВС)  ).

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

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

Простые высказывания могут иметь постоянные значения, то есть быть истинными или ложными, но могут и не иметь определенного значения. Тогда такие высказывания называют переменными высказываниями. Например, высказывание X>10 является переменным, так как, например, при Х=11 оно истинно, а при Х=8 оно ложно. Условимся переменные высказывания обозначать X, Y, Z, ... или X₁, Х₂, ..., X_n, а формулу алгебры высказываний символически записывать так F(X, Y, Z, ...) или F(X₁, Х₂, ..., X_n,).

Так как каждое из высказываний принимает одно значение из {И, Л}, то и формула алгебры высказываний принимает значение из этого множества.

Чтобы найти значение истинности формулы F от n высказываний, надо составить для нее таблицу истинности и из последнего столбца таблицы узнать значение истинности.

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

П

3

1

F (X, Y, Z) = ((XY) Z)  Y

Из последнего столбца таблицы следует, что данная формула при всех возможных значениях истинности высказываний X, Y, Z принимает 6 раз значение истины и 2 раза значение лжи.