Решать экзаменационные задачи на логику: поиск значений переменных, при которых выражение истинно/ложно, и анализ систем условий.
Стратегии анализа логических выражений
Методы поиска наборов значений переменных
На экзамене часто встречаются задачи: «при каких значениях переменных выражение истинно» или «сколько наборов удовлетворяют условию». Есть несколько стратегий:
1. Полный перебор. Строим полную таблицу истинности (2ⁿ строк) и считаем нужные строки. Работает при 2–3 переменных (4–8 строк), при большем числе переменных становится трудоёмко.
2. Рассуждение от требуемого значения. Если нужно, чтобы A∧B=1, сразу заключаем: A=1 и B=1. Если A∨B=0, то A=0 и B=0. Если A→B=0, то A=1 и B=0. Такой анализ значительно сокращает перебор.
3. Разбор системы логических уравнений. Иногда задача формулируется как система: выражение1=1 И выражение2=0. Каждое условие ограничивает допустимые наборы, берём пересечение.
Типичные ловушки:
• Импликация ложна только в одном случае (A=1, B=0) — большинство наборов делают её истинной!
• Не забывайте приоритет: ¬ выполняется раньше ∧, ∧ — раньше ∨.
• Эквиваленция — это не равенство значений по модулю, а совпадение: оба 1 или оба 0.
Образцовый разбор: найти все наборы (A, B, C), при которых (A∨B)∧(¬B∨C)=1.
Оба множителя конъюнкции должны быть равны 1. Разберём:
— (A∨B)=1: не оба нулевые → 3 варианта: (0,1), (1,0), (1,1).
— (¬B∨C)=1: ложно только при B=1, C=0 → допустимы все, кроме B=1,C=0.
Пересечение: исключаем наборы с B=1,C=0: из трёх вариантов для (A,B) убираем те, где B=1,C=0 — это (0,1,0) и (1,1,0). Итого допустимых наборов: (0,1,1), (1,0,0), (1,0,1), (1,1,1) — 4 набора.
Lesson notes
Методы поиска наборов значений переменных
На экзамене часто встречаются задачи: «при каких значениях переменных выражение истинно» или «сколько наборов удовлетворяют условию». Есть несколько стратегий:
1. Полный перебор. Строим полную таблицу истинности (2ⁿ строк) и считаем нужные строки. Работает при 2–3 переменных (4–8 строк), при большем числе переменных становится трудоёмко.
2. Рассуждение от требуемого значения. Если нужно, чтобы A∧B=1, сразу заключаем: A=1 и B=1. Если A∨B=0, то A=0 и B=0. Если A→B=0, то A=1 и B=0. Такой анализ значительно сокращает перебор.
3. Разбор системы логических уравнений. Иногда задача формулируется как система: выражение1=1 И выражение2=0. Каждое условие ограничивает допустимые наборы, берём пересечение.
Типичные ловушки:
• Импликация ложна только в одном случае (A=1, B=0) — большинство наборов делают её истинной!
• Не забывайте приоритет: ¬ выполняется раньше ∧, ∧ — раньше ∨.
• Эквиваленция — это не равенство значений по модулю, а совпадение: оба 1 или оба 0.
Образцовый разбор: найти все наборы (A, B, C), при которых (A∨B)∧(¬B∨C)=1.
Оба множителя конъюнкции должны быть равны 1. Разберём:
— (A∨B)=1: не оба нулевые → 3 варианта: (0,1), (1,0), (1,1).
— (¬B∨C)=1: ложно только при B=1, C=0 → допустимы все, кроме B=1,C=0.
Пересечение: исключаем наборы с B=1,C=0: из трёх вариантов для (A,B) убираем те, где B=1,C=0 — это (0,1,0) и (1,1,0). Итого допустимых наборов: (0,1,1), (1,0,0), (1,0,1), (1,1,1) — 4 набора.