Информатика ЕГЭ 23 задание разбор

• Поскольку в скобках одинаковые действия, и переменные повторяются, то введем обозначения:

¬a ≡ b
¬b ≡ c
¬c ≡ d
¬d ≡ e
¬e ≡ f

• Вместо отрицания первого операнда просто будем использовать «не эквивалентно»:

a ≠ b
b ≠ c
c ≠ d
d ≠ e
e ≠ f

• Вспомним, как выглядит таблица истинности для эквивалентности:

x1	x2	F
0	0	1
0	1	0
1	0	0
1	1	1

• Рассмотрим, в каких случаях выражения будут возвращать ложь. Каждое из пяти выражений будет ложно, когда: либо оба операнда истинны, либо оба операнда ложны (операция равносильность = истине: при 00 или 11).
• Составим битовую маску для наших уравнений. В цепочке значений от a до f не может быть двух единиц или двух нулей, идущих подряд, так как в этом случае система будет ложна (к примеру, a ≠ b, если 0 ≠ 0 — это ложь). Таким образом, для данных уравнений существует всего две цепочки решений:

  цеп.1  цеп.2 
a   0      1
b   1      0
c   0      1
d   1      0
e   0      1
f   1      0

• Теперь вспомним о заменах: каждая из переменных от a до f представляет собой скобку, внутри которой две переменные, связанные дизъюнкцией. Дизъюнкция двух переменных истинна в трех случаях (01, 10, 11), а ложна — в одном (00). Т.е., к примеру:

x1 ∨ y1 = 1 тогда, когда: либо 0 ∨ 1, либо 1 ∨ 0, либо 1 ∨ 1
 
x1 ∨ y1 = 0 тогда и только тогда, когда 0 ∨ 0

• Это говорит о том, что на каждую единицу в цепочке приходится три варианта значений, а на каждый ноль — один. Т.о. получаем:

для первой цепочки: 33 * 13 = 27 наборов значений, 
и для второй:  33 * 13 = 27 наборов значений 

• Итого наборов:

27 * 2 = 54

Результат: 54

• Поскольку в скобках одинаковые действия, и переменные повторяются, то введем обозначения:

¬a ≡ b
¬b ≡ c
¬c ≡ d
¬d ≡ e
¬e ≡ f
¬f ≡ g
¬g ≡ h
¬h ≡ i

• Вместо отрицания первого операнда просто будем использовать «не эквивалентно»:

a ≠ b
b ≠ c
c ≠ d
d ≠ e
e ≠ f
f ≠ g
g ≠ h
h ≠ i

• Вспомним таблицу истинности для эквивалентности:

x1	x2	F
0	0	1
0	1	0
1	0	0
1	1	1

• Теперь рассмотрим, в каких случаях полученные условия будут возвращать ложь. Каждое из условий будет ложно, если либо оба операнда истинны, либо оба операнда ложны:

  например 
  a ≠ b = 0, если: a=0 и b=0 или a=1 и b=1
  

  Это означает, что для одного условия не может быть такого случая, что a=0 и b=0 или a=1 и b=1.

• Составим битовую маску для условий. В цепочке значений от a до i не может быть двух единиц или двух нулей, идущих подряд, так как в этом случае система будет ложна. Таким образом, для данных условий существует всего две цепочки решений:

  цеп.1  цеп.2  цеп. цеп.
a   0      1     0    1
b   1      0     0    1   не может быть! 
c   0      1    ...  ...
d   1      0
e   0      1
f   1      0
g   0      1
h   1      0
i   0      1

• Теперь вспомним, что каждая из переменных от a до i представляет собой скобку, внутри которой две переменные, связанные конъюнкцией. Конъюнкция двух переменных истинна в одном случае, а ложна — в трех. Т.е., к примеру:

x1 ∧ y1 = 0 тогда, когда: либо 0 ∧ 1, либо 1 ∧ 0, либо 0 ∧ 0
 
x1 ∧ y1 = 1 тогда и только тогда, когда 1 ∧ 1

• Это говорит о том, что на каждый 0 в цепочке приходится три варианта значений, а на каждую 1 — один. Т.о. получаем:

для первой цепочки: 35 * 14 = 243 набора значений, 
и для второй:  34 * 15 = 81 набор значений

• Итого наборов:

243 + 81 = 324

Результат: 324

• Поскольку в скобках одинаковые действия, и скобки повторяются в разных уравнениях, то введем обозначения. Обозначим латинскими буквами в алфавитном порядке скобки с переменными согласно их номерам:

1-a
2-b
3-c
4-d
5-e
6-f
7-g
8-h

• После замены получим следующие выражения:

¬((a ≡ c) → b)
¬((b ≡ d) → ¬c)
¬((c ≡ e) → d)
¬((d ≡ f) → ¬e)
¬((e ≡ g) → f)
¬((f ≡ h) → ¬g)

• Используя законы алгебры логики, преобразуем одно из условий (первое). Потом по аналогии выполним преобразования для остальных условий:
1. Избавимся от импликации:

было:  ¬((a ≡ c) → b)
стало: ¬(¬(a ≡ c) ∨ b)

2. По закону Де Моргана избавимся от отрицания над общей внешней скобкой:

было:  ¬(¬(a ≡ c) ∨ b)
стало: (a ≡ c) ∧ ¬b

• По аналогии преобразуем остальные условия, учитывая, что двойное отрицание просто аннулирует отрицание:

(a ≡ c) ∧ ¬b
(b ≡ d) ∧ c
(c ≡ e) ∧ ¬d
(d ≡ f) ∧ e
(e ≡ g) ∧ ¬f
(f ≡ h) ∧ g	

• Рассмотрим, в каких случаях условия будут возвращать истину. Внешняя операция конъюнкция: каждое из условий будет истинно только в том случае, если оба операнда истинны:

  например: 
  (a ≡ c) ∧ ¬b  возвратит истину, если:
  (a ≡ c) = 1 и ¬b = 1

  Это означает, что все операнды, стоящие после знака конъюнкции, должны быть истинны.

• Составим битовую маску для наших уравнений с учетом указанного требования:

  цеп.1  
a   ?      
b   0      
c   1      
d   0      
e   1      
f   0      
g   1      
h   ?      

• Значение для переменной a найдем из условия (a ≡ c) ∧ b. В битовой маске с=1, значит, чтобы условие a ≡ c было истинным, а должно тоже равняться 1 (таблица истинности эквивалентности).
• Значение для переменной h найдем из условия (f ≡ h) ∧ ¬g. В битовой маске f=0, значит, чтобы условие f ≡ h было истинным, h должно тоже равняться 0 (таблица истинности эквивалентности).
• Получим итоговую битовую маску:

  цеп.1  
a   1      
b   0      
c   1      
d   0      
e   1      
f   0      
g   1      
h   0      

• Теперь вспомним, что каждая из переменных от a до h представляет собой скобку, внутри которой две переменные, связанные конъюнкцией. Конъюнкция двух переменных истинна в одном случае, а ложна — в трех. Т.е., к примеру:

x1 ∧ y1 = 0 тогда, когда: либо 0 ∧ 1, либо 1 ∧ 0, либо 0 ∧ 0
 
x1 ∧ y1 = 1 тогда и только тогда, когда 1 ∧ 1

• Это говорит о том, что на каждый 0 в цепочке приходится три варианта значений, а на каждую 1 — один. Т.о., получаем:

	34 * 14 = 81 набор значений

Результат: 81

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

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 будут обозначаться x_i и y_i, а x2 и y2 будут обозначаться x_i+1 и y_i+1.



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



• В итоге получаем:

1 + 19 + 1 + 1 = 22

Результат: 22

• Внешняя логическая операция — ∨ — дизъюнкция. Таблица истинности:

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

• Поскольку все равенства однотипны (кроме последнего), отличаются только сдвигом номеров переменных на единицу, то для решения будем использовать метод отображения: когда, найдя результат для первого равенства, необходимо применить тот же принцип с последующими равенствами, учитывая полученные результаты для каждого из них.
• Рассмотрим первое равенство. В нем внешняя операция — это конъюнкция, результат которой должна быть истина. Конъюнкция истинна если:

1 -> 1
т.е.:
(y1 → (y2 ∧ x1)) ∧ (x1 → x2) = 1
    1                1

• Найдем случаи, когда равенство будет ложным (чтобы в дальнейшем исключить эти случаи):

(y1 → (y2 ∧ x1)) ∧ (x1 → x2) = 0

• Внутри первой «большой» скобки находится операция импликации. Которая ложна:

1 -> 0 = 0
т.е. случаи:
y1=1 → (y2=0 ∧ x1=1)
y1=1 → (y2=1 ∧ x1=0)
y1=1 → (y2=0 ∧ x1=0)

• Таким же образом проанализируем вторую скобку. В ней импликация вернет ложь:

(x1=1 → x2=0)

• Построим таблицу истинности для первого уравнения, учтем все возможные варианты. Поскольку переменных 4, то строк будет 2⁴ = 16. Выделим те строки, которые возвращают ложь:



• Теперь переходим к методу отображения. Для первого уравнения x1 и y1 обозначим x_i и y_i, а x2 и y2 обозначим x_i+1 и y_i+1. Стрелками обозначим значения только тех строк таблицы истинности, которые возвращают 1.



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



• Теперь вернемся к последнему равенству. По условию оно должно быть истинным. Равенство вернет ложь только в одном случае:

y7=1 → x7=0 = 0

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

1 + 7 + 28 = 36

Результат: 36

• Поскольку в малых скобках везде одна и та же операция (∧), и переменные в скобках не пересекаются, то можно выполнить замену:

¬((a ≡ b) → c) = 1
¬((b ∨ ¬c) → d) = 1
...

• Избавимся от отрицания, указав, что каждое выражение при этом становится ложным:

(a ≡ b) → c = 0
(b ∨ ¬c) → d = 0
(c ≡ d) → e = 0
(d ∨ ¬e) → f = 0

• Внешняя операция во всех выражениях — импликация (→). Вспомним таблицу истинности для операции импликация:

0  → 0 = 1
0  → 1 = 1
1  → 0 = 0
1  → 1 = 1
 

• Импликация ложна только в одном случае: 1 → 0 = 0. Все выражения в задании ложны. Учтем это.
• Построим побитовую маску, прослеживая значение каждой переменной, двигаясь с первого выражения к последнему:

   цеп1   цеп2
a   0      1
b   0      1
c   0      0
d   0      0
e   0      0
f   0      0
 

• Так как каждая переменная изначально заменяет скобку, в которой находится операция конъюнкция (∧), то, вспомнив таблицу истинности для этой операции, сопоставим для каждого нуля 3 решения (конъюнкция ложна в трех случаях), а для каждой единицы — 1 решение (конъюнкция истинна в одном случае).
• Посчитаем значение для каждой побитовой цепочки:

цеп1 = 3*3*3*3*3*3 = 729 решений
цеп2 = 1*1*3*3*3*3 = 81 решение

• Поскольку цепочки не могут выполняться одновременно, а выполнится либо одна, либо другая, то полученные значения необходимо сложить:

729 + 81 = 810 решений

Ответ: 810

• В первых пяти выражениях имеем импликацию, которая ложна. Импликация ложна в единственном случае 1 → 0 = 0. То есть в этих выражениях левая часть (посылка) должна быть везде = 1, а правая часть 0.
• Первые пять условий можно решить методом отображений. Для этого построим схему отображений:



• На основе схемы построим таблицу отображений:



• В последнем уравнении ((x1 ≡ x4) ∨ (x5 ≡ x8) ∨ (x2 ≡ x12) = 1) имеем дизъюнкцию, которая равна 1. Для дизъюнкции всегда проще найти ложный случай (когда она = 0), так как это единственный вариант в таблице истинности дизъюнкции (0 ∨ 0 = 0). Найдем количество таких решений, т.е. найдем решения уравнения: (x1 ≡ x4) ∨ (x5 ≡ x8) ∨ (x2 ≡ x12) = 0
• Построим побитовую маску для данного уравнения:

x1 x2 x4 x5 x8 x12
0  0  1  0  1  1
0  1  1  0  1  0
0  0  1  1  0  1
0  1  1  1  0  0
1  0  0  0  1  1
1  1  0  0  1  0
1  0  0  1  0  1
1  1  0  1  0  0

• Так как в схеме отображений значения для пары x1 и x2 равные 00 и 11 не используются, то выделим их и не будем использовать в последующих вычислениях. Выпишем оставшиеся варианты:

x1 x2 x4 x5 x8 x12
0  1  1  0  1  0    y1
0  1  1  1  0  0    y2
1  0  0  0  1  1    y3
1  0  0  1  0  1    y4

• Построим таблицу отображений отдельно для каждой получившейся строки, учитывая значения операндов (x_n):






• Посчитаем число решений для всех полученных строк: 4 + 4 + 2 + 2 = 12
• Эти решения необходимо исключить, т.к. мы рассмотрели ложный случай уравнения 6:

96 - 12 = 84

Ответ: 84