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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

С точки зрения выразительности, логику высказываний можно охарактеризовать как классическую логику нулевого порядка[источник не указан 204 дня].

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

Язык логики высказываний[править | править вики-текст]

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

Алфавит языка логики высказываний[править | править вики-текст]

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

  • пропозициональные буквы (пропозициональные переменные):
p, q, r, s, t, p_1, q_1, r_1, s_1, t_1, ...
  • технические знаки: ( — левая скобка, ) — правая скобка.

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

Пропозициональные переменные[править | править вики-текст]

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

Пропозициональные формулы[править | править вики-текст]

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

Индуктивное определение формулы логики высказываний:[4][1]

  1. пропозициональная переменная есть формула;
  2. если A — произвольная формула, то \neg A — тоже формула;
  3. если A и B — произвольные формулы, то (A \to B), (A \wedge B), (A \leftrightarrow B), (A \vee B) и (A ~ \dot\or ~ B ~) — тоже формулы;

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

Язык логики высказываний можно рассматривать как множество пропозициональных формул[4].

Для формул логики высказываний можно определить понятие интерпретации как приписывание каждой пропозициональной переменной истинностного значения[6] («истина» или «ложь», хотя исчисление высказываний никак не ограничивает множество возможных значений при интерпретации: например, можно задать интерпретацию как отображение в множество \{0,1,\ldots,k\}, где k\in \mathbb{N}, — такой подход может использоваться, к примеру, при доказательстве независимости схем аксиом исчисления высказываний).

Правила построения формул логики высказываний[править | править вики-текст]

  1. Элементарное высказывание (буква) является формулой нулевого уровня. Если элементарное логическое высказывание всегда верно, мы будем его обозначать буквой И, а если оно всегда неверно, — буквой Л. Тогда формулы первого уровня — это элементарные высказывания, к которым применена только одна логическая связка.
  2. Пусть Ф1 и Ф2 — формулы ненулевого уровня. Тогда записи (¬(Ф1)), ((Ф1)\vee(Ф2)), ((Ф1)\wedge(Ф2)), ((Ф1)→(Ф2)) также являются формулами. Если же одна из формул Ф1 и Ф2 , к которым применяется логическая связка, имеет нулевой уровень, то она в скобки не заключается.

Теперь, зная буквы-элементарные высказывания, мы никогда не ошибёмся, определяя, является ли формулой запись, содержащая эти буквы, скобки и символы связок, то есть правильно ли построено сложное высказывание. В процессе подобного опознавания мы выделяем части формулы, то есть более короткие формулы, из которых на каждом этапе строится более длинная формула с применением одной связки. Самыми простыми частями формулы являются, разумеется, элементарные высказывания. Значит, логический анализ формулы сводится к выделению всех её частей.

Пример[править | править вики-текст]

Пусть элементарными высказываниями являются А, В, С. Записи

¬ A\wedge BC и (B)\wedge(B\veeA→C)

c формальной точки зрения не являются формулами, так как мы натыкаемся при их разборе на нарушение правил построения формул. (В первом случае отсутствует логическая связка между B и C и отсутствуют скобки вокруг ¬A. Во втором случае формула нулевого уровня В включена в скобки). А записи

(¬ A)\wedge(B\veeC) и B\wedge((B\veeA)→C)

вполне соответствуют требованиям построения формулы. В процессе анализа формулы (¬ A)\wedge(B\veeC) выделяются следующие её части:

               ( ¬A ) \wedge ( B\veeC )
                      \wedge                     | Связующее действие
                 ¬A       B \vee C             | Разделённые части (формулы первого уровня)
                 ¬          \vee               | Связующее действие
                 A        B    C             | Разделённые части (формулы нулевого уровня)
                                             | Все разделённые части являются элементарными высказываниями; разбор закончен.   

'

Соглашения о скобках[править | править вики-текст]

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

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

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

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

Интерпретация языка логики высказываний[править | править вики-текст]

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

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

~M\colon Vars \to \mathbb{B},

которое каждой пропозициональной переменной p сопоставляет истинностное значение M(p)[7].

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

p\! \neg p
0\!
1\!
1\!
0\!

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

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

Тождественно истинные формулы (тавтологии)[править | править вики-текст]

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

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

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

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

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

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

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

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

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

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

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

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

Исчисление высказываний[править | править вики-текст]

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

A_1 : A \rightarrow (B \rightarrow A);

A_2 : ((A \rightarrow (B \rightarrow C)) \rightarrow ((A \rightarrow B) \rightarrow (A \rightarrow C)));

A_3 : A \wedge B \rightarrow A;

A_4 : A \wedge B \rightarrow B;

A_5 : A \rightarrow (B \rightarrow (A \wedge B));

A_6 : A \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_9 : \neg A \rightarrow (A \rightarrow B);

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

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

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

\frac{A \rightarrow B, A}{B} (Modus ponens)

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. 1 2 3 4 5 6 7 Чупахин, Бродский, 1977, с. 203—205
  2. 1 2 Кондаков, 1971, статья «Исчисление высказываний»
  3. 1 2 НФЭ, 2010
  4. 1 2 3 Герасимов, 2011, с. 13
  5. Войшвилло, Дегтярев, 2001, с. 91—94
  6. Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. — С. 18-19
  7. 1 2 Герасимов, 2011
  8. Герасимов, 2011, с. 19

Литература[править | править вики-текст]

  • Кондаков Н. И. Логический словарь / Горский Д. П.. — М.: Наука, 1971. — 656 с.
  • Чупахин И. Я.,Бродский И. Н. Формальная логика. — Ленинград: Издательство Ленинградского университета, 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