WikiSort.ru - Не сортированное

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

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

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

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

Алфавит языка логики высказываний

Исходные символы, или алфавит языка логики высказываний, разделены на следующие три категории^[1][5]:

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

${\displaystyle p,q,r,s,t,p_{1},q_{1},r_{1},s_{1},t_{1},...}$

• логические знаки (логические союзы):

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

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

Этот раздел не завершён. Вы поможете проекту, исправив и дополнив его.

Для улучшения этой статьи желательно: Проставив сноски, внести более точные указания на источники.

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

${\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 из истинных высказываний можно получить только истинные. Доказательство этой теоремы тривиально и сводится к непосредственной проверке. Куда более интересен тот факт, что все остальные тавтологии можно получить из аксиом с помощью правила вывода — это так называемая теорема полноты логики высказываний.

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

Этот раздел не завершён. Вы поможете проекту, исправив и дополнив его.

Для улучшения этой статьи желательно: Проставив сноски, внести более точные указания на источники.

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

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

${\displaystyle M\colon Vars\to \mathbb {B} }$ ,

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

Оценка отрицания ${\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}$

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

Этот раздел не завершён. Вы поможете проекту, исправив и дополнив его.

Для улучшения этой статьи желательно: Проставив сноски, внести более точные указания на источники.

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

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

${\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)}$ .

См. также

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

Примечания

Литература

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