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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

M\colon {\text{Var}}\to \mathbb {B}

M\colon {\text{Var}}\to \mathbb {B}

,

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

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

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

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

$p$ $p$	$q$ $q$	$p\rightarrow q$ $p\rightarrow q$	$p\wedge q$ $p\wedge q$	$p\vee q$ $p\vee q$
$0$ $0$	$0$ $0$	$1$ $1$	$0$ $0$	$0$ $0$
$0$ $0$	$1$ $1$	$1$ $1$	$0$ $0$	$1$ $1$
$1$ $1$	$0$ $0$	$0$ $0$	$0$ $0$	$1$ $1$
$1$ $1$	$1$ $1$	$1$ $1$	$1$ $1$	$1$ $1$

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

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

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

\neg (p\vee q)\leftrightarrow (\neg p\wedge \neg q)

\neg (p\vee q)\leftrightarrow (\neg p\wedge \neg q)

;

\neg (p\wedge q)\leftrightarrow (\neg p\vee \neg q)

\neg (p\wedge q)\leftrightarrow (\neg p\vee \neg q)

;

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

(p\rightarrow q)\leftrightarrow (\neg q\rightarrow \neg p)

(p\rightarrow q)\leftrightarrow (\neg q\rightarrow \neg p)

;

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

p\vee (p\wedge q)\leftrightarrow p

p\vee (p\wedge q)\leftrightarrow p

;

p\wedge (p\vee q)\leftrightarrow p

p\wedge (p\vee q)\leftrightarrow p

;

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

p\wedge (q\vee r)\leftrightarrow (p\wedge q)\vee (p\wedge r)

p\wedge (q\vee r)\leftrightarrow (p\wedge q)\vee (p\wedge r)

;

p\vee (q\wedge r)\leftrightarrow (p\vee q)\wedge (p\vee r)

p\vee (q\wedge r)\leftrightarrow (p\vee q)\wedge (p\vee r)

.

См. также

Примечания

↑ , с. 203—205.
↑ , статья «Исчисление высказываний».
.
↑ , с. 13.
, с. 91—94.
Ершов Ю. Л. , Палютин Е. А. Математическая логика. — М. , Наука , 1979. — с. 24
, с. 130.
, с. 128.
, с. 32.
↑ , с. 17—19.
, с. 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 .