обновлено 6 нояб.офлайн

ГлавнаяФормулы ДМ4.md

---
tags: [mephi, legacy, discrete-math, logic]
created: 2026-11-06
updated: 5 нояб.
---

Формулы ДМ4

ДМ4mephi legacy discrete-math logic5 нояб.3 мин

Содержание

1. Базовые определения связок в $P_{1}$

Обозначение	Определение	Как читать	Зачем нужно
$t$	$f \supset f$	истина	Истина определяется через ложь и импликацию
$\neg A$	$A \supset f$	не $A$	Отрицание через импликацию к ложности
$A \lor B$	$A \supset B \supset B$	$A$ или $B$	Дизъюнкция через импликацию
$A \land B$	$\neg (\neg A \lor \neg B)$	$A$ и $B$	Конъюнкция через отрицание и дизъюнкцию
$A \equiv B$	$(A \supset B) \land (B \supset A)$	$A$ эквивалентно $B$	Взаимная выводимость
$A \subset B$	$B \supset A$	обратная импликация	Сокращение для обратного следования
$A ↑ B$	$\neg A \land \neg B$	ни $A$ , ни $B$	Техническая связка
$A ∣ B$	$\neg A \lor \neg B$	не $A$ или не $B$	Техническая связка

2. Аксиомы пропозиционального исчисления $P_{1}$

Номер	Название	Формула	Смысл
A1	$K$	$p \supset (q \supset p)$	Если $p$ есть, то $p$ можно получить при любой дополнительной посылке $q$
A2	$S$	$(s \supset (p \supset q)) \supset ((s \supset p) \supset (s \supset q))$	Если из $s$ следует $p \supset q$ , и из $s$ следует $p$ , то из $s$ следует $q$
A3	$E \neg$	$\neg\neg p \supset p$	Закон исключения двойного отрицания

3. Правила вывода

Название	Запись	Как работает	Когда применять
$M P$ / Modus Ponens	$\frac{⊢ A \supset B , ⊢ A}{⊢ B}$	Если доказано $A \supset B$ и доказано $A$ , можно вывести $B$	Главное правило вывода
$β$ / правило подстановки	$A ⊢ [B / b] A$	В формуле $A$ можно заменить переменную $b$ на формулу $B$	Нужно, чтобы получать частные случаи аксиом и теорем

5. Что считать теоремами в рамках лекции 5

Объект	Статус	Формулировка	Комментарий
Теорема	определение	Теорема — формула, которая имеет доказательство	Это не конкретная формула, а определение понятия
Доказательство	определение	Доказательство формулы $B$ — последовательность формул, где каждая формула является аксиомой или выводится из предыдущих, а последняя формула равна $B$	Это база для всех следующих задач
$p \supset p$	будет теоремой дальше	$(I) : p \supset p$	В лекции 5 ещё не доказывается, но это первая важная теорема в следующем блоке
$B$	будет теоремой дальше	$(q \supset s) \supset ((p \supset q) \supset (p \supset s))$	Закон транзитивности импликации
$C$	будет теоремой дальше	$(p \supset (q \supset s)) \supset (q \supset (p \supset s))$	Закон перестановки посылок
$C \neg$	будет теоремой дальше	$(\neg p \supset \neg q) \supset (q \supset p)$	Закон контрпозиции

Лекция 6. Стэк важных формул

Название	Формула	Смысл	Когда использовать
$K$	$p \supset (q \supset p)$	Если $p$ есть, то из любой дополнительной посылки $q$ можно снова получить $p$	Когда нужно добавить лишнюю посылку
$S$	$(s \supset (p \supset q)) \supset ((s \supset p) \supset (s \supset q))$	Если в контексте $s$ есть $p \supset q$ и есть $p$ , то в контексте $s$ есть $q$	Для применения импликации внутри общего условия
$E \neg$	$\neg\neg p \supset p$	Снятие двойного отрицания	Когда нужно из $\neg\neg A$ получить $A$
$M P$	$\frac{⊢ A \supset B , ⊢ A}{⊢ B}$	Modus Ponens: из импликации и её левой части получаем правую	Главное правило вывода
$β$	$A ⊢ [B / b] A$	Подстановка формулы $B$ вместо переменной $b$ в формуле $A$	Чтобы получать частные случаи аксиом и теорем

Основные теоремы лекции 6

Название	Формула	Смысл	Когда использовать
$I$	$p \supset p$	Тождественная импликация: любое утверждение следует из самого себя	Когда нужно доказать $A \supset A$
$B$	$(q \supset s) \supset ((p \supset q) \supset (p \supset s))$	Транзитивность импликации	Чтобы склеить $p \supset q$ и $q \supset s$ в $p \supset s$
$B^{'}$	$(p \supset q) \supset ((q \supset s) \supset (p \supset s))$	Та же транзитивность, но с другим порядком посылок	Когда сначала дана формула $p \supset q$ , а потом $q \supset s$
$C$	$(p \supset (q \supset s)) \supset (q \supset (p \supset s))$	Перестановка посылок	Чтобы менять порядок вложенных условий
$C^{'}$	$(p \supset (q \supset s)) \equiv (q \supset (p \supset s))$	Эквивалентность формул с переставленными посылками	Когда нужно показать, что порядок посылок не важен
$C \neg$	$(\neg p \supset \neg q) \supset (q \supset p)$	Контрпозиция в одну сторону	Чтобы из $\neg A \supset \neg B$ получить $B \supset A$
$I \neg$	$p \supset \neg\neg p$	Введение двойного отрицания	Чтобы из $A$ получить $\neg\neg A$
$C \neg^{'}$	$(p \supset q) \supset (\neg q \supset \neg p)$	Обычная контрпозиция	Чтобы из $A \supset B$ получить $\neg B \supset \neg A$