Об одном способе решения систем логических уравнений

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 004. 023
Семенов Сергей Максимович
Владивостокский государственный университет экономики и сервиса Россия. Владивосток
Об одном способе решения систем логических уравнений
Рассматривается способ определения количества решений системы логических уравнений. Способ основан на построении дерева решений и определении рекуррентных соотношений для уровня N. Применение разработанного способа обеспечивает конструктивный подход к решению задачи В15 ЕГЭ.
Ключевые слова и словосочетания: системы логических уравнений, дерево решений, рекуррентные соотношения, B15, ЕГЭ.
На практике системы логических уравнений [1] полезны при разработке цифровых логических устройств [2]. Решению систем логических уравнений посвящена одна из задач ЕГЭ по информатике. К сожалению, различные известные способы решения этой задачи не позволяют сформировать какой-то один подход к решению этой задачи. В результате решение задачи вызывает большие затруднения у выпускников. Мы предлагаем способ решения систем логических уравнений, который позволяет выпускнику следовать вполне определенному алгоритму. Идея этого способа изложена в [2]. Мы применили и развили данную идею (построение дерева решений), почти не используя таблицы истинности для всего дерева. При решении различных задач выяснилось, что количество решений многих систем логических уравнений подчиняется рекуррентным соотношениям, таким, как числа Фибоначчи и др.
Системы логических уравнений. Будем придерживаться следующих обозначений: дизъюнкция (+), конъюнкция (•), исключающее ИЛИ ((c)), импликация (-& gt-¦), эквивалентность (=), отрицание (-¦). На рисунках темный кружок обозначает 1, а светлый кружок — 0. Fl — количество решений при Х1, равном 1. Fo — количество решений при Х1, равном 0. N — число переменных в системе уравнений. F (N) = F1(N) + F0(N) — общее число решений.
Задание 1. Нужно найти количество решений системы уравнений ([1], тест № 2)
Х1+Х2-Хз=1
Х2+Хз'-Х4=1
Х7+Х8'-Х9=1
181
Вначале полагаем Х1 = 1. Тогда для первого уравнения значения Х2 и Хз могут быть любыми. Таким образом, дерево построено до третьего уровня. Далее с учетом Х2 и Хз выбираем Х4. После этого алгоритм повторяется для каждой тройки переменных (рис. 1). Начиная с четвертого уровня можно заметить, что Fl (4)=Fl (3)+Fl (1), Fl (5)=Fl (4)+Fl (2). Таким образом, получаем Fl (N) = Fl (N-1) + Fl (N-3) (1)
Рис. 1. Задание 1
Из уравнения (1) следует:
Бх (8) = 16 + 7 = 23,
Fl (9) = 23 + 11 = 34.
Чтобы построить дерево из нуля, можно воспользоваться нижней ветвью из рис. 1. Легко видеть, что она повторяет основное дерево, но со сдвигом вправо на 2, то есть
Fo (9)=Fl (7)=16.
Итого, F (9) = Fl (9) + Fo (9) = 34 + 16 = 50.
При построении дерева решений можно визуально установить рекуррентные соотношения для определения количества решений на уровне N.
Принцип математической индукции гласит: пусть имеется последовательность утверждений Fl, F2, Fз и пусть первое утверждение Fl верно. Мы можем доказать, что из верности утверждения FN следует верность FN+l. Тогда все утверждения в этой последовательности верны.
Рассмотрим рис. 2 для задания 1.
182
к2 & gt-3×5 хб Х7
Рис. 2. Анализ дерева решений
На рисунке 2 выделены фигуры, имеющие общую вершину (комбинации значений переменных) для первых пяти уравнений системы. В каждом уравнении задействованы три переменных, поэтому фигуры составляются из значений трех переменных (трех уровней дерева). Для того чтобы идентифицировать фигуры, можно было бы ввести обозначения. Однако мы поступим следующим образом: каждой фигуре поставим в соответствие количество составляющих ее кружков (значений переменных). Тогда получим для последовательности следующие уравнения:
1. 7
2. 7, 4
3. 7, 4, 4, 1
4. 7, 4, 4, 1, 7
5. 7, 4, 4, 1, 7, 7, 4.
С уравнения 4 можно видеть, что фигуры для уравнения N состоят из фигур уравнения N-1 и фигур уравнения N-3. Важно, что других фигур нет и быть не может для данного типа уравнений, то есть переход от одного уравнения к другому производится путем увеличения числа фигур из ограниченного набора по строго определенным правилам. Этот факт и является основным для того, чтобы утверждать по индукции, что для уравнения N+1 набор фигур будет состоять из фигур уравнения N и фигур уравнения N-2.
183
Другим способом идентификации фигур является определение количества значений переменных на последнем уровне для данного уравнения, то есть нужно перейти от номера уравнения к номеру уровня дерева, поскольку нам нужно определить количество решений для системы уравнений, Тогда для построенного дерева получим последовательность: 1, 2, 4, 5, 7, 11, 16. Для этой последовательности справедлива формула: FN = FN-1 + FN-3.
В соответствии с нашими рассуждениями эта формула будет верна для N+1, а по индукции и для любого N.
Приведенный способ доказательства можно использовать для любых систем подобного типа. На практике достаточно определять рекуррентное соотношение для уровня N поскольку в основе его лежит ограниченный набор фигур и способов их преобразований при переходе от уравнения, соответствующего уровню N к уравнению, соответствующему уровню N+1.
Задание 2. Нужно найти количество решений системы уравнений ([1], 4. 16)
(Х1=Х2) + (Х1 = Х3) = 1 (Х2=Хз) + (Х2 = Х4) = 1 (Хз=Х4) + (Хз = Х5) = 1 (Х4=Х5) + (Х4 = Х6)=1 (Х5 = Х6) + (Х5 = Х7) = 1
XI Х2 ХЗ & gt-:1 Х5 Хб Х7
Рис. 3. Задание 2
Для получения числа решений задания 2 можно было не строить дерево решений полностью (рис. 3), так как очевидно, что Fl (N) = N. Аналогично, Fo (N) = N. Итого F (7) = 7 + 7 = 14.
Задание 3. Нужно найти количество решений системы уравнений ([1], тест № 1)
(Х1 ^ Х2) ¦ (Х2 ^ Хз) ¦ (Хз ^ Х4) ¦ (Х4 ^ Х5) = 1
(Yl ^ Y2) ¦ (У2 ^ Yз) ¦ (Yз ^ Y4) ¦ (Y4 ^ Y5) = 1
(Yl ^ Х1) ¦ (У2 ^ Х2) ¦ (Yз ^ Хз) ¦ (У4 ^ Х4) ¦ (Y5 ^ Х5) = 1
184
На рисунке 4 показаны деревья решений для X и Y и приведены соответствующие таблицы истинности.
Рис. 4. Задание 3
Из первых двух уравнений, поскольку X и Y независимы, следует, что общее число решений F (5) = 6 * 6 = 36. Для того чтобы учесть третье уравнение, нужно для каждой переменной Y подсчитать, какое число наборов из таблицы X не удовлетворяет уравнению. Импликация Yi ^ Xi = 0, если Yi = 1, а Xi = 0. Иначе говоря, для Yl = 1 третьему уравнению не удовлетворяют все строки из таблицы X, где Х1 = 0. Число таких строк равно 5. Для Y2 = 1 таких строк — 4 и т. д. Общее число строк, которые не удовлетворяют третьему уравнению, равно 5 + 4 + 3 + 2 + 1 = 15.
Таким образом, общее число допустимых решений равно 36 — 15 = 21. Задание 4. Нужно найти количество решений системы уравнений ([1], 4. 17. а)
(Х1=Х2) + (Х1 = Х3) = (Х2 = Х3) + (Х2 = Х4) = (Х4=Х5) + (Х4 = Х6) = (Х5 = Х6) + (Х5 = Х7) = (Хб=Х7) + (Хб = Х8) = (Х5=Х6) = 0
185
Рис. 5. Задание 4
Для данного примера сложно определить конечную формулу F (N), проще построить дерево решений до конца (или хотя бы до Х6). На рисунке 5 показано построенное дерево решений. В результате получаем F (8) = Fl (8) + Fo (8) = 5 + 5 = 10.
Задание 5. Необходимо найти количество решений системы уравнений ([1], 4. 17. б)
(Х1=Х2) + (Х1 = Х3) = 1 (Х2=Х3) + (Х2 = Х4) = 1 (Х3 = Х4) + (Х3 = Х5) = 1 (Х4=Х5) + (Х4 = Х6)=1 (Х5 = Х6) + (Х5 = Х7) = 1 (Х6 = Х8) = 1
Для этого примера, так же как и для предыдущего, проще построить дерево решений до конца (рис. 6). В результате получаем F (8) = Fl (8) + Fo (8) = 7 + 7 = 14.
Задание 6. Нужно найти количество решений системы уравнений ([!]& gt- 4. 17. в)
(Х!8'-Х2) + (Х2ЕХз) = 1 (Х2фХз) + (Хз = Х4) = 1 (Хз8'-Х4) + (Х4 = Х5) = 1 (Х4(c)Х5) + (Х5 = Хб) = 1 (Х5фХб) + (Хб = Х7) = 1 (Хб (c)Х7) + (Х7 = Х8) = 1 Дерево решений показано на рис. 7.
186
XI Х2 ХЗ Х4 Х5 Х6 Х7 Х8 XI Х2 ХЗ Х4 Х5 Х6 Х7 Х8
Рис. 6. Задание 5 Рис. 7. Задание 6
Для данной системы уравнений можно было не строить полное дерево решений, так как уже с третьего — четвертого шага понятно, что F1(N) = N. Легко увидеть, что Fo (N) можно получить из дерева, начинающегося на втором уровне из нуля. Тогда Fo (N) = N. Итого, F (8) = Fl (8) + Fo (8) = 8 + 8 = 16.
Задание 7. Нужно найти количество решений системы уравнений
(Х4ЭХ5) + (Х4 (c)Х6) = 1 (Х5(c)Хб) + (Х5(c)Х7) = 1
Заметим, что если X! = X2 = 1, то первое уравнение выполняется при Xз = 0. Построим сначала дерево для Xl = X2 = 1 (рис. 8). Тогда число решений Fl (N) = Fll (N) + Flo (N).
187
XI Х2 ХЗ Х4 Х5 Х6 Х7 Х8
Рис. 8. Задание 7
Из рисунка 8 видно, что число решений F11(N) = F11(N-1) + F11(N-2). Иначе говоря, число решений описывается числами Фибоначчи. Вторую ветку дерева для F10 можно не строить, так как она получается из рис. 1, начиная со второго уровня. Тогда F10(N) = F11(N+1). Окончательно получаем, что Fll (8) = 1з и Flo (8) = Fll (9) = 1з + 8 = 21. Тогда Fl (8) = Fll (8) + Flo (8) = 1з + 21 = з4.
Для того чтобы получить F0(N), также необязательно строить дерево решений, поскольку оно получается из рис. 1 начиная с третьего уровня. Тогда Fo (N) = Fll (N+2). Отсюда получаем, что Fo (8) = Fll (10) = Fll (9) + Fll (8) = 21 + 1з = з4. Таким образом, общее число решений F (8)= F1(8) + F0(8) = з4 + з4 = 68.
Задание 8. Нужно найти количество решений системы уравнений ([з], Задание 2)
(Х1 + Х2) ^ (Хз + Х4) = 1 (Хз + Х4) ^ (Х5 + Х6) = 1 (Х5 + Х6) ^ (Х7 + Х8) = 1 (Х7 + Х8) ^ (Х9 + Х10) = 1
Сделаем подстановку (Х1 + Х2) = Yl и т. д. и получим систему уравнений:
^ ^ Y2 = 1 Y2 ^ Yз = 1 Yз ^ Y4 = 1 Y4 ^ Y5 = 1
Дерево решений и таблица истинности для этой системы в точности совпадают с деревом и таблицей, изображенными на рис. 4. С учетом подстановки отметим, что выражение (Х1 + Х2) равно единице в трех случаях (за исключением варианта, когда обе переменные равны нулю).
188
Поскольку переменные Y независимы, то для первой строки таблицы истинности, показанной на рис. 4, число различных комбинаций равно 35, для второй строки — 34 и т. д. Общее число различных комбинаций равно 35 + 34 + 33 + 32 + 31 + 30 = 364.
Задание 9. Нужно найти количество решений системы уравнений ([3], Задание 4)
(^ ^ Ъ) ¦ (-X ^ Xз) ¦ № ^ X) ¦ (-X ^ Кз) = 1 № ^ Y2) ¦ (У1 ^ Yз) ¦ (-Г1 ^ Y4) ¦ (У1 ^ Y5) = 1 (-X + Y 1) ¦ (-X + Y5) = 1
Для X и Y имеем следующие деревья решений
X V
Рис. 9. Задание 8
С учетом третьего уравнения получаем следующие четыре набора комбинаций:
А — С: 4 * 4 = 16 ((-?1 + Y 1) ¦ (-X + Y5) = (0 + 1) ¦ (0 + 1) = 1) В — С: 4 * 4 = 16 ((-X + Y 1) ¦ (-X + Y5) = (1 + 1) ¦ (1 + 1) = 1) А — D: = 0 (0 + 0) ¦ (-X + Y5) = 0) В — D: 4 * 4 = 16 (1 + 0) ¦ (1 + Y5) = 1) Всего получается 48 наборов решений.
Задание 10. Нужно найти количество решений системы уравнений [4] (^1 = Ъ) + (Xз = X)) ¦ = Ъ) + -фз = X4)) =1 ((Xз = X4) + (X5 = X6)) ¦ (-(X = X) + -(X = X6)) =1 ((X5 = X6) +7 = X")) ¦ (-(X = X6) + -(^7 = X8)) =1
((X7 = X8) + (X9 = Xlo)) ¦ (-^7 = X8) + = Xlo)) =1 Проведем замену: (Xl = Ъ) = Yl (Xз = X4) = Y2
189
(Х5 = Х) = Yз (Х7 = Х8) = Y4 (Х9 = Х10) = Y5
Перепишем систему уравнений с учетом замены:
2) ¦ (-Ъ + ^)=1
(Y2+Yз) ¦ № + -Тз)=1
(Yз+Y4) ¦ № + ^)=1
(Y4+Y5) ¦ (^4 + ^)=1
На рисунке 10 показано дерево решений
У1 У2 УЗ У4 У5
Рис. 10. Задание 10
С учетом подстановки отметим, что выражение (Х1 = Х2) равно единице (или нулю) в двух случаях (когда значения переменных совпадают). С учетом независимости переменных для каждого дерева получаем, что число наборов решений равно 25 = з2. Общее число наборов решений равно 64.
Задание 11. Нужно найти количество решений системы уравнений ([2], Пример 2)
-Х1 + Х2 = 1 -Х2 + Хз = 1
-Х9 + Х10 = 1
На рисунке 11 показано дерево решений. Мы ограничились четырьмя уровнями вместо десяти, так как очевидно, что F1(N) = 1 и F0(N) = N. Тогда Р (Ы) = Р1(Ы) + БоСЫ) = 1 + N. В нашем случае Р (10) = 1 + 10 = 11.
Рис. 11. Задание 11
Задание 12. Нужно найти количество решений системы уравнений ([2], Пример з)
(Х1 = Х2) + (Х2 = Хз) = 1
190
(Х1 = Хз) + (Хз = Х4) (Х1 = Х4) + (Х4 = Х5) (Х1 = Х5) + (Х5 = Х6) (Х1 = Х6) + (Х6 = Х7) (Х1 = Х7) + (Х7 = Х8) (Х1 = Х) + (Х8 = Х9) (Х1 = Х9) + (Х9 = Х10) (Х1 = Х10) = 0
Рис. 12. Задание 12
Построив дерево решений из «1» (ограничимся пятью уровнями), заметим, что Fl (N) = N. Причем значения Хн состоят из N-1 значений «0» и одного значения «1». Однако последнее уравнение в нашей системе запрещает значение «1″ для Х10. Поэтому число решений Fl (10) = 10 — 1. Нетрудно заметить, что дерево решений из „0″ будет симметричным (вместо нулей будут единицы). Поэтому F0 = 10 — 1. Окончательно
F (N) = 2×9 = 18.
Задание 13. Нужно найти количество решений системы уравнений ([2], Пример 4)
— (Х1 = Х2) + (Хз = Х4) = 1
— (Хз = Х4) + (Х5 = Х) = 1
— (Х = Х) + (Х7 = Х) = 1
— (Х7 = Х8) + (Х9 = Х10) = 1
Проведем замену:
(Х1 = Х2) = Yl
(Хз = X) = Y2
(Х5 = Х) = Yз
(Х7 = Х8) = Y4
(Х9 = Х10) = Y5
Перепишем систему уравнений с учетом замены:
— Yl + Y2 =1
= 1
191
— Y2 + Yз =1
— Yз + Y4 =1
— Y4 + Y5 =1
Из задания 11 видно, что F (5) = 5 + 1 = 6. Таблица истинности представлена на рис. 13.
У1 У2 УЗ У4 У5
1 1 1 1 1

0 1 1 1 1

0 0 1 I 1

0 0 0 1 1

0 0 0 0 1

0 0 0 0 0
Рис. 13. Задание 13
С учетом подстановки отметим, что выражение ^ = X2) равно единице (или нулю) в двух случаях (когда значения переменных совпадают). С учетом независимости переменных для каждой строки таблицы получаем, что число наборов решений равно 25 = 32. Общее число наборов решений равно 6 * 32 = 192.
Задание 14. Нужно найти количество решений системы уравнений ([2], Задание 1)
((Х = Ъ) ¦ (Xз = X4)) + (4X1 = Ъ) ¦ -(X = X)) =0 ((Xз = X4) ¦ (X5 = X6)) + (4X3 = X4) ¦ -(X = X6)) =0
((X5 = X) ¦ (X7 = X8)) + (-(X = X6) ¦ 4X7 = X8)) =0 ((X7 = X8) ¦ (X9 = X“,)) + (-(^7 = X8) ¦9 = Xlo)) =0 Проведем замену:
= Ъ) = Yl (X = ^4) = Y2
(X5 = X6) = Yз7 = X8) = Y49 = Xlo) = Y5
Перепишем систему уравнений с учетом замены:
(УЛ) + (-У» ¦ -У2)=0
(Y2•Yз) + (-У2 ¦ -У3)=0 (У3-У4) + (-У3 ¦ -У4)=0 (У4-У5) + (-У4 ¦ -У5)=0
(У1 = У2) = 0
192
(У2 = Yз) = 0 (Уз = У4) = 0 (У4 = У5) = 0
На рисунке 14 показано дерево решений
У1 У2 УЗ У4 У5
Рис. 14. Задание 14
С учетом подстановки отметим, что выражение (Х1 = Х2) равно единице (или нулю) в двух случаях (когда значения переменных совпадают). С учетом независимости переменных для каждого дерева получаем, что число наборов решений равно 25 = з2. Общее число наборов решений равно 64.
Задание 15. Нужно найти количество решений системы уравнений ([2], Задание 2)
(Х1 Х2) + (-Х1 -Х2) + (Х1 = Хз) = 1
(Х2 Хз) + (-Х -Хз) + (Х2 = Х4) = 1
(Хз Х4) + (-Хз -Х4) + (Хз = Х5) = 1
(Х4 Х5) + (-Х4 -Х5) + (Х4 = Х) = 1
(Х5 Х) + (-Х -Х6) + (Х5 = Х7) = 1
(X Х7) + (-Х -Х7) + (Х = Х8) = 1
(Х7 Х) + (-Х7 -Х8) + (Х7 = Х9) = 1
(Х8 Х9) + (-Х -Х9) + (Х8 = Х10) = 1
Заметим, что систему уравнений можно переписать в виде:
(Х1 = Х2) + (Х1 = Хз) = 1
(Х = Хз) + (Х2 = Х4) = 1
(Хз = Х4) + (Хз = Х5) = 1
(Х4 = Х5) + (Х4 = Х) = 1
(Х5 = Х6) + (Х5 = Х7) = 1
(Х = Х7) + (Х6 = Х8) = 1
(Х7 = Х8) + (Х7 = Х9) = 1
(Х = Х9) + (Х8 = Х10) = 1
Но эта система повторяет систему из задания 5, только без условия ограничения и для N = 10. Тогда число решений равно F (N) = F1(N) + F0(N) = N + N. При N = 10 получаем F (N)= 20.
193
Задание 16. Нужно найти количество решений системы уравнений ([2], Задание 3)
(Х1 Х2) + (-Х1 -Х2) + (Х1 = Хз) = 1
(Х2 Хз) + (-Х -Хз) + (Х2 = Х4) = 1
(Хз Х4) + (-Хз -Х4) + (Хз = Х5) = 1
(Х4 Х5) + (-Х -Х5) + (Х4 = Хб) = 1
(Х5 Хб) + (-Х -Хб) + (Х5 = Х7) = 1
(Хб Х7) + (-Хб -Х7) + (Хб = Х8) = 1
(Х7 Х8) + (-Х7 -Х8) + (Х7 = Х9) = 1
(Х8 Х9) + (-Х8 -Х9) + (Х8 = Х10) = 0
Эту систему уравнений, как и в предыдущем задании, можно переписать в виде:
(XI = Х2) + (XI = Хз) = 1 (Х = Хз) + (Х2 = X) = 1 (Хз = X) + (Хз = Х5) = 1 (X = Х5) + (Х4 = Хб) = 1 (Х5 = Хб) + (Х5 = Х7) = 1 (Хб = Х7) + (Хб = Х8) = 1 (Х = Х8) + (Х7 = Х9) = 1 (Х = Х9) + (Х8 = Ххс) = 0
Из последнего уравнения легко проверить, что после N = 8 число решений перестает возрастать. Тогда F (10) = F (8) = 8 + 8 = 16.
Задание 17. Нужно найти количество решений системы уравнений ([2], Задание 4)
(Х1 Х2) + (-Х1 -Х2) + (Х2 Хз) + (-Х2 -Хз) = 1
(Х2 Хз) + (-Х2 -Хз) + (Хз Х) + (-Хз ¦ -Х4) = 1
(Хз Х) + (-Хз -Х4) + (Х4 Х5) + (-Х4 -Х5) = 1
(Х4 X) + (-Х -Х5) + (Х5 Хб) + (-Х5 -Хб) = 1
(Х5 Хб) + (-Х -Хб) + (Хб Х7) + (-Хб ¦ -Х7) = 1
(Хб Х7) + (-Хб -Х7) + (Х7 Х8) + (-Х7 -Х8) = 1
(Х7 Х) + (-Х7 -Х8) + (Х8 Х9) + (-Х8 -Х9) = 1
(Х8 Х9) + (-Х8 -Х9) + (Х9 Х10) + (-Х9 ¦ -Х10) = 1
Заметим, что систему уравнений можно переписать в виде:
(Х= Х2) + (X = Хз) = 1 (Х= Хз) + (X = Х) = 1 (Хз= Х4) + (Х4 = Х5) = 1 (Х = Х5) + (Х5 = Хб) = 1 (Х5 = Хб) + (Хб = Х7) = 1
194
(Хб = Х7) + (Х7 = X) = 1 (Х7 = Х8) + (Х8 = Х9) = 1 (Хв = X 9) + (Х9 = Х10) = 1
На рисунке 15 дерево построено до пятого уровня и видно, что число решений описывается числами Фибоначчи, то есть Fl (N) = Fl (N-1) + Fl (N-2). Тогда Fl (10) = 89. Легко проверить, что для F0(N) дерево будет симметрично. Поэтому Fo (10) = 89. Б (10) = р1(10) + Ро (10) = 89 + 89 =178.
Рис. 15. Задание 17
Задание 18. Нужно найти количество решений системы уравнений ([2], Задание 5)
(Х1 Х2) + (-Х1 -Х2) + (Х2 Хз) + (-Х2 ¦ -Хз) = 1
(Х2 Хз) + (-Х -Хз) + (Хз Х4) + (-Хз -Х4) = 1
(Хз Х4) + (-Хз -Х4) + (Х4 Х5) + (-Х4 ¦ -Х5) = 1
(Х4 Х5) + (-Х4 -Х5) + (Х Хб) + (-Х5 ¦ -Хб) = 1
(Х5 Хб) + (-Х5 -Хб) + (Хб Х7) + (-Хб ¦ -Х7) = 1
(Хб Х7) + (-Хб -Х7) + (Х7 Х8) + (-Х7 ¦ -Х8) = 1
(Х7 Х8) + (-Х7 -Х8) + (Х8 Х9) + (-Х8 -Х9) = 1
(Х8 Х9) + (-Х8 -Х9) + (Х9 Х10) + (-Х9 ¦ -Х10) = 0
Заметим, что систему уравнений можно переписать в виде:
(Х= Х2) + (Х2 = Х3) = 1 (Х2= Хз) + (Хз = Х4) = 1
195
(Хз= Х) + (Х4 = Х5) = 1 (Х = Х5) + (Х5 = Хб) = 1 (Х = Хб) + (Хб = Х7) = 1 (Хб = Х7) + (Х7 = Х8) = 1 (Х7 = Х8) + (Х8 = Х9) = 1 (Х8 = Х 9) + (Х = Х10) = 0
Задание 18 похоже на задание 17, однако последнее уравнение приводит к тому, что начиная с седьмого уровня число решений не увеличивается. В результате F (10) = Fl (10) + Fo (10) = Fl (7) + Fo (7) = 21 + 21 = 42.
Задание 19. Нужно найти количество решений системы уравнений ([2], Задание б)
(Х= Х2) + (Х = Х10) = 1 (Х= Хз) + (Х2 = Х10) = 1 (Хз= Х4) + (X = Х10) = 1 (Х = Х5) + (Х = Х10) = 1 (Х = Хб) + (Х5 = Х10) = 1 (Хб = Х7) + (Хб = Х10) = 1 (Х7 = Х) + (Х = Х10) = 1 (Х8 = Х9) + (Х = Х10) = 1 (Х9 = Х10) + (Х9 = Х10) = 1 (Х = Х10) = 0
•-•-•-•-*-•-•-•-*-о
Рис. 1б. Задание 19
Деревья решений для получения F1(N) и F0(N) показаны на рис. 1б. Однако уравнение (Х9 = Х10) = 1 не может быть выполнено. Поэтому система уравнений не имеет решений.
Задание 20. Нужно найти количество решений системы уравнений ([2], Задание 7)
(Х ^ Х2) + (Х ^ Хз) = 1 (Х2 ^ Хз) + (Х2 * Х4) = 1 (Хз ^ Х4) + (Хз ^ Х5) = 1 (Х ^ Х5) + (Х4 ^ Хб) = 1 (Х5 ^ Хб) + (Х5 ^ Х7) = 1 (Хб ^ Х7) + (Хб ^ Х8) = 1
196
(X7 ^ Xs) + (X7 ^ X9) = 1 (Xs ^ X9) + (Xs ^ X10) = 1
На рисунке 17 показано дерево решений из «1».
Рис. 17. Задание 20 Рис. 18. Задание 20
Вместо десяти уровней мы ограничились пятью, так как задача схожа с заданием 17. Однако из «0» дерево будет выглядеть иначе (рис. 18).
Заметим, что F0(N) = Fx (N+1) — 1. Тогда Fx (10) = 89, а F0(10) = Fx (11) — 1 = 144 — 1. Итого, F (10) = F1(10) + F0(10) = 89 + 143 = 232.
В заключение приведем программу на бейсике VBA, с помощью которой можно решать системы логических уравнений. Программа может понадобиться при составлении новых систем уравнений. На рисунке 19 показана программа, с помощью которой решается система уравнений из задания 7.
В программе, показанной на рис. 19, массив m и переменная c содержат значения переменных, удовлетворяющих системе уравнений из задания 7. Программа выдает ответ 68. В программе используется факт, что число различных наборов значений n логических переменных равно 2n. Для получения всех наборов нужно выполнить цикл от 0 до 2n-1. Переменная цикла на каждом шаге переводится в двоичную систему, результат записывается в массив m, и затем уже проверяются условия из системы уравнений. Для решения другой системы уравнений достаточно поменять размерность массива m, изменить значение переменной vg (равна размерности) и поменять условия проверки.
197
Sub calc{)
Dim m (S) As Integer, k As Integer, j. As Integer. _ j As Integer. N As Integer, vg As Integer Dim с As String vg=S j-0
For 1 To 2 ¦'-& quot-¦ vg '-Цикл по ^ от 1 до 2n. где n=,.g For k = 1 To vg
m (k)= 0 Next k
N = }.- 1: Двоично e пр e ц ставл e нне начинается с нуля k= 1
Do & quot-^Tiils N & gt- 0 '-Перевод e двоичную сЯстему m (k) = N Mod 2 К = N ¦ 2 k=k+ ! Loop
Ifim (l) О m (2) Or m (l)0- ni (3)) And_ '-Условия уравнении (m{2) & lt-o- m{3) Or m (2) о иШ)) And _ ГшГЗ) -О mf4) Or m (3) -О m{5)) And _ (m (4) О m (5) Or ni (4) -O m (6)) And _ (ni (5) О m (5) Or m (S) О m (7)). And _ (m{6) -O m (7) Or m (5)-0 m (S)) Then
c= & quot-"- & quot-Переменная с на каждом шаге оудет содержать решение системы For k= 1 То vg
с = с — Foimat{m (k)j Next k j-j-1 End If Next I.
Ms^Eox i '-Количество решений
VvVvVlVvVvv- -1 i
End Sub
Рис. 19. Программа для задания 7
1. Крылов С. С. ЕГЭ 2014. Информатика. Тематические тестовые задания / С. С. Крылов, Д. М. Ушаков. — М.: Изд-во «Экзамен». — 245 с.
2. Сайт К. Ю. Полякова. Режим доступа: http: //kpolyakov. namd. -ru/download/inf-2011−14. pdf
3. Методический сертифицированный курс фирмы «1С» «Подготовка к ЕГЭ по информатике. Модуль 1». — М.: Изд-во «1С». — 218 с.
4. Успешно сдать ЕГЕ по информатике. Режим доступа: http: //infoegehelp. ru/index. php? Itemid=77&-id=103&-option=com_con-
tent & amp-view=article.
198

ПоказатьСвернуть
Заполнить форму текущей работой