Логика высказываний и доказательства: задачи с пошаговыми решениями
Бесплатные задачи по теме Логика высказываний и доказательства с рисунками, подсказками и подробными решениями. Каждый раз новые значения, трёх уровней: таблицы истинности, эквивалентности и методы доказательства, кванторы и рассуждения.
Бесплатная задачаЛёгкая
Заполните таблицу истинности (1 = истина, 0 = ложь). В скольких строках, N, формула (p → r) ↔ (r ∨ q) истинна?
Изучите тему «Логика высказываний и доказательства» с нуля
1Высказывания и связки
Высказывание — это утверждение, которое либо истинно, либо ложно, например «7 — простое число». Мы обозначаем его буквой, p или q, а его значение истинности записываем как 1 (истина) или 0 (ложь).
Связки строят из простых формул более сложные:
¬p (не p) меняет значение на противоположное.
p ∧ q (и) равно 1 только тогда, когда оба равны 1.
p ∨ q (или) равно 0 только тогда, когда оба равны 0. Это включающее «или»: оба могут быть истинными.
p → q (если p, то q) равно 0 только при p = 1 и q = 0.
p ↔ q (тогда и только тогда) равно 1, когда p и q имеют одинаковое значение.
Импликация удивляет многих студентов: когда p ложно, p → q истинно при любом q. Обещание «если пойдёт дождь, я возьму зонт» нарушено только в дождливый день без зонта.
Самопроверка p = 0 и q = 1. Чему равно значение p → q?
0
1
Зависит от контекста
Не определено
Ответ: 1. Импликация ложна только тогда, когда условие выполнено, а вывод нет (p = 1, q = 0). При p = 0 она истинна при любом q.
2Таблицы истинности
В таблице истинности перечислены все комбинации значений истинности переменных. Для n различных переменных получается 2ⁿ строк: 4 для двух переменных, 8 для трёх, 16 для четырёх. Переменная, встречающаяся дважды, всё равно считается один раз.
Работайте изнутри наружу. Отведите каждой подформуле отдельный столбец, чтобы для каждого нового столбца нужно было применить лишь одну связку к уже имеющимся столбцам.
Перечислите переменные и запишите все 2ⁿ комбинаций, начиная со строки из одних 1.
Добавьте столбец для каждой подформулы, начиная с самых внутренних.
Заполняйте каждый столбец по правилу его главной связки.
Прочитайте ответ в последнем столбце: посчитайте единицы или найдите нужную строку.
Самопроверка Сколько строк в таблице истинности формулы (p ∧ q) → (r ∨ p)?
16
4
6
8
Ответ: 8. В формуле три различные переменные, p, q и r, поэтому 2³ = 8 строк. p встречается дважды, но это одна переменная; 16 было бы 2⁴ для четырёх вхождений.
3Разобранный пример
Пройдите каждый шаг. Попробуйте предсказать следующий, прежде чем открыть его.
Разобранный пример
В скольких строках таблицы истинности формула (p → q) ∧ ¬q истинна?
1
Переменные и строки
Две переменные, p и q, поэтому 4 строки: (1, 1), (1, 0), (0, 1), (0, 0).
2
Столбец p → q
Он равен 0 только в строке p = 1, q = 0:
p → q: 1, 0, 1, 1
3
Столбец ¬q
¬q: 0, 1, 0, 1
4
Конъюнкция
Оба столбца должны быть равны 1. Это бывает только в последней строке, при p = 0 и q = 0.
(p → q) ∧ ¬q: 0, 0, 0, 1
Ответ
Формула истинна в 1 строке, в строке p = 0, q = 0. Поэтому p → q и ¬q вместе дают ¬p (modus tollens).
4Эквивалентности и методы доказательства
Две формулы эквивалентны (≡), когда их столбцы в таблице истинности совпадают. Тавтология равна 1 в каждой строке, противоречие равно 0 в каждой строке, а нейтральная формула (contingency) — ни то ни другое.
Законы, которые используются чаще всего:
¬(p ∧ q) ≡ ¬p ∨ ¬q ¬(p ∨ q) ≡ ¬p ∧ ¬q
p → q ≡ ¬p ∨ q ≡ ¬q → ¬p ¬(p → q) ≡ p ∧ ¬q
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
Эти законы лежат в основе методов доказательства. Доказательство p → q от контрапозиции доказывает вместо этого ¬q → ¬p, что эквивалентно. Доказательство от противного предполагает p ∧ ¬q — единственный способ, которым импликация может не выполняться, — и выводит нечто невозможное.
Осторожно: обратное утверждение q → p и противоположное ¬p → ¬q не эквивалентны p → q.
Самопроверка Какая формула эквивалентна ¬(p ∧ q)?
p ∨ q
¬p ∧ q
¬p ∧ ¬q
¬p ∨ ¬q
Ответ: ¬p ∨ ¬q. По закону де Моргана ∧ превращается в ∨, и обе части отрицаются. ¬p ∧ ¬q — это отрицание p ∨ q, другое утверждение: оно ложно, когда истинно ровно одно из p и q, тогда как ¬(p ∧ q) истинно.
5Кванторы и правильные рассуждения
Для переменных на некоторой области ∀x P(x) означает «P выполняется для каждого x», а ∃x P(x) — «P выполняется хотя бы для одного x». Отрицание меняет квантор:
¬∀x P(x) ≡ ∃x ¬P(x) ¬∃x P(x) ≡ ∀x ¬P(x)
Переносите отрицание внутрь по одному шагу; внутри пользуйтесь законами логики высказываний. Например, ¬∀x (P(x) → Q(x)) ≡ ∃x (P(x) ∧ ¬Q(x)): «не каждое P является Q» означает «некоторое P не является Q».
Рассуждение правильно, если вывод равен 1 в каждой строке, где все посылки равны 1. Классические правильные формы: modus ponens (p → q, p, значит q), modus tollens (p → q, ¬q, значит ¬p) и гипотетический силлогизм (p → q, q → r, значит p → r).
Строка, где все посылки равны 1, а вывод равен 0, — это контрпример. Подтверждение следствия (p → q, q, значит p) неправильно: строка p = 0, q = 1 — контрпример.
Ответ: ∃x ¬P(x): некоторый студент не сдал. Одного студента, который не сдал, достаточно, чтобы сделать «все студенты сдали» ложным. «Никто не сдал» гораздо сильнее, чем отрицание.
6Типичные ошибки
Считать p → q ложным, когда p ложно. Оно ложно только при p = 1 и q = 0.
Считать повторяющуюся переменную дважды при определении числа строк.
Путать контрапозицию ¬q → ¬p с обратным утверждением q → p или противоположным ¬p → ¬q.
Отрицать ∀x P(x) как ∀x ¬P(x): квантор должен смениться на ∃.
Записывать ¬(p ∧ q) как ¬p ∧ ¬q: закон де Моргана меняет и связку.
Самопроверка Какое утверждение является контрапозицией утверждения «если n² чётно, то n чётно»?
n² чётно, а n нечётно
Если n нечётно, то n² нечётно
Если n чётно, то n² чётно
Если n² нечётно, то n нечётно
Ответ: Если n нечётно, то n² нечётно. Поменяйте две части местами и отрицайте обе: не (n чётно) → не (n² чётно). «Если n чётно, то n² чётно» — это обратное утверждение; последний вариант — то, что предполагается в доказательстве от противного.
7Как выглядят экзаменационные задачи
Лёгкий: таблицы истинности. Вы находите число строк, считаете строки, в которых формула истинна, или выбираете единственную строку, делающую формулу истинной или ложной.
Средний: эквивалентности и методы доказательства. Вы определяете, является ли формула тавтологией, противоречием или нейтральной формулой, выбираете эквивалентную формулу или утверждение, которое нужно доказывать при доказательстве от контрапозиции или от противного.
Сложный: кванторы и рассуждения. Вы отрицаете высказывания с кванторами, выбираете вывод, следующий из посылок, выбираете строку-контрпример неправильного рассуждения или считаете истинные строки в таблице с четырьмя переменными.
Ровно одна строка таблицы истинности делает ¬(p ∨ q) → q ложным. Нажмите на эту строку.
¬(p ∨ q) → q
1p = 1, q = 1
2p = 1, q = 0
3p = 0, q = 1
4p = 0, q = 0
Показать подсказки
a → b равно 0 только при a = 1 и b = 0. ¬a меняет значение на противоположное. a ∨ b равно 0 только тогда, когда оба равны 0.
Сначала определите главную связку: какими должны быть её две части, чтобы вся формула была 0?
Отведите каждой части отдельный столбец: p ∨ q; ¬(p ∨ q); ¬(p ∨ q) → q.
Показать ответ и объяснение
Таблицы истинности: у формулы с n различными переменными 2ⁿ строк, по одной для каждой комбинации значений истинности (1 = истина, 0 = ложь). Работайте изнутри наружу и отводите каждой подформуле отдельный столбец. ¬a меняет значение на противоположное; a ∧ b равно 1 только тогда, когда оба равны 1; a ∨ b равно 0 только тогда, когда оба равны 0; a → b равно 0 только при a = 1 и b = 0; a ↔ b равно 1, когда обе части равны.
Какая формула логически эквивалентна (b ∧ c) → a? Нажмите на неё.
(b ∧ c) → a
1(b → a) ∧ (c → a)
2b → (c → a)
3b ∧ (c → a)
4(b → c) → a
Показать подсказки
Эквивалентные формулы совпадают в каждой строке таблицы истинности. Одна строка, где они различаются, исключает вариант.
Попробуйте строку, в которой (b ∧ c) → a равно 0, и проверьте, какие варианты в ней тоже равны 0.
Экспортация: (a ∧ b) → c ≡ a → (b → c). Обе равны 0 только при a = 1, b = 1 и c = 0.
Показать ответ и объяснение
Логическая эквивалентность: две формулы эквивалентны (≡), если в каждой строке таблицы истинности они имеют одинаковое значение. Тавтология равна 1 в каждой строке, противоречие равно 0 в каждой строке, а нейтральная формула (contingency) — ни то ни другое. Полезные законы: законы де Моргана, ¬(a ∧ b) ≡ ¬a ∨ ¬b и ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (контрапозиция); ¬(a → b) ≡ a ∧ ¬b; а также законы дистрибутивности, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).
Закон
Экспортация: (a ∧ b) → c ≡ a → (b → c). Обе равны 0 только при a = 1, b = 1 и c = 0.
(b ∧ c) → a ≡ b → (c → a)
Проверка по таблице истинности
a = 1, b = 1, c = 1: 1 | 1 1 1 1
a = 1, b = 1, c = 0: 1 | 1 1 1 1
a = 1, b = 0, c = 1: 1 | 1 1 0 1
a = 1, b = 0, c = 0: 1 | 1 1 0 1
a = 0, b = 1, c = 1: 0 | 0 0 0 0
a = 0, b = 1, c = 0: 1 | 0 1 1 1
a = 0, b = 0, c = 1: 1 | 0 1 0 0
a = 0, b = 0, c = 0: 1 | 1 1 0 0
Ответ
b → (c → a)
Столбцы после черты — варианты ответа в показанном порядке.
Пример 3Сложная
Даны посылки (q ∧ p) → r; q; ¬r. Какой вывод из них следует? Нажмите на него.
(q ∧ p) → rq¬r
1p
2p ∧ ¬r
3¬p
4r
Показать подсказки
Вывод следует, если он равен 1 в каждой строке, где все посылки равны 1.
Найдите строки, в которых все посылки равны 1, затем проверьте каждый вариант в этих строках.
Это стандартное правило: modus tollens с конъюнкцией.
Показать ответ и объяснение
Кванторы и рассуждения: ¬∀x P(x) ≡ ∃x ¬P(x) и ¬∃x P(x) ≡ ∀x ¬P(x). Переносите отрицание внутрь, меняйте каждый квантор, через который оно проходит, и отрицайте внутреннюю формулу по законам логики высказываний, например ¬(a → b) ≡ a ∧ ¬b. Рассуждение правильно, если вывод равен 1 в каждой строке, где все посылки равны 1. Одной строки с истинными посылками и ложным выводом достаточно, чтобы получить контрпример и показать, что рассуждение неправильно.
Строки, в которых все посылки истинны
p = 0, q = 1, r = 0: p = 0, p ∧ ¬r = 0, ¬p = 1, r = 0
Вывод
¬p (modus tollens с конъюнкцией)
Ответ
¬p
Вопросы и ответы
Логика высказываний и доказательства: что это?
Связки строят из простых формул более сложные:
Импликация удивляет многих студентов: когда p ложно, p → q истинно при любом q. Обещание «если пойдёт дождь, я возьму зонт» нарушено только в дождливый день без зонта.
Логика высказываний и доказательства: как решать задачи шаг за шагом?
Подсчитайте различные переменные: в таблице истинности 2ⁿ строк, и начинается она со строки, где все переменные равны 1.
Отведите каждой подформуле отдельный столбец и заполняйте столбцы изнутри наружу.
Применяйте правило каждой связки: → равно 0 только для 1 → 0, ↔ равно 1, когда обе части совпадают.
Для эквивалентностей сравнивайте последние столбцы строка за строкой; для рассуждения смотрите только на строки, в которых все посылки равны 1.
Чтобы отрицать высказывание с квантором, переносите ¬ внутрь, меняйте ∀ и ∃ местами и отрицайте внутреннюю формулу.
Логика высказываний и доказательства: какие ошибки самые частые?
Считать p → q ложным, когда p ложно.
Считать повторяющуюся переменную дважды при определении числа строк.
Путать контрапозицию ¬q → ¬p с обратным утверждением q → p.
Отрицать ∀x P(x) как ∀x ¬P(x) вместо ∃x ¬P(x).
Применять закон де Моргана, не меняя ∧ и ∨ местами.
Логика высказываний и доказательства: что вы тренируете?
Лёгкая: таблицы истинности
Средняя: эквивалентности и методы доказательства
Сложная: кванторы и рассуждения
В каждой задаче новые значения, поэтому вы учите метод, а не ответ. Застряли? Сначала откройте небольшую подсказку, а полное объяснение — только когда оно понадобится.
Как проходят занятия
В каждой задаче новые значения, поэтому вы учите метод, а не ответ.
Застряли? Сначала откройте небольшую подсказку, а полное объяснение — только когда оно понадобится.
Ваш прогресс, ошибки и сохранённые задачи остаются, поэтому перед экзаменом вы сможете всё повторить.