Пропозициональная логика

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

История

Зарождение пропозициональной логики как формальной дисциплины связано с работами античных философов. Основы силлогистики, заложенные Аристотелем в IV веке до н. э., включали анализ некоторых логических связок, однако полноценное исчисление высказываний было разработано позже. Значительный вклад внесли философы-стоики (III–II века до н. э.), в частности Хрисипп, который систематизировал правила умозаключений, включая модус поненс и модус толленс, и ввёл понятие условного высказывания (импликации).

В Средние века развитие логики продолжилось в схоластике. Учёные, такие как Пётр Абеляр и Уильям Оккам, анализировали логические связки и законы непротиворечия. Однако современный вид пропозициональная логика приобрела лишь в XIX–XX веках. В 1847 году английский математик Джордж Буль опубликовал работу «Математический анализ логики», заложив основы булевой алгебры, которая является алгебраической интерпретацией пропозициональной логики. В 1879 году немецкий логик Готлоб Фреге в работе «Исчисление понятий» впервые построил аксиоматическую систему пропозициональной логики, используя символы для отрицания и импликации. Дальнейшее развитие система получила в работах Бертрана Рассела и Альфреда Норта Уайтхеда в «Principia Mathematica» (1910–1913), где было формализовано исчисление высказываний. В XX веке пропозициональная логика стала основой для создания математической логики, теории алгоритмов и компьютерных наук.

Основные понятия

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

Пропозициональная переменная — это символ, обозначающий простое высказывание, истинностное значение которого может быть либо истиной (True, обозначается 1 или T), либо ложью (False, обозначается 0 или F). Обычно переменные обозначают строчными латинскими буквами: \( p, q, r, s \). Каждая переменная представляет цельное утверждение, например: \( p \) — «Сегодня идёт дождь».

Логические связки (операторы)

Логические связки — это символы, которые соединяют простые высказывания в сложные. Основные связки в классической пропозициональной логике:

• Отрицание (\(\neg\)): унарная связка, меняет истинностное значение высказывания на противоположное. Например, \(\neg p\) означает «не \(p\)».
• Конъюнкция (\(\land\)): бинарная связка, истинна только тогда, когда оба исходных высказывания истинны. Соответствует союзу «и». Например, \(p \land q\) — «\(p\) и \(q\)».
• Дизъюнкция (\(\lor\)): бинарная связка, истинна, если истинно хотя бы одно из высказываний. Соответствует союзу «или» в неисключающем смысле. Например, \(p \lor q\) — «\(p\) или \(q\)».
• Импликация (\(\to\) или \(\Rightarrow\)): бинарная связка, соответствует конструкции «если …, то …». Импликация \(p \to q\) ложна только в случае, когда \(p\) истинно, а \(q\) ложно. В остальных случаях истинна.
• Эквиваленция (\(\leftrightarrow\) или \(\Leftrightarrow\)): бинарная связка, истинна тогда и только тогда, когда оба высказывания имеют одинаковое истинностное значение. Соответствует «тогда и только тогда» или «равносильно».

Истинностные таблицы

Истинностная таблица — это табличное представление, показывающее значение сложного высказывания для всех возможных комбинаций истинностных значений пропозициональных переменных. Например, для конъюнкции таблица имеет вид:

Формула и подформула

Формула пропозициональной логики — это корректно построенное выражение, состоящее из пропозициональных переменных, логических связок и скобок, определяющих порядок операций. Подформулой называется часть формулы, сама являющаяся формулой. Например, в формуле \((p \land q) \to r\) подформулами являются \(p\), \(q\), \(r\), \(p \land q\) и сама формула целиком.

Аксиоматизация и формальные системы

Пропозициональная логика может быть представлена в виде формальной аксиоматической системы. Наиболее известной является система, предложенная в «Principia Mathematica». В ней используются три аксиомы (с учётом замены переменных) и правило вывода modus ponens: из \(A\) и \(A \to B\) выводится \(B\). Однако существуют и другие эквивалентные аксиоматизации. Ключевым результатом является теорема о полноте: классическая пропозициональная логика полна относительно стандартной истинностной семантики — любая тавтология (общезначимая формула) доказуема в системе, и любая доказуемая формула является тавтологией.

Теорема дедукции

Теорема дедукции устанавливает связь между импликацией и выводимостью: если из множества гипотез \(\Gamma\) и формулы \(A\) выводится \(B\), то из \(\Gamma\) выводится \(A \to B\). Этот результат является фундаментальным для построения доказательств.

Семантика

Семантика пропозициональной логики определяет, как интерпретировать формулы. Классическая семантика строится на основе истинностных значений. Функция оценки (интерпретация) \(v\) сопоставляет каждой пропозициональной переменной значение 0 или 1 (ложь или истина). Затем значение любой формулы вычисляется по правилам истинностных таблиц для связок. Формула называется тавтологией (общезначимой), если она истинна при любой оценке; выполнимой, если существует хотя бы одна оценка, при которой она истинна; противоречием, если она ложна при всех оценках.

Логическое следствие

Формула \(B\) является логическим следствием множества формул \(\Gamma\) (обозначается \(\Gamma \vDash B\)), если для любой оценки \(v\), при которой все формулы из \(\Gamma\) истинны, \(B\) также истинна. Это отношение является центральным в логическом выводе.

Основные законы и тождества

Классическая пропозициональная логика подчиняется ряду фундаментальных законов:

• Закон непротиворечия: \(\neg (A \land \neg A)\) (высказывание не может быть одновременно истинным и ложным).
• Закон исключённого третьего: \(A \lor \neg A\) (любое высказывание либо истинно, либо ложно, третьего не дано).
• Закон двойного отрицания: \(\neg \neg A \equiv A\).
• Законы де Моргана: \(\neg (A \land B) \equiv \neg A \lor \neg B\) и \(\neg (A \lor B) \equiv \neg A \land \neg B\).
• Коммутативность: \(A \land B \equiv B \land A\), \(A \lor B \equiv B \lor A\).
• Ассоциативность: \((A \land B) \land C \equiv A \land (B \land C)\), то же для дизъюнкции.
• Дистрибутивность: \(A \land (B \lor C) \equiv (A \land B) \lor (A \land C)\) и \(A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)\).
• Идемпотентность: \(A \land A \equiv A\), \(A \lor A \equiv A\).
• Поглощение: \(A \land (A \lor B) \equiv A\), \(A \lor (A \land B) \equiv A\).
• Свойства констант: \(A \land \text{Истина} \equiv A\), \(A \lor \text{Ложь} \equiv A\), \(A \land \text{Ложь} \equiv \text{Ложь}\), \(A \lor \text{Истина} \equiv \text{Истина}\).

Разрешимость

Пропозициональная логика является разрешимой: существует алгоритм, который для любой формулы за конечное число шагов определяет, является ли она тавтологией, выполнимой или противоречием. Простейший метод — построение полной истинностной таблицы. Однако для сложных формул с большим числом переменных этот метод экспоненциально трудоёмок. Более эффективным является метод редукции (например, алгоритм Дэвиса — Патнема или метод резолюций). Задача определения выполнимости (SAT) является классической NP-полной задачей в теории сложности вычислений.

Применение

Математика

Пропозициональная логика является основой для построения математических доказательств, формальных теорий и аксиоматизаций. Она используется для анализа структуры теорем и лемм.

Компьютерные науки

• Цифровые схемы: Логические элементы (И, ИЛИ, НЕ) реализуют операции пропозициональной логики и являются базой для построения процессоров и микросхем.
• Программирование: Условные операторы, циклы и булевы выражения в языках программирования основаны на пропозициональной логике.
• Искусственный интеллект: Логические системы вывода, автоматическое доказательство теорем, проверка моделей (model checking) и логическое программирование (например, язык Prolog) используют пропозициональную логику или её расширения.
• Базы данных: Использование логических запросов (например, SQL-условия WHERE).

Философия

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

Критика и ограничения

Классическая пропозициональная логика имеет ряд ограничений. Она не учитывает внутреннюю структуру высказываний, что не позволяет выражать кванторы («для всех», «существует») и отношения между объектами. Для этого используется логика предикатов. Кроме того, классическая логика основывается на принципе двузначности (истина/ложь), который подвергается критике в контексте интуиционистской и многозначных логик. В интуиционистской логике, например, закон исключённого третьего не принимается безоговорочно, а истинность может рассматриваться как конструктивная доказуемость.

Источники

1. Горский Д. П. Логика. — М.: Учпедгиз, 1961.
2. Мендельсон Э. Введение в математическую логику. — М.: Наука, 1984.
3. Новиков П. С. Элементы математической логики. — М.: Наука, 1973.
4. Черч А. Введение в математическую логику. — М.: Издательство иностранной литературы, 1960.
5. Boolos G., Burgess J. P., Jeffrey R. C. Computability and Logic. — Cambridge University Press, 2007.