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

23-е задание: «Преобразование логических выражений»
Уровень сложности — высокий,
Максимальный балл — 1,
Примерное время выполнения — 10 минут.

Разбор 23 задания ЕГЭ по информатике 2017 года ФИПИ вариант 1 (Крылов С.С., Чуркина Т.Е.):

Сколько существует различных наборов значений логических переменных x1, x2, … x6, y1, y2, … y6, которые удовлетворяют всем перечисленным ниже условиям?

(¬(x1 ∨  y1)) ≡ (x2 ∨  y2)
(¬(x2 ∨  y2)) ≡ (x3 ∨  y3)

(¬(x5 ∨  y5)) ≡ (x6 ∨  y6)

Подобные задания для тренировки

* Аналогичное задание находится в сборнике «Типовые экзаменационные варианты», Крылов С.С., Чуркина Т.Е. 2019 года, вариант 7.

Ответ: 54

Показать решение (с использованием метода побитовая маска):

  • Поскольку в скобках одинаковые действия, и переменные повторяются, то введем обозначения:
  • ¬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
    

📹 Видео


Разбор 23 задания ЕГЭ по информатике 2017 года ФИПИ вариант 3 (Крылов С.С., Чуркина Т.Е.):

Сколько существует различных наборов значений логических переменных x1, x2, … x9, y1, y2, … y9, которые удовлетворяют всем перечисленным ниже условиям?

(¬(x1 ∧  y1)) ≡ (x2 ∧  y2)
(¬(x2 ∧  y2)) ≡ (x3 ∧  y3)

(¬(x8 ∧  y8)) ≡ (x9 ∧  y9)

В качестве ответа Вам нужно указать количество таких наборов.

Подобные задания для тренировки

* Аналогичное задание находится в сборнике «Типовые экзаменационные варианты», Крылов С.С., Чуркина Т.Е. 2019 года, вариант 9.


Ответ: 324

Показать решение (использование метода побитовая маска):

  • Поскольку в скобках одинаковые действия, и переменные повторяются, то введем обозначения:
  • ¬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
    

📹 Видео


Разбор 23 задания ЕГЭ по информатике 2017 года ФИПИ вариант 5 (Крылов С.С., Чуркина Т.Е.):

Сколько существует различных наборов значений логических переменных x1, x2, … x8, y1, y2, … y8, которые удовлетворяют всем перечисленным ниже условиям?

¬(((x1 ∧  y1) ≡ (x3 ∧  y3)) → (x2 ∧  y2))
¬(((x2 ∧  y2) ≡ (x4 ∧  y4)) → ¬(x3 ∧  y3))
¬(((x3 ∧  y3) ≡ (x5 ∧  y5)) → (x4 ∧  y4))
¬(((x4 ∧  y4) ≡ (x6 ∧  y6)) → ¬(x5 ∧  y5))
¬(((x5 ∧  y5) ≡ (x7 ∧  y7)) → (x6 ∧  y6))
¬(((x6 ∧  y6) ≡ (x8 ∧  y8)) → ¬(x7 ∧  y7))

В качестве ответа Вам нужно указать количество таких наборов.

Подобные задания для тренировки

* Аналогичное задание находится в сборнике «Типовые экзаменационные варианты», Крылов С.С., Чуркина Т.Е., 2019 года, вариант 11.

Ответ: 81

Показать решение (с использованием метода побитовая маска):

  • Поскольку в скобках одинаковые действия, и скобки повторяются в разных уравнениях, то введем обозначения. Обозначим латинскими буквами в алфавитном порядке скобки с переменными согласно их номерам:
  • 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. Избавимся от импликации:
    2. было:  ¬((a ≡ c) → b)
      стало: ¬(¬(a ≡ c) ∨ b)
      
    3. По закону Де Моргана избавимся от отрицания над общей внешней скобкой:
    4. было:  ¬(¬(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 набор значений
    

📹 Видео


Разбор 23 задания ЕГЭ по информатике демоверсия 2018 года ФИПИ:

Сколько существует различных наборов значений логических переменных x1, x2, … x7, y1, y2, … y7, которые удовлетворяют всем перечисленным ниже условиям?

(¬x1 ∨ y1) → (¬x2 ∧ y2) = 1
(¬x2 ∨ y2) → (¬x3 ∧ y3) = 1

(¬x6 ∨ y6) → (¬x7 ∧ y7) = 1

В качестве ответа Вам нужно указать количество таких наборов.

Ответ: 22

Показать решение (используется метод отображения):

  • Внешняя операция в отдельно взятом уравнении — это импликация, результат которой должна быть истина. Импликация истинна если:
  • 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:
  • решение 23 задания демоверсия 2018

  • Поскольку уравнения однотипные и отличаются только сдвигом номеров переменных на единицу, то будем использовать метод отображения. Для первого уравнения x1 и y1 будут обозначаться xi и yi, а x2 и y2 будут обозначаться xi+1 и yi+1.
  • задание 23 егэ демоверсия 2018 решение

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

  • В итоге получаем:
  • 1 + 19 + 1 + 1 = 22

📹 Видео


Решение 23 задания ЕГЭ по информатике 2018 (диагностический вариант, С.С. Крылов, Д.М. Ушаков, Тренажер ЕГЭ 2018 года):

Сколько различных решений имеет уравнение:

(a → b) ∨ (c → ¬d) ∨ ¬(e ∨ a ∨ c) = 1

где a, b, c, d, e — логические переменные?

В качестве ответа указать количество таких наборов.


Ответ: 30

Показать решение:

  • Внешняя логическая операция — — дизъюнкция. Таблица истинности:
  • 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
    


Разбор 23 задания демоверсии егэ по информатике 2019:

Сколько существует различных наборов значений логических переменных x1, x2, … x7, y1, y2, … y7, которые удовлетворяют всем перечисленным ниже условиям?

(y1 → (y2 ∧ x1)) ∧ (x1 → x2) = 1
(y2 → (y3 ∧ x2)) ∧ (x2 → x3) = 1
…
(y6 → (y7 ∧ x6)) ∧ (x6 → x7) = 1
y7 → x7 = 1

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


Ответ: 36

Показать решение:

  • Поскольку все равенства однотипны (кроме последнего), отличаются только сдвигом номеров переменных на единицу, то для решения будем использовать метод отображения: когда, найдя результат для первого равенства, необходимо применить тот же принцип с последующими равенствами, учитывая полученные результаты для каждого из них.
  • Рассмотрим первое равенство. В нем внешняя операция — это конъюнкция, результат которой должна быть истина. Конъюнкция истинна если:
  • 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, то строк будет 24 = 16. Выделим те строки, которые возвращают ложь:
  • решение 23 задания демоверсии егэ 2019

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

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

  • Теперь вернемся к последнему равенству. По условию оно должно быть истинным. Равенство вернет ложь только в одном случае:
  • y7=1 → x7=0 = 0
    
  • Найдем соответствующие переменные в нашей таблице:2
  • Рассчитаем сумму по последнему столбцу, не учитывая строку, возвращающую ложь:
  • 1 + 7 + 28 = 36

📹 Видео


Разбор 23 задания ЕГЭ по информатике «Типовые экзаменационные варианты», Крылов С.С., Чуркина Т.Е., 2019, вариант 16 (ФИПИ):

Сколько существует различных наборов значений логических переменных x1, x2, … x6, y1, y2, … y6, которые удовлетворяют всем перечисленным ниже условиям?

¬(((x1 ∧  y1)) ≡ (x2 ∧  y2)) → (x3 ∧  y3))
¬(((x2 ∧  y2)) ∨ ¬(x3 ∧  y3)) → (x4 ∧  y4))
¬(((x3 ∧  y3)) ≡ (x4 ∧  y4)) → (x5 ∧  y5))
¬(((x4 ∧  y4)) ∨ ¬(x5 ∧  y5)) → (x6 ∧  y6))

В качестве ответа Вам нужно указать количество таких наборов.

Подобные задания для тренировки

Ответ: 810

Показать решение:

  • Поскольку в малых скобках везде одна и та же операция (), и переменные в скобках не пересекаются, то можно выполнить замену:
  • ¬((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 решений

📹 Видео


Разбор 23 задания ЕГЭ по информатике «Типовые экзаменационные варианты», Крылов С.С., Чуркина Т.Е., 2019, вариант 2 (ФИПИ):

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

¬(x1 ≡ x2) → (x3 ∧  x4) = 0
¬(x3 ≡ x4) → (x5 ∧  x6) = 0
¬(x5 ≡ x6) → (x7 ∧  x8) = 0
¬(x7 ≡ x8) → (x9 ∧  x10) = 0
¬(x9 ≡ x10) → (x11 ∧  x12) = 0
(x1 ≡ x4) ∨ (x5 ≡ x8) ∨ (x2 ≡ x12) = 1

В качестве ответа Вам нужно указать количество таких наборов.

Ответ: 84

Показать решение:

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

  • В последнем уравнении ((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
    
  • Построим таблицу отображений отдельно для каждой получившейся строки, учитывая значения операндов (xn):



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

Поделитесь уроком с коллегами и друзьями:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

*
*


Вставить формулу как
Блок
Строка
Дополнительные настройки
Цвет формулы
Цвет текста
#333333
Используйте LaTeX для набора формулы
Предпросмотр
\({}\)
Формула не набрана
Вставить