Урокът разгледа решението на задача 23 от изпита по информатика: дадено е подробно обяснение и анализ на задачата от 2017 г.
23-та задача - "Преобразуване на логически изрази" - се характеризира като задача с високо ниво на сложност, времето за изпълнение е приблизително 10 минути, максималната оценка е 1
Елементи на алгебрата на логиката: трансформации на логически изрази
За изпълнение на задача 23 от изпита е необходимо да се повторят следните теми и понятия:
- Помислете за тема.
- Помислете за тема.
Има 23 различни вида задачи и тяхното решение от прости до сложни:
1. Едно уравнение с непресичащи се операнди на външната операция и едно решение:
2. Едно уравнение с непресичащи се операнди на външната операция и няколко решения
3. Едно уравнение с пресичащи се операнди на външната операция
4. Няколко уравнения: метод за показване на решения на уравнение
Методът на показване може да се използва:
5. Множество уравнения: Използване на битови маски
Bitmask (bitmask) е метод, който може да се използва:
Решаване на 23 USE задачи по информатика
Анализ на 23-те задачи на Единния държавен изпит по информатика 2017 FIPI вариант 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 | Е |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Резултат: 54
За подробно обяснение на тази задача вижте видеоклипа:
23_2: Анализ на 23-те задачи на Единния държавен изпит по информатика 2017 FIPI вариант 3 (Крилов С.С., Чуркина Т.Е.):
Колко различни набора от булеви стойности има x1, x2, … x9, y1, y2, … y9които отговарят на всички изброени по-долу условия?
(¬(x1 ∧ y1)) ≡ (x2 ∧ y2)
(¬(x2 ∧ y2)) ≡ (x3 ∧ y3)
…
(¬(x8 ∧ y8)) ≡ (x9 ∧ y9)
* Подобна задача е в колекцията "Типични варианти на преглед", Крилов С.С., Чуркина Т.Е. 2019 версия 9.
✍ Решение (използвайки метода на битовата маска):
- Тъй като действията в скоби са еднакви и променливите се повтарят, въвеждаме нотацията:
| x1 | x2 | Е |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Това означава, че за едно условие не може да има такъв случай, че а=0и b=0или а=1и b=1.
Резултат: 324
Предлагаме ви да видите видео с решението на тази 23 задача:
23_3: Анализ на 23-те задачи на Единния държавен изпит по информатика 2017 FIPI вариант 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.
✍ Решение, използващо метода на битовата маска:
- Тъй като скобите са едни и същи действия и скобите се повтарят в различни уравнения, въвеждаме обозначението. Нека обозначим скоби с променливи с латински букви по азбучен ред според техните номера:
- Нека се отървем от внушението: Беше: ¬((a ≡ c) → b)стана: ¬(¬(a ≡ c) ∨ b)
- Съгласно закона на Де Морган, ние се отърваваме от отрицанието над общата външна скоба: Беше: ¬(¬(a ≡ c) ∨ b)стана: (a ≡ c) ∧ ¬b
Това означава, че всички операнди след конюнкцията трябва да са верни.
Резултат: 81
23_4: Анализ на 23-те задачи на USE по информатика демо версия на 2018 FIPI:
Колко различни набора от булеви стойности има 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
Резултат: 22
Видео анализ на демо версия 2018 23 задачи вижте тук:
23_5: Решение 23 на задачата USE по информатика 2018 (диагностична опция, S.S. Krylov, D.M. Ushakov, USE симулатор 2018):
Колко различни решения има уравнението:
(a → b) ∨ (c → ¬d) ∨ ¬(e ∨ a ∨ c) = 1
където а б В Г Д- Булеви променливи?
Като отговор посочете броя на тези комплекти.
✍ Решение:
- Външна логическа операция − ∨ - дизюнкция. Таблица на истината:
Резултат: 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, при които е изпълнена дадената система от равенства.
Като отговор трябва да посочите броя на тези комплекти.
✍ Решение:
- Тъй като всички равенства са от един тип (с изключение на последното), те се различават само в изместването на номерата на променливите с единица, тогава ще използваме метода на картографиране за решението: когато, след като намерим резултата за първото равенство , е необходимо да се приложи същия принцип с последващи равенства, като се вземат предвид резултатите, получени за всяко от тях.
- Разгледайте първото равенство. При него външната операция е конюнкция, резултатът от която трябва да е верен. Конюнкцията е вярна, ако:
Резултат: 36
Видео решение за 23 задачи от демо версията на изпита 2019:
23_7: Анализ на 23 задачи от Единния държавен изпит по информатика „Типови изпитни опции“, Крилов С.С., Чуркина Т.Е., 2019 г., опция 16 (FIPI):
Колко различни набора от булеви стойности има 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
Наличен е видео анализ на задача 23:
23_8: Анализ на 23 задачи от Единния държавен изпит по информатика „Типови изпитни опции“, Крилов С. С., Чуркина Т. Е., 2019 г., вариант 2 (FIPI):
Колко различни набора от булеви стойности има 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
Като отговор трябва да посочите броя на тези комплекти.
✍ Решение:
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
Носкин Андрей Николаевич,
IT-учител
най-висока квалификационна категория,
Кандидат на военните науки, доцент
GBOU лицей №1575 Москва
Оптимизиран метод за картографиране за решаване на задача 23 от KIM USE по информатика и ИКТ
Една от най-трудните задачи в KIM USE е задача 23, в която трябва да намерите броя на различните набори от стойности на логически променливи, които отговарят на определеното условие.
Тази задача е може би най-трудната задача на KIM USE по информатика и ИКТ. По правило с него се справят не повече от 5% от изследваните (1).
Толкова малък процент от учениците, изпълнили тази задача, се обяснява със следното:
- учениците могат да объркат (забравят) знаците на логическите операции;
- математически грешки в процеса на извършване на изчисления;
- грешки в разсъжденията при търсене на решение;
- грешки в процеса на опростяване на логически изрази;
- учителите препоръчват решаването на този проблем след приключване на цялата работа, тъй като вероятността да се направи предположение
грешките са много високи, а „тежестта“ на задачата е само един основен резултат.
Освен това на някои учители им е трудно да решават този тип проблеми и затова се опитват да решават по-прости проблеми с децата.
Също така усложнява ситуацията, че в този блок има голям брой различни задачи и е невъзможно да се избере някакво шаблонно решение.
За да коригира тази ситуация, педагогическата общност финализира основните два метода за решаване на проблеми от този тип: решаване с битови вериги (2) и метод на картографиране (3).
Необходимостта от усъвършенстване (оптимизиране) на тези методи се дължи на факта, че задачите постоянно се променят както в структурата, така и в броя на променливите (само един тип променливи X, два типа променливи X и Y, три типа: X, Y , Z).
Сложността на овладяването на тези методи за решаване на проблеми се потвърждава от факта, че на уебсайта на K.Yu. Поляков, има анализ на този тип задачи в размер на 38 броя (4). В някои анализи се дава повече от един тип решение на проблема.
Наскоро в KIM USE в компютърните науки има проблеми с два типа променливи X и Y.
Оптимизирах метода на показване и предлагам на моите ученици да използват подобрения метод.
Това дава резултат. Процентът на моите ученици, които изпълняват тази задача, варира до 43% от преминалите. По правило всяка година изпит по информатика полагат от 25 до 33 души от всички 11 класове.
Преди появата на задачи с два вида променливи методът на показване се използваше от учениците много успешно, но след появата в логическия израз Y започнах да забелязвам, че отговорите на децата вече не съвпадат с тестовете. Оказа се, че те не разбират съвсем ясно как да създадат таблица за картографиране с нов тип променлива. Тогава ми хрумна мисълта, че за удобство е необходимо целият израз да бъде приведен към един тип променлива, както е удобно за децата.
Нека опиша този метод по-подробно. За удобство ще го разгледам на примера на система от логически изрази, дадена в (4).
Колко различни решения има системата от логически уравнения
(х 1 ^ y1)=(¬x 2 V ¬
г 2
)
(x2 ^ y2)= (¬
х 3
V ¬
г 3
)
...
(x5 ^ y 5)
= (¬
х 6
V ¬
г 6
)
Решение:
1. От анализа на системата от логически уравнения виждаме, че има 6 променливи хи 6 променливи При. Тъй като всяка от тези променливи може да приема само две стойности (0 и 1), ние ще заменим тези променливи с 12 променливи от същия тип, например Z.
2. Сега нека пренапишем системата с нови променливи от същия тип. Сложността на задачата ще се крие във внимателната нотация при промяна на променливите.
(z1 ^ z2)=
(¬z 3V¬
z 4
)
(z3 ^ z4)=
(¬
z 5
V¬
z 6
)
...
(z9 ^ z 10)
=
(¬
z 11
V¬
z 12)
3. Нека изградим таблица, в която ще сортираме всички опции z 1 , z 2 , z 3 , z 4 , тъй като в първото логическо уравнение има четири променливи, таблицата ще има 16 реда (16=2 4); премахнете такива стойности от таблицата z 4 , за които първото уравнение няма решение (задраскани числа).
| 0 | 0 | 0 | 0 |
| 1 | |||
| 1 | 0 | ||
| 1 | |||
| 1 | 0 | 0 | |
| 1 | |||
| 1 | 0 | ||
| 1 | |||
| 1 | 0 | 0 | 0 |
| 1 | |||
| 1 | 0 | ||
| 1 | |||
| 1 | 0 | 0 | |
| 1 | |||
| 1 | 0 | ||
| 1 |
4. Анализирайки таблицата, изграждаме правило за показване на двойки променливи (например двойка З 1 З 2 =00 съвпадениядвойка З 3 З 4 = 11) .
5. Попълнете таблицата, като изчислите броя на двойките променливи, за които системата има решение. 
6. Съберете всички резултати: 9 + 9 + 9 + 27 = 54
7. Отговор: 54.
Горният оптимизиран метод за решаване на задача 23 от KIM USE позволи на студентите да възвърнат увереността си и успешно да решат този тип задачи.
Литература:
1. ФИПИ. Методически препоръки за учители, изготвени въз основа на анализ на типичните грешки на участниците в ЕГИ по ИНФОРМАТИКА и ИКТ за 2015 г. Режим на достъп: http://www.fipi.ru/sites/default/files/document/1442163533/informatika_i_ikt.pdf
2. К.Ю. Поляков, М.А. Ройтберг.Системи логически уравнения: решение с битови низове. сп. Информатика, бр. 12, 2014, с. 4-12.Издателство "Първи септември", Москва.3. Е.А. Мирончик, Метод на показване.Списание Информатика, бр.10, 2013, с. 18-26. Издателство "Първи септември", Москва.
Решаване на системи от логически уравнения чрез промяна на променливи
Методът за промяна на променливите се използва, ако някои променливи са включени в уравненията само под формата на конкретен израз и нищо друго. Тогава този израз може да бъде обозначен с нова променлива.
Пример 1
Колко различни набора от стойности на логически променливи x1, x2, x3, x4, x5, x6, x7, x8 има, които отговарят на всички от следните условия?
(x1 → x2) → (x3 → x4) = 1
(x3 → x4) → (x5 → x6) = 1
(x5 → x6) → (x7 → x8) = 1
Отговорът не трябва да изброява всички различни набори от стойности на променливите x1, x2, x3, x4, x5, x6, x7, x8, при които тази система от равенства е изпълнена. Като отговор трябва да посочите броя на тези комплекти.
Решение:
(x1 → x2) = y1; (x3 → x4) = y2; (x5 → x6) = y3; (x7 → x8) = y4.
Тогава системата може да се напише като едно уравнение:
(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Конюнкцията е 1 (вярно), когато всеки операнд дава оценка на 1. Това е, всяко от импликациите трябва да е вярно и това е вярно за всички стойности с изключение на (1 → 0). Тези. в таблицата със стойности на променливите y1, y2, y3, y4 единицата не трябва да е отляво на нулата:
Тези. условията са изпълнени за 5 комплекта y1-y4.
защото y1 = x1 → x2, тогава стойността y1 = 0 се постига на един набор x1, x2: (1, 0), а стойността y1 = 1 се постига на три набора x1, x2: (0,0) , ( 0,1), (1.1). По същия начин за y2, y3, y4.
Тъй като всеки набор (x1,x2) за променлива y1 се комбинира с всеки набор (x3,x4) за променлива y2 и т.н., броят на наборите от променливи x се умножава:
|
Брой комплекти на x1…x8 |
||||
Нека добавим броя на комплектите: 1 + 3 + 9 + 27 + 81 = 121.
Отговор: 121
Пример 2
Колко различни набора от стойности на булеви променливи x1, x2, ... x9, y1, y2, ... y9 има, които отговарят на всички от следните условия?
(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)
(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)
(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)
В отговор няма нуждаизбройте всички различни набори от стойности на променливите x1, x2, ... x9, y1, y2, ... y9, при които е изпълнена дадената система от равенства. Като отговор трябва да посочите броя на тези комплекти.
Решение:
Нека направим промяна на променливите:
(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9
Системата може да се напише като едно уравнение:
(¬z1 ≡ z2) ∧ (¬z2 ≡ z3) ∧ …..∧ (¬z8 ≡ z9)
Еквивалентността е вярна само ако и двата операнда са равни. Решенията на това уравнение ще бъдат две групи:
| z1 | z2 | z3 | z4 | z5 | z6 | z7 | z8 | z9 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
защото zi = (xi ≡ yi), тогава стойността zi = 0 съответства на две групи (xi,yi): (0,1) и (1,0), а стойността zi = 1 съответства на две групи (xi,yi ): (0 ,0) и (1,1).
Тогава първият набор z1, z2,…, z9 съответства на 2 9 набора (x1,y1), (x2,y2),…, (x9,y9).
Същият номер съответства на втория набор z1, z2,…, z9. Тогава има общо 2 9 +2 9 = 1024 комплекта.
Отговор: 1024
Решаване на системи от логически уравнения чрез визуална дефиниция на рекурсия.
Този метод се използва, ако системата от уравнения е достатъчно проста и редът на увеличаване на броя на наборите при добавяне на променливи е очевиден.
Пример 3
Колко различни решения има системата от уравнения
¬x9 ∨ x10 = 1,
където x1, x2, ... x10 са булеви променливи?
Отговорът не трябва да изброява всички различни набори от стойности x1, x2, ... x10, за които е валидна дадената система от равенства. Като отговор трябва да посочите броя на тези комплекти.
Решение:
Нека решим първото уравнение. Дизюнкцията е равна на 1, ако поне един от нейните операнди е равен на 1. Тоест, решенията са множествата:
За x1=0 има две x2 стойности (0 и 1), а за x1=1 има само една x2 стойност (1), така че множеството (x1,x2) е решението на уравнението. Само 3 комплекта.
Нека добавим променливата x3 и да разгледаме второто уравнение. Подобно е на първото, което означава, че за x2=0 има две стойности на x3 (0 и 1), а за x2=1 има само една стойност на x3 (1), така че множеството ( x2,x3) е решение на уравнението. Има общо 4 комплекта.
Лесно се вижда, че при добавяне на друга променлива се добавя един набор. Тези. рекурсивна формула за броя на комплектите на (i+1) променливи:
N i +1 = N i + 1. Тогава за десет променливи получаваме 11 комплекта.
Отговор: 11
Решаване на системи от логически уравнения от различни видове
Пример 4
Колко различни набора от стойности на булеви променливи x 1 , ..., x 4 , y 1 ,..., y 4 , z 1 ,..., z 4 има, които отговарят на всички от следните условия?
(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) = 1
(y 1 → y 2) ∧ (y 2 → y 3) ∧ (y 3 → y 4) = 1
(z 1 → z 2) ∧ (z 2 → z 3) ∧ (z 3 → z 4) = 1
x 4 ∧ y 4 ∧ z 4 = 0
В отговор няма нуждаизбройте всички различни набори от стойности на променливите x 1 , ..., x 4 , y 1 , ..., y 4 , z 1 , ..., z 4 , при които е изпълнена дадената система от равенства .
Като отговор трябва да посочите броя на тези комплекти.
Решение:
Обърнете внимание, че трите уравнения на системата са еднакви за различни независими набори от променливи.
Разгледайте първото уравнение. Една конюнкция е вярна (равна на 1) само ако всички нейни операнди са верни (равни на 1). Импликацията е 1 за всички набори с изключение на (1,0). Това означава, че решението на първото уравнение ще бъдат такива набори x1, x2, x3, x4, в които 1 не е отляво на 0 (5 комплекта):
По същия начин, решенията на второто и третото уравнение ще бъдат точно същите набори от y1,…,y4 и z1,…,z4.
Сега нека анализираме четвъртото уравнение на системата: x 4 ∧ y 4 ∧ z 4 = 0. Решението ще бъдат всички множества x4, y4, z4, в които поне една от променливите е равна на 0.
Тези. за x4 = 0 са подходящи всички възможни набори (y4, z4), а за x4 = 1 са подходящи набори (y4, z4), които съдържат поне една нула: (0, 0), (0,1) , ( 1, 0).
|
Брой комплекти |
||||
Общият брой комплекти е 25 + 4*9 = 25 + 36 = 61.
Отговор: 61
Решаване на системи от логически уравнения чрез построяване на рекурентни формули
Методът за конструиране на рекурентни формули се използва за решаване на сложни системи, в които редът на увеличаване на броя на наборите не е очевиден и изграждането на дърво е невъзможно поради обеми.
Пример 5
Колко различни набора от стойности на булеви променливи x1, x2, ... x7, y1, y2, ... y7 има, които отговарят на всички от следните условия?
(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1
(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1
(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1
Отговорът не трябва да изброява всички различни набори от стойности на променливите x1, x2, ..., x7, y1, y2, ..., y7, при които е валидна дадената система от равенства. Като отговор трябва да посочите броя на тези комплекти.
Решение:
Имайте предвид, че първите шест уравнения на системата са еднакви и се различават само в набора от променливи. Разгледайте първото уравнение. Неговото решение ще бъде следните набори от променливи:
Означават:
брой комплекти (0,0) на променливи (x1,y1) до A 1,
брой комплекти (0,1) на променливи (x1,y1) до B 1,
брой комплекти (1,0) на променливи (x1,y1) чрез C 1,
брой комплекти (1,1) на променливи (x1,y1) чрез D 1 .
брой комплекти (0,0) на променливи (x2,y2) до A 2,
брой комплекти (0,1) на променливи (x2,y2) чрез B 2,
брой комплекти (1,0) на променливи (x2,y2) чрез C 2,
брой комплекти (1,1) на променливи (x2,y2) чрез D 2 .
От дървото на решенията виждаме това
A 1 =0, B 1 =1, C 1 =1, D 1 =1.
Обърнете внимание, че кортежът (0,0) на променливите (x2,y2) се получава от кортежите (0,1), (1,0) и (1,1) на променливите (x1,y1). Тези. A 2 \u003d B 1 + C 1 + D 1.
Множеството (0,1) на променливите (x2,y2) се получава от множествата (0,1), (1,0) и (1,1) на променливите (x1,y1). Тези. B 2 \u003d B 1 + C 1 + D 1.
Като се аргументираме по подобен начин, отбелязваме, че C 2 \u003d B 1 + C 1 + D 1. D2 = D1.
Така получаваме рекурсивни формули:
A i+1 = B i + C i + D i
B i+1 = B i + C i + D i
C i+1 = B i + C i + D i
D i+1 = A i + B i + C i + D i
Да направим маса
| Комплекти | Символ. | Формула |
Брой комплекти |
||||||
| i=1 | i=2 | i=3 | i=4 | i=5 | i=6 | i=7 | |||
| (0,0) | A i | Ai+1 =Bi +Ci +Di | 0 | 3 | 7 | 15 | 31 | 63 | 127 |
| (0,1) | B i | B i+1 = B i + C i + D i | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,0) | C i | C i+1 = B i + C i + D i | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,1) | D i | D i+1 =D i | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Последното уравнение (x7 ∨ y7) = 1 е изпълнено от всички комплекти, с изключение на тези, в които x7=0 и y7=0. В нашата таблица броят на тези набори е A 7 .
Тогава общият брой серии е B 7 + C 7 + D 7 = 127+127+1 = 255
Отговор: 255
