дискретная логика

Логика работает с формой рассуждения: выделяем высказывания и связки, затем считаем их по приоритету.

высказывание и открытое предложение

Высказывание имеет ровно одно значение: истина или ложь. «$7$ — простое число» — высказывание; вопрос или команда — нет.

Открытое предложение зависит от переменной: $x>3$ становится высказыванием после подстановки $x$ или связывания квантором.

связки и приоритет

Отрицание $\neg p$ меняет значение. $p\land q$ требует истины обеих частей, $p\lor q$ — хотя бы одной. $p\to q$ ложна только при $p=1,q=0$, а $p\leftrightarrow q$ истинна при совпадении значений.

Знак $\equiv$ означает «равносильно»: две формулы при одинаковых исходных значениях всегда дают один и тот же результат. В их таблицах истинности совпадают итоговые столбцы.

Без скобок порядок таков: $\neg$, $\land$, $\lor$, $\to$, $\leftrightarrow$. При сомнении скобки лучше записать явно.

$$p\to q\equiv\neg p\lor q$$

нельзя обращать импликацию

Из $p\to q$ не следует $q\to p$. Если число делится на $4$, оно чётное, но чётное $6$ не делится на $4$.

проверка рассуждения

Таблица истинности показывает, верно ли следствие при каждом наборе значений.

modus ponens

условие: Дано $p\to q$ и $p$. Можно ли заключить $q$?

ход решения

1. Первая посылка запрещает набор $p=1,q=0$

2. Вторая посылка фиксирует $p=1$

3. Значит, остаётся только $q=1$

ответ: Да: $((p\to q)\land p)\to q$ — тавтология.

проверка: В полной таблице итоговый столбец состоит из единиц.

что запомнить

• Высказывание уже имеет значение; открытое предложение зависит от переменной.

• Импликация ложна только когда истина ведёт к лжи.

• Приоритет: $\neg$, $\land$, $\lor$, $\to$, $\leftrightarrow$.

• Обратная импликация не равносильна исходной.

самопроверка

• Почему $x^2=4$ не высказывание без уточнения $x$?

• Когда ложна $p\to q$?

• Как читается $\neg p\lor q$?

• Приведите контрпример к ошибочному переходу от $p\to q$ к $q\to p$.

источники

• материал занятия: краткий конспект «дискретная логика» — /materials/lectures/discrete-math-01.pdf

• материал занятия: фотографии конспекта, страницы 75–78 — /materials/notes/discrete_math/photo_75@20-09-2026_10-16-52.jpg

• редакционная сверка: MIT OpenCourseWare: Mathematics for Computer Science, readings — https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-fall-2010/resources/readings/