Логика высказываний
Логика высказываний (также пропозициональная логика, исчисление высказываний) — это раздел формальной логики, изучающий логические связи между простыми высказываниями, рассматриваемыми как неделимые атомарные единицы, и построение из них сложных высказываний с помощью логических операций (связок). В отличие от логики предикатов, логика высказываний не учитывает внутреннюю структуру простых высказываний (субъектно-предикатную структуру), а оперирует только их истинностными значениями («истина» или «ложь»). Она является фундаментальной основой для математической логики, теории алгоритмов, цифровой схемотехники и программирования.
История
Истоки логики высказываний восходят к античной философии. Аристотель в «Органоне» заложил основы силлогистики, которая, однако, оперировала терминами, а не высказываниями. Стоики (Хрисипп, III век до н. э.) разработали первую систему пропозициональной логики, изучая условные и разделительные умозаключения.
В Средние века схоласты, такие как Пьер Абеляр и Уильям Оккам, развивали теорию следования (consequentiae). Однако современный вид логика высказываний приобрела в XIX—XX веках благодаря работам Джорджа Буля («Исследование законов мысли», 1854), который алгебраизировал логику, создав булеву алгебру. Дальнейшее развитие связано с именами Готлоба Фреге («Begriffsschrift», 1879), введшего современную нотацию и аксиоматизацию, Бертрана Рассела и Альфреда Норта Уайтхеда («Principia Mathematica», 1910—1913), а также Давида Гильберта, сформулировавшего метатеоретические проблемы исчисления высказываний. В 1921 году Эмиль Пост и независимо от него Людвиг Витгенштейн доказали полноту и непротиворечивость пропозициональной логики.
Язык логики высказываний
Язык логики высказываний строится на основе формального алфавита и правил построения формул.
Алфавит
Алфавит включает три категории символов:
- Пропозициональные переменные: обычно обозначаются строчными латинскими буквами (p, q, r, s, p1, p2, ...). Каждая переменная представляет собой простое (атомарное) высказывание, которое может быть истинным или ложным.
- Логические связки (операторы): символы, обозначающие операции над высказываниями.
- Вспомогательные символы: скобки (левая и правая) для указания порядка операций.
Логические связки
Основные логические связки (в порядке убывания приоритета, если не заданы скобки):
| Название | Символ (распространённые варианты) | Читается как | Определение (таблица истинности: A, B — операнды) | |
|---|---|---|---|---|
| Отрицание | ¬, ~, ! | «не A», «неверно, что A» | Истинно, когда A ложно; ложно, когда A истинно. | |
| Конъюнкция | ∧, &, · | «A и B» | Истинно только тогда, когда оба операнда истинны. | |
| Дизъюнкция | ∨, +, \ | «A или B» (нестрогая) | Ложно только тогда, когда оба операнда ложны. | |
| Импликация | →, ⇒, ⊃ | «если A, то B», «A влечёт B» | Ложно только в случае, когда A истинно, а B ложно. | |
| Эквиваленция | ↔, ≡, ⇔ | «A тогда и только тогда, когда B» | Истинно, когда значения A и B совпадают. |
Существуют также производные связки, такие как «исключающее ИЛИ» (XOR, ⊕), «штрих Шеффера» (NAND, |) и «стрелка Пирса» (NOR, ↓).
Формулы
Правильно построенные формулы (ППФ) определяются рекурсивно:
- Любая пропозициональная переменная является формулой.
- Если A — формула, то ¬A — формула.
- Если A и B — формулы, то (A ∧ B), (A ∨ B), (A → B), (A ↔ B) — формулы.
- Ничто иное формулой не является.
Семантика и таблицы истинности
Семантика логики высказываний основана на приписывании формулам истинностных значений. Функция интерпретации (оценки) сопоставляет каждой пропозициональной переменной одно из двух значений: 1 (истина) или 0 (ложь). Истинностное значение сложной формулы вычисляется по таблицам истинности для каждой связки.
Таблица истинности для всех основных связок (A и B — пропозициональные переменные):
| A | B | ¬A | A ∧ B | A ∨ B | A → B | A ↔ B |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 |
Законы и тавтологии
Формула, которая принимает значение «истина» при любой интерпретации входящих в неё переменных, называется тавтологией (или логическим законом). Основные законы логики высказываний:
- Закон тождества: p → p
- Закон непротиворечия: ¬(p ∧ ¬p)
- Закон исключённого третьего: p ∨ ¬p
- Закон двойного отрицания: ¬¬p ≡ p
- Законы де Моргана: ¬(p ∧ q) ≡ ¬p ∨ ¬q; ¬(p ∨ q) ≡ ¬p ∧ ¬q
- Коммутативность: p ∧ q ≡ q ∧ p; p ∨ q ≡ q ∨ p
- Ассоциативность: (p ∧ q) ∧ r ≡ p ∧ (q ∧ r); (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
- Дистрибутивность: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r); p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
- Законы поглощения: p ∧ (p ∨ q) ≡ p; p ∨ (p ∧ q) ≡ p
- Материальная импликация: p → q ≡ ¬p ∨ q
- Транзитивность импликации: ((p → q) ∧ (q → r)) → (p → r)
Методы доказательства
В логике высказываний существует несколько методов установления общезначимости (тавтологичности) формулы или логического следования.
Таблицы истинности
Наиболее прямой, но громоздкий метод. Для формулы с n переменными строится таблица из 2^n строк. Если во всех строках формула принимает значение 1, она является тавтологией.
Алгебраические преобразования
Использование законов логики (см. выше) для упрощения формулы до вида 1 (истина). Этот метод основан на понятии эквивалентности формул.
Метод резолюций
Эффективный алгоритм автоматического доказательства теорем. Формула приводится к конъюнктивной нормальной форме (КНФ), затем применяется правило резолюции: из дизъюнктов (A ∨ C) и (B ∨ ¬C) выводится новый дизъюнкт (A ∨ B). Если в результате выводится пустой дизъюнкт (ложь), исходная формула является противоречием. Для доказательства тавтологии используется доказательство от противного: формула отрицается, и если её отрицание приводит к пустому дизъюнкту, исходная формула — тавтология.
Семантические таблицы (метод аналитических таблиц)
Графический метод, при котором формула разбивается на подформулы по правилам для каждой связки. Если все ветви таблицы закрываются (содержат противоречие вида A и ¬A), исходная формула является тавтологией.
Применение
- Математика: Логика высказываний является базой для построения аксиоматических теорий и доказательства теорем.
- Программирование: Логические выражения (if-else, while, условия циклов) напрямую реализуют операции логики высказываний. Компиляторы используют её для оптимизации кода.
- Цифровая схемотехника: Булева алгебра лежит в основе проектирования логических вентилей (AND, OR, NOT, NAND, NOR, XOR), из которых строятся все цифровые микросхемы — от простых сумматоров до микропроцессоров.
- Искусственный интеллект: Системы логического вывода, экспертные системы и планировщики задач часто используют пропозициональную логику для представления знаний и автоматического вывода решений.
- Базы данных: Реляционная алгебра и SQL-запросы (условия WHERE, JOIN) основаны на логике высказываний.
Связь с другими логиками
Логика высказываний является подсистемой более мощных логик:
- Логика предикатов (первого порядка): Добавляет кванторы (∀ — для всех, ∃ — существует) и предикаты (отношения между объектами), что позволяет выражать более сложные утверждения, чем в пропозициональной логике.
- Модальные логики: Вводят модальные операторы (необходимость □, возможность ◇, знание, время), расширяя выразительные возможности.
- Многозначные логики: Отказываются от принципа бивалентности (только два значения истинности), допуская три и более значений (например, «истина», «ложь», «неопределённо»).
Критика и ограничения
Основное ограничение логики высказываний — её неспособность анализировать внутреннюю структуру высказываний. Например, утверждения «Все люди смертны» и «Сократ — человек» не могут быть соединены в пропозициональной логике для вывода «Сократ смертен», так как они рассматриваются как атомарные символы без внутренней связи. Для этого требуется логика предикатов. Кроме того, классическая логика высказываний является двузначной, что не позволяет адекватно моделировать неопределённость или неполноту информации.
Источники
- Гильберт Д., Аккерман В. Основы теоретической логики. — М.: Иностранная литература, 1947.
- Клини С. К. Математическая логика. — М.: Мир, 1973.
- Мендельсон Э. Введение в математическую логику. — М.: Наука, 1976.
- Чёрч А. Введение в математическую логику. — М.: Иностранная литература, 1960.
- Новиков П. С. Элементы математической логики. — М.: Наука, 1973.
- Boolos G., Burgess J., Jeffrey R. Computability and Logic. — Cambridge University Press, 2007.
BFOmetr — база данных и аналитика по компаниям России.
На главную BFOmetr →