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

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

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

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

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

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

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

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

Var = {p, q, r . . .}

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

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

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

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

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

Индуктивное определение множества формул $F m$ логики высказываний:Шаблон:Sfn Шаблон:Sfn

Если $p \in Var$ , то $p \in Fm$ (всякая пропозициональная переменная есть формула);
если $A$ — формула, то $\neg A$ — тоже формула;
если $A$ и $B$ — произвольные формулы, то $(A \land B)$ , $(A \lor B)$ , $(A \to B)$ — тоже формулы.

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

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

$A : : = p | (\neg A) | (A \land B) | (A \lor B) | (A \to B)$

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

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

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

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

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

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

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

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

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

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

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

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

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

$A_{3} : A \land B \to A$ ;

$A_{4} : A \land B \to B$ ;

$A_{5} : A \to (B \to (A \land B))$ ;

$A_{6} : A \to (A \lor B)$ ;

$A_{7} : B \to (A \lor B)$ ;

$A_{8} : (A \to C) \to ((B \to C) \to ((A \lor B) \to C))$ ;

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

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

$A_{11} : A \lor \neg A$ .

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

$\frac{A (A \to B)}{B}$ (Modus ponens)

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

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

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

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

M : Var \to 𝔹

,

которое каждую пропозициональную переменную $p$ сопоставляет с истинностным значением $M (p)$ Шаблон:Sfn.

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

$p$	$\neg p$
$0$	$1$
$1$	$0$

Значения двухместных логических связок $\to$ (импликация), $\lor$ (дизъюнкция) и $\land$ (конъюнкция) определяются так:

$p$	$q$	$p \to q$	$p \land q$	$p \lor q$
$0$	$0$	$1$	$0$	$0$
$0$	$1$	$1$	$0$	$1$
$1$	$0$	$0$	$0$	$1$
$1$	$1$	$1$	$1$	$1$

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

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

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

\neg (p \lor q) \leftrightarrow (\neg p \land \neg q)

;

\neg (p \land q) \leftrightarrow (\neg p \lor \neg q)

;

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

(p \to q) \leftrightarrow (\neg q \to \neg p)

;

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

p \lor (p \land q) \leftrightarrow p

;

p \land (p \lor q) \leftrightarrow p

;

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

p \land (q \lor r) \leftrightarrow (p \land q) \lor (p \land r)

;

p \lor (q \land r) \leftrightarrow (p \lor q) \land (p \lor r)

.

См. также

Примечания

Шаблон:Примечания

Литература

Шаблон:Вс Шаблон:Логика

↑ Ершов Ю. Л., Палютин Е. А. Математическая логика. — Шаблон:М., Наука, 1979. — с. 24

[Erch-1] Ершов Ю. Л., Палютин Е. А. Математическая логика. — Шаблон:М., Наука, 1979. — с. 24

[1]

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

Содержание

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

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

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

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

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

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

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

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

См. также

Примечания

Литература

Навигация

$p$	$q$	$p \to q$	$p \land q$	$p \lor q$
$0$	$0$	$1$	$0$	$0$
$0$	$1$	$1$	$0$	$1$
$1$	$0$	$0$	$0$	$1$
$1$	$1$	$1$	$1$	$1$

$p$	$q$	$p \to q$	$p \land q$	$p \lor q$
$0$	$0$	$1$	$0$	$0$
$0$	$1$	$1$	$0$	$1$
$1$	$0$	$0$	$0$	$1$
$1$	$1$	$1$	$1$	$1$

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

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

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

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

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

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

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

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

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

См. также

Примечания

Литература

Навигация

Поиск

$p$	$q$	$p \to q$	$p \land q$	$p \lor q$
$0$	$0$	$1$	$0$	$0$
$0$	$1$	$1$	$0$	$1$
$1$	$0$	$0$	$0$	$1$
$1$	$1$	$1$	$1$	$1$