УДК 004.023
Семенов Сергей Максимович
Владивостокский государственный университет экономики и сервиса Россия. Владивосток
Об одном способе решения систем логических уравнений
Рассматривается способ определения количества решений системы логических уравнений. Способ основан на построении дерева решений и определении рекуррентных соотношений для уровня N. Применение разработанного способа обеспечивает конструктивный подход к решению задачи В15 ЕГЭ.
Ключевые слова и словосочетания: системы логических уравнений, дерево решений, рекуррентные соотношения, B15, ЕГЭ.
На практике системы логических уравнений полезны при разработке цифровых логических устройств . Решению систем логических уравнений посвящена одна из задач ЕГЭ по информатике. К сожалению, различные известные способы решения этой задачи не позволяют сформировать какой-то один подход к решению этой задачи. В результате решение задачи вызывает большие затруднения у выпускников. Мы предлагаем способ решения систем логических уравнений, который позволяет выпускнику следовать вполне определенному алгоритму. Идея этого способа изложена в . Мы применили и развили данную идею (построение дерева решений), почти не используя таблицы истинности для всего дерева. При решении различных задач выяснилось, что количество решений многих систем логических уравнений подчиняется рекуррентным соотношениям, таким, как числа Фибоначчи и др.
Системы логических уравнений. Будем придерживаться следующих обозначений: дизъюнкция (+), конъюнкция ( ), исключающее ИЛИ (©), импликация (->■), эквивалентность (=), отрицание (-■). На рисунках темный кружок обозначает 1, а светлый кружок - 0. Fl - количество решений при Х1, равном 1. Fo - количество решений при Х1, равном 0. N - число переменных в системе уравнений. F(N) = F1(N) + F0(N) - общее число решений.
Задание 1. Нужно найти количество решений системы уравнений (, тест № 2)
Вначале полагаем Х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, то есть
Итого, F(9) = Fl(9) + Fo(9) = 34 + 16 = 50.
При построении дерева решений можно визуально установить рекуррентные соотношения для определения количества решений на уровне N.
Принцип математической индукции гласит: пусть имеется последовательность утверждений Fl, F2, Fз и пусть первое утверждение Fl верно. Мы можем доказать, что из верности утверждения FN следует верность FN+l. Тогда все утверждения в этой последовательности верны.
Рассмотрим рис. 2 для задания 1.
к2 >3 х5 хб Х7
Рис. 2. Анализ дерева решений
На рисунке 2 выделены фигуры, имеющие общую вершину (комбинации значений переменных) для первых пяти уравнений системы. В каждом уравнении задействованы три переменных, поэтому фигуры составляются из значений трех переменных (трех уровней дерева). Для того чтобы идентифицировать фигуры, можно было бы ввести обозначения. Однако мы поступим следующим образом: каждой фигуре поставим в соответствие количество составляющих ее кружков (значений переменных). Тогда получим для последовательности следующие уравнения:
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.
Другим способом идентификации фигур является определение количества значений переменных на последнем уровне для данного уравнения, то есть нужно перейти от номера уравнения к номеру уровня дерева, поскольку нам нужно определить количество решений для системы уравнений, Тогда для построенного дерева получим последовательность: 1, 2, 4, 5, 7, 11, 16. Для этой последовательности справедлива формула: FN = FN-1 + FN-3.
В соответствии с нашими рассуждениями эта формула будет верна для N+1, а по индукции и для любого N.
Приведенный способ доказательства можно использовать для любых систем подобного типа. На практике достаточно определять рекуррентное соотношение для уровня N поскольку в основе его лежит ограниченный набор фигур и способов их преобразований при переходе от уравнения, соответствующего уровню N к уравнению, соответствующему уровню N+1.
Задание 2. Нужно найти количество решений системы уравнений (, 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 ХЗ >:1 Х5 Хб Х7
Рис. 3. Задание 2
Для получения числа решений задания 2 можно было не строить дерево решений полностью (рис. 3), так как очевидно, что Fl(N) = N. Аналогично, Fo(N) = N. Итого F(7) = 7 + 7 = 14.
Задание 3. Нужно найти количество решений системы уравнений (, тест № 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
На рисунке 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. Нужно найти количество решений системы уравнений (, 4.17.а)
(Х1=Х2) + (Х1 = Х3) = (Х2 = Х3) + (Х2 = Х4) = (Х4=Х5) + (Х4 = Х6) = (Х5 = Х6) + (Х5 = Х7) = (Хб=Х7) + (Хб = Х8) = (Х5=Х6) = 0
Рис. 5. Задание 4
Для данного примера сложно определить конечную формулу F(N), проще построить дерево решений до конца (или хотя бы до Х6). На рисунке 5 показано построенное дерево решений. В результате получаем F(8) = Fl(8) + Fo(8) = 5 + 5 = 10.
Задание 5. Необходимо найти количество решений системы уравнений (, 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. Нужно найти количество решений системы уравнений ([!]> 4.17.в)
(Х!8"Х2) + (Х2ЕХз) = 1 (Х2фХз) + (Хз = Х4) = 1 (Хз8"Х4) + (Х4 = Х5) = 1 (Х4©Х5) + (Х5 = Хб) = 1 (Х5фХб) + (Хб = Х7) = 1 (Хб©Х7) + (Х7 = Х8) = 1 Дерево решений показано на рис. 7.
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 ©Х6) = 1 (Х5©Хб) + (Х5©Х7) = 1
Заметим, что если X! = X2 = 1, то первое уравнение выполняется при Xз = 0. Построим сначала дерево для Xl = X2 = 1 (рис. 8). Тогда число решений Fl(N) = Fll(N) + Flo(N).
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) равно единице в трех случаях (за исключением варианта, когда обе переменные равны нулю).
Поскольку переменные Y независимы, то для первой строки таблицы истинности, показанной на рис. 4, число различных комбинаций равно 35, для второй строки - 34 и т.д. Общее число различных комбинаций равно 35 + 34 + 33 + 32 + 31 + 30 = 364.
Задание 9. Нужно найти количество решений системы уравнений (, Задание 4)
(^ ^ Ъ) ■ (-X ^ Xз) ■ № ^ X) ■ (-X ^ Кз) = 1 № ^ Y2) ■ (У1 ^ Yз) ■ (-Г1 ^ Y4) ■ (У1 ^ Y5) = 1 (-X + Y 1) ■ (-X + Y5) = 1
Для X и Y имеем следующие деревья решений
Рис. 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. Нужно найти количество решений системы уравнений (^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
(Х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
Задание 11. Нужно найти количество решений системы уравнений (, Пример 2)
Х1 + Х2 = 1 -Х2 + Хз = 1
На рисунке 11 показано дерево решений. Мы ограничились четырьмя уровнями вместо десяти, так как очевидно, что F1(N) = 1 и F0(N) = N. Тогда Р(Ы) = Р1(Ы) + БоСЫ) = 1 + N. В нашем случае Р(10) = 1 + 10 = 11.
Рис. 11. Задание 11
Задание 12. Нужно найти количество решений системы уравнений (, Пример з)
(Х1 = Х2) + (Х2 = Хз) = 1
(Х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. Нужно найти количество решений системы уравнений (, Пример 4)
- (Х1 = Х2) + (Хз = Х4) = 1
- (Хз = Х4) + (Х5 = Х) = 1
- (Х = Х) + (Х7 = Х) = 1
- (Х7 = Х8) + (Х9 = Х10) = 1
Проведем замену:
(Х1 = Х2) = Yl
(Х5 = Х) = Yз
(Х7 = Х8) = Y4
(Х9 = Х10) = Y5
Перепишем систему уравнений с учетом замены:
Из задания 11 видно, что F(5) = 5 + 1 = 6. Таблица истинности представлена на рис. 13.
У1 У2 УЗ У4 У5
Рис. 13. Задание 13
С учетом подстановки отметим, что выражение ^ = X2) равно единице (или нулю) в двух случаях (когда значения переменных совпадают). С учетом независимости переменных для каждой строки таблицы получаем, что число наборов решений равно 25 = 32. Общее число наборов решений равно 6 * 32 = 192.
Задание 14. Нужно найти количество решений системы уравнений (, Задание 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) = Y4 ^9 = Xlo) = Y5
Перепишем систему уравнений с учетом замены:
(УЛ) + (-У« ■ -У2)=0
(Y2 Yз) + (-У2 ■ -У3)=0 (У3-У4) + (-У3 ■ -У4)=0 (У4-У5) + (-У4 ■ -У5)=0
(У2 = Yз) = 0 (Уз = У4) = 0 (У4 = У5) = 0
На рисунке 14 показано дерево решений
У1 У2 УЗ У4 У5
Рис. 14. Задание 14
С учетом подстановки отметим, что выражение (Х1 = Х2) равно единице (или нулю) в двух случаях (когда значения переменных совпадают). С учетом независимости переменных для каждого дерева получаем, что число наборов решений равно 25 = з2. Общее число наборов решений равно 64.
Задание 15. Нужно найти количество решений системы уравнений (, Задание 2)
(Х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.
Задание 16. Нужно найти количество решений системы уравнений (, Задание 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. Нужно найти количество решений системы уравнений (, Задание 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
(Хб = Х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. Нужно найти количество решений системы уравнений (, Задание 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
(Хз= Х) + (Х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) + (Х = Х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. Нужно найти количество решений системы уравнений (, Задание 7)
(Х ^ Х2) + (Х ^ Хз) = 1 (Х2 ^ Хз) + (Х2 * Х4) = 1 (Хз ^ Х4) + (Хз ^ Х5) = 1 (Х ^ Х5) + (Х4 ^ Хб) = 1 (Х5 ^ Хб) + (Х5 ^ Х7) = 1 (Хб ^ Х7) + (Хб ^ Х8) = 1
(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 (равна размерности) и поменять условия проверки.
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 ■""■ vg "Цикл по ^ от 1 до 2n. где n=,.g For k = 1 To vg
N = }.- 1: Двоично e пр e ц ставл e нне начинается с нуля k= 1
Do "^Tiils N > 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) c= "" "Переменная с на каждом шаге оудет содержать решение системы For k= 1 То vg с = с - Foimat{m(k)j Next k j-j-1 End If Next I. Ms^Eox i "Количество решений VvVvVlVvVvv- -1 i Рис. 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- Как решать некоторые задачи разделов A и B экзамена по информатике
Урок №3. Логика. Логические функции. Решение уравнений
Большое количество задач ЕГЭ посвящено логике высказываний. Для решения большинства из них достаточно знания основных законов логики высказываний, знания таблиц истинности логических функций одной и двух переменных. Приведу основные законы логики высказываний. Представление логических функций Любую логическую функцию от n переменных – F(x 1 , x 2 , … x n) можно задать таблицей истинности. Такая таблица содержит 2 n наборов переменных, для каждого из которых задается значение функции на этом наборе. Такой способ хорош, когда число переменных относительно невелико. Уже при n > 5 представление становится плохо обозримым. Другой способ состоит в том, чтобы задавать функцию некоторой формулой, используя известные достаточно простые функции. Система функций {f 1 , f 2 , … f k } называется полной, если любую логическую функцию можно выразить формулой, содержащей только функции f i . Полной является система функций {¬, ˄, ˅}. Законы 9 и 10 являются примерами, демонстрирующими, как импликация и тождество выражается через отрицание, конъюнкцию и дизъюнкцию. Фактически полной является и система из двух функций – отрицания и конъюнкции или отрицания и дизъюнкции. Из законов де-Моргана следуют представления, позволяющие выразить конъюнкцию через отрицание и дизъюнкцию и соответственно выразить дизъюнкцию через отрицание и конъюнкцию: (а ˅ b) ≡ ¬(¬а ˄ ¬b) Парадоксально, но полной является система, состоящая всего из одной функции. Существуют две бинарные функции – антиконънкция и антидизъюнкция, называемые стрелкой Пирса и штрих Шеффера, представляющие полую систему. В состав базовых функций языков программирования включают обычно тождество, отрицание, конъюнкцию и дизъюнкцию. В задачах ЕГЭ наряду с этими функциями часто встречается импликация. Рассмотрим несколько простых задач, связанных с логическими функциями. Задача 15:
Дан фрагмент таблицы истинности. Какая из трех приведенных функций соответствует этому фрагменту?
Функция под номером 3. Для решения задачи нужно знать таблицы истинности базовых функций и помнить о приоритетах операций. Напомню, что конъюнкция (логическое умножение) имеет более высокий приоритет и выполняется раньше, чем дизъюнкция (логическое сложение). При вычислениях нетрудно заметить, что функции с номерами 1 и 2 на третьем наборе имеют значение 1 и уже по этой причине фрагменту не соответствуют. Задача 16:
Какое из приведенных чисел удовлетворяет условию:
(цифры, начиная со старшего разряда, идут в порядке убывания) → (число — четное) ˄ (младшая цифра – четная) ˄ (старшая цифра – нечетная)
Если таких чисел несколько, укажите наибольшее.
Условию удовлетворяет число под номером 4. Первые два числа условию не удовлетворяют уже по той причине, что младшая цифра является нечетной. Конъюнкция условий ложна, если один из членов конъюнкции ложен. Для третьего числа не выполняется условие для старшей цифры. Для четвертого числа выполняются условия, накладываемые на младшую и старшую цифры числа. Первый член конъюнкции также истинен, поскольку импликация истинна, если ее посылка ложна, что имеет место в данном случае. Задача 17: Два свидетеля дали следующие показания:
Первый свидетель: Если А виновен, то В и подавно виновен, а С – невиновен.
Второй свидетель: Виновны двое. А точно виновен и виновен один из оставшихся, но кто именно сказать не могу.
Какие заключения о виновности А, В и С можно сделать на основании свидетельских показаний?
Ответ: Из свидетельских показаний следует, что А и В виновны, а С – невиновен. Решение: Конечно, ответ можно дать, основываясь на здравом смысле. Но давайте рассмотрим, как это можно сделать строго и формально. Первое, что нужно сделать – это формализовать высказывания. Введем три логические переменные — А, В и С, каждая из которых имеет значение true (1), если соответствующий подозреваемый виновен. Тогда показания первого свидетеля задаются формулой: A → (B ˄ ¬C) Показания второго свидетеля задаются формулой: A ˄ ((B ˄ ¬C) ˅ (¬B ˄ C)) Показания обоих свидетелей полагаются истинными и представляют конъюнкцию соответствующих формул. Построим таблицу истинности для этих показаний: Суммарные свидетельские показания истинны только в одном случае, приводящие к однозначному ответу – А и В виновны, а С – невиновен. Из анализа этой таблицы также следует, что показания второго свидетеля более информативны. Из истинности его показания следует только два возможных варианта — А и В виновны, а С – невиновен или А и С виновны, а В – невиновен. Показания первого свидетеля менее информативны – существует 5 различных вариантов, соответствующих его показаниям. Совместно показания обоих свидетелей дают однозначный ответ о виновности подозреваемых. Логические уравнения и системы уравнений Пусть F(x 1 , x 2 , …x n) – логическая функция от n переменных. Логическое уравнение имеет вид: F(x 1 , x 2 , …x n) = С, Константа С имеет значение 1 или 0. Логическое уравнение может иметь от 0 до 2 n различных решений. Если С равно 1, то решениями являются все те наборы переменных из таблицы истинности, на которых функция F принимает значение истина (1). Оставшиеся наборы являются решениями уравнения при C, равном нулю. Можно всегда рассматривать только уравнения вида: F(x 1 , x 2 , …x n) = 1 Действительно, пусть задано уравнение: F(x 1 , x 2 , …x n) = 0 В этом случае можно перейти к эквивалентному уравнению: ¬F(x 1 , x 2 , …x n) = 1 Рассмотрим систему из k логических уравнений: F 1 (x 1 , x 2 , …x n) = 1 F 2 (x 1 , x 2 , …x n) = 1 F k (x 1 , x 2 , …x n) = 1 Решением системы является набор переменных, на котором выполняются все уравнения системы. В терминах логических функций для получения решения системы логических уравнений следует найти набор, на котором истинна логическая функция Ф, представляющая конъюнкцию исходных функций F: Ф = F 1 ˄ F 2 ˄ … F k Если число переменных невелико, например, менее 5, то нетрудно построить таблицу истинности для функции Ф, что позволяет сказать, сколько решений имеет система и каковы наборы, дающие решения. В некоторых задачах ЕГЭ по нахождению решений системы логических уравнений число переменных доходит до значения 10. Тогда построить таблицу истинности становится практически неразрешимой задачей. Для решения задачи требуется другой подход. Для произвольной системы уравнений не существует общего способа, отличного от перебора, позволяющего решать такие задачи. В предлагаемых на экзамене задачах решение обычно основано на учете специфики системы уравнений. Повторяю, кроме перебора всех вариантов набора переменных, общего способа решения задачи нет. Решение нужно строить исходя из специфики системы. Часто полезно провести предварительное упрощение системы уравнений, используя известные законы логики. Другой полезный прием решения этой задачи состоит в следующем. Нам интересны не все наборы, а только те, на которых функция Ф имеет значение 1. Вместо построения полной таблицы истинности будем строить ее аналог — бинарное дерево решений. Каждая ветвь этого дерева соответствует одному решению и задает набор, на котором функция Ф имеет значение 1. Число ветвей в дереве решений совпадает с числом решений системы уравнений. Что такое бинарное дерево решений и как оно строится, поясню на примерах нескольких задач. Задача 18
Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют системе из двух уравнений?
Ответ: Система имеет 36 различных решений. Решение: Система уравнений включает два уравнения. Найдем число решений для первого уравнения, зависящего от 5 переменных – x 1 , x 2 , …x 5 . Первое уравнение можно в свою очередь рассматривать как систему из 5 уравнений. Как было показано, система уравнений фактически представляет конъюнкцию логических функций. Справедливо и обратное утверждение, — конъюнкцию условий можно рассматривать как систему уравнений. Построим дерево решений для импликации (x1→ x2) — первого члена конъюнкции, который можно рассматривать как первое уравнение. Вот как выглядит графическое изображение этого дерева: Дерево состоит из двух уровней по числу переменных уравнения. Первый уровень описывает первую переменную X 1 . Две ветви этого уровня отражают возможные значения этой переменной – 1 и 0. На втором уровне ветви дерева отражают только те возможные значения переменной X 2 , для которых уравнение принимает значение истина. Поскольку уравнение задает импликацию, то ветвь, на которой X 1 имеет значение 1, требует, чтобы на этой ветви X 2 имело значение 1. Ветвь, на которой X 1 имеет значение 0, порождает две ветви со значениями X 2 , равными 0 и 1. Построенное дерево задает три решения, на которых импликация X 1 → X 2 принимает значение 1. На каждой ветви выписан соответствующий набор значений переменных, дающий решение уравнения. Вот эти наборы: {(1, 1), (0, 1), (0, 0)} Продолжим построение дерева решений, добавляя следующее уравнение, следующую импликацию X 2 → X 3 . Специфика нашей системы уравнений в том, что каждое новое уравнение системы использует одну переменную из предыдущего уравнения, добавляя одну новую переменную. Поскольку переменная X 2 уже имеет значения на дереве, то на всех ветвях, где переменная X 2 имеет значение 1, переменная X 3 также будет иметь значение 1. Для таких ветвей построение дерева продолжается на следующий уровень, но новые ветви не появляются. Единственная ветвь, где переменная X 2 имеет значение 0, даст разветвление на две ветви, где переменная X 3 получит значения 0 и 1. Таким образом, каждое добавление нового уравнения, учитывая его специфику, добавляет одно решение. Исходное первое уравнение: (x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1 Второе уравнение нашей системы аналогично первому: (y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1 Разница лишь в том, что в уравнении используются переменные Y. Это уравнение также имеет 6 решений. Поскольку каждое решение для переменных X i может быть скомбинировано с каждым решением для переменных Y j , то общее число решений равно 36. Заметьте, построенное дерево решений дает не только число решений (по числу ветвей), но и сами решения, выписанные на каждой ветви дерева. Задача 19
Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, которые удовлетворяют всем перечисленным ниже условиям?
(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1 Эта задача является модификацией предыдущей задачи. Разница в том, что добавляется еще одно уравнение, связывающее переменные X и Y. Из уравнения X 1 → Y 1 следует, что когда X 1 имеет значение 1(одно такое решение существует), то и Y 1 имеет значение 1. Таким образом, существует один набор, на котором X 1 и Y 1 имеют значения 1. При X 1 , равном 0, Y 1 может иметь любое значение, как 0, так и 1. Поэтому каждому набору с X 1 , равном 0, а таких наборов 5, соответствует все 6 наборов с переменными Y. Следовательно, общее число решений равно 31. Задача 20
(¬X 1 ˅ X 2) ˄ (¬X 2 ˅ X 3) ˄ (¬X 3 ˅ X 4) ˄ (¬X 4 ˅ X 5) ˄ (¬X 5 ˅ X 1) = 1 Решение: Вспоминания основные эквивалентности, запишем наше уравнение в виде: (X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) = 1 Циклическая цепочка импликаций означает тождественность переменных, так что наше уравнение эквивалентно уравнению: X 1 ≡ X 2 ≡ X 3 ≡ X 4 ≡ X 5 = 1 Это уравнение имеет два решения, когда все X i равны либо 1, либо 0. Задача 21
(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) = 1 Решение: Так же, как и в задаче 20, от циклических импликаций перейдем к тождествам, переписав уравнение в виде: (X 1 → X 2) ˄ (X 2 ≡ X 3 ≡ X 4) ˄ (X 4 → X 5) = 1 Построим дерево решений для этого уравнения: Задача 22
Сколько решений имеет следующая система уравнений?
((X 1 ≡
X 2) ˄ (X 3 ≡
X 4)) ˅(¬(X 1 ≡
X 2) ˄ ¬(X 3 ≡
X 4)) = 0
((X 3 ≡
X 4) ˄ (X 5 ≡
X 6)) ˅(¬(X 3 ≡
X 4) ˄ ¬(X 5 ≡
X 6)) = 0
((X 5 ≡
X 6) ˄ (X 7 ≡
X 8)) ˅(¬(X 5 ≡
X 6) ˄ ¬(X 7 ≡
X 8)) = 0
((X 7 ≡
X 8) ˄ (X 9 ≡
X 10)) ˅(¬(X 7 ≡
X 8) ˄ ¬(X 9 ≡
X 10)) = 0
Ответ: 64
Решение: Перейдем от 10 переменных к 5 переменным, введя следующую замену переменных: Y 1 = (X 1 ≡ X 2); Y 2 = (X 3 ≡ X 4); Y 3 = (X 5 ≡ X 6); Y 4 = (X 7 ≡ X 8); Y 5 = (X 9 ≡ X 10); Тогда первое уравнение примет вид: (Y 1 ˄ Y 2) ˅ (¬Y 1 ˄ ¬Y 2) = 0 Уравнение можно упростить, записав его в виде: (Y 1 ≡ Y 2) = 0 Переходя к традиционной форме, запишем систему после упрощений в виде: ¬(Y 1 ≡ Y 2) = 1 ¬(Y 2 ≡ Y 3) = 1 ¬(Y 3 ≡ Y 4) = 1 ¬(Y 4 ≡ Y 5) = 1 Дерево решений для этой системы простое и состоит из двух ветвей с чередующимися значениями переменных: Как видите, каждая задача на решение системы уравнений требует своего подхода. Общим приемом является выполнение эквивалентных преобразований для упрощения уравнений. Общим приемом является и построение деревьев решений. Применяемый подход частично напоминает построение таблицы истинности с той особенностью, что строятся не все наборы возможных значений переменных, а лишь те, на которых функция принимает значение 1 (истина). Часто в предлагаемых задачах нет необходимости в построении полного дерева решений, поскольку уже на начальном этапе удается установить закономерность появления новых ветвей на каждом следующем уровне, как это сделано, например, в задаче 18. В целом задачи на нахождение решений системы логических уравнений являются хорошими математическими упражнениями. Если задачу трудно решить вручную, то можно поручить решение задачи компьютеру, написав соответствующую программу решения уравнений и систем уравнений. Написать такую программу несложно. Такая программа легко справится со всеми задачами, предлагаемыми в ЕГЭ. Как это ни странно, но задача нахождения решений систем логических уравнений является сложной и для компьютера, оказывается и у компьютера есть свои пределы. Компьютер может достаточно просто справиться с задачами, где число переменных 20 -30, но начнет надолго задумываться на задачах большего размера. Дело в том, что функция 2 n , задающая число наборов, является экспонентой, быстро растущей с увеличением n. Настолько быстро, что обычный персональный компьютер за сутки не справится с задачей, у которой 40 переменных. Программа на языке C# для решения логических уравнений
Написать программу для решения логических уравнений полезно по многим причинам, хотя бы потому, что с ее помощью можно проверять правильность собственного решения тестовых задач ЕГЭ. Другая причина в том, что такая программа является прекрасным примером задачи на программирование, соответствующей требованиям, предъявляемым к задачам категории С в ЕГЭ. Идея построения программы проста, — она основана на полном переборе всех возможных наборов значений переменных. Поскольку для заданного логического уравнения или системы уравнений число переменных n известно, то известно и число наборов – 2 n , которые требуется перебрать. Используя базовые функции языка C# — отрицание, дизъюнкцию, конъюнкцию и тождество, нетрудно написать программу, которая для заданного набора переменных вычисляет значение логической функции, соответствующей логическому уравнению или системе уравнений. В такой программе нужно построить цикл по числу наборов, в теле цикла по номеру набора сформировать сам набор, вычислить значение функции на этом наборе, и если это значение равно 1, то набор дает решение уравнения. Единственная сложность, возникающая при реализации программы, связана с задачей формирования по номеру набора самого набора значений переменных. Красота этой задачи в том, что эта, казалось бы, трудная задача, фактически сводится к простой, уже неоднократно возникавшей задаче. Действительно, достаточно понять, что соответствующий числу i набор значений переменных, состоящий из нулей и единиц, представляет двоичную запись числа i. Так что сложная задача получения набора значений переменных по номеру набора сводится к хорошо знакомой задаче перевода числа в двоичную систему. Вот как выглядит функция на языке C#, решающая нашу задачу: /// /// программа подсчета числа решений /// логического уравнения (системы уравнений) /// ///
/// логическая функция — метод, /// сигнатура которого задается делегатом DF /// /// число переменных /// static int SolveEquations(DF fun, int n) bool set = new bool[n]; int m = (int)Math.Pow(2, n); //число наборов int p = 0, q = 0, k = 0; //Полный перебор по числу наборов for (int i = 0; i < m; i++) //Формирование очередного набора — set, //заданного двоичным представлением числа i for (int j = 0; j < n; j++) k = (int)Math.Pow(2, j); //Вычисление значения функции на наборе set Для понимания программы, надеюсь, достаточно сделанных объяснений идеи программы и комментариев в ее тексте. Остановлюсь лишь на пояснении заголовка приведенной функции. У функции SolveEquations два входных параметра. Параметр fun задает логическую функцию, соответствующую решаемому уравнению или системе уравнений. Параметр n задает число переменных функции fun. В качестве результата функция SolveEquations возвращает число решений логической функции, то есть число тех наборов, на которых функция принимает значение true. Для школьников привычно, когда у некоторой функции F(x) входным параметром x является переменная арифметического, строкового или логического типа. В нашем случае используется более мощная конструкция. Функция SolveEquations относится к функциям высшего порядка – функциям типа F(f), у которых параметрами могут быть не только простые переменные, но и функции. Класс функций, которые могут передаваться в качестве параметра функции SolveEquations, задается следующим образом: delegate bool DF(bool vars); Этому классу принадлежат все функции, которым в качестве параметра передается набор значений логических переменных, заданных массивом vars. В качестве результата возвращается значение булевского типа, представляющее значение функции на этом наборе. В заключение приведу программу, в которой функция SolveEquations используется для решения нескольких систем логических уравнений. Функция SolveEquations является частью приводимого ниже класса ProgramCommon: class ProgramCommon delegate bool DF(bool vars); static void Main(string args) Console.WriteLine(«У Функции And решений — » + SolveEquations(FunAnd, 2)); Console.WriteLine(«У Функции 51 решений — » + SolveEquations(Fun51, 5)); Console.WriteLine(«У Функции 53 решений — » + SolveEquations(Fun53, 10)); static bool FunAnd(bool vars) return vars && vars; static bool Fun51(bool vars) f = f && (!vars || vars); f = f && (!vars || vars); f = f && (!vars || vars); f = f && (!vars || vars); f = f && (!vars || vars); static bool Fun53(bool vars) f = f && ((vars == vars) || (vars == vars)); f = f && ((vars == vars) || (vars == vars)); f = f && ((vars == vars) || (vars == vars)); f = f && ((vars == vars) || (vars == vars)); f = f && ((vars == vars) || (vars == vars)); f = f && ((vars == vars) || (vars == vars)); f = f && (!((vars == vars) || (vars == vars))); Вот как выглядят результаты решения по этой программе: 10 задач для самостоятельной работы
Какой из трех функций соответствует этот фрагмент: Ответы к задачам:
Данной материал содержит презентацию, в которой представлены методы решения логических уравнений и систем логических уравнений в задании В15 (№ 23, 2015) ЕГЭ по информатике. Известно, что это задание является одним из самых сложных среди заданий ЕГЭ. Презентация может быть полезна при проведении уроков по теме "Логика" в профильных классах, а также при подготовке к сдаче ЕГЭ. Чтобы пользоваться предварительным просмотром презентаций создайте себе аккаунт (учетную запись) Google и войдите в него: https://accounts.google.com Решение задания В15 (системы логических уравнений) Вишневская М.П., МАОУ «Гимназия №3» 18 ноября 2013 г., г. Саратов Задание В15 - одно из самых сложных в ЕГЭ по информатике!!! Проверяются умения: преобразовывать выражения, содержащие логические переменные; описывать на естественном языке множество значений логических переменных, при которых заданный набор логических переменных истинен; подсчитывать число двоичных наборов, удовлетворяющих заданным условиям. Самое сложное, т.к. нет формальных правил, как это сделать, требуется догадка. Без чего не обойтись! Без чего не обойтись! Условные обозначения конъюнкция: A /\ B , A B , AB , А &B, A and B дизъюнкция: A \ / B , A + B , A | B , А or B отрицание: A , А, not A эквиваленция: A В, A B, A B исключающее «или»: A B , A xor B Метод замены переменных Сколько существует различных наборов значений логических переменных х1, х2, …, х9, х10, которые удовлетворяют всем перечисленным ниже условиям: ((x1 ≡ x2) \/ (x3 ≡ x4)) /\ (¬(x1 ≡ x2) \/ ¬(x3 ≡ x4)) = 1 ((x3 ≡ x4) \/ (x5 ≡ x6)) /\ (¬(x3 ≡ x4) \/ ¬(x5 ≡ x6)) = 1 ((x5 ≡ x6) \/ (x7 ≡ x8)) /\ (¬(x5 ≡ x7) \/ ¬(x7 ≡ x8)) = 1 ((x7 ≡ x8) \/ (x9 ≡ x10)) /\ (¬(x7 ≡ x8) \/ ¬(x9 ≡ x10)) = 1 В ответе не нужно перечислять все различные наборы х1, х2, …, х9, х10, при которых выполняется данная система равенств. В качестве ответа необходимо указать количество таких наборов (демо-версия 2012 г.) Решение Шаг 1. Упрощаем, выполнив замену переменных t1 = x1 x2 t2 = x3 x4 t3 = x5 x6 t4 = x7 x8 t5 = x9 x10 После упрощения: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 (t2 \/ t3) /\ (¬t2 \/ ¬ t3) =1 (t3 \/ t4) /\ (¬t3 \/ ¬ t4) =1 (t4 \/ t5) /\ (¬t4 \/ ¬ t5) =1 Рассмотрим одно из уравнений: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 Очевидно, оно =1 только если одна из переменных равна 0, а другая – 1. Воспользуемся формулой для выражения операции XOR через конъюнкцию и дизъюнкцию: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) = t1 t2 = ¬(t1 ≡ t2) =1 ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1 Шаг2. Анализ системы ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1 t1 t2 t3 t4 t5 0 1 0 1 0 1 0 1 0 1 Т.к. tk = x2k-1 ≡ x2k (t1 = x1 x2 ,….), то каждому значению tk соответствует две пары значений x2k-1 и x2k , например: tk =0 соответствуют две пары - (0,1) и (1,0) , а tk =1 – пары (0,0) и (1,1). Шаг3. Подсчет числа решений. Каждое t имеет 2 решения, количество t – 5. Т.о. для переменных t существует 2 5 = 32 решения. Но каждому t соответствует пара решений х, т.е. исходная система имеет 2*32 = 64 решения. Ответ: 64 Метод исключения части решений Сколько существует различных наборов значений логических переменных х1, х2, …, х5, y1,y2,… , y5 , которые удовлетворяют всем перечисленным ниже условиям: (x1→ x2)∧(x2→ x3)∧(x3→ x4)∧(x4→ x5) =1; (y1→ y2)∧(y2→ y3)∧(y3→ y4) ∧(y4→ y5) =1; y5→ x5 =1. В ответе не нужно перечислять все различные наборы х1, х2, …, х5, y 1 ,y2,… , y5, при которых выполняется данная система равенств. В качестве ответа необходимо указать количество таких наборов. Решение. Шаг1. Последовательное решение уравнений х1 1 0 х2 1 0 1 х3 1 0 1 1 х4 1 0 1 1 1 х5 1 0 1 1 1 1 Первое уравнение – конъюнкция нескольких операций импликации, равна 1, т.е. каждая из импликаций истинна. Импликация ложна только в одном случае, когда 1 0, во всех других случаях (0 0, 0 1, 1 1) операция возвращает 1. Запишем это в виде таблицы: Шаг1. Последовательное решение уравнений Т.о. получено 6 наборов решений для х1,х2,х3,х4,х5: (00000), (00001), (00011), (00111), (01111), (11111). Рассуждая аналогично, приходим к выводу, что для y1, y2, y3, y4, y5 существует такой же набор решений. Т.к. уравнения эти независимы, т.е. в них нет общих переменных, то решением этой системы уравнений (без учета третьего уравнения) будет 6*6= 36 пар «иксов» и «игреков». Рассмотрим третье уравнение: y5→ x5 =1 Решением являются пары: 0 0 0 1 1 1 Не является решением пара: 1 0 Сопоставим полученные решения Там, где y5 =1, не подходят x5=0. таких пар 5. Количество решений системы: 36-5= 31 . Ответ: 31 Понадобилась комбинаторика!!! Метод динамического программирования Сколько различных решений имеет логическое уравнение x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1, где x 1, x 2, …, x 6 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количеств о таких наборов. Решение Шаг1. Анализ условия Слева в уравнении последовательно записаны операции импликации, приоритет одинаков. Перепишем: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 NB! Каждая следующая переменная зависит не от предыдущей, а от результата предыдущей импликации! Шаг2. Выявление закономерности Рассмотрим первую импликацию, X 1 → X 2. Таблица истинности: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 Из одного 0 получили 2 единицы, а из 1 получили один 0 и одну 1. Всего один 0 и три 1, это результат первой операции. Шаг2. Выявление закономерности Подключив к результату первой операции x 3 , получим: F(x 1 ,x 2) x 3 F(x 1 ,x 2) x 3 0 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 Из двух 0 – две 1, из каждой 1 (их 3) по одному 0 и 1 (3+3) Шаг 3. Вывод формулы Т.о. можно составить формулы для вычисления количества нулей N i и количества единиц E i для уравнения с i переменными: , Шаг 4. Заполнение таблицы Заполним слева направо таблицу для i = 6, вычисляя число нулей и единиц по приведенным выше формулам; в таблице показано, как строится следующий столбец по предыдущему: : число переменных 1 2 3 4 5 6 Число нулей N i 1 1 3 5 11 21 Число единиц E i 1 2*1+1= 3 2*1+3= 5 11 21 43 Ответ: 43 Метод с использованием упрощений логических выражений Сколько различных решений имеет уравнение ((J → K) → (M N L)) ((M N L) → (¬ J K)) (M → J) = 1 где J , K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений J , K, L, M и N, при которых выполнено данное равенство. В качестве ответа Вам нужно указать количество таких наборов. Решение Заметим, что J → K = ¬ J K Введем замену переменных: J → K=А, M N L =В Перепишем уравнение с учетом замены: (A → B) (B → A) (M → J)=1 4. (A B) (M → J)= 1 5. Очевидно, что A B при одинаковых значениях А и В 6. Рассмотрим последнюю импликацию M → J =1 Это возможно, если: M=J=0 M=0, J=1 M=J=1 Решение Т.к. A B , то При M=J=0 получаем 1 + К=0. Нет решений. При M=0, J=1 получаем 0 + К=0, К=0, а N и L - любые, 4 решения: ¬ J K = M N L K N L 0 0 0 0 0 1 0 1 0 0 1 1 Решение 10. При M=J=1 получаем 0+К=1 *N * L , или K=N*L, 4 решения: 11. Итого имеет 4+4=8 решений Ответ: 8 K N L 0 0 0 0 0 1 0 1 0 1 1 1 Источники информации: О.Б. Богомолова, Д.Ю. Усенков. В15: новые задачи и новое решение // Информатика, № 6, 2012, с. 35 – 39. К.Ю. Поляков. Логические уравнения // Информатика, № 14, 2011, с. 30-35. http://ege-go.ru/zadania/grb/b15/ , [ Электронный ресурс ] . http://kpolyakov.narod.ru/school/ege.htm , [ Электронный ресурс ] . Решение систем логических уравнений методом замены переменных
Метод замены переменных применяется, если некоторые переменные входят в состав уравнений только в виде конкретного выражения, и никак иначе. Тогда это выражение можно обозначить новой переменной. Пример 1.
Сколько существует различных наборов значений логических переменных x1, х2, х3, х4, х5, х6, х7, х8, которые удовлетворяют всем перечисленным ниже условиям? (x1 → х2) → (х3→ х4) = 1 (х3 → х4) → (х5 → х6) = 1 (х5 → х6) → (х7 → х8) = 1 В ответе не нужно перечислять все различные наборы значений переменных x1, х2, х3, х4, х5, х6, х7, х8, при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов. Решение:
(x1 → х2) = y1; (х3 → х4) = y2; (х5 → х6) = y3; (х7 → х8) = 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) Эквивалентность истинна, только если оба операнда равны. Решениями этого уравнения будут два набора: Т.к. 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 =B 1 +C 1 +D 1 . Набор (0,1) на переменных (x2,y2) получается из наборов (0,1), (1,0) и (1,1) на переменных (x1,y1). Т.е. B 2 =B 1 +C 1 +D 1 . Аналогично рассуждая, заметим, что С 2 =B 1 +C 1 +D 1 . D 2 = D 1 . Таким образом, получаем рекуррентные формулы: 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 Составим таблицу Количество наборов
Последнему уравнению (x7 ∨ y7) = 1 удовлетворяют все наборы, кроме тех, в которых x7=0 и y7=0. В нашей таблице число таких наборов A 7 . Тогда общее количество наборов равно B 7 + C 7 + D 7 = 127+127+1 = 255 Ответ:
255 Способы
решения систем логических уравнений
Киргизова
Е.В., Немкова А.Е.
Лесосибирский
педагогический институт –
филиал
Сибирского федерального университета, Россия
Умение мыслить последовательно, рассуждать
доказательно, строить гипотезы, опровергать негативные выводы, не приходит само
по себе, это умение развивает наука логика . Логика – это наука, изучающая
методы установленияистинности или
ложности одних высказываний на основе истинности или ложности других
высказываний .
Овладение азами этой науки невозможно без
решения логических задач. Проверка сформированности умений применять свои
знания в новой ситуации осуществляется за счет сдачи. В частности, это умение
решать логические задачи. Задания В15 в ЕГЭ, являются заданиями повышенной
сложности, так как они содержат системы логических уравнений. Можно выделить
различные способы решения систем логических уравнений. Это сведение к одному
уравнению, построение таблицы истинности, декомпозиция, последовательное
решение уравнений и т.д.
Задача:
Решить систему
логических уравнений:
Рассмотрим метод сведения к одному уравнению
.
Данный метод предполагает преобразование логических уравнений, таким образом,
чтобы правые их части были равны истинностному значению (то есть 1). Для этого
применяют операцию логического отрицания. Затем, если в уравнениях есть сложные
логические операции, заменяем их базовыми: «И», «ИЛИ», «НЕ». Следующим шагом
объединяем уравнения в одно, равносильное системе, с помощью логической
операции «И». После этого, следует сделать преобразования полученного уравнения
на основе законов алгебры логики и получить конкретное решение системы.
Решение 1:
Применяем
инверсию к обеим частям первого уравнения:
Представим импликацию через базовые
операции «ИЛИ», «НЕ»:
Поскольку левые части уравнений
равны 1, можно объединить их с помощью операции “И” в одно уравнение,
равносильное исходной системе:
Раскрываем
первую скобку по закону де Моргана и преобразовываем полученный результат:
Полученное
уравнение, имеет одно решение:
A
=0
, B
=0
и C
=1
.
Следующий способ – построение таблиц истинности
.
Поскольку логические величины имеют только два значения, можно просто перебрать
все варианты и найти среди них те, при которых выполняется данная система
уравнений. То есть, мы строим одну общую таблицу истинности для всех уравнений
системы и находим строку с нужными значениями.
Решение 2:
Составим таблицу истинности для системы:
0
0
1
1
0
1
Полужирным выделена строчка, для
которой выполняются условия задачи. Таким образом, A
=0
, B
=0
и C
=1
.
Способ декомпозиции
.
Идея состоит в том, чтобы зафиксировать значение одной из
переменных (положить ее равной 0 или 1) и за счет этого упростить уравнения.
Затем можно зафиксировать значение второй переменной и т.д.
Решение 3:
Пусть A
= 0, тогда
:
Из первого уравнения получаем
B
=0,
а из второго – С=1. Решение системы: A
=
0
, B
= 0
и C
= 1
.
Так же можно воспользоваться
методом последовательного решения уравнений
, на каждом шаге добавляя по
одной переменной в рассматриваемый набор. Для этого необходимо преобразовать
уравнения таким образом, что бы переменные вводились в алфавитном порядке.
Далее строим дерево решений, последовательно добавляя в него переменные.
Первое уравнение системы зависит
только от A
и B
, а второе уравнение от А и C
. Переменная А может принимать 2
значения 0 и 1:
Таким
образом, получили решение системы: A
=
0
, B
= 0
и C
= 1
.
В ЕГЭ по информатике очень часто требуется
определить количество решений системы логических уравнений, без нахождения
самих решений, для этого тоже существуют определенные методы. Основной способ
нахождения количества решений системы логических уравнений – замена переменных
. Сначала необходимо
максимально упростить каждое из уравнений на основе законов алгебры логики, а
затем заменить сложные части уравнений новыми переменными и определить
количество решений новой системы. Далее вернуться к замене и определить для нее
количество решений.
Задача:
Сколько решений имеет уравнение (A
→
B
) +
(C
→
D
) = 1? Где A, B, C, D –
логические переменные.
Решение:
Введем новые переменные:
X
=
A
→
B
и
Y
=
C
→
D
. С
учетом новых переменных уравнение запишется в виде:
X
+
Y
=
1.
Дизъюнкция верна в трех случаях: (0;1), (1;0) и
(1;1), при этом
X
и
Y
является импликацией,
то есть является истинной в трех случаях и ложной – в одном. Поэтому случай
(0;1) будет соответствовать трем возможным сочетаниям параметров. Случай (1;1)
– будет соответствовать девяти возможным сочетаниям параметров исходного
уравнения. Значит, всего возможных решений данного уравнения 3+9=15.
Следующий способ определения количества решений
системы логических уравнений – бинарное
дерево
. Рассмотрим данный метод на примере.
Задача:
Сколько различных
решений имеет система логических уравнений:
Приведенная система уравнений равносильна
уравнению:
(
x
1
→
x
2
)*(
x
2
→
x
3
)*…*(
x m
-1
→
x m
) = 1.
Предположим, что
x
1
–
истинно, тогда из первого уравнения получаем, что
x
2
также истинно, из
второго -
x
3
=1, и так далее до
x m
= 1. Значит набор (1; 1; …; 1) из
m
единиц является решением системы. Пусть теперь
x
1
=0, тогда из первого
уравнения имеем
x
2
=0 или
x
2
=1.
Когда
x
2
истинно получаем, что
остальные переменные также истинны, то есть набор (0; 1; …; 1) является
решением системы. При
x
2
=0 получаем, что
x
3
=0 или
x
3
=, и так далее.
Продолжая до последней переменной, получаем, что решениями уравнения являются
следующие наборы переменных (m
+1 решение, в каждом
решении по
m
значений переменных):
(1; 1; 1; …; 1)
(0; 1; 1; …; 1)
(0; 0; 0; …; 0)
Такой подход хорошо иллюстрируется с помощью
построения бинарного дерева. Количество возможных решений – количество
различных ветвей построенного дерева. Легко заметить, что оно равно
m
+1.
Переменные
Дерево
Количество
решений
x 1
x 2
x 3
В случае трудностей в рассуждениях и построении
дерева решений можно искать решение с использованием таблиц истинности
, для одного – двух уравнений.
Перепишем систему уравнений в виде:
И составим таблицу истинности отдельно для
одного уравнения:
x 1
x 2
(x 1 → x 2)
Составим таблицу истинности для двух уравнений:
x 1
x 2
x 3
x 1 → x 2
x 2 → x 3
(x 1 → x 2) * (x 2 → x 3)
Далее можно увидеть, что одно уравнение истинно
в следующих трех случаях: (0; 0), (0; 1), (1; 1). Система двух уравнений истина
в четырех случаях (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1). При этом сразу
видно, что существует решение, состоящее из одних нулей и еще m
решений,
в которых добавляется по одной единице, начиная с последней позиции до
заполнения всех возможных мест. Можно предположить, что общее решение будет
иметь такой же вид, но чтобы такой подход стал решением, требуется
доказательство, что предположение верно.
Подводя итог всему вышесказанному, хочется
обратить внимание, на то, что не все рассмотренные методы являются
универсальными. При решении каждой системы логических уравнений следует
учитывать ее особенности, на основе которых и выбирать метод решения.
Литература:
1.
Логические задачи / О.Б.
Богомолова – 2-е изд. – М.: БИНОМ. Лаборатория знаний, 2006. – 271 с.: ил.
2.
Поляков К.Ю. Системы
логических уравнений / Учебно-методическая газета для учителей информатики:
Информатика №14, 2011 г.
a ˅ b ≡ b ˅ a
a ^ b ≡ b ^ a
a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
a ^ (b ˅ с) ≡ (a ^ b) ˅ (a ^ с)
¬(¬а) ≡ а
a ^ ¬а ≡ false
a ˅ ¬а ≡ true
¬(а ˅ b) ≡ ¬а ˄ ¬b
¬(а ˄ b) ≡ ¬а ˅ ¬b
a ˄ a ≡ a
a ˅ a ≡ a
a ˄ true ≡ a
a ˄ false ≡ false
a ˄ (a ˅ b) ≡ a
a ˅ (a ˄ b) ≡ a
a → b ≡ ¬a ˅ b
a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)
(а ˄ b) ≡ ¬(¬а ˅ ¬b)X 1
X 2
X 3
X 4
F
1
1
0
0
1
0
1
1
1
1
1
0
0
1
0
A
B
C
F 1
F 2
F 1 ˄ F 2
0
0
0
1
0
0
0
0
1
1
0
0
0
1
0
1
0
0
0
1
1
1
0
0
1
0
0
0
0
0
1
0
1
0
1
0
1
1
0
1
1
1
1
1
1
0
0
0
имеет 6 решений. Вот как выглядит полное дерево решений для этого уравнения:
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
(x1→y1) = 1
Возвращаясь к исходным переменным X, заметим, что каждому значению переменной Y соответствует 2 значения переменных X, поэтому каждое решение в переменных Yпорождает 2 5 решений в переменных X. Две ветви порождают 2 * 2 5 решений, так что общее число решений равно 64.
X 1
X 2
X 3
X 4
F
1
0
0
1
1
0
1
1
1
1
1
0
1
0
0
Какие из следующих предложений правильно построены:
(a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
(a → b) → c = 0
X 0 → X 1 ˄ X 1 → X 2 = 1
X 2 → X 3 ˄ X 3 → X 4 = 1
X 5 → X 6 ˄ X 6 → X 7 = 1
X 7 → X 8 ˄ X 8 → X 9 = 1
X 0 → X 5 = 1
((((X 0 → X 1) → X 2) → X 3) →X 4) →X 5 = 1
P ˄ (M 1 ˅ M 2)
¬((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
(¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
(¬P 3 ˄ ¬P 4))Скачать:
Предварительный просмотр:
Подписи к слайдам:
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
Наборы
Обозн
.
Формула
i=1
i=2
i=3
i=4
i=5
i=6
i=7
(0,0)
A i
A i+1 =B i +C i +D i
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
Из первого уравнения следует, что
,
поэтому при A
=
0 п
олучаем B
= 0
, а при A
= 1
имеем B
= 1
. Итак, первое
уравнение имеет два решения относительно переменных A
и B
.
Изобразим второе уравнение, из которого определим значения C
для каждого варианта. При A
=1
импликация не может быть ложной, то есть вторая ветка дерева не
имеет решения. При
A
=0
получаем единственное решение
C
= 1
:
