Материал: 4553

22

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

Примеры истинных высказываний: «Река Волга впадает в Каспийское море»; «Луна – спутник Земли». Примеры ложных высказываний: «Воронеж – столица Японии»; «В Томске водятся кентавры».

Если высказывание является истинным (ложным) в любой логической ситуации, то оно называется тождественно истинным (ложным) или логической константой, которую принято обозначать И(Л). В противном случае высказывание называется переменным.

23

Простейшие высказывания, из которых можно образовать различные новые высказывания, будем называть элементарными и обозначать А, В, С,…, X, Y, Z,… . Обсудим ниже логические операции над элементарными высказываниями.

Дизъюнкция. Обозначается А В, читается: «А или В». При этом разделительный смысл союза «или» исключается. Истинностная таблица дизъюнкции имеет следующий вид:

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

Конъюнкция. Эта операция обозначается А В (читается «А и В»). Значения истинности или ложности полученного сложного высказывания задаются следующей таблицей истинности:

Итак, конъюнкция двух элементарных высказываний истинна тогда и только тогда, когда оба элементарные высказывания истинны.

Отрицание. Обозначается , читается «не А». Это единственная логическая операция, относящаяся к одному высказыванию, – унарная, в отличие от остальных – бинарных, относящихся к двум высказываниям. Таблица истинности указанной операции следующая:

Таблица 3.3

Импликация. Обозначается А В, читается: «если А, то В». При этом А называется посылкой, а В – следствием. Истинностная таблица импликации:

Таблица 3.4

Импликация ложна тогда и только тогда, когда посылка А истинна, а следствие В – ложь.

Двойная импликация. Обозначается А↔В, читается: «А тогда и только тогда, когда В». Таблица истинности:

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

Замечания.

1. Отметим, что число строк истинностной таблицы для n элементарных высказываний равно (без «командной» строки). Так, в таблицах 3.1, 3.2, 3.4, 3.5 по четыре строки, а в таблице 3.3 – две.

2. Естественный порядок указанных выше логических операций следующий: отрицание, конъюнкция, дизъюнкция, импликация, двойная импликация. Скобки применяются в случае, когда этот порядок нужно нарушить.

25

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

Дадим следующее определение формулы алгебры высказываний.

1.Отдельно стоящая буква А, В, С, …, X, Y, Z, … – формула.

2.Если А, В – формулы, то формулами являются и (), (), (А В),

(А В), (А→В), (А↔В).

3.Других формул нет.

Например, высказывание S=(А→В) (( является формулой.

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

Ниже приводим основные равносильные формулы алгебры

Отметим, что операции импликации и двойной импликации можно заменить дизъюнкцией, конъюнкцией, отрицанием, используя следующие равносильные формулы: А→В = ,

А↔В = ( В) (А ),

А↔В = (А В) ().