Решение системы уравнений в информатике

Решение системы уравнений в информатике

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

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

Рассмотрим метод сведения к одному уравнению. Данный метод предполагает преобразование логических уравнений, таким образом, чтобы правые их части были равны истинностному значению (то есть 1). Для этого применяют операцию логического отрицания. Затем, если в уравнениях есть сложные логические операции, заменяем их базовыми: «И», «ИЛИ», «НЕ». Следующим шагом объединяем уравнения в одно, равносильное системе, с помощью логической операции «И». После этого, следует сделать преобразования полученного уравнения на основе законов алгебры логики и получить конкретное решение системы.

Решение 1: Применяем инверсию к обеим частям первого уравнения:

Представим импликацию через базовые операции «ИЛИ», «НЕ»:

Поскольку левые части уравнений равны 1, можно объединить их с помощью операции “И” в одно уравнение, равносильное исходной системе:

Раскрываем первую скобку по закону де Моргана и преобразовываем полученный результат:

Полученное уравнение, имеет одно решение: A =0, B=0 и C=1.

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

Решение 2: Составим таблицу истинности для системы:

Полужирным выделена строчка, для которой выполняются условия задачи. Таким образом, 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 ₁ – истинно, тогда из первого уравнения получаем, что x ₂ также истинно, из второго — x ₃=1, и так далее до x_m = 1. Значит набор (1; 1; …; 1) из m единиц является решением системы. Пусть теперь x ₁=0, тогда из первого уравнения имеем x ₂ =0 или x ₂ =1.

Когда x ₂ истинно получаем, что остальные переменные также истинны, то есть набор (0; 1; …; 1) является решением системы. При x ₂=0 получаем, что x ₃=0 или x ₃=, и так далее. Продолжая до последней переменной, получаем, что решениями уравнения являются следующие наборы переменных ( m +1 решение, в каждом решении по m значений переменных):

Такой подход хорошо иллюстрируется с помощью построения бинарного дерева. Количество возможных решений – количество различных ветвей построенного дерева. Легко заметить, что оно равно m +1.

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

Обращаем Ваше внимание, что в соответствии с Федеральным законом N 273-ФЗ «Об образовании в Российской Федерации» в организациях, осуществляющих образовательную деятельность, организовывается обучение и воспитание обучающихся с ОВЗ как совместно с другими обучающимися, так и в отдельных классах или группах.

Описание презентации по отдельным слайдам:

14.06.2005 (формальная) Математическая логика Часть 5. Решение систем логических уравнений

Системы логических уравнений (ЕГЭ-2011) Три типа задач: I тип — В уравнениях используется операции дизъюнкции (конъюнкции), одна переменная входит в 2 уравнения. II тип — В уравнениях используется операции дизъюнкции (конъюнкции), сложные переменные представлены тождеством, одна сложная переменная входит в 2 уравнения. III тип — В уравнениях используется операции дизъюнкции (конъюнкции), сложные переменные, которые могут быть упрощены путем введения независимых новых переменных и применения законов логических преобразований. IV тип — В уравнениях используется операции дизъюнкции (конъюнкции), сложные переменные, которые не могут быть упрощены путем введения независимых новых переменных. V тип – Одна переменная входит в одно слагаемое во всех уравнениях VI, VII тип – Одна переменная входит во все слагаемые в уравнении одним из наиболее известных проектов создания компьютеров пятого поколения пред­полагается использование логических исчислений в качестве ос­новной системы программирования. Поэтому специалисты, ра­ботающие в различных областях информатики, проявляют все большее внимание и интерес к математической логике. Проник­новение методов математической логики в информатику уже привело к новым результатам, имеющим первостепенное практичес­кое значение. В частности, к созданию нового языка программи­рования ПРОЛОГ — языка, принципиально отличающегося от всех созданных ранее.

I тип Сколько различных решений имеет система уравнений ¬X1  X2 = 1 ¬X2  X3 = 1 . ¬X9  X10 = 1 где x1, x2, …, x10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов. ¬X1  X2 = 1 Ответ: 11 вариантов решений Типы уравнений I Решаем второе уравнение http://krolyakov.narod.ru ¬X1 = 0 X2 = 1 ¬X1 = 1 X2 = 0 ¬X1 = 1 X2 = 1 X1 = 1 X2 = 1 X1 = 0 X2 = 0 X1 = 0 X2 = 1 X2 = 1 X3 = 1 X2 = 0 X3 = 0 X2 = 0 X3 = 1 X2 X1 0 0 1 0 1 1 X3 X2 X1 0 0 0 1 0 0 1 1 0 1 1 1 Кол-во уравнений Кол-вопеременных Кол-во вариантов решений 1 2 3 2 3 4 3 4 5 Решаем по очереди уравнения и ищем закономерности накопления вариантов решений:

Сколько различных решений имеет система уравнений X1  ¬ X2 = 1 X2  ¬ X3 = 1 . X9  ¬ X10 = 1 где x1, x2, …, x10 – логические переменные? Решаем самостоятельно Первое уравнение: X1  ¬ X2 = 1 Второе уравнение: X2  ¬ X3 = 1 Ответ: 11 вариантов решений http://krolyakov.narod.ru X1 = 0 ¬ X2 = 1 X1 = 1 ¬ X2 = 0 X1 = 1 ¬ X2 = 1 X1 = 0 X2 = 0 X1 = 1 X2 = 1 X1 = 1 X2 = 0 X2 = 0 X3 = 0 X2 = 1 X3 = 1 X2 = 1 X3 = 0 X2 X1 0 0 0 1 1 1 X3 X2 X1 0 0 0 0 0 1 0 1 1 1 1 1 Кол-вопеременных Кол-во вариантов решений 2 3 3 4 4 5

Сколько различных решений имеет система уравнений ¬X1  X2 = 0 ¬X2  X3 = 0 . ¬X9  X10 = 0 где x1, x2, …, x10 – логические переменные? Сколько различных решений имеет система уравнений ¬X1  X2 = 0 ¬X2  X3 = 0 . ¬X9  X10 = 0 где x1, x2, …, x10 – логические переменные? Сколько различных решений имеет система уравнений ¬X1  X2 = 1 ¬X2  X3 = 1 . ¬X9  X10 = 1 где x1, x2, …, x10 – логические переменные? Нет решения I 11 вариантов Нет решения Решаем по очереди уравнения и ищем закономерности накопления вариантов решений:

Вывод: Система уравнений типа ¬X1  X2 = 1, где используются операции дизъюнкции и одна переменная входит в 2 уравнения, имеют решение только в случае, когда дизъюнкция двух переменных равна 1. Кол-во вариантов решений = кол-во уравнений + 2, или Кол-во вариантов решений = кол-во переменных + 1. I

Задача 1. Следующие два высказывания истинны: Неверно, что если корабль А вышел в море, то корабль С – нет. В море вышел корабль В или корабль С, но не оба вместе. Какие корабли вышли в море. А= «корабль А вышел в море» В= «корабль В вышел в море» С= «корабль С вышел в море» А→ ¬ С = 0 А  В = 1 Последовательное решение уравнений: А  В = 1 А = 1 В = 0 А = 0 В = 1 А→ ¬ С = 0 А = 1 ¬ С = 0 А = 1 С = 1 А = 1 В = 0 С=1 Ответ:

II тип Сколько различных решений имеет система уравнений ¬(X1  X2)  (X3  X4) = 1 ¬(X3  X4)  (X5  X6) = 1 ¬(X5  X6)  (X7  X8) = 1 ¬(X7  X8)  (X9  X10) = 1 где x1, x2, …, x10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов. Введем обозначение сложных переменных: Y1 = (X1  X2) Y2= (X3  X4) Y3 = (X5  X6) Y4 = (X7  X8) Y5 = (X9  X10) Запишем систему уравнений: ¬Y1  Y2 = 1 ¬Y2  Y3 = 1 ¬Y3  Y4 = 1 ¬Y4  Y5 = 1 Cистема имеет 6 вариантов решений. Переменные Y — независимые II http://krolyakov.narod.ru Y5 Y4 Y3 Y2 Y1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1

Найдем варианты решений для исходных переменных Кол-во комбинаций для одного варианта решений: N=25=32 Всего решений: 32*6=192 Алгоритм 1. Ввести обозначения для сложных переменных. 2. Записать систему для новых переменных. 3. Найти количество вариантов решений для системы с новыми переменными (m). 4. Определить число состояний (k) исходных переменных для одного варианта решения. 5. Определить число комбинаций (N) с учетом всего количества введенных переменных (n): N=kn 6. Определить итоговое количество вариантов решения системы: N*m II http://krolyakov.narod.ru Y1 = 0; Y1 = 1; X1 =1; X2=0; X1 =0; X2=1; X1 =0; X2=0; X1 =1; X2=1; X1  X2=0; X1  X2=1;

III. Сколько различных решений имеет система уравнений (X1  X2)  (¬X1  ¬X2)  (¬X3  X4)  (X3  ¬X4) = 1 (X3  X4)  (¬X3  ¬X4)  (¬X5  X6)  (X5  ¬X6) = 1 (X5  X6)  (¬X5  ¬X6)  (¬X7  X8)  (X7  ¬X8) = 1 (X7  X8)  (¬X7  ¬X8)  (¬X9  X10)  (X9  ¬X10) = 1 где x1, x2, …, x10 – логические переменные? Используется закон замены эквивалентности: A  B = (A  B)  (¬ A  ¬B) и замены инверсии эквивалентности: ¬ (A  B) = ¬((A  B)  (¬ A  ¬B)) = ¬(A  B)  ¬(¬ A  ¬B) = (¬ A ¬ B)  (A  B) = ¬ A  A  ¬ A  B  A ¬ B  ¬ B  B = (¬ A  B)  (A ¬ B ) III (X1  X2)  ¬ (X3  X4) =1 (X3  X4)  ¬ (X5  X6) =1 (X5  X6)  ¬ (X7  X8) =1 (X7  X8)  ¬ (X9  X10) =1 Упростим уравнения: Решить самостоятельно. Проверка http://krolyakov.narod.ru

Замена эквивалентности Закон замены эквивалентности: A  B = (A  B)  (¬ A  ¬B) Замена инверсии эквивалентности: ¬ (A  B) = ¬((A  B)  (¬ A  ¬B)) = ¬(A  B)  ¬(¬ A  ¬B) = (¬ A ¬ B)  (A  B) = ¬ A  A  ¬ A  B  A ¬ B  ¬ B  B = (¬ A  B)  (A ¬ B )

Введем обозначение сложных переменных: Y1 = (X1  X2) Y2= (X3  X4) Y3 = (X5  X6) Y4 = (X7  X8) Y5 = (X9  X10) Запишем систему уравнений: Y1  ¬Y2 = 1 Y2  ¬Y3 = 1 Y3  ¬Y4 = 1 Y4  ¬Y5 = 1 Cистема имеет 6 вариантов решений. III Найдем варианты решений для исходных переменных N=25=32 Всего решений: 32*6=192 http://krolyakov.narod.ru Y1 = 0; Y1 = 1; X1  X2=0; X1  X2=1; X1 =1; X2=0; X1 =0; X2=1; X1 =0; X2=0; X1 =1; X2=1; Y5 Y4 Y3 Y2 Y1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1

Сколько различных решений имеет система уравнений ((X1  X2)  (X3  X4))  (¬(X1  X2)  ¬(X3  X4)) = 1 ((X3  X4)  (X5  X6))  (¬(X3  X4)  ¬(X5  X6)) = 1 ((X5  X6)  (X7  X8))  (¬(X5  X6)  ¬(X7  X8)) = 1 ((X7  X8)  (X9  X10))  (¬(X7  X8)  ¬(X9  X10)) = 1 где x1, x2, …, x10 – логические переменные? IV Алгоритм решения: Вводим обозначения сложных высказываний и переписываем уравнения. Упрощаем уравнения, используя замену эквивалентности и инверсии эквивалентности. Определяем количество вариантов решения для веденных переменных. Определяем количество комбинаций исходных переменных для одного варианта. Определяем итоговое количество вариантов решения Решаем самостоятельно http://krolyakov.narod.ru

Введем обозначение сложных переменных: Y1 = (X1  X2) Y2= (X3  X4) Y3 = (X5  X6) Y4 = (X7  X8) Y5 = (X9  X10) Запишем систему уравнений: (Y1  Y2)  (¬ Y1  ¬ Y2) = 1 (Y2  Y3)  (¬ Y2  ¬ Y3) = 1 (Y3  Y4)  (¬ Y3  ¬ Y4) = 1 (Y4  Y5)  (¬ Y4  ¬ Y5) = 1 Cистема имеет 2 варианта решения. IV Упростим уравнения: Y1  Y2 = 1 Y2  Y3 = 1 Y3  Y4 = 1 Y4  Y5 = 1 Кол-во комбинаций для одного варианта решений: N=25=32 Всего решений: 32*2=64 http://krolyakov.narod.ru Y5 Y4 Y3 Y2 Y1 0 0 0 0 0 1 1 1 1 1

Сколько различных решений имеет система уравнений (X2  X1)  (X2  X3)  (¬X2 ¬ X3)= 1 (X3  X1)  (X3  X4)  (¬X3 ¬ X4)= 1 . (X9  X1)  (X9  X10)  (¬X9 ¬ X10)= 1 (X10  X1) = 0 где x1, x2, …, x10 – логические переменные? V Используется закон замены эквивалентности: (X2  X1)  (X2  X3) = 1 (X3  X1)  (X3  X4) = 1 . (X9  X1)  (X9  X10)= 1 (X10  X1) = 0 http://krolyakov.narod.ru Применить замену переменных нельзя, так как не получится независимых переменных. Решаем табличным способом по уравнению.

V (X2  X1)  (X2  X3) = 1 Решаем второе уравнение: (X3  X1)  (X3  X4) = 1 Решаем первое уравнение: X2  X1=0 X2  X3=1 X2  X1=1 X2  X3=0 X2  X1=1 X2  X3=1 X1=0 X2 =1 X3=1 X1=1 X2 =0 X3=0 X1=1 X3 =1 X4=0 X1=0 X2 =0 X3=1 X1=1 X2 =1 X3=1 X1=0 X2 =0 X3=0 X3  X1=0 X3  X4=1 X3  X1=1 X3  X4=0 X3  X1=1 X3  X4=1 X1=0 X3 =1 X4=1 X1=1 X3 =0 X4=0 X1=1 X2 =1 X3=0 X1=0 X3 =0 X4=1 X1=1 X3 =1 X4=1 X1=0 X3 =0 X4=0 X1 X3 X2 0 0 0 0 1 0 1 0 0 0 1 1 1 0 1 1 1 1 X1 X4 X3 X2 0 0 0 0 0 1 0 0 0 1 1 0 1 0 0 0 0 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 Кол-вопере-менных Кол-во вариантов решений 3 6 4 8 5 10 6 12 7 14 8 16 9 18 10 20

V (X10  X1) = 0 X10 <> X1 Подключаем последнее уравнение: Ответ: Кол-во решений = 20-2=18 http://krolyakov.narod.ru X1 X4 X3 X2 0 0 0 0 0 1 0 0 0 1 1 0 1 0 0 0 0 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1

VI. Сколько различных решений имеет система уравнений (X1  X2)  (¬X1  ¬X2)  (X1  X3) = 1 (X2  X3)  (¬X2  ¬X3)  (X2  X4) = 1 . (X8  X9)  (¬X8  ¬X9)  (X8  X10) = 1 где x1, x2, …, x10 – логические переменные? VI Решаем самостоятельно Применим закон замены эквивалентности: (X1  X2)(X1  X3)=1 (X2  X3)(X2  X4)=1 . (X8  X9)(X8  X10)=1 http://krolyakov.narod.ru Независимые переменные ввести нельзя, решаем по уравнению

Решаем первое уравнение: (X1  X2)(X1  X3)=1 Решаем второе уравнение: (X2  X3)(X2  X4)=1 VI http://krolyakov.narod.ru X1  X2=0 X1  X3=1 X1=0 X2 =1 X3=0 X1=1 X2 =0 X3=1 X1=0 X2 =0 X3=1 X1=1 X2 =1 X3=1 X1=0 X2 =0 X3=0 X1=1 X2 =1 X3=0 X1  X2=1 X1  X3=0 X1  X2=1 X1  X3=1 X2  X3=0 X2  X4=1 X2  X3=1 X2  X4=0 X2  X3=1 X2  X4=1 X2=0 X3 =1 X4=0 X2=1 X3 =0 X4=1 X2=0 X3 =0 X4=1 X2=1 X3 =1 X4=1 X2=0 X3 =0 X4=0 X2=1 X3 =1 X4=0 X3 X2 X1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 1 1 1 1 X4 X3 X2 X1 0 0 0 0 1 0 0 0 1 0 1 0 1 0 1 1 1 1 1 1 X4 X3 X2 X1 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 0 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1

Ответ: 20 вариантов VI http://krolyakov.narod.ru X3 X2 X1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 1 1 1 1 X4 X3 X2 X1 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 0 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 Кол-вопеременных Кол-во вариантов решений 3 6 4 8 5 10 6 12 7 14 8 16 9 18 10 20 i Xi=Xi-1 Xi<>Xi-1 всего решений 3 2 4 6 4 2 2+4=6 8 5 2 2+6=8 10 6 2 2+8=10 12 7 2 2+10=12 14 8 2 2+12=14 16 9 2 2+14=16 18 10 2 2+16=18 20

(X1  X2)(X1  X3)=1 (X2  X3)(X2  X4)=1 . (X8  X9)(X8  X10)=1 Решение при помощи графа: дерево 1 0 X1 X2 1 X3 1 0 0 1 1 0 1 0 0 2 4 6 1 0 X4 1 0 0 1 0 1 8 Ответ: 20 вариантов VI X1=0 X2 =1 X3=0 X1=1 X2 =0 X3=1 X1=0 X2 =0 X3=1 X1=1 X2 =1 X3=1 X1=0 X2 =0 X3=0 X1=1 X2 =1 X3=0 X2=0 X3 =1 X4=0 X2=1 X3 =0 X4=1 X2=0 X3 =0 X4=1 X2=1 X3 =1 X4=1 X2=0 X3 =0 X4=0 X2=1 X3 =1 X4=0

VII Сколько различных решений имеет система уравнений (X1  X2)  (¬X1  ¬X2)  (X2  X3)  (¬X2  ¬X3) = 1 (X2  X3)  (¬X2  ¬X3)  (X3  X4)  (¬X3  ¬X4) = 1 . (X8  X9)  (¬X8  ¬X9)  (X9  X10)  (¬X9  ¬X10) = 1 где x1, x2, …, x10 – логические переменные? Применим закон замены эквивалентности: (X1  X2)(X2  X3)=1 (X2  X3)(X3 X4)=1 . (X8  X9)(X9  X10)=1 Решаем самостоятельно Ответ: 178 вариантов 1 0 X1 X2 1 X3 1 0 0 0 1 0 1 0 1 2 4 6 1 0 X4 0 0 1 1 0 1 10 1 0 0 1 0 0 1 1 0 1 0 1 1 0 1 0 0 1 X5 16

VII i всего решений 3 4 2 6 4 4+2=6 4 10 5 6+4=10 6 16 6 10+6=16 10 26 7 16+10=26 16 42 8 26+16=42 26 68 9 42+26=68 42 110 10 68+42=110 68 178

Задача №23. Решение систем логических уравнений.

Решение систем логических уравнений методом замены переменных

Метод замены переменных применяется, если некоторые переменные входят в состав уравнений только в виде конкретного выражения, и никак иначе. Тогда это выражение можно обозначить новой переменной.

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных 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.

Сколько существует различных наборов значений логических переменных x1, x2, . x9, y1, y2, . 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 наборов.

Решение систем логических уравнений методом визуального определения рекурсии.

Этот метод применяется, если система уравнений достаточно проста и порядок увеличения количества наборов при добавлении переменных очевиден.

Сколь­ко раз­лич­ных ре­ше­ний имеет си­сте­ма урав­не­ний

где 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 наборов.

Решение систем логических уравнений различного типа

Сколь­ко су­ще­ству­ет раз­лич­ных на­бо­ров зна­че­ний ло­ги­че­ских пе­ре­мен­ных x₁, . x₄, y₁. y₄, z₁. z₄, ко­то­рые удо­вле­тво­ря­ют всем пе­ре­чис­лен­ным ниже усло­ви­ям?

В от­ве­те не нужно пе­ре­чис­лять все раз­лич­ные на­бо­ры зна­че­ний пе­ре­мен­ных x₁, . x₄, y₁, . y₄, z₁, . z₄, при ко­то­рых вы­пол­не­на дан­ная си­сте­ма ра­венств.

В ка­че­стве от­ве­та Вам нужно ука­зать ко­ли­че­ство таких на­бо­ров.

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

Рассмотрим первое уравнение. Конъюнкция истинна (равна 1) только тогда, когда все ее операнды истинны (равны 1). Импликация равна 1 на всех наборах, кроме (1,0). Значит, решением первого уравнения будут такие наборы x1, x2, x3, x4, в которых 1 не стоит левее 0 (5 наборов):