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

На уроке рассмотрено решение 23 задания ЕГЭ по информатике: дается подробное объяснение и разбор задания 2017 года

Объяснение задания 23 ЕГЭ по информатике

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

Элементы алгебры логики: преобразования логических выражений

Для выполнения 23 задания ЕГЭ необходимо повторить следующие темы и понятия:

Разные типы заданий 23 и их решение от простого к сложному:

1. Одно уравнение с непересекающимися операндами внешней операции и одним вариантом решения:

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

    переменные не пересекаются

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

  • Результат истинен (равен единице) для операции дизъюнкция (логическое сложение) имеет 3 решения (01, 10 и 11):
  • решения системы для 23 задания

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

2. Одно уравнение с непересекающимися операндами внешней операции и несколькими вариантами решения

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

    2

  • Так как внешняя операция — дизъюнкция (логическое сложение), результат истинен (равен единице) в трех случаях: 01, 10 11. То есть мы имеем три решения для внешней операции.
  • Переменные не пересекаются, значит, ищем отдельные решения для двух уравнений, НО! для трех случаев:
  • системы уравнений

  • Результат единица для операции конъюнкция (логическое умножение) имеет 1 решение (11), а результат ноль — 3 решения (00, 01 и 10):
  • Одно уравнение с непересекающимися операндами

  • Поскольку для двух уравнений решения в трех случаях «работать» одновременно не могут, то результат — это сложение трех решений:
  • 3 + 3 + 1 = 7

3. Одно уравнение с пересекающимися операндами внешней операции

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

    уравнение с пересекающимися операндами внешней операции

  • Так как внешняя операция — импликация, результат ложен (равен нулю) в одном случае (1 → 0). То есть мы имеем одно решение для внешней операции.
  • Составим систему уравнений:
  • 1

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

  • Рассмотрим каждый случай отдельно и учтем его результаты для второго уравнения системы:
  • 1

  • Поскольку для двух уравнений решения в трех случаях не могут «работать» одновременно, то результат — это сложение трех решений:
  • 4 + 3 + 3 = 10

    4. Несколько уравнений: метод отображения решений уравнения

    Сколько существует различных наборов значений логических переменных?

    Метод отображения можно использовать:

    1. Если структура всех уравнения аналогична, и меняются лишь неизвестные.
    2. Если какие-либо операнды внешней операции первого уравнения повторяются во втором, второго — в третьем, и т.д.
    3. метод отображения при решении 23 задания

    Пример решения

    5. Несколько уравнений: использование битовых масок

    Сколько существует различных наборов значений логических переменных?

    Побитовая маска (битовая маска) — метод, который можно использовать:

    1. Если при рассмотрении одного из уравнений в нем не обнаружены пересекающиеся переменные внешней операции (случай когда одна из переменных первого операнда встречается во втором операнде уже не подходит).
    2. Если структура всех уравнения аналогична, и меняются лишь неизвестные.
    3. Если какие-либо операнды внешней операции первого уравнения повторяются во втором, второго — в третьем, и т.д.
    4. метод битовых масок при решении 23 задания

    Пример решения

    Решение 23 заданий ЕГЭ по информатике


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

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

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

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

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

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


    ✍ Решение с использованием метода побитовая маска:

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

    Подробное объяснение данного задания смотрите на видео:



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

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

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

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

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

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

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


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

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

    Предлагаем посмотреть видео с решением данного 23 задания:



    23_3: Разбор 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.


    ✍ Решение с использованием метода побитовая маска:

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

    Результат: 81

    Для закрепления материала рекомендуем посмотреть видео с разбором данного 23 задания:



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

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

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

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

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


    ✍ Решение, используется метод отображения:

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

    Результат: 22

    Видеоразбор демоверсии 2018 23 задания смотрите здесь:



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

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

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

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

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


    ✍ Решение:

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




    23_6: Разбор 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, при которых выполнена данная система равенств.
    В качестве ответа Вам нужно указать количество таких наборов.


    ✍ Решение:

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

    Результат: 36

    Видео решения 23 задания демоверсии егэ 2019:



    23_7: Разбор 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))

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

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


    ✍ Решение:
     

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

    Доступен видеоразбор задания 23:



    23_8: Разбор 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

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


    ✍ Решение:
     

    • В первых пяти выражениях имеем импликацию, которая ложна. Импликация ложна в единственном случае 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

    Ответ: 84


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

      Andy

      У вас тут ошибка:
      «3. Одно уравнение с пересекающимися операндами внешней операции
      Так как внешняя операция импликация, результат равен нулю в одном случае (0 → 1). То есть мы имеем одно решение для внешней операции. »
      А должно быть (1 → 0).

        Yan

        Поддерживаю,тоже хотел написать но ты опередил)

        admin

        Спасибо! Исправлено)

      Tir

      Касаясь последнего, почему 00 тоже подходит, если в следующем, в эквиваленции со знаком «не», оно даст 0 и импликация будет истинна? То есть, ¬(x1 ≡ x2) → (0 ∧ 0) = 0
      ¬(0 ≡ 0) → (0 ∧ 0) = 1

      Роман

      добрый день, а где решение на последнее задание?
      Не совсем понятно…

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

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

    *
    *


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