Как решать логические функции по информатике. Логика в информатике решение уравнений

УДК 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-

Данной материал содержит презентацию, в которой представлены методы решения логических уравнений и систем логических уравнений в задании В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 перемножаются:

Сло­жим ко­ли­че­ство наборов: 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

Применение уравнений широко распространено в нашей жизни. Они используются во многих расчетах, строительстве сооружений и даже спорте. Уравнения человек использовал еще в древности и с тех пор их применение только возрастает. В математике существуют определенные задачи, которые посвящены логике высказываний. Чтобы решить данного рода уравнения необходимо обладать неким багажом знаний: знания законов логики высказываний, знания таблиц истинности логических функций 1 или 2 переменных, методы преобразования логических выражений. Кроме того, необходимо знать следующие свойства логических операций: конъюнкции, дизъюнкции, инверсии, импликации и эквивалентности.

Любую логическую функцию от \ переменных - \можно задать таблицей истинности.

Решим несколько логически уравнений:

\[\rightharpoondown X1\vee X2=1 \]

\[\rightharpoondown X2\vee X3=1\]

\[\rightharpoondown X3\vee X4=1 \]

\[\rightharpoondown X9\vee X10=1\]

Начнем решение с \[Х1\] и определим какие значения данная переменная может принимать: 0 и 1. Далее рассмотрим каждое их вышеприведенных значений и посмотрим, какое может быть при этом \[Х2.\]

Как видно из таблицы наше логическое уравнение имеет 11 решений.

Где можно решить логическое уравнение онлайн?

Решить уравнение вы можете на нашем сайте https://сайт. Бесплатный онлайн решатель позволит решить уравнение онлайн любой сложности за считанные секунды. Все, что вам необходимо сделать - это просто ввести свои данные в решателе. Так же вы можете посмотреть видео инструкцию и узнать, как решить уравнение на нашем сайте. А если у вас остались вопросы, то вы можете задать их в нашей групе Вконтакте http://vk.com/pocketteacher. Вступайте в нашу группу, мы всегда рады помочь вам.

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

Алгоритм решения систем уравнений по этому методу:

Преобразовать логическое уравнение, упростить его.

Определить последовательность решения уравнений в системе, так как в большинстве случаев идет последовательное решение уравнений сверху вниз (как они расположены в системе), но есть варианты, когда удобнее, проще начать решать снизу вверх.

Построить таблицу переменных, где задать начальные значения первой переменной (или последней).

Последовательно прописать возможные варианты следующей переменной при каждом значении первой.

После решения предыдущего уравнения, переходя на следующее, обязательно обращать внимание: какие переменные используются в предыдущем и последующем уравнении, так как полученные при решении в предыдущих уравнениях значения переменных переходят как варианты для следующих уравнений.

Обращать внимание на получаемые количества решения при переходе к следующей переменной, т.к. может быть выявлена закономерность в увеличении решений.

Пример1.

¬ X 1 ˅ X 2=1

¬ X 2 ˅ X 3=1

¬ X 3 ˅ X 4=1

¬ X 9 ˅ X 10=1

Начнем с Х1 и посмотрим какие значения эта переменная может принимать: 0 и 1.

Затем рассмотрим каждое из этих значений и посмотрим, какое может быть при этом Х2.

Ответ: 11 решений

Пример 2.

( X 1˄ X 2)˅(¬ X 1˄¬ X 2) ˅( X 1↔ X 3)=1

( X 2˄ X 3)˅(¬ X 2˄¬ X 3) ˅( X 2↔ X 4)=1

(X8˄ X9)˅(¬X8˄¬X9) ˅(X8↔X10)=0

Преобразуем по формуле (A ˄ B )˅ (¬ A ˄ ¬ B )= A ↔ B

Получаем:

( X 1↔ X 2) ˅ ( X 1↔ X 3) =1

( X 2↔ X 3) ˅ ( X 2↔ X 4) =1

( X 8↔ X 9) ˅ ( X 8↔ X 10) =0

Для Х1 =0 - 8 решений

Возьмем Х1=1 и посмотрим какие значение может принимать Х2. Теперь для каждого Х2 рассмотрим какие значения может принимать Х3 и т.д.

Для Х1=1 – 8 решений

Итого 8+8=16 решений

Ответ. 16 решений

Пример 3 .

¬ ( X 1↔ X 2) ˄ ( X 1 ˅ X 3) ˄ (¬ X 1 ˅ ¬ X 3 )=0

¬ ( X 2↔ X 3) ˄ ( X 2 ˅ X 4) ˄ (¬ X 2 ˅ ¬ X 4)=0

….

¬ ( X 8↔ X 9) ˄ ( X 8 ˅ X 10) ˄ (¬ X 8 ˅ ¬ X 10)=0

После преобразований (A ˅ B ) ˄(¬ A ˅¬ B )= ¬( A ↔ B )

получаем:

¬ ( X 1↔ X 2) ˄ ¬ ( X 1↔ X 3)=0

¬ ( X 2↔ X 3) ˄ ¬ ( X 2↔ X 4)=0

…..

¬ ( X 8↔ X 9) ˄ ¬ ( X 8↔ X 10)=0

Возьмем Х1=0 и посмотрим какие значение может принимать Х2. Теперь для каждого Х2 рассмотрим какие значения может принимать Х3 и т.д

Получилось 10 решений для Х1=0

То же самое проделаем для Х1=1. Получим тоже 10 решений

Итого:10+10=20

Ответ: 20 решений.

Пример 4.

(Х1 ˄ Х2) ˅ (¬Х1 ˄ ¬Х2 ) ˅ (Х2 ˄ Х3) ˅ (¬Х2 ˄¬ Х3) =1

(Х2 ˄ Х3) ˅ (¬Х2 ˄ ¬Х3) ˅ (Х3˄ Х4) ˅ (¬Х3 ˄¬ Х4)=1

….

(Х8 ˄ Х9) ˅ (¬Х8˄ ¬Х9) ˅ (Х9 ˄ Х10) ˅ (¬Х9 ˄¬ Х10)=0

Преобразуем по формулам. (A ˄ B )˅ (¬ A ˄ ¬ B )= A ↔ B . Получим:

(Х1↔ Х2) ˅ (Х2↔ Х3)=1

(Х2↔ Х3) ˅ (Х3↔ Х4)=1

(Х3↔ Х4) ˅ (Х4↔ Х5)=1

(Х4↔ Х5) ˅ (Х5↔ Х6)=1

(Х5↔ Х6) ˅ (Х6↔ Х7)=1

(Х6↔ Х7) ˅ (Х7↔ Х8)=1

(Х7↔ Х8) ˅ (Х8↔ Х9)=1

(Х8↔ Х9) ˅ (Х9↔ Х10)=0

Начнем с конца, потому что в последнем уравнении переменные определятся однозначно.

Пусть Х10=0, тогда Х9=1, Х8=0, Х7=0, Х6=0, а следующие переменные могут принимать разные значения. Будем рассматривать каждое .

Итого 21 решение для Х10=0

Теперь рассмотрим для Х10=1. Получаем тоже 21 решение

Итого:21+21=42

Ответ: 42 решения

Пример 5.

( X 1 ˄ X 2) ˅ (¬ X 1 ˄ ¬ X 2) ˅ (¬ X 3 ˄ X 4) ˅ ( X 3 ˄ ¬ X 4)=1

( X 3 ˄ X 4) ˅ (¬ X 3 ˄ ¬ X 4) ˅ (¬ X 5 ˄ X 6) ˅ ( X 5 ˄ ¬ X 6)=1

( X 5 ˄ X 6) ˅ (¬ X 5 ˄ ¬ X 6) ˅ (¬ X 7 ˄ X 8) ˅ ( X 7 ˄ ¬ X 8)=1

( X 7 ˄ X 8) ˅ (¬ X 7 ˄ ¬ X 8) ˅ (¬ X 9 ˄ X 10) ˅ ( X 9˄ ¬ X 10) =1

Преобразуем по формулам: (¬ A ˄ B ) ˅ ( A ˄ ¬ B )= A ↔ ¬ B

( A ˄ B )˅ (¬ A ˄ ¬ B )= A ↔ B

( X 1↔ X 2) ˅ ( X 3 ↔ ¬ X 4)=1

( X 3↔ X 4) ˅ ( X 5 ↔ ¬ X 6)=1

( X 5↔ X 6) ˅ ( X 7 ↔ ¬ X 8)=1

( X 7↔ X 8) ˅ ( X 9 ↔ ¬ X 10)=1

Рассмотрим какие значения могут принимать Х1 и Х2: (0,0), (0,1), (1,0), (1,1).

Рассмотрим каждый вариант и посмотрим какие значения при этом могут принимать Х3, Х4

Начиная с Х7, Х8 будем сразу записывать количество решений, так как сразу видно, что когда значения одинаковые (1,1) и (0,0), то следующие переменные имеют 4 решения, а когда разные (0,1) и (1,0) – 2 решения.

Итого: 80+80+32=192

Ответ:192 решения

Пример 6.

(Х1↔ Х2) ˅ (Х2 ↔Х3)=1

(Х2↔ Х3) ˅ (Х3↔Х4)=1

(Х3↔ Х4) ˅ (Х4 ↔Х5)=1

….

(Х8↔ Х9) ˅ (Х9 ↔Х10)=1

Возьмем Х1=0 и посмотрим какие значение может принимать Х2. Теперь для каждого Х2 рассмотрим какие значения может принимать Х3 и т.д.

Видим некоторую закономерность: Количество следующих решений равно сумме двух предыдущих.

То же самое для Х1=1 получаем 89 решений

Итого: 89+89=178 решений

Ответ: 178 решений

Решим еще одним способом

(Х1↔ Х2) ˅ (Х2 ↔Х3)=1

(Х2↔ Х3) ˅ (Х3↔Х4)=1

(Х3↔ Х4) ˅ (Х4 ↔Х5)=1

….

(Х8↔ Х9) ˅ (Х9 ↔Х10)=1

Введем замену:

T 1 =(Х1↔ Х2)

T 2 =(Х2↔ Х3)

T 3 =(Х3↔ Х4)

T 4 =(Х4↔ Х5)

T 5 =(Х5↔ Х6)

T 6 =(Х6↔ Х7)

T 7 =(Х7↔ Х8)

T 8 =(Х8↔ Х9)

T 9 =(Х9↔ Х10)

Получаем:

T 1 ˅ T 2=1

T 2 ˅ T 3=1

T 3 ˅ T 4=1

T 4 ˅ T 5=1

T 5 ˅ T 6=1

T 6 ˅ T 7=1

T 7 ˅ T 8=1

T 8 ˅ T 9=1

T 9 ˅ T 10=1

Возьмем T 1=1 и используем свойства дизъюнкции:

НО Вспомним, что

T 1 =(Х1↔ Х2)

T 2 =(Х2↔ Х3) и т.д.

Воспользуемся свойством эквивалентности и убедимся, глядя на таблицу, что

Когда Т =1, то получается два решения. А когда =0 –одно решение.

Следовательно, можно подсчитать количество единиц и умножить их на 2+ количество нулей. Подсчет, так же используя закономерность .

Получается, что количество единиц = предыдущему общему количеству решений Т, а количество нулей равно предыдущему количеству единиц

Итак. Получим. Так как единица дает два решения, то 34*2=68 решений из единицы+21 решение из 0.

Итого 89 решений для Т=1. Аналогичным способом получаем 89 решений для Т=0

Итого 89+89=178

Ответ: 178 решений

Пример 7.

(X 1 ↔ X 2) ˅ (X 3↔ X 4) ˄ ¬(X 1 ↔ X 2) ˅ ¬(X 3↔ X 4)=1

(X 3 ↔ X 4) ˅ (X 5↔ X 6) ˄ ¬(X 3 ↔ X 4) ˅ ¬(X 5↔ X 6)=1

(X 5 ↔ X 6) ˅ (X 7↔ X 8) ˄ ¬(X 5 ↔ X 6) ˅ ¬(X 7↔ X 8)=1

(X 7 ↔ X 8) ˅ (X 9↔ X 10) ˄ ¬(X 7 ↔ X 8) ˅ ¬(X 9↔ X 10)=1

Введем замену:

T 1=(X 1 ↔ X 2)

T 2=(X 3↔ X 4)

T 3=(X 5↔ X 6)

T 4=(X 7 ↔ X 8)

T 5=(X 9↔ X 10)

Получим:

(Т1 ˅ Т2) ˄ ¬(Т1 ˅¬ Т2)=1

(Т2 ˅ Т3) ˄ ¬(Т2˅¬ Т3)=1

(Т3 ˅ Т4) ˄ ¬(Т3 ˅¬ Т4)=1

(Т4 ˅ Т5) ˄ ¬(Т4˅¬ Т5)=1

Рассмотрим какие могут быть Т:

Т1

Т2

Т3

Т4

Т5

Итого

0

1

0

1

0

32

1

0

1

0

1

32

Т K ≠Т К+1 И Т K =Т К+2

Получаем: 2 5 =32 для Т

Итого: 32+32=64

Ответ: 64 решения.