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

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

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

Несмотря на свою важность и широкую сферу применения, логика высказываний является простейшей логикой и имеет очень ограниченные средства для исследования суждений[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}, — такой подход может использоваться, к примеру, при доказательстве независимости схем аксиом исчисления высказываний).

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

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

  • Если опущены внешние скобки, то они восстанавливаются.
  • Если рядом стоят две конъюнкции или дизъюнкции (например, 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 \quad (A \rightarrow B)}{B} (Modus ponens)

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

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

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

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