Сколько решений имеет система логических уравнений. Логика
Способы решения систем логических уравнений
Киргизова Е.В., Немкова А.Е.
Лесосибирский педагогический институт –
филиал Сибирского федерального университета, Россия
Умение мыслить последовательно, рассуждать доказательно, строить гипотезы, опровергать негативные выводы, не приходит само по себе, это умение развивает наука логика . Логика – это наука, изучающая методы установленияистинности или ложности одних высказываний на основе истинности или ложности других высказываний .
Овладение азами этой науки невозможно без решения логических задач. Проверка сформированности умений применять свои знания в новой ситуации осуществляется за счет сдачи. В частности, это умение решать логические задачи. Задания В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 , а при A = 1 имеем B = 1 . Итак, первое уравнение имеет два решения относительно переменных A и B .
Изобразим второе уравнение, из которого определим значения C для каждого варианта. При A =1 импликация не может быть ложной, то есть вторая ветка дерева не имеет решения. При A =0 получаем единственное решение C = 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 г.
Данной материал содержит презентацию, в которой представлены методы решения логических уравнений и систем логических уравнений в задании В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 , [ Электронный ресурс ] .
Тема урока: Решение логических уравнений
Образовательная – изучение способов решения логических уравнений, формирование умений и навыков решения логических уравнений и построения логического выражения по таблице истинности;Развивающая - создать условия для развития познавательного интереса учащихся, способствовать развитию памяти, внимания, логического мышления;
Воспитательная : способствовать воспитанию умения выслушивать мнение других, воспитание воли и настойчивости для достижения конечных результатов.
Тип урока: комбинированный урок
Оборудование: компьютер, мультимедийный проектор, презентация 6.
Ход урока
Повторение и актуализацию опорных знаний. Проверка домашнего задания (10 минут)
На предыдущих уроках мы познакомились с основными законами алгебры логики, научились использовать эти законы для упрощения логических выражений.
Выполним проверку домашнего задания по упрощению логических выражений:
1. Какое из приведенных слов удовлетворяет логическому условию:
(первая буква согласная→вторая буква согласная) ٨ (последняя буква гласная → предпоследняя буква гласная)? Если таких слов несколько, укажите наименьшее из них.
1) АННА 2) МАРИЯ 3) ОЛЕГ 4) СТЕПАН
Введем обозначения:
А – первая буква согласная
В – вторая буква согласная
С – последняя буква гласная
D – предпоследняя буква гласная
Составим выражение:
Составим таблицу:
2. Укажите, какое логическое выражение равносильно выражению
Упростим запись исходного выражения и предложенных вариантов:
3. Дан фрагмент таблицы истинности выражения F:
Какое выражение соответствует F?Определим значения этих выражений при указанных значениях аргументов:
Ознакомление с темой урока, изложение нового материала (30 минут)
Мы продолжаем изучать основы логики и тема нашего сегодняшнего урока «Решение логических уравнений». Изучив данную тему, вы узнаете основные способы решения логических уравнений, получите навыки решения этих уравнений путем использования языка алгебры логики и умения составления логического выражения по таблице истинности.
1. Решить логическое уравнение
(¬K M) → (¬L M N) =0
Ответ запишите в виде строки из четырех символов: значений переменных K, L, M и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что K=1, L=1, M=0, N=1.
Решение:
Преобразуем выражение (¬K M) → (¬L M N)
Выражение ложно, когда оба слагаемые ложны. Второе слагаемое равно 0, если M
=0, N
=0, L
=1. В первом слагаемом K
=0, так как М=0, а
.
Ответ: 0100
2. Сколько решений имеет уравнение (в ответе укажите только число)?
Решение: преобразуем выражение
(A +B )*(C +D )=1
A +B =1 и C +D =1
2 способ: составление таблицы истинности
3 способ : построение СДНФ – совершенной дизъюнктивной нормальной формы для функции – дизъюнкции полных правильных элементарных конъюнкций.Преобразуем исходное выражение, раскроем скобки для того, чтобы получить дизъюнкцию конъюнкций:
(A+B)*(C+D)=A*C+B*C+A*D+B*D=
Дополним конъюнкции до полных конъюнкций (произведение всех аргументов), раскроем скобки:
Учтем одинаковые конъюнкции:
В итоге получаем СДНФ, содержащую 9 конъюнкций. Следовательно, таблица истинности для данной функции имеет значение 1 на 9 строках из 2 4 =16 наборов значений переменных.
3. Сколько решений имеет уравнение (в ответе укажите только число)?
Упростим выражение:
,
3 способ : построение СДНФ
Учтем одинаковые конъюнкции:
В итоге получаем СДНФ, содержащую 5 конъюнкций. Следовательно таблица истинности для данной функции имеет значение 1 на 5 строках из 2 4 =16 наборов значений переменных.
Построение логического выражения по таблице истинности:
для каждой строки таблицы истинности, содержащей 1 составляем произведение аргументов, причем, переменные, равные 0, входят в произведение с отрицанием, а переменные, равные 1 – без отрицания. Искомое выражение F будет составляется из суммы полученных произведений. Затем, если возможно, это выражение необходимо упростить.
Пример: дана таблица истинности выражения. Построить логическое выражение.
Решение:3. Задание на дом (5 минут)
Решить уравнение:
Сколько решений имеет уравнение (в ответе укажите только число)?
По заданной таблице истинности составить логическое выражение и
упростить его.
Можно выделить различные способы решения систем логических уравнений. Это сведение к одному уравнению, построение таблицы истинности и декомпозиция.
Задача: Решить систему логических уравнений:
Рассмотрим метод сведения к одному уравнению . Данный метод предполагает преобразование логических уравнений, таким образом, чтобы правые их части были равны истинностному значению (то есть 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 →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) |