Исчисление высказываний - NiNa.Az

Логика высказываний, пропозициональная логика (лат. propositio — «высказывание») или исчисление высказываний, также логика нулевого порядка — это раздел символической логики, изучающий сложные высказывания, образованные из простых, и их взаимоотношения. В отличие от логики предикатов, пропозициональная логика не рассматривает внутреннюю структуру простых высказываний, она лишь учитывает, с помощью каких союзов и в каком порядке простые высказывания сочленяются в сложные.

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

Язык логики высказываний

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

Синтаксис логики высказываний

Исходные символы, или алфавит языка логики высказываний:

• множество пропозициональных переменных (пропозициональных букв):

${\displaystyle {\text{Var}}=\{p,q,r...\}}$

• пропозициональные связки (логические союзы):

Символ	Значение
${\displaystyle \neg }$	Знак отрицания
${\displaystyle \land }$ или &	Знак конъюнкции («логическое И»)
${\displaystyle \vee }$	Знак дизъюнкции («логическое ИЛИ»)
${\displaystyle \rightarrow }$	Знак импликации

• Вспомогательные символы: левая скобка (, правая скобка ).

Пропозициональные формулы

Запрос «Пропозициональная формула»^[d] перенаправляется сюда. На эту тему нужно создать отдельную статью.

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

Индуктивное определение множества формул ${\displaystyle Fm}$ логики высказываний:

1. Если ${\displaystyle p\in {\text{Var}}}$, то ${\displaystyle p\in {\text{Fm}}}$ (всякая пропозициональная переменная есть формула);
2. если ${\displaystyle A}$ — формула, то ${\displaystyle \neg A}$ — тоже формула;
3. если ${\displaystyle A}$ и ${\displaystyle B}$ — произвольные формулы, то ${\displaystyle (A\wedge B)}$, ${\displaystyle (A\vee B)}$, ${\displaystyle (A\to B)}$ — тоже формулы.

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

Форма Бэкуса — Наура, определяющая синтаксис логики высказываний, имеет запись:

${\displaystyle A::=p\;|\;(\neg A)\;|\;(A\land B)\;|\;(A\lor B)\;|\;(A\to B)}$

Заглавные латинские буквы ${\displaystyle A}$, ${\displaystyle B}$ и другие, которые употребляются в определении формулы, принадлежат не языку логики высказываний, а его метаязыку, то есть языку, который используется для описания самого языка логики высказываний. Содержащие метабуквы выражения ${\displaystyle \neg A}$, ${\displaystyle (A\to B)}$ и другие — не пропозициональные формулы, а схемы формул. Например, выражение ${\displaystyle (A\wedge B)}$ есть схема, под которую подходят формулы ${\displaystyle (p\wedge q)}$, ${\displaystyle (p\wedge (r\vee s))}$ и другие.

Относительно любой последовательности знаков алфавита языка логики высказываний можно решить, является она формулой или нет. Если эта последовательность может быть построена в соответствии с пп. 1—3 определения формулы, то она формула, если нет, то не формула.

Соглашения о скобках

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

• Если опущены внешние скобки, то они восстанавливаются.
• Если рядом стоят две конъюнкции или дизъюнкции (например, ${\displaystyle A\wedge B\wedge C}$), то в скобки заключается сначала самая левая часть (то есть эти связки левоассоциативны).
• Если рядом стоят разные связки, то скобки расставляются согласно приоритетам: ${\displaystyle \neg ,\wedge ,\vee }$ и ${\displaystyle \to }$ (от высшего к низшему).

Когда говорят о длине формулы, имеют в виду длину подразумеваемой (восстанавливаемой) формулы, а не сокращённой записи.

Например: запись ${\displaystyle A\vee B\wedge \neg C}$ означает формулу ${\displaystyle (A\vee (B\wedge (\neg C)))}$, а её длина равна 12.

Формализация и интерпретация

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

Аксиомы и правила вывода формальной системы логики высказываний

Одним из возможных вариантов (гильбертовской) аксиоматизации логики высказываний является следующая система аксиом:

${\displaystyle A_{1}:A\rightarrow (B\rightarrow A)}$;

${\displaystyle A_{2}:(A\rightarrow (B\rightarrow C))\rightarrow ((A\rightarrow B)\rightarrow (A\rightarrow C))}$;

${\displaystyle A_{3}:A\wedge B\rightarrow A}$;

${\displaystyle A_{4}:A\wedge B\rightarrow B}$;

${\displaystyle A_{5}:A\rightarrow (B\rightarrow (A\wedge B))}$;

${\displaystyle A_{6}:A\rightarrow (A\vee B)}$;

${\displaystyle A_{7}:B\rightarrow (A\vee B)}$;

${\displaystyle A_{8}:(A\rightarrow C)\rightarrow ((B\rightarrow C)\rightarrow ((A\vee B)\rightarrow C))}$;

${\displaystyle A_{9}:\neg A\rightarrow (A\rightarrow B)}$;

${\displaystyle A_{10}:(A\rightarrow B)\rightarrow ((A\rightarrow \neg B)\rightarrow \neg A)}$;

${\displaystyle A_{11}:A\vee \neg A}$.

вместе с единственным правилом:

${\displaystyle {\frac {A\quad (A\rightarrow B)}{B}}}$ (Modus ponens)

Теорема корректности исчисления высказываний утверждает, что все перечисленные выше аксиомы являются тавтологиями, а с помощью правила modus ponens из истинных высказываний можно получить только истинные. Доказательство этой теоремы тривиально и сводится к непосредственной проверке. Куда более интересен тот факт, что все остальные тавтологии можно получить из аксиом с помощью правила вывода — это так называемая теорема полноты логики высказываний.

Таблицы истинности основных операций

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

Пусть ${\displaystyle \mathbb {B} }$ — множество всех истинностных значений ${\displaystyle \{0,1\}}$, а ${\displaystyle Var}$ — множество пропозициональных переменных. Тогда интерпретацию (или модель) языка логики высказываний можно представить в виде отображения

${\displaystyle M\colon {\text{Var}}\to \mathbb {B} }$,

которое каждую пропозициональную переменную ${\displaystyle p}$ сопоставляет с истинностным значением ${\displaystyle M(p)}$.

Оценка отрицания ${\displaystyle \neg p}$ задаётся таблицей:

${\displaystyle p}$	${\displaystyle \neg p}$
${\displaystyle 0}$	${\displaystyle 1}$
${\displaystyle 1}$	${\displaystyle 0}$

Значения двухместных логических связок ${\displaystyle \rightarrow }$ (импликация), ${\displaystyle \vee }$ (дизъюнкция) и ${\displaystyle \wedge }$ (конъюнкция) определяются так:

${\displaystyle p}$	${\displaystyle q}$	${\displaystyle p\rightarrow q}$	${\displaystyle p\wedge q}$	${\displaystyle p\vee q}$
${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle 1}$	${\displaystyle 0}$	${\displaystyle 0}$
${\displaystyle 0}$	${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle 0}$	${\displaystyle 1}$
${\displaystyle 1}$	${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle 1}$
${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle 1}$

Тождественно истинные формулы (тавтологии)

Формула является тождественно истинной, если она истинна при любых значениях входящих в неё переменных (то есть, при любой интерпретации). Далее перечислены несколько широко известных примеров тождественно истинных формул логики высказываний:

• законы де Моргана:

${\displaystyle \neg (p\vee q)\leftrightarrow (\neg p\wedge \neg q)}$;

${\displaystyle \neg (p\wedge q)\leftrightarrow (\neg p\vee \neg q)}$;

• закон контрапозиции:

${\displaystyle (p\rightarrow q)\leftrightarrow (\neg q\rightarrow \neg p)}$;

• законы поглощения:

${\displaystyle p\vee (p\wedge q)\leftrightarrow p}$;

${\displaystyle p\wedge (p\vee q)\leftrightarrow p}$;

• законы дистрибутивности:

${\displaystyle p\wedge (q\vee r)\leftrightarrow (p\wedge q)\vee (p\wedge r)}$;

${\displaystyle p\vee (q\wedge r)\leftrightarrow (p\vee q)\wedge (p\vee r)}$.

См. также

• Логика первого порядка
• Дизъюнктивная нормальная форма
• Конъюнктивная нормальная форма

Примечания

1. Чупахин, Бродский, 1977, с. 203—205.
2. Кондаков, 1971, статья «Исчисление высказываний».
3. НФЭ, 2010.
4. Герасимов, 2011, с. 13.
5. Войшвилло, Дегтярев, 2001, с. 91—94.
6. Ершов Ю. Л., Палютин Е. А. Математическая логика. — М., Наука, 1979. — с. 24
7. Эдельман, 1975, с. 130.
8. Эдельман, 1975, с. 128.
9. Игошин, 2008, с. 32.
10. Герасимов, 2011, с. 17—19.
11. Герасимов, 2011, с. 19.

Литература

• Кондаков Н. И. Логический словарь / Горский Д. П.. — М.: Наука, 1971. — 656 с.
• Эдельман С. Л. Математическая логика. — М.: Высшая школа, 1975. — 176 с.
• Чупахин И. Я., Бродский И. Н. Формальная логика. — Ленинград: Издательство Ленинградского университета, 1977. — 357 с.
• Войшвилло Е. К., Дегтярев М. Г. Логика. — М.: ВЛАДОС-ПРЕСС, 2001. — 528 с. — ISBN 5-305-00001-7.
• Математическая логика и теория алгоритмов. — 2-е изд., стереотип.. — М.: Издательский центр «Академия», 2008. — 448 с. — ISBN 978-5-7695-4593-1.
• А. С. Карпенко. Логика высказываний // Новая философская энциклопедия : в 4 т. / пред. науч.-ред. совета В. С. Стёпин. — 2-е изд., испр. и доп. — М. : Мысль, 2010. — 2816 с.
• Герасимов А. С. Курс математической логики и теории вычислимости. — СПб.: Издательство «ЛЕМА», 2011. — 284 с. — ISBN 978-5-98709-292-7.