1. Логические исчисления

   1. Логика высказываний

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

• За окном идет снег.

• Завтра будет Новый год.

• Столица России – Москва.

Не всякое предложение может быть истинным или ложным, а значит, быть высказыванием. Так, вопросительное или повелительное предложение не является высказыванием.

Например, повествовательное предложение "Я лгу" не может быть высказыванием (парадокс лжеца). Действительно, если бы это предложение было верным, то по смыслу оно было бы ложным. А если бы предложение было бы ложным, то по смыслу оно должно быть истинным. Но ни то, ни другое для высказывания невозможно, так как оно не может быть одновременно и истинным, и ложным. Этот пример показывает, насколько внимательно следует относиться к принимаемым определениям (в данном случае - к определению высказывания).

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

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

• Не A (или то, что получится в результате вставки частицы "не" перед глаголом – основным или вспомогательным)

• A не имеет места

• A не верно

Конъюнкцией двух высказываний A и B называется высказывание, истинное тогда и только тогда, когда истинны оба высказывания. Обозначается A&Q. В естественном языке конъюнкция A&B соответствует следующим конструкциям

• A и B

• Не только A, но и B

• B, хотя и A

• B, несмотря на A

• Как A, так и B

• A вместе с B

• A, в то время как B

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

• A или B, или оба

• A или B

• A, если не B

• A и/или B (в юридических текстах)

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

• Если A, то B

• Коль скоро A, то B

• В случае A имеет место B

• Для B достаточно A

• Для A необходимо B

• A, только если B

• B, если A

• A влечет B

• A имплицирует B

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

• A, если и только если B

• Если A, то B, и обратно

• A, если B, и B, если A

• Для A необходимо и достаточно B

• A равносильно B

• A тогда и только тогда, когда B

Можно попытаться прочесть полученные высказывания, когда A - это высказывание "Солнце взошло", а B - высказывание "Птицы смолкли".

Алфавит логики высказываний содержит следующие символы: высказывательные переменные – обычно заглавные латинские буквы; логические символы, символы скобок (, ).

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

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

2. если A и B – формулы, то (A&B), (AVB), (A→B), (A~B), ¬A – формулы.

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

Для упрощения записи вводится приоритет операций (¬, &, V, ~, →) и лишние скобки опускаются.

Пример 1. Выражение (A&B) (AVB) является формулой, поскольку получено при помощи логической связки  из двух подформул (A&B), (AVB). Каждая из подформул представляет собой логическую связку двух переменных.

Пример 2. Выражение (A&B) (AVB) не является формулой, поскольку логическая связка  связывает два выражения (A&B), (AVB). Первое выражение не является формулой, поскольку не получено по правилам 1 –3.

Пример 3 Перевести следующее высказывание в логическую символику:

Я заплачу за работу по ремонту телевизора, если он будет работать.

Выделим отдельные высказывания, встречающиеся в данном высказывании и обозначим их переменными.

А=”Я заплачу за работу по ремонту телевизора”

В=”Телевизор будет работать”

Высказывания А и В связаны между собой импликацией, поэтому формула, соответствующая высказыванию, выглядит так BA.

Если каждой высказывательной переменной, входящей в формулу, придавать истинностное значение И и Л, то формула будет определять истинностную функцию (т.е. функцию, определенную на множестве высказывательных переменных) со значениями в множестве {И, Л}. Если, кроме того, принять И=1, Л=0, то любую формулу логики высказываний можно интерпретировать как формулу логики переключательных функций. По аналогии с переключательными функциями, для любого высказывания можно построить таблицу истинности.

Пример. Построим таблицу истинности для формулы (A&B) (AVB)

A	B	(A&B) (AVB)
Л	Л	И
Л	И	И
И	Л	Л
И	И	И

Упорядоченный набор высказывательных переменных <X1, X2, ..., Xk> назовем списком переменных формулы A, если все переменные формулы A содержатся в этом наборе. В списке переменных формулы A часть переменных может быть фиктивной, т.е. может не входить явно в формулу A. Очевидно, что если список переменных для формулы A содержит k переменных, то таблица истинности для формулы A будет содержать 2^k строк.

Пусть формула A зависит от списка переменных <X1, X2, ..., Xk>. Формула A называется тавтологией (тождественно-истинной формулой – ТИФ), если при любых значениях (интерпретации) переменных списка <X1, X2, ..., Xk> она принимает значение И. Формула A называется выполнимой (условно-истинной формулой – УИФ), если при некоторой значениях переменных списка <X1, X2, ..., Xk> она принимает значение И. Формула A называется тождественно ложной (противоречием) формулой – ТЛФ, если при любых значениях переменных списка <X1, X2, ..., Xk> она принимает значение Л. Формула A называется опровержимой (условно-ложной формулой), если при некоторых значениях переменных списка <X1, X2, ..., Xk> она принимает значение Л.

Формула В логически следует из формулы А (АВ), если формула В имеет значение И при всех интерпретациях, при которых формула А имеет значение И. Формулы А и В логически эквивалентны (АВ), если они являются логическим следствием друг друга. Логически эквивалентные формулы имеют одинаковые значения при любой интерпретации.

Теорема. Имеют место следующие логические эквивалентности

(АВ) АВ

АВ (АВ)&(ВА)

Доказательство проводится сравнением таблиц истинности двух формул.

Теорема.Справедливы следующие логические эквивалентности для алгебры высказываний (1 и 0 – тождественно истинное и тождественно ложное высказывания соответственно)

1	¬¬A≡A	Закон двойного отрицания
2		Законы коммутативности
3
4		Законы ассоциативности
5
6		Законы дистрибутивности
7
8		Законы идемпотентности
9
10		Законы де Моргана
11
12		Законы нуля и единицы
13
14
15
16		Законы поглощения
17
18		Закон противоречия
19		Закон исключенного третьего

Приведем теорему о логическом следствии двух формул

Теорема. А₁&…&A_n  Q тогда и только тогда, когда (А₁&…&A_n)Q – тавталогия. А₁&…&A_n  Q тогда и только тогда, когда А₁&…&A_n&Q – противоречие.

Доказательство. Докажем первое утверждение.

Необходимость. Пусть формула А₁&…&A_n принимает значение И при некоторой интерпретации. Обозначим это I(А₁&…&A_n)=И. Тогда I(Q)= И и I(А₁&…&A_n)Q)=И. Пусть I(А₁&…&A_n)=Л. Тогда I((А₁&…&A_n)Q)=И. Таким образом формула (А₁&…&A_n)Q – общезначима.

Достаточность. Пусть I((А₁&…&A_n)Q)=И. Тогда если I(А₁&…&A_n)=И, то и I(Q)= И. Таким образом, Q является логическим следствием формулы А₁&…&A_n.