Задача к ЕГЭ по информатике на тему «системы логических уравнений» №2

Просмотров 7 Комментарии 0

Сколько существует различных наборов значений логических переменных $x1,x2,x3,x4,x5,x6, x7,x8,x9,x10,$ которые удовлетворяют всем перечисленным ниже условиям:
$((x1 → x2) → (x3 → x4)) ∧ ((x3 → x4) → (x5 → x6)) = 1$
$((x5 → x6) → (x7 → x8)) ∧ ((x7 → x8) → (x9 → x10)) = 1$
$x1 ∧ x3 ∧ x5 ∧ x7 ∧ x9 = 1$

В ответе не нужно перечислять все различные наборы значений переменных $x1,x2,x3,x4, x5,x6,x7,x8,x9, x10,$ при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.

(ЕГЭ 2017, СтатГрад, 30 сентября 2016)

Чтобы выполнилось последнее уравнение, все $x$ с нечётными номерами должны быть равны 1.
Перепишем нашу систему, заменяя такие $x$ на 1 и разделяя каждую конъюнкцию на два уравнения:
$(x1 → x2) → (x3 → x4) = 1$
$(x3 → x4) → (x5 → x6) = 1$
$(x5 → x6) → (x7 → x8) = 1$
$(x → x ) → (x → x ) = 1 7 8 9 10$
Поскольку уравнения однотипные и отличаются только сдвигом номеров переменных на два, то будем использовать метод отображения, применяя его к каждой последующей комбинации $xi,xi+1,i ∈ {2,4,6,8,10 }.$

Также можно заметить, что для таких пар при наборе 1 0 уравнения истинны не будут, так как внешняя импликация будет равна 0 . Теперь найдем общее количество решений, подставляя в отображении соответствующие $x,$ учитывая предыдущие значения:

|---|-----|------|-----|------| |---|x2x4-|x4x6--|x6x8-|x8x10-| |00 | 1 | 1 | 1 | 1 | |---|-----|------|-----|------| |01-|--1--|--1---|-1---|--1---| -11----1-----2-----3------4----

Суммируем и получаем ответ: $1 + 1 + 4 = 6.$

Ответ: 6