Логика высказываний
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\) | формальная процедура |
| Корректность | всё доказанное истинно | доверие системе |
| Полнота | всё истинное доказуемо | завершённость |
| Силлогизм | цепочка следований | “логическая лестница” |
| Дедукция | строгое следствие | требует доказательства |
| Индукция | обобщение наблюдений | вероятностное |
| Абдукция | догадка о причине | гипотетическое |