Презентация ЕГЭ Задание 23 метод битовых цепочек

• 1 слайд

  Решение задания №23
  Метод битовых цепочек
  Шумицкая В.Ю, МАОУ Видновская СОШ №9
  

• 2 слайд

  Основные идеи
  Решение системы уравнений – это битовая цепочка (битовый вектор)
  
  
  Битовый вектор рассматривается как единый объект.
  Уравнения – это ограничения на битовый вектор (ограничения на комбинации битов).
  Нужно выделить элементарные уравнения и записать ограничения «на русском языке».
  Количество решений находится по правилам комбинаторики.
  для любого i
  

• 3 слайд

  Возможный обобщенный алгоритм выполнения задания
  Построить таблицу истинности для первого уравнения, определить количество комбинаций, которые являются решением.
  Подключить к этим комбинациям новые переменные из второго уравнения.
  Посмотреть сколько комбинаций добавляет или сокращает второе уравнение.
  Аналогичным образом провести операции с остальными уравнениями.
  Сформулировать ответ.
  
  

• 4 слайд

  Общие рекомендации:
  Эта задача – одна из самых сложных в экзамене,
  Для ее решения ученик должен уметь
  преобразовывать логические выражения (включая выполнение замены переменных);
  переводить формальное описание, в виде системы логических условий, на нормальный, "человеческий" язык;
  подсчитать число двоичных наборов, удовлетворяющих заданным условиям.
  подсчет числа интересующих двоичных наборов
  

• 5 слайд

  Х1+Х2=1
  Х2+Х3=1
  …
  Х9+Х10=1
  
  
  1
  0
  2
  1
  0
  1
  3
  1
  0
  1
  1
  0
  5
  1
  0
  1
  1
  0
  1
  0
  1
  8
  13
  +
  +
  +
  +
  21
  34
  55
  89
  144
  Ответ: 144
  

• 6 слайд

  (Х1≡Х2)→(Х𝟐≡Х𝟑)=1
  (Х2≡Х3)→(Х𝟑≡Х𝟒)=1
  …
  (Х6≡Х7)→(Х𝟕≡Х𝟖)=1
  
  
  2
  4
  6
  8
  10
  12
  14
  16
  Ответ: 16
  0
  0
  0
  0
  0
  0
  0
  0
  0
  0
  1
  1
  1
  1
  1
  1
  1
  1
  1
  1
  

• 7 слайд

  (Х1Х2)V(Х2Х3)=1
  (Х2Х3)V(Х3Х4)=1
  …
  (Х8Х9)V(Х9Х10)=1
  
  1
  0
  2
  1
  0
  1
  0
  4
  1
  0
  0
  1
  1
  0
  6
  1
  0
  0
  1
  0
  1
  0
  1
  1
  0
  10
  16
  +
  +
  +
  +
  26
  42
  68
  110
  178
  Ответ: 178
  

• 8 слайд

  1
  0
  2
  1
  0
  1
  0
  ¬X1 + X2 + X3 = 1
  ¬X2 + X3 + X4 = 1
  …
  ¬X8 + X9 + X10 = 1
  
  
  4
  1
  0
  1
  1
  0
  1
  0
  1
  0
  1
  1
  0
  1
  1
  0
  1
  0
  1
  0
  7
  12
  20
  33
  54
  88
  143
  232
  Ответ: 232
  

• 9 слайд

  Сколько существует различных наборов значений логических переменных x1, x2, ... x10, которые удовлетворяют всем перечисленным ниже условиям?
  
  (x1 ∧ x2) ∨ (¬x1 ∧ ¬x2) ∨ (¬x3 ∧ x4) ∨ (x3 ∧ ¬x4) = 1
  (x3 ∧ x4) ∨ (¬x3 ∧ ¬x4) ∨ (¬x5 ∧ x6) ∨ (x5 ∧ ¬x6) = 1
  ...
  (x7 ∧ x8) ∨ (¬x7 ∧ ¬x8) ∨ (¬x9 ∧ x10) ∨ (x9 ∧ ¬x10) = 1
  
  

• 10 слайд

  2
  4
  8
  12
  24
  32
  64
  80
  160
  192
  *2
  +2
  *2
  +4
  +8
  *2
  *2
  +16
  +32
  Ответ: 192
  

• 11 слайд

  Решить систему уравнений
  (x1 V x2) & (x1 & x2 → x3) & (¬ x1 V y1) = 1
  (x2 V x3) & (x2 & x3 → x4) & (¬ x2 V y2) = 1
  (x3 V x4) & (x3 & x4 → x5) & (¬ x3 V y3) = 1
  (x4 V x5) & (x4 & x5 → x6) & (¬ x4 V y4) = 1
  (x5 V x6) & (x5 & x6 → x7) & (¬ x5 V y5) = 1
  (x6 V x7) & (x6 & x7 → x8) & (¬ x6 V y6) = 1
  (x7 V x8) & (¬ x7 V y7) = 1
  ¬ x8 V y8 = 1
  
  Ответ: 61
  

• 12 слайд

  Спасибо за внимание!