Задание 23.
Преобразование логических выражений: Демонстрационный вариант ЕГЭ по информатике 2018; государственный выпускной экзамен 2018; тренировочные варианты ЕГЭ по информатике, тематические тестовые задания и задачи из тренажера по информатике 2018
*** КАНАЛ ЮТЬЮБ ***
ЕГЭ по информатике -> ЕГЭ 2018 -> ЕГЭ 2018 — 23
Разбор 23 задания ЕГЭ по информатике демоверсия 2018 года ФИПИ:
Сколько существует различных наборов значений логических переменных x1, x2, … x7, y1, y2, … y7, которые удовлетворяют всем перечисленным ниже условиям?
(¬x1 ∨ y1) → (¬x2 ∧ y2) = 1
(¬x2 ∨ y2) → (¬x3 ∧ y3) = 1
…
(¬x6 ∨ y6) → (¬x7 ∧ y7) = 1
В качестве ответа Вам нужно указать количество таких наборов.
📹 Видеоразбор
✍ Показать решение (используется метод отображения):
- Внешняя операция в отдельно взятом уравнении — это импликация, результат которой должна быть истина. Импликация истинна если:
0 -> 0
0 -> 1
1 -> 1
т.е. ложна только, когда 1 -> 0
Если скобка (¬x1 ∨ y1) = 0, то для скобки (¬x2 ∧ y2) возможны варианты 0 или 1.
Если скобка (¬x1 ∨ y1) = 1, то для скобки (¬x2 ∧ y2) возможен один вариант — 1.
В скобках дизъюнкция (∨) истинна, когда: 0 ∨ 1, 1 ∨ 0, 1 ∨ 1; ложна, когда: 0 ∨ 0.
В скобках конъюнкция истинна, когда 1 ∧ 1 и ложна во всех остальных случаях.
Построим таблицу истинности для первого уравнения, учтем все возможные варианты. Выделим в ней те строки, которые возвращают ложь: т.е. где первая скобка (¬x1 ∨ y1) возвратит 1, а вторая (¬x2 ∧ y2) — 0:
Поскольку уравнения однотипные и отличаются только сдвигом номеров переменных на единицу, то будем использовать метод отображения. Для первого уравнения x1 и y1 будут обозначаться xi и yi, а x2 и y2 будут обозначаться xi+1 и yi+1.
Теперь найдем общее количество решений, подставляя в отображении соответствующие x и y, и, учитывая предыдущие значения:
В итоге получаем:
1 + 19 + 1 + 1 = 22
Результат: 22
Решение 23 задания ЕГЭ по информатике, вариант 3 (ФИПИ, «ЕГЭ информатика и ИКТ, типовые экзаменационные варианты 2018», 10 вариантов, С.С. Крылов, Т.Е. Чуркина):
Сколько существует различных наборов значений логических переменных x1, x2, … x6, y1, y2, … y6, которые удовлетворяют всем перечисленным ниже условиям?
(x1 ∨ y1) → (x2 ∧ y2) = 0
(x2 ∨ y2) → (x3 ∧ y3) = 0
…
(x5 ∨ y5) → (x6 ∧ y6) = 0
В качестве ответа указать количество таких наборов.
📹 Видеоразбор
Решение 23 задания ЕГЭ по информатике 2018 (диагностический вариант, С.С. Крылов, Д.М. Ушаков, Тренажер ЕГЭ 2018 года):
Сколько различных решений имеет уравнение:
(a → b) ∨ (c → ¬d) ∨ ¬(e ∨ a ∨ c) = 1
где a, b, c, d, e — логические переменные?
В качестве ответа указать количество таких наборов.
✍ Показать решение:
- Внешняя логическая операция — ∨ — дизъюнкция. Таблица истинности:
0 ∨ 0 = 0
0 ∨ 1 = 1
1 ∨ 0 = 1
1 ∨ 1 = 1
Поскольку дизъюнкция равна единице аж в трех случаях, то искать количество вариантов будет достаточно сложно. Значительно проще найти варианты, когда ∨ = 0 и вычесть их из общего количества вариантов.
Найдем общее количество строк в таблице истинности. Всего 5 переменных, поэтому:
количество строк в ТаблИстин = 25 = 32
Посчитаем, сколько вариантов имеют решение при значении уравнения = 0. Чтобы потом вычесть это значение из общего количества. Для операции дизъюнкция (∨) каждая скобка должна быть равна нулю:
(a → b) ∨ (c → ¬d) ∨ ¬(e ∨ a ∨ c) = 0
0 0 0
Теперь рассмотрим каждую скобку отдельно:
1. (a → b) = 0, импликация ложна в одном случае (1 → 0) = 0
т.е. имеем a = 1, b = 0
2. (c → ¬d) = 0, импликация ложна в одном случае (1 → 0) = 0
т.е. имеем c = 1, d = 1
3. ¬(e ∨ a ∨ c) = 0
т.к. перед скобкой стоит отрицание, то для большей понятности раскроем скобки по закону Де Моргана:
¬e ∧ ¬a ∧ ¬c = 0
Конъюнкция равна 0, когда хоть один операнд = 0.
из п.1 и п.2 имеем a = 1 и c = 1. Тогда для e имеем два варианта: e = 0, e = 1, т.е.:
¬0 ∧ ¬1 ∧ ¬1 = 0
¬1 ∧ ¬1 ∧ ¬1 = 0
То есть всего имеем 2 цепочки «исключаемых» решений:
1. a = 1, b = 0, c = 1, d = 1, e = 0
2. a = 1, b = 0, c = 1, d = 1, e = 1
Эти два варианта исключаем (вычитаем) из общего количества:
32 - 2 = 30
Результат: 30
ЕГЭ по информатике -> ЕГЭ 2018 -> ЕГЭ 2018 — 23
