Логика высказываний
Логика высказываний, или пропозициональная логика (лат. propositio — «высказывание»[1]), или исчисление высказываний[2] — это раздел символической логики, изучающий сложные высказывания, образованные из простых, и их взаимоотношения. В отличие от логики предикатов, пропозициональная логика не рассматривает внутреннюю структуру простых высказываний, она лишь учитывает, с помощью каких союзов и в каком порядке простые высказывания сочленяются в сложные[3].
Несмотря на свою важность и широкую сферу применения, логика высказываний является простейшей логикой и имеет очень ограниченные средства для исследования суждений[2].
Содержание
1 Язык логики высказываний
1.1 Алфавит языка логики высказываний
1.2 Пропозициональные переменные
1.3 Пропозициональные формулы
1.4 Соглашения о скобках
1.5 Формализация и интерпретация
2 Аксиомы и правила вывода формальной системы логики высказываний
3 Таблицы истинности основных операций
4 Тождественно истинные формулы (тавтологии)
5 См. также
6 Примечания
7 Литература
Язык логики высказываний |
Язык логики высказываний (пропозициональный язык[4]) — формализованный язык, предназначенный для анализа логической структуры сложных высказываний[1].
Алфавит языка логики высказываний |
Исходные символы, или алфавит языка логики высказываний, разделены на следующие три категории[1][5]:
- пропозициональные буквы (пропозициональные переменные):
- p,q,r,s,t,p1,q1,r1,s1,t1,...{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 } | Знак эквивалентности |
Пропозициональные переменные |
Пропозициональная переменная — переменная, которая в пропозициональных формулах служит для замены собой элементарных логических высказываний[3].
Пропозициональные формулы |
Роль структурных образований, аналогичных элементарным и сложным высказываниям, играют в этом языке формулы. Пропозициональная формула — слово языка логики высказываний[6], т.е. конечная последовательность знаков алфавита, построенная по изложенным ниже правилам и образующая законченное выражение языка логики высказываний[1]. Заглавные латинские буквы A{displaystyle A}
Индуктивное определение формулы логики высказываний:[4][1]
- пропозициональная переменная есть формула;
- если A{displaystyle A}
- если A{displaystyle A}
, (A∨B){displaystyle (Avee B)}
и (A ∨˙ B ){displaystyle (A~{dot {lor }}~B~)}
— тоже формулы.
Других формул в языке логики высказываний нет.
Относительно любой последовательности знаков алфавита языка логики высказываний можно решить, является она формулой или нет. Если эта последовательность может быть построена в соответствии с пп. 1—3 определения формулы, то она формула, если нет, то не формула[1].
Соглашения о скобках |
Поскольку в построенных по определению формулах оказывается слишком много скобок, иногда и не обязательных для однозначного понимания формулы, математики приняли соглашения о скобках, по которым некоторые из скобок можно опускать. Записи с опущенными скобками восстанавливаются по следующим правилам.
- Если опущены внешние скобки, то они восстанавливаются.
- Если рядом стоят две конъюнкции или дизъюнкции (например, A∧B∧C{displaystyle Awedge Bwedge C}
), то в скобки заключается сначала самая левая часть (то есть две подформулы со связкой между ними). (Говорят также, что эти связки левоассоциативны.)
- Если рядом стоят разные связки, то скобки расставляются согласно приоритетам: ¬,∧,∨{displaystyle neg ,wedge ,vee }
и →{displaystyle to }
(от высшего к низшему).
Когда говорят о длине формулы, имеют в виду длину подразумеваемой (восстанавливаемой) формулы, а не сокращённой записи.
Например: запись A∨B∧¬C{displaystyle Avee Bwedge neg C}
Формализация и интерпретация |
Как и любой другой формализованный язык, язык логики высказываний можно рассматривать как множество всех слов, построенных с использованием алфавита этого языка[7]. Язык логики высказываний можно рассматривать как множество всевозможных пропозициональных формул[4]. Предложения естественного языка могут быть переведены на символический язык логики высказываний, где они будут представлять из себя формулы логики высказываний. Процесс перевода высказывания в формулу языка логики высказываний называется формализацией. Обратный процесс подстановки вместо пропозициональных переменных конкретных высказываний называется интерпретацией[8].
Аксиомы и правила вывода формальной системы логики высказываний |
 | Этот раздел не завершён. |
 | Для улучшения этой статьи желательно: |
Одним из возможных вариантов (гильбертовской) аксиоматизации логики высказываний является следующая система аксиом:
A1:A→(B→A){displaystyle A_{1}:Arightarrow (Brightarrow A)}
A2:(A→(B→C))→((A→B)→(A→C)){displaystyle A_{2}:(Arightarrow (Brightarrow C))rightarrow ((Arightarrow B)rightarrow (Arightarrow C))}
A3:A∧B→A{displaystyle A_{3}:Awedge Brightarrow A}
A4:A∧B→B{displaystyle A_{4}:Awedge Brightarrow B}
A5:A→(B→(A∧B)){displaystyle A_{5}:Arightarrow (Brightarrow (Awedge B))}
A6:A→(A∨B){displaystyle A_{6}:Arightarrow (Avee B)}
A7:B→(A∨B){displaystyle A_{7}:Brightarrow (Avee B)}
A8:(A→C)→((B→C)→((A∨B)→C)){displaystyle A_{8}:(Arightarrow C)rightarrow ((Brightarrow C)rightarrow ((Avee B)rightarrow C))}
A9:¬A→(A→B){displaystyle A_{9}:neg Arightarrow (Arightarrow B)}
A10:(A→B)→((A→¬B)→¬A){displaystyle A_{10}:(Arightarrow B)rightarrow ((Arightarrow neg B)rightarrow neg A)}
A11:A∨¬A{displaystyle A_{11}:Avee neg A}
вместе с единственным правилом:
A(A→B)B{displaystyle {frac {Aquad (Arightarrow B)}{B}}}
Теорема корректности исчисления высказываний утверждает, что все перечисленные выше аксиомы являются тавтологиями, а с помощью правила modus ponens из истинных высказываний можно получить только истинные. Доказательство этой теоремы тривиально и сводится к непосредственной проверке. Куда более интересен тот факт, что все остальные тавтологии можно получить из аксиом с помощью правила вывода — это так называемая теорема полноты логики высказываний.
Таблицы истинности основных операций |
| Этот раздел не завершён. |
| Для улучшения этой статьи желательно: |
Основной задачей логики высказываний является установление истинностного значения формулы, если даны истинностные значения входящих в неё переменных. Истинностное значение формулы в таком случае определяется индуктивно (с шагами, которые использовались при построении формулы) с использованием таблиц истинности связок[9].
Пусть B{displaystyle mathbb {B} }
M:Vars→B{displaystyle Mcolon Varsto mathbb {B} },
которое каждую пропозициональную переменную p{displaystyle p}
Оценка отрицания ¬p{displaystyle neg p}
| p{displaystyle p} | ¬p{displaystyle neg p} |
|---|---|
0{displaystyle 0} | 1{displaystyle 1}  |
| 1{displaystyle 1} | 0{displaystyle 0} |
Значения двухместных логических связок →{displaystyle rightarrow }
и ∧{displaystyle wedge }
p{displaystyle p} | q{displaystyle q}  | p→q{displaystyle prightarrow q}  | p∧q{displaystyle pwedge q}  | p∨q{displaystyle pvee q}  |
|---|---|---|---|---|
0{displaystyle 0} | 0{displaystyle 0} | 1{displaystyle 1} | 0{displaystyle 0} | 0{displaystyle 0} |
0{displaystyle 0} | 1{displaystyle 1} | 1{displaystyle 1} | 0{displaystyle 0} | 1{displaystyle 1} |
1{displaystyle 1} | 0{displaystyle 0} | 0{displaystyle 0} | 0{displaystyle 0} | 1{displaystyle 1} |
1{displaystyle 1} | 1{displaystyle 1} | 1{displaystyle 1} | 1{displaystyle 1} | 1{displaystyle 1} |
Тождественно истинные формулы (тавтологии) |
| Этот раздел не завершён. |
| Для улучшения этой статьи желательно: |
Формула является тождественно истинной, если она истинна при любых значениях входящих в неё переменных (то есть, при любой интерпретации)[10]. Далее перечислены несколько широко известных примеров тождественно истинных формул логики высказываний:
законы де Моргана:
¬(p∨q)↔(¬p∧¬q){displaystyle neg (pvee q)leftrightarrow (neg pwedge neg q)};
¬(p∧q)↔(¬p∨¬q){displaystyle neg (pwedge q)leftrightarrow (neg pvee neg q)};
закон контрапозиции:
(p→q)↔(¬q→¬p){displaystyle (prightarrow q)leftrightarrow (neg qrightarrow neg p)};
законы поглощения:
p∨(p∧q)↔p{displaystyle pvee (pwedge q)leftrightarrow p};
p∧(p∨q)↔p{displaystyle pwedge (pvee q)leftrightarrow p};
законы дистрибутивности:
p∧(q∨r)↔(p∧q)∨(p∧r){displaystyle pwedge (qvee r)leftrightarrow (pwedge q)vee (pwedge r)};
p∨(q∧r)↔(p∨q)∧(p∨r){displaystyle pvee (qwedge r)leftrightarrow (pvee q)wedge (pvee r)}.
См. также |
- Логика первого порядка
- Дизъюнктивная нормальная форма
- Конъюнктивная нормальная форма
Примечания |
↑ 1234567 Чупахин, Бродский, 1977, с. 203—205.
↑ 12 Кондаков, 1971, статья «Исчисление высказываний».
↑ 12 НФЭ, 2010.
↑ 123 Герасимов, 2011, с. 13.
↑ Войшвилло, Дегтярев, 2001, с. 91—94.
↑ Эдельман, 1975, с. 130.
↑ Эдельман, 1975, с. 128.
↑ Игошин, 2008, с. 32.
↑ 12 Герасимов, 2011, с. 17—19.
↑ Герасимов, 2011, с. 19.
Литература |
- Кондаков Н. И. Логический словарь / Горский Д. П.. — М.: Наука, 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.
