Высказывание — утверждение, которое может быть истинным или ложным, но не одновременно. Логика высказываний (пропозициональная логика) изучает составные высказывания, построенные из простых с помощью логических связок: отрицание (НЕ), конъюнкция (И), дизъюнкция (ИЛИ), импликация (ЕСЛИ...ТО), эквиваленция (ТОГДА И ТОЛЬКО ТОГДА). Формализована Джорджем Булем в 1854 году.
Представьте выключатель света: он либо включен (истина), либо выключен (ложь). Два выключателя можно соединить последовательно (И — свет горит, только если оба включены) или параллельно (ИЛИ — свет горит, если хотя бы один включен). Логика высказываний — это алгебра переключателей, на которой построены компьютеры.
Основные логические операции
Отрицание (¬A): Переворачивает истинность. Если A = "идёт дождь" (истина), то ¬A = "не идёт дождь" (ложь). Таблица истинности: A=1 → ¬A=0, A=0 → ¬A=1.
Конъюнкция (A ∧ B): Истинна, только если оба высказывания истинны. A = "чётное число", B = "больше 5". Число 8 удовлетворяет A ∧ B, число 3 — нет. Таблица: 1∧1=1, остальные комбинации дают 0.
Дизъюнкция (A ∨ B): Истинна, если хотя бы одно высказывание истинно. "Студент сдал экзамен ИЛИ получил автомат" — достаточно одного условия. Таблица: 0∨0=0, остальные комбинации дают 1.
Импликация (A → B): "ЕСЛИ A, ТО B". Ложна только когда A истинно, а B ложно. "Если дождь, то асфальт мокрый" — ложно, если дождь идёт, но асфальт сухой. Таблица: 1→0=0, остальные комбинации дают 1. Парадокс: из лжи следует всё (0→1=1, 0→0=1).
Эквиваленция (A ↔ B): "A ТОГДА И ТОЛЬКО ТОГДА, КОГДА B". Истинна, когда A и B одновременно истинны или одновременно ложны. "Треугольник равносторонний ↔ все углы по 60°". Таблица: 1↔1=1, 0↔0=1, 1↔0=0, 0↔1=0.
Таблицы истинности
Таблица истинности — метод анализа сложных высказываний. Строки — все возможные комбинации значений переменных (для n переменных — 2^n строк), столбцы — промежуточные выражения и финальный результат.
Пример: (A ∨ B) → C. Три переменные — 8 строк. Вычисляем A ∨ B для каждой комбинации, затем результат подставляем в импликацию.
Таблицы используют для проверки эквивалентности формул (тавтологии): если столбцы совпадают, формулы равносильны. Например, A → B эквивалентно ¬A ∨ B (закон исключения импликации).
Законы логики высказываний
Законы де Моргана: ¬(A ∧ B) = ¬A ∨ ¬B, ¬(A ∨ B) = ¬A ∧ ¬B. "Неверно, что Петя и Маша пришли" = "Петя не пришёл ИЛИ Маша не пришла".
Закон исключённого третьего: A ∨ ¬A = 1 (всегда истина). Утверждение либо истинно, либо ложно — третьего не дано. Интуиционистская логика отвергает этот закон для бесконечных объектов.
Закон противоречия: A ∧ ¬A = 0 (всегда ложь). Утверждение не может быть одновременно истинным и ложным.
Дистрибутивность: A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C), A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C). Работает как раскрытие скобок в алгебре.
Нормальные формы
Дизъюнктивная нормальная форма (ДНФ): Дизъюнкция конъюнкций. Пример: (A ∧ B) ∨ (¬A ∧ C). Любую формулу можно привести к ДНФ через таблицу истинности: берём строки с результатом 1, для каждой составляем конъюнкцию переменных (прямых или отрицаний), объединяем дизъюнкцией.
Конъюнктивная нормальная форма (КНФ): Конъюнкция дизъюнкций. Пример: (A ∨ B) ∧ (¬A ∨ C). Получается из ДНФ через законы де Моргана или из таблицы истинности (строки с результатом 0).
КНФ используется в SAT-решателях (проверка выполнимости формулы) — основа верификации микросхем и планирования в AI.
Применение в цифровой электронике
Клод Шеннон в 1938 году в магистерской диссертации показал: булева алгебра описывает релейные схемы. Это стало основой цифровых компьютеров. Логические элементы (вентили): НЕ (инвертор), И (AND), ИЛИ (OR), ИСКЛЮЧАЮЩЕЕ ИЛИ (XOR), И-НЕ (NAND), ИЛИ-НЕ (NOR).
Универсальные элементы: NAND и NOR. Из NAND можно построить любой другой элемент: НЕ (входы соединены), И (NAND + НЕ), ИЛИ (по закону де Моргана). Процессоры Intel состоят из миллиардов транзисторов, реализующих NAND.
Пример схемы: Полусумматор складывает два бита. Сумма S = A ⊕ B (XOR), перенос C = A ∧ B (AND). Комбинируя полусумматоры, строят сумматоры для 32-битных чисел.
Применение в программировании
Условные операторы (if, while) используют логические выражения. В языке C: 0 = ложь, ненулевое = истина. Операторы: && (И), || (ИЛИ), ! (НЕ). Ленивые вычисления: в A && B, если A ложно, B не вычисляется (короткое замыкание).
Пример: if (x != 0 && y / x > 5) — безопасно, так как деление на ноль не выполнится (x != 0 проверяется первым).
Битовые операции (&, |, ^, ~) применяют логику к отдельным битам числа. Используются в криптографии, сжатии данных, работе с флагами.
Логические парадоксы
Парадокс лжеца: "Это утверждение ложно". Если истинно → ложно, если ложно → истинно. Парадокс показывает границы формальной логики: не всякая фраза на естественном языке — корректное высказывание.
Парадокс Рассела: Множество всех множеств, не содержащих себя. Содержит ли оно себя? Привёл к кризису оснований математики в начале XX века, решён аксиоматической теорией множеств (Цермело-Френкель, 1908-1922).