Логика высказываний
1. Сущность и предмет логики высказываний
Логика высказываний (или пропозициональная логика) — раздел математической логики,
изучающий высказывания, которые могут быть только истинными или ложными,
и законы, по которым из одних высказываний можно логически вывести другие.
Цель — установить формальные отношения следования между высказываниями.
2. Основные термины и обозначения
| Термин | Обозначение | Формальное определение | Простое объяснение |
|---|---|---|---|
| Высказывание (формула) | $p, q, r, \dots$ | предложение, имеющее определённое значение истинности $v(p)\in{0,1}$ | утверждение, которое либо правда, либо нет |
| Атом (атомарное высказывание) | $p, q, r$ | неделимая логическая единица, не содержащая связок | «идёт дождь», «2+2=4» |
| Составная формула | $(p \land q)$ | формула, содержащая логические связки | комбинация простых высказываний |
| Интерпретация | $I$ | отображение атомов в ${0,1}$ | присвоение каждому высказыванию истины или лжи |
| Модель | $I \vDash \varphi$ | интерпретация, при которой $\varphi$ истинна | конкретный случай, когда формула “работает” |
| Синтаксис | — | правила построения правильных формул | как грамматика в языке |
| Семантика | — | значения формул при интерпретациях | смысл формул |
| Теорема (доказуемая формула) | $\vdash \varphi$ | формула, выводимая по правилам исчисления | то, что можно доказать |
| Следствие (логическое) | $\vDash \varphi$ | формула, истинная при всех моделях посылок | то, что всегда следует из других утверждений |
3. Логические связки и их смысл
| Название | Символ | Формула | Таблица истинности | Комментарий |
|---|---|---|---|---|
| Отрицание | $\lnot p$ | $1 \to 0, 0 \to 1$ | меняет значение на противоположное | “не p” |
| Конъюнкция | $p \land q$ | $(1,1)\to1$, иначе 0 | оба должны быть истинны | “и” |
| Дизъюнкция | $p \lor q$ | $(0,0)\to0$, иначе 1 | хотя бы одно истинно | “или” |
| Импликация | $p \to q$ | $(1,0)\to0$, иначе 1 | ложна только когда $p$ истина, а $q$ — ложь | “если p, то q” |
| Эквиваленция | $p \leftrightarrow q$ | истина при $p=q$ | совпадение значений | “p тогда и только тогда, когда q” |
| Исключающее ИЛИ (XOR) | $p \oplus q$ | истина при $p\neq q$ | ровно одно истинно |
4. Виды формул
| Тип | Условие | Пример | Смысл |
|---|---|---|---|
| Тавтология | истинна при любой интерпретации | $p \lor \lnot p$ | всегда истина |
| Противоречие | ложна при любой интерпретации | $p \land \lnot p$ | всегда ложь |
| Контингентная | истинна не при всех интерпретациях | $p \to q$ | иногда истина, иногда ложь |
5. Основные законы логики
| Название | Формула | Интерпретация |
|---|---|---|
| Двойное отрицание | $\lnot(\lnot p) \equiv p$ | отрицание отрицания |
| Де Моргана | $\lnot(p \land q) \equiv \lnot p \lor \lnot q$; $\lnot(p \lor q) \equiv \lnot p \land \lnot q$ | “не (и)” превращается в “или” и наоборот |
| Коммутативность | $p \lor q \equiv q \lor p$, $p \land q \equiv q \land p$ | порядок не важен |
| Ассоциативность | $(p \lor q) \lor r \equiv p \lor (q \lor r)$ | скобки можно менять |
| Дистрибутивность | $p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$ | распределение “и” через “или” |
| Импликация через дизъюнкцию | $p \to q \equiv \lnot p \lor q$ | “если–то” = “не p или q” |
6. Виды рассуждений (по форме вывода)
Дедуктивные рассуждения
От общего к частному.
Если посылки истинны, заключение истинно обязательно.
Пример:
Все люди смертны. Сократ — человек.
⇒ Сократ смертен.
Форма:
\[
(p \to q),\; p \;\vdash\; q
\]
(Modus Ponens)
Формальная идея: при истинных посылках результат обязателен → доказываются.
Индуктивные рассуждения
От частных случаев к общему выводу.
Не гарантирует истины, лишь вероятность.
Пример:
Солнце всходит каждый день → вероятно, завтра тоже взойдёт.
Форма:
\[
p_1, p_2, \dots, p_n \;\Rightarrow\; \text{обобщение } Q
\]
Формальная идея: вероятностное следование → не доказывается строго, а обосновывается.
Абдуктивные рассуждения
От следствия к гипотетической причине.
Пример:
Земля мокрая → вероятно, шёл дождь.
Форма:
\[
(q),\; (p \to q) \;\Rightarrow\; p?
\]
Формальная идея: предположение причины → требует проверки (не доказательство).
7. Формальные отношения
| Символ | Читается как | Смысл |
|---|---|---|
| $\vdash$ | «доказуемо» | синтаксическое следование — можно вывести формально |
| $\vDash$ | «логически следует» | семантическое следование — истинно при всех интерпретациях |
| $\equiv$ | «эквивалентно» | формулы равносильны по значению |
8. Правила вывода (Inference Rules)
| № | Название (сокр.) | Формальная схема | Короткое объяснение |
|---|---|---|---|
| 1 | Modus Ponens (→E) | $\,\; \varphi\to\psi,\quad \varphi \;\vdash\; \psi \,$ | Если из $\varphi$ следует $\psi$, и $\varphi$ истинно, то $\psi$ истинно. (основное правило) |
| 2 | Modus Tollens | $\,\; \varphi\to\psi,\quad \lnot\psi \;\vdash\; \lnot\varphi \,$ | Если из $\varphi$ следует $\psi$, но $\psi$ ложно, то $\varphi$ ложно. (контрапозиция на практике) |
| 3 | Введение конъюнкции (∧I) | $\,\; \varphi,\quad \psi \;\vdash\; \varphi\land\psi \,$ | Если обе формулы истинны, можно соединить их через «и». |
| 4 | Элиминация конъюнкции (∧E) | $\,\; \varphi\land\psi \;\vdash\; \varphi \quad$ и $\quad \varphi\land\psi \;\vdash\; \psi$ | Из «$\varphi$ и $\psi$» можно выделить любую часть. |
| 5 | Введение дизъюнкции (∨I) | $\,\; \varphi \;\vdash\; \varphi\lor\psi \,$ | Если $\varphi$ истинно, то «$\varphi$ или $\psi$» тоже истинно. |
| 6 | Устранение дизъюнкции (∨E) | $\,\; \varphi\lor\psi,\; [\varphi\vdash\chi],\; [\psi\vdash\chi] \;\vdash\; \chi \,$ | Если из каждого дизъюнкта следует одна и та же $\chi$, то из дизъюнкции следует $\chi$. (разбора по случаям) |
| 7 | Дизъюнктивный силлогизм | $\,\; \varphi\lor\psi,\quad \lnot\varphi \;\vdash\; \psi \,$ | Частный случай: если одно исключено, то истинно другое. |
| 8 | Введение отрицания (¬I) | $\,\; [\varphi]\vdash\bot \;\Rightarrow\; \lnot\varphi \,$ | Если допущение $\varphi$ ведёт к противоречию ($\bot$), то $\varphi$ ложно. (доказательство от противного) |
| 9 | Из противоречия (⊥E) | $\,\; \bot \;\vdash\; \chi \,$ | Из противоречия можно вывести любую формулу (ex falso quodlibet). |
| 10 | Введение импликации (→I) | $\,\; [\varphi]\vdash\psi \;\Rightarrow\; \varphi\to\psi \,$ | Если при допущении $\varphi$ получается $\psi$, то можно вывести $\varphi\to\psi$. (правило дедукции) |
| 11 | Устранение импликации (→E) | (то же, что Modus Ponens) $\,\; \varphi\to\psi,\; \varphi \;\vdash\; \psi \,$ | Аналогично пункту 1 — использование импликации. |
| 12 | Гипотетический силлогизм | $\,\; \varphi\to\psi,\; \psi\to\chi \;\vdash\; \varphi\to\chi \,$ | Цепочка: если $\varphi\Rightarrow\psi$ и $\psi\Rightarrow\chi$, то $\varphi\Rightarrow\chi$. |
| 13 | Введение эквиваленции (↔I) | $\,\; \varphi\to\psi,\; \psi\to\varphi \;\vdash\; \varphi\leftrightarrow\psi \,$ | Если две формулы взаимно следуют друг из друга, они эквивалентны. |
| 14 | Элиминация эквиваленции (↔E) | $\,\; \varphi\leftrightarrow\psi \;\vdash\; (\varphi\to\psi)\land(\psi\to\varphi) \,$ | Эквиваленция распадается на две импликации. |
| 15 | Резолюция | $\,\; (\varphi\lor p),\; (\lnot p\lor\psi) \;\vdash\; (\varphi\lor\psi) \,$ | Устраняет противоположные литералы $p$ и $\lnot p$ — основной шаг в алгоритме резолюции (SAT). |
9. Корректность и полнота
| Свойство | Формально | Смысл |
|---|---|---|
| Корректность (Soundness) | Если $\vdash \varphi$, то $\vDash \varphi$ | всё доказуемое — истинно |
| Полнота (Completeness) | Если $\vDash \varphi$, то $\vdash \varphi$ | всё истинное можно доказать |
| Непротиворечивость | невозможно, что $\vdash \varphi$ и $\vdash \lnot \varphi$ | нельзя доказать и утверждение, и его отрицание |
10. Пример формального вывода (доказательство)
Доказать:
из $(p \to q)$ и $p$ следует $q$.
- $(p \to q)$ — посылка
- $p$ — посылка
- Применяем modus ponens
⇒ $q$
\[
(p \to q), p \vdash q
\]
Семантически: при всех интерпретациях, где $p$ и $p \to q$ истинны, $q$ истинно.
\[
(p \to q), p \vDash q
\]
11. Силлогизмы
Силлогизм — рассуждение из двух посылок и заключения.
Общая схема:
\[
\begin{cases}
A \to B, \\
B \to C \\
\hline
A \to C
\end{cases}
\]
Пример:
Если человек смертен, а Сократ — человек,
то Сократ смертен.
12. Проверка формул на истинность
- Таблицей истинности — перебор всех комбинаций значений.
- Приведение к нормальной форме (КНФ или ДНФ).
- Метод резолюций — опровержение отрицания цели.
13. Логическая структура доказательств
- Посылки — исходные формулы (аксиомы, гипотезы).
- Правила вывода — допустимые преобразования.
- Заключение — формула, выведенная по правилам.
- Доказательство — последовательность формул, где каждая либо посылка, либо выведена из предыдущих по правилу.
14. Итог
| Понятие | Что это | Как понять |
|---|---|---|
| Атом | элементарное высказывание | «кирпичик» формулы |
| Формула | комбинация атомов и связок | логическая конструкция |
| Тавтология | всегда истина | проверяется таблицей |
| Следование | $\vDash$ | смысловое отношение |
| Выводимость | $\vdash$ | формальная процедура |
| Корректность | всё доказанное истинно | доверие системе |
| Полнота | всё истинное доказуемо | завершённость |
| Силлогизм | цепочка следований | “логическая лестница” |
| Дедукция | строгое следствие | требует доказательства |
| Индукция | обобщение наблюдений | вероятностное |
| Абдукция | догадка о причине | гипотетическое |