Отрицание импликации — таблица истинности и задачи

Допустим, в школьной библиотеке действует правило «Если ученику выдали планшет, то в его карточке указали дату возврата». Лена получила планшет, а поле для даты осталось пустым. Одного такого случая достаточно, чтобы показать, что правило нарушили.

В высказывании «если p, то q» первая часть — условие p, вторая — заключение q. Чтобы записать отрицание импликации, сохраните условие, отрицайте заключение целиком и соедините части словом «и». Получится «p и не q». В примере это «Лене выдали планшет, и дату возврата в её карточке не указали».

¬(p → q) ≡ p ∧ ¬q

Знак ¬ означает «не», ∧ — «и», а ≡ показывает, что обе формулы принимают одинаковые значения во всех строках таблицы.

Когда импликация ложна

Импликация p → q ложна только при p = 1 и q = 0. Именно так вышло у Лены. Если бы ей не выдали планшет и в карточке тоже не было даты, импликация была бы истинной. Требование указать дату действует при выдаче планшета. Таблица истинности импликации в учебнике OpenStax.

Здесь 1 означает истину, 0 — ложь. Чтобы получить столбец ¬(p → q), замените каждую единицу в столбце p → q на ноль, а каждый ноль — на единицу. Сравните результат со столбцом p ∧ ¬q.

p	q	p → q	¬(p → q)	p ∧ ¬q	p → ¬q
0	0	1	0	0	1
0	1	1	0	0	1
1	0	0	1	1	1
1	1	1	0	0	0

Проверьте, к чему относится отрицание

В записи p → ¬q знак ¬ относится только к заключению. Получается «Если Лене выдали планшет, то дату возврата в её карточке не указали». При p = 0 эта формула даёт единицу в обеих строках, а отрицание всей импликации — ноль.

Если поменять условие и заключение местами, получится обратное высказывание q → p — «Если в карточке Лены указали дату возврата, то ей выдали планшет». При p = 0 и q = 0 оно даёт единицу, тогда как ¬(p → q) даёт ноль.

Значения остальных связок можно освежить по таблицам конъюнкции, дизъюнкции и отрицания. Чтобы применить строку 1 → 0 внутри более длинной формулы, попробуйте задачу на порядок столбцов в таблице истинности.

Найдите контрпример к утверждению «для каждого»

В таблице одна строка задаёт значения p и q. Если правило начинается со слов «для каждого x», значения обеих частей зависят от выбранного x. Чтобы опровергнуть правило, найдите хотя бы один объект из указанного множества, для которого условие истинно, а заключение ложно. Такой объект называется контрпримером. Поэтому отрицание «для каждого» начинается со слов «существует хотя бы один». Разбор отрицаний в руководстве Стэнфорда по доказательствам.

В библиотечном примере правило можно сформулировать для всех учеников. Его отрицание — «Есть хотя бы один ученик, которому выдали планшет и у которого в карточке нет даты возврата». Таким учеником оказалась Лена.

Три задачи на отрицание импликации

1. «Если 13 — чётное число, то 13 больше 10». Запишите отрицание всего высказывания. Обозначьте условие через p, а заключение через q и сравните значение отрицания со значением p → ¬q.
2. «Если система приняла файл, то в журнале указаны имя файла и время сдачи». Обозначьте принятие файла через p, наличие имени через q, а наличие времени через r. Запишите отрицание так, чтобы знак ¬ стоял только перед отдельными буквами. Будет ли оно истинным, если файл приняли, имя записали, а время сдачи пропустили?
3. «Для каждого целого числа n от 1 до 12 верно, что если n делится на 3, то n нечётно». Сформулируйте отрицание и выпишите все контрпримеры в этом диапазоне.

Ответы

1. «Число 13 чётное и не больше 10». Здесь p = 0 и q = 1, поэтому p ∧ ¬q = 0. Формула p → ¬q даёт единицу, поскольку её условие ложно.
2. Получается p ∧ (¬q ∨ ¬r). По закону де Моргана ¬(q ∧ r) ≡ ¬q ∨ ¬r. Знак ∨ означает «или». Выражение в скобках истинно, когда отсутствует хотя бы одна из двух записей. При p = 1, q = 1 и r = 0 отрицание истинно. Файл приняли, а время сдачи пропустили.
3. «Существует целое число от 1 до 12, которое делится на 3 и при этом чётно». Кратные трём в этом диапазоне — 3, 6, 9 и 12. Контрпримеры — 6 и 12. Любого из них достаточно, чтобы опровергнуть утверждение.

Повторите без таблицы

Назовите по памяти пару значений p и q, при которой импликация ложна. Затем придумайте своё правило со словами «если…, то…» и запишите случай, который его нарушает. Вернитесь к той же задаче завтра и ещё раз через несколько дней. Когда попытки вспомнить ответ распределены во времени, выученное дольше держится в памяти. Исследование интервального повторения с проверкой по памяти.

Для такой тренировки есть русскоязычная колода из 30 карточек по таблицам истинности. В ней есть короткие вопросы на импликацию и отрицание, а также задания, где нужно найти ошибку в строке таблицы.

Статья и упражнения подготовлены с помощью ИИ. Перебором проверены все строки таблицы, значения в первых двух задачах и числа от 1 до 12 в третьей.