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

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

Сколько существует различных наборов значений $x1,x2,...x10$ , которые удовлетворяют всем перечисленным ниже условиям?

$(x1 ∧ x2) → (x3 ∨ x4 ) = 1$

$(x3 ∧ x4) → (x5 ∨ x6 ) = 1$

$(x5 ∧ x6) → (x7 ∨ x8 ) = 1$

$(x7 ∧ x8) → (x9 ∨ x10) = 1$

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

Внешняя операция в отдельно взятом уравнении — это импликация, в результате которой должна быть истина. Импликация истинна, если:

$0 → 1$

$0 → 0$

$1 → 1$

Если скобка $(x1 ∧ x2 ) = 1$ (это верно в таких случаях $x1 = 1,x2 = 1)$ , то для скобки $(x3 ∧ x4)$ возможны только варианты $(x3 = 0,x4 = 1;x3 = 1,x4 = 0;x3 = 0,x4 = 0 )$ , при $(x3 = 0,x4 = 0)$ $(x ∨ x ) = 0 3 4$ импликация становится равна 0.

Если $(x1 ∧ x2) = 0$ (это верно в таких случаях $x1 = 0,x2 = 1; x1 = 1,x2 = 0;x1 = 0,x2 = 0)$ , то для скобки $(x3 ∧ x4)$ возможны любые значения, импликация этих скобок будет истинна. Поскольку уравнения однотипные и отличаются только сдвигом номеров переменных на единицу, то будем использовать метод отображения, применяя его к каждой последующей комбинации $x ,x ,i ∈ [1;9 ] i i+1$ .

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

$|---|--------|--------|-------|--------|---------| | |x1 ∧ x2 |x3 ∧ x4 |x5 ∧ x6|x7 ∧ x8 |x9 ∧ x10 | |00-|---1----|---3----|--11---|---41---|---153---| |---|--------|--------|-------|--------|---------| |01-|---1----|---4----|--15---|---56---|---209---| |10-|---1----|---4----|--15---|---56---|---209---| |11 | 1 | 4 | 15 | 56 | 209 | --------------------------------------------------$

$|---|--------|-------------|--------------|------------------|-------------------| |---|x1-∧-x2-|---x3 ∧-x4---|---x5-∧-x6----|-----x7-∧-x8------|-----x9-∧-x10------| |00 | 1 |1 + 1 + 1 + 1| 3 + 4 + 4 | 15 + 15 + 11 | 41 + 56 + 56 | |---|--------|-------------|--------------|------------------|-------------------| |01-|---1----|1 +-1 +-1-+-1|3-+-4-+-4-+-4-|15-+-15-+-15-+-11-|41-+-56-+-56-+-56--| |10-|---1----|1 +-1 +-1-+-1|3-+-4-+-4-+-4-|15-+-15-+-15-+-11-|41-+-56-+-56-+-56--| -11-----1-----1 +-1 +-1-+-1-3-+-4-+-4-+-4--15-+-15-+-15-+-11--41-+-56-+-56-+-56---$

В итоге получаем: $153 + 209 + 209 + 209 = 780$ .

Ответ: 780