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

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

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

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

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

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

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

• логические знаки (логические союзы):  — знак отрицания,  — знак конъюнкции,  — знак дизъюнкции,  — знак строгой дизъюнкции,  — знак импликации,  — знак эквивалентности;

• технические знаки:  — левая скобка,  — правая скобка.

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

Пропозициональные переменные

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

Пропозициональные формулы

Роль структурных образований, аналогичных элементарным и сложным высказываниям, играют в этом языке формулы. Пропозициональная формула — конечная последовательность знаков алфавита, построенная по изложенным ниже правилам и образующая законченное выражение языка логики высказываний^[1]. Заглавные латинские буквы , и др., которые употребляются в определении формулы, принадлежат не языку логики высказываний, а его метаязыку, то есть языку, который используется для описания самого языка логики высказываний. Содержащие метабуквы выражения , и др. — не пропозициональные формулы, а схемы формул. Например, выражение есть схема формул , и др^[1].

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

1. пропозициональная переменная есть формула;
2. если  — произвольная формула, то  — тоже формула;
3. если и  — произвольные формулы, то , , , и  — тоже формулы;

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

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

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

Соглашения о скобках

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

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

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

Например: запись означает формулу , а её длина равна 12.

Интерпретация языка логики высказываний

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

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

,

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

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

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

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

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

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

1) ;

2) ;

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

;

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

1) ;

2) ;

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

1) ;

2) .

Исчисление высказываний

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

;

;

;

;

;

;

;

;

;

;

.

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

(Modus ponens)

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

См. также

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

Примечания

Литература

• Кондаков Н. И. Логический словарь / Горский Д. П.. — М.: Наука, 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.

Логика   Математика