- Логика высказываний
-
Для улучшения этой статьи желательно?: - Проставив сноски, внести более точные указания на источники.
Логика высказываний (или пропозициональная логика от англ. propositional logic, или исчисление высказываний[1]) — это формальная теория, основным объектом которой служит понятие логического высказывания. С точки зрения выразительности, её можно охарактеризовать как классическую логику нулевого порядка.
Несмотря на свою важность и широкую сферу применения, логика высказываний является простейшей логикой и имеет очень ограниченные средства для исследования суждений[1].
Содержание
Основные понятия
Базовыми понятиями логики высказываний являются пропозициональная переменная — переменная, значением которой может быть логическое высказывание, и (пропозициональная) формула, определяемой индуктивно следующим образом[2]:
- Если P — пропозициональная переменная, то P — формула.
- Если A — формула, то — формула.
- Если A и B — формулы, то , и — формулы.
- Других формул нет.
Множество пропозиционных формул называется языком логики высказываний (англ. propositional language, PL)[2].
Знаки и (отрицание, конъюнкция, дизъюнкция и импликация) называются пропозициональными связками. Подформулой называется часть формулы, сама являющаяся формулой. Собственной подформулой называется подформула, не совпадающая со всей формулой.
Правила построения формул логики высказываний
- Элементарное высказывание (буква) является формулой нулевого уровня. Если элементарное логическое высказывание всегда верно, мы будем его обозначать буквой И, а если оно всегда неверно, — буквой Л. Тогда формулы первого уровня — это элементарные высказывания, к которым применена только одна логическая связка.
- Пусть Ф1 и Ф2 — формулы ненулевого уровня. Тогда записи (¬(Ф1)), ((Ф1)(Ф2)), ((Ф1)(Ф2)), ((Ф1)→(Ф2)) также являются формулами. Если же одна из формул Ф1 и Ф2 , к которым применяется логическая связка, имеет нулевой уровень, то она в скобки не заключается.
Теперь, зная буквы-элементарные высказывания, мы никогда не ошибёмся, определяя, является ли формулой запись, содержащая эти буквы, скобки и символы связок, то есть правильно ли построено сложное высказывание. В процессе подобного опознавания мы выделяем части формулы, то есть более короткие формулы, из которых на каждом этапе строится более длинная формула с применением одной связки. Самыми простыми частями формулы являются, разумеется, элементарные высказывания. Значит, логический анализ формулы сводится к выделению всех её частей.
Пример
Пусть элементарными высказываниями являются А, В, С. Записи
¬ A BC и (B)(BA→C)
c формальной точки зрения не являются формулами, так как мы натыкаемся при их разборе на нарушение правил построения формул. (В первом случае отсутствует логическая связка между B и C и отсутствуют скобки вокруг ¬A. Во втором случае формула нулевого уровня В включена в скобки). А записи
(¬ A)(BC) и B((BA)→C)
вполне соответствуют требованиям построения формулы. В процессе анализа формулы (¬ A)(BC) выделяются следующие её части:
( ¬A ) ( BC ) | Связующее действие ¬A B C | Разделённые части (формулы первого уровня) ¬ | Связующее действие A B C | Разделённые части (формулы нулевого уровня) | Все разделённые части являются элементарными высказываниями; разбор закончен.
Соглашения о скобках
Поскольку в построенных по определению формулах оказывается слишком много скобок, иногда и не обязательных для однозначного понимания формулы, математики приняли соглашения о скобках, по которым некоторые из скобок можно опускать. Записи с опущенными скобками восстанавливаются так:
- Если опущены внешние скобки, то они восстанавливаются.
- Если рядом стоят две конъюнкции или дизъюнкции (например, ), то в скобки заключается сначала самая левая часть (т.е. две подформулы со связкой между ними). (Говорят также, что эти связки левоассоциативны.)
- Если рядом стоят разные связки, то скобки расставляются согласно приоритетам: и (от высшего к низшему).
Когда говорят о длине формулы, имеют в виду длину подразумеваемой (восстанавливаемой) формулы, а не сокращённой записи.
Например: запись означает формулу , а её длина равна 12.
Истинностное значение
Интерпретацией (моделью) языка логики высказываний называется функция из множества всех пропозициональных переменных в множество истинностных значений {0, 1}. Основной задачей логики высказываний является установление истинностного значения формулы, если даны истинностные значения входящих в неё переменных. Истинностное значение формулы в таком случае определяется индуктивно (с шагами, которые использовались при построении формулы) с использованием таблиц истинности связок[3].
Оценка отрицания задаётся таблицей:
Значение двуместных логических связок (импликация), (дизъюнкция) и (конъюнкция) определяются так:
Тождественно истинные формулы (тавтологии)
Формула является тождественно истинной, если она истинна при любых значениях входящих в неё переменных (то есть, при любой интерпретации)[4]. Вот несколько широко известных примеров тождественно истинных формул логики высказываний:
1) ;
2) ;
;
Законы поглощения:
1) ;
2) ;
1) ;
2) .
Исчисление высказываний
Одним из возможных вариантов (Гильбертовской) аксиоматизации логики высказываний является следующая система аксиом:
;
;
;
;
;
;
;
;
;
;
.
вместе с единственным правилом:
Теорема корректности исчисления высказываний утверждает, что все перечисленные выше аксиомы являются тавтологиями, а с помощью правила modus ponens из истинных высказываний можно получить только истинные. Доказательство этой теоремы тривиально и сводится к непосредственной проверке. Куда более интересен тот факт, что все остальные тавтологии можно получить из аксиом с помощью правила вывода — это так называемая теорема полноты логики высказываний.
См. также
Примечания
- ↑ 1 2 Кондаков, 1971, статья «Исчисление высказываний»
- ↑ 1 2 Герасимов, 2011, с. 13
- ↑ Герасимов, 2011, с. 17-19
- ↑ Герасимов, 2011, с. 19
Литература
- Герасимов А. С. Курс математической логики и теории вычислимости. — СПб.: Издательство «ЛЕМА», 2011. — 284 с. — ISBN 978-5-98709-292-7
- Кондаков Н. И. Логический словарь / Горский Д. П.. — М.: Наука, 1971. — 656 с.
- Игошин В. И. Математическая логика и теория алгоритмов. — 2-е изд., стереотип.. — М.: Издательский центр «Академия», 2008. — 448 с. — ISBN 978-5-7695-4593-1
Категория:- Логика высказываний
Wikimedia Foundation. 2010.