Исчисление высказываний
Исчисление высказываний — это формальная система, изучающая логические связи между простыми (атомарными) высказываниями, истинностное значение которых (истина или ложь) считается заданным, и построение из них сложных высказываний с помощью логических связок (операций). В отличие от логики предикатов, исчисление высказываний не учитывает внутреннюю структуру простых высказываний (субъект, предикат, кванторы), оперируя только их истинностными значениями. Является фундаментальным разделом математической логики и лежит в основе логического программирования, цифровой схемотехники и теории доказательств.
История
Истоки исчисления высказываний восходят к античной логике, в первую очередь к трудам Аристотеля (IV век до н. э.), который систематизировал силлогистику — учение о формах умозаключений, основанных на категорических высказываниях. Однако систематическое изучение пропозициональных связок (конъюнкции, дизъюнкции, импликации) началось в эллинистический период в школе стоиков (Хрисипп, III век до н. э.). Стоики разработали первую формальную систему пропозициональной логики, включавшую правила вывода и таблицы истинности для основных связок.
В Средние века логика развивалась в рамках схоластики (Петр Абеляр, Уильям Оккам), но существенного прогресса в формализации исчисления высказываний не произошло. Современный вид исчисление высказываний приобрело в XIX — начале XX века. Основополагающий вклад внесли:
- Джордж Буль (1854) — в работе «Законы мысли» установил аналогию между логическими операциями и алгебраическими законами, заложив основы булевой алгебры.
- Готлоб Фреге (1879) — в «Исчислении понятий» впервые построил аксиоматическую систему для логики высказываний и логики предикатов, введя современные обозначения для импликации и отрицания.
- Бертран Рассел и Альфред Норт Уайтхед (1910—1913) — в «Principia Mathematica» представили полную аксиоматизацию исчисления высказываний в рамках более общей логической системы.
- Давид Гильберт и Вильгельм Аккерман (1928) — в книге «Основы теоретической логики» дали современное изложение исчисления высказываний, включая понятия формальной системы, выводимости и разрешимости.
В XX веке исчисление высказываний стало основой для создания цифровых электронных схем (Клод Шеннон, 1937), а также для развития логического программирования (язык Пролог, 1972).
Основные понятия
Атомарные высказывания и пропозициональные переменные
Атомарное высказывание — это простейшее высказывание, которое не может быть разложено на более простые. В исчислении высказываний атомарные высказывания обозначаются пропозициональными переменными (обычно латинскими буквами: \( p, q, r, s, \dots \)). Каждая переменная может принимать одно из двух истинностных значений: истина (обозначается 1, T или \(\top\)) или ложь (0, F или \(\bot\)).
Логические связки (операции)
Из атомарных высказываний с помощью логических связок строятся сложные (составные) высказывания. Основные бинарные (двухместные) и унарные (одноместные) связки:
| Связка | Название | Обозначение | Чтение | Истинностное условие |
|---|---|---|---|---|
| \(\neg\) | Отрицание | \(\neg p\) | «не \(p\)» | Истинно, если \(p\) ложно |
| \(\land\) | Конъюнкция | \(p \land q\) | «\(p\) и \(q\)» | Истинно, если оба истинны |
| \(\lor\) | Дизъюнкция | \(p \lor q\) | «\(p\) или \(q\)» | Истинно, если хотя бы одно истинно |
| \(\rightarrow\) | Импликация | \(p \rightarrow q\) | «если \(p\), то \(q\)» | Ложно только если \(p\) истинно, а \(q\) ложно |
| \(\leftrightarrow\) | Эквиваленция | \(p \leftrightarrow q\) | «\(p\) тогда и только тогда, когда \(q\)» | Истинно, если значения совпадают |
Реже используются штрих Шеффера (антиконъюнкция, \(p \mid q\)) и стрелка Пирса (антидизъюнкция, \(p \downarrow q\)), которые являются функционально полными (позволяют выразить все остальные связки).
Формулы
Формулы исчисления высказываний строятся индуктивно:
- Любая пропозициональная переменная есть формула.
- Если \(A\) — формула, то \(\neg A\) — формула.
- Если \(A\) и \(B\) — формулы, то \((A \land B)\), \((A \lor B)\), \((A \rightarrow B)\), \((A \leftrightarrow B)\) — формулы.
- Ничто иное формулой не является.
Скобки используются для указания порядка операций; для упрощения приняты приоритеты: \(\neg\) > \(\land\) > \(\lor\) > \(\rightarrow\) > \(\leftrightarrow\).
Семантика (интерпретация)
Семантика исчисления высказываний определяет истинностное значение любой формулы при заданном наборе значений пропозициональных переменных (интерпретации). Основной метод — таблицы истинности.
Пример таблицы истинности для импликации \(p \rightarrow q\):
| \(p\) | \(q\) | \(p \rightarrow q\) |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Формула называется:
- Тождественно истинной (тавтологией), если она истинна при всех интерпретациях (например, \(p \lor \neg p\)).
- Тождественно ложной (противоречием), если она ложна при всех интерпретациях (например, \(p \land \neg p\)).
- Выполнимой, если существует хотя бы одна интерпретация, при которой она истинна.
Понятие логического следования: формула \(B\) является логическим следствием множества формул \(\Gamma\) (обозначается \(\Gamma \models B\)), если при любой интерпретации, в которой все формулы из \(\Gamma\) истинны, \(B\) также истинна.
Синтаксис и аксиоматизация
Исчисление высказываний может быть задано как формальная система, состоящая из аксиом и правил вывода. Одна из классических аксиоматизаций (система Гильберта) использует три схемы аксиом и одно правило вывода — modus ponens (MP: из \(A\) и \(A \rightarrow B\) выводится \(B\)).
Схемы аксиом (для любых формул \(A, B, C\)):
- \(A \rightarrow (B \rightarrow A)\)
- \((A \rightarrow (B \rightarrow C)) \rightarrow ((A \rightarrow B) \rightarrow (A \rightarrow C))\)
- \((\neg B \rightarrow \neg A) \rightarrow (A \rightarrow B)\)
Выводом формулы \(B\) из множества гипотез \(\Gamma\) называется конечная последовательность формул, каждая из которых является либо аксиомой, либо гипотезой из \(\Gamma\), либо получена из предыдущих по правилу MP. Формула \(B\) называется теоремой (обозначается \(\vdash B\)), если она выводима из пустого множества гипотез.
Теорема о дедукции
Важное метаутверждение: если из множества гипотез \(\Gamma \cup \{A\}\) выводима формула \(B\), то из \(\Gamma\) выводима формула \(A \rightarrow B\). Эта теорема связывает понятия выводимости и импликации.
Свойства
Исчисление высказываний обладает рядом фундаментальных свойств, доказанных в рамках метатеории:
- Непротиворечивость: не существует формулы \(A\) такой, что одновременно выводимы \(A\) и \(\neg A\).
- Полнота: любая тождественно истинная формула (тавтология) является теоремой системы. Иными словами, \(\models A\) влечёт \(\vdash A\).
- Разрешимость: существует алгоритм, который для любой формулы за конечное число шагов определяет, является ли она тавтологией (например, метод таблиц истинности или метод резолюций). Это отличает исчисление высказываний от логики предикатов, которая неразрешима в общем случае.
- Компактность: если множество формул \(\Gamma\) невыполнимо, то существует его конечное подмножество, которое также невыполнимо.
Применение
Цифровая схемотехника
Исчисление высказываний является математической основой булевой алгебры, которая применяется для проектирования и анализа цифровых логических схем. Логические элементы (И, ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ) реализуют соответствующие пропозициональные операции. Минимизация логических функций (например, с помощью карт Карно) позволяет оптимизировать схемы.
Логическое программирование
В языке Пролог и других системах логического программирования программы записываются в виде множества дизъюнктов (клаузул), которые являются формулами исчисления высказываний или логики предикатов. Вычисление ответа на запрос сводится к доказательству теоремы методом резолюций.
Теория доказательств
Исчисление высказываний служит базовой моделью для изучения формальных доказательств. На его основе строятся более сложные логические системы (интуиционистская логика, модальная логика, временная логика).
Искусственный интеллект
В системах, основанных на знаниях, исчисление высказываний используется для представления фактов и правил вывода. Алгоритмы SAT-решателей (проверка выполнимости булевых формул) применяются в планировании, верификации программ и криптоанализе.
Критика и ограничения
Основное ограничение исчисления высказываний — неспособность выражать высказывания о свойствах объектов и отношениях между ними (например, «все люди смертны»). Для этого требуется логика предикатов, которая вводит кванторы и предикаты. Кроме того, исчисление высказываний не учитывает модальности (необходимость, возможность) и временные аспекты.
В философии логики обсуждается вопрос о соответствии классической двузначной логики (истина/ложь) реальному мышлению, где возможны неопределённые или нечёткие высказывания. Это привело к развитию многозначных и нечётких логик.
Источники
- Гильберт Д., Аккерман В. Основы теоретической логики. — М.: Иностранная литература, 1947.
- Клини С. К. Математическая логика. — М.: Мир, 1973.
- Мендельсон Э. Введение в математическую логику. — М.: Наука, 1976.
- Чёрч А. Введение в математическую логику. — М.: Иностранная литература, 1960.
- Шеннон К. Работы по теории информации и кибернетике. — М.: Иностранная литература, 1963.
BFOmetr — база данных и аналитика по компаниям России.
На главную BFOmetr →