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

Просмотров 7 Комментарии 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 = 1,x4 = 1)$ , при любых других конъюнкция будет равна 0.

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

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

$|---|--------|--------|-------|--------|---------| |---|x1-∧-x2-|x3 ∧-x4-|x5 ∧-x6|x7-∧-x8-|x9-∧-x10-| |00 | 1 | 3 | 9 | 27 | 81 | |01-|---1----|---3----|--9----|---27---|---81----| |---|--------|--------|-------|--------|---------| |10-|---1----|---3----|--9----|---27---|---81----| -11-----1--------4-------13-------40-------121----$

$|---|--------|-------------|--------------|---------------|------------------| |---|x1-∧-x2-|---x3 ∧-x4---|---x5-∧-x6----|----x7 ∧-x8----|-----x9 ∧-x10-----| |00-|---1----|--1 +-1 +-1--|--3-+-3-+-3---|---9 +-9 +-9---|---27 +-27 +-27---| |01 | 1 | 1 + 1 + 1 | 3 + 3 + 3 | 9 + 9 + 9 | 27 + 27 + 27 | |---|--------|-------------|--------------|---------------|------------------| |10-|---1----|--1 +-1 +-1--|--3-+-3-+-3---|---9 +-9 +-9---|---27 +-27 +-27---| -11-----1-----1 +-1 +-1-+-1-3-+-3-+-3-+-4--9-+-9-+-9-+-13--27-+-27-+-27-+-40--$

В итоге получаем: $81 + 81 + 81 + 121 = 364$ .

Ответ: 364