Исчисление высказываний

Исчисление высказываний изучает предложения, которые могут быть либо истинными, либо ложными. Не всякое предложение является высказыванием. Например, бессмысленно говорить об истинности вопросительных предложений. Не являются высказываниями предложения, для которых нет единого мнения о том, истинны эти предложения или ложны. По-видимому, далеко не все согласятся с утверждением «математическая логика – увлекательный предмет».

Предложение «Шел снег» также не является высказыванием, так как, чтобы судить о его истинности, нужны дополнительные сведения о том, когда и где шел снег.

Объединяя предложения с помощью связок типа «и», «или»,«если… то…», можно образовывать новые предложения.

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

Конъюнкция (логическое И) истинна только тогда, когда оба составляющих ее высказывания истинны.

Дизъюнкция (логическое ИЛИ) ложна только тогда, когда ложны оба составляющих ее высказывания.

У импликации (соответствует связке «Если…, то…») первый операнд называется посылкой, а второй – заключением. Импликация ложна только тогда, когда ее посылка истинна, а заключение – ложно.

Логическая операция эквивалентность соответствует связке «тогда и только тогда». Ее результатом является истина, если оба высказывания или одновременно истинны, или одновременно ложны.

Логическое отрицание выполняется над одним высказыванием. Высказывание и его отрицание всегда имеют противоположные истинностные значения.

Символы, используемые для обозначений высказываний, называют атомами.

Правильно построенные формулы в логике высказываний рекурсивно определяются следующим образом:

1) атом есть формула;

2) если A и B – формулы, то формулами являются

и ØA, A Ù B, A Ú B, A ® B, A « B.

Здесь связки обозначены символами:

Ú - логическое ИЛИ (дизъюнкция);

Ù - логическое И (конъюнкция);

® - логическое СЛЕДУЕТ (импликация);

« - логическое ЭКВИВАЛЕНТНО (эквиваленция);

Ø - логическое отрицание.

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

Формула, состоящая из n различных атомов, имеет 2ⁿ различных интерпретаций.

Формула, истинная при всех интерпретациях, называется общезначимой (например, A Ú ØA).

Формула, ложная при всех интерпретациях, называется противоречивой (например, A ÙØA).

Формула, для которой существует хотя бы одна интерпретация, при которой она истинна, называется выполнимой.

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

Для преобразований формул исчисления высказываний применяют следующие эквивалентности:

1) A Ú ØA = true (истина);

A Ù ØA = false (ложь);

2) правило двойного отрицания

Ø (ØA) = A;

3) A ® B = ØA Ú B;

4) A « B = (A ® B) Ù (B ® A);

5) законы коммутативности

A Ú B = B Ú A, A Ù B = B Ù A;

6) законы ассоциативности

(A Ú B) Ú C =A Ú (B Ú C), (A Ù B) ÙC = A Ù (B Ù C);

7) законы дистрибутивности

A Ú (B Ù C) = (A Ú B) Ù (A Ú C), A Ù (B Ú C) = (A Ù B) Ú (A Ù C);

8) законы де Моргана

Ø(A Ú B) = ØA Ù ØB, Ø(A Ù B) = ØA Ú ØB;

9) A ® B = ØB ® ØA.