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

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

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

$(x1 ∧ x2) → (x3 ∧ x4 ) = 0$

$(x3 ∧ x4) → (x5 ∧ x6 ) = 0$

$(x5 ∧ x6) → (x7 ∧ x8 ) = 0$

$(x7 ∧ x8) → (x9 ∧ x10) = 0$

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

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

$1 → 0$

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

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

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

$|---|--------|--------|-------|--------|---------| |---|x1-∧-x2-|x3 ∧-x4-|x5 ∧-x6|x7-∧-x8-|x9-∧-x10-| |00-|---1----|---1----|--0----|---0----|----0----| |01-|---1----|---1----|--0----|---0----|----0----| |10 | 1 | 1 | 0 | 0 | 0 | |---|--------|--------|-------|--------|---------| -11-----1--------0-------0--------0---------0-----$

Так как начиная с $x3 ∧ x4$ у нас в комбинации 11 стоит 0, то все остальные значения будут равны 0. В итоге получаем: $0 + 0 + 0 + 0 = 0$ .

Ответ: 0