14.06.2005 Жуланова В. П., КРИПКиПРО Часть 5. Решение систем логических уравнений. - презентация

1 Жуланова В. П., КРИПКиПРО Часть 5. Решение систем логических уравнений

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

3 I тип Сколько различных решений имеет система уравнений ¬X 1 X 2 = 1 ¬X 2 X 3 = 1... ¬X 9 X 10 = 1 где x 1, x 2, …, x 10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов. ¬X 1 X 2 = 1 ¬X 1 = 0 X 2 = 1 ¬X 1 = 1 X 2 = 0 ¬X 1 = 1 X 2 = 1 X2X2 X1X X 1 = 1 X 2 = 1 X 1 = 0 X 2 = 0 X 1 = 0 X 2 = 1 X 3 = 1 X 2 = 0 X 3 = 0 X 2 = 0 X 3 = 1 X3X3 X2X2 X1X Кол-во уравнений Кол-во переменных Кол-во вариантов решений Ответ: 11 вариантов решений Типы уравнений Решаем второе уравнение

4 Сколько различных решений имеет система уравнений X 1 ¬ X 2 = 1 X 2 ¬ X 3 = 1... X 9 ¬ X 10 = 1 где x 1, x 2, …, x 10 – логические переменные? Решаем самостоятельно X 1 = 0 ¬ X 2 = 1 X 1 = 1 ¬ X 2 = 0 X 1 = 1 ¬ X 2 = 1 X 1 = 0 X 2 = 0 X 1 = 1 X 2 = 1 X 1 = 1 X 2 = 0 X 3 = 0 X 2 = 1 X 3 = 1 X 2 = 1 X 3 = 0 Первое уравнение: X 1 ¬ X 2 = 1 X2X2 X1X Второе уравнение: X 2 ¬ X 3 = 1 X3X3 X2X2 X1X Кол-во переменных Кол-во вариантов решений Ответ: 11 вариантов решений

5 Сколько различных решений имеет система уравнений ¬X 1 X 2 = 0 ¬X 2 X 3 = 0... ¬X 9 X 10 = 0 где x 1, x 2, …, x 10 – логические переменные? Сколько различных решений имеет система уравнений ¬X 1 X 2 = 0 ¬X 2 X 3 = 0... ¬X 9 X 10 = 0 где x 1, x 2, …, x 10 – логические переменные? Сколько различных решений имеет система уравнений ¬X 1 X 2 = 1 ¬X 2 X 3 = 1... ¬X 9 X 10 = 1 где x 1, x 2, …, x 10 – логические переменные? Нет решения 11 вариантов Нет решения

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

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

8 II тип Сколько различных решений имеет система уравнений ¬(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 где x 1, x 2, …, x 10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов. Введем обозначение сложных переменных: 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 = 1 ¬Y 2 Y 3 = 1 ¬Y 3 Y 4 = 1 ¬Y 4 Y 5 = 1 Cистема имеет 6 вариантов решений. Переменные Y - независимые Y5Y5 Y4Y4 Y3Y3 Y2Y2 Y1Y

9 Y 1 = 0;Y 1 = 1; X 1 =1; X 2 =0; X 1 =0; X 2 =1; X 1 =0; X 2 =0; X 1 =1; X 2 =1; X 1 X 2 =0;X 1 X 2 =1; Найдем варианты решений для исходных переменных Кол-во комбинаций для одного варианта решений: N=2 5 =32 Всего решений: 32*6=192 Алгоритм 1. Ввести обозначения для сложных переменных. 2. Записать систему для новых переменных. 3. Найти количество вариантов решений для системы с новыми переменными ( m ). 4. Определить число состояний ( k ) исходных переменных для одного варианта решения. 5. Определить число комбинаций ( N ) с учетом всего количества введенных переменных ( n ): N=k n 6. Определить итоговое количество вариантов решения системы: N*m

10 III. Сколько различных решений имеет система уравнений (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 где x 1, x 2, …, x 10 – логические переменные? Используется закон замены эквивалентности: 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 ) (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 Упростим уравнения: Решить самостоятельно. Проверка

11 Замена эквивалентности Закон замены эквивалентности: 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 )

12 Введем обозначение сложных переменных: 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 = 1 Y 2 ¬Y 3 = 1 Y 3 ¬Y 4 = 1 Y 4 ¬Y 5 = 1 Cистема имеет 6 вариантов решений. Y5Y5 Y4Y4 Y3Y3 Y2Y2 Y1Y Найдем варианты решений для исходных переменных Y 1 = 0;Y 1 = 1; X 1 X 2 =0;X 1 X 2 =1; X 1 =1; X 2 =0; X 1 =0; X 2 =1; X 1 =0; X 2 =0; X 1 =1; X 2 =1; N=2 5 =32 Всего решений: 32*6=192

13 Сколько различных решений имеет система уравнений ((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 где x 1, x 2, …, x 10 – логические переменные? Алгоритм решения: 1.Вводим обозначения сложных высказываний и переписываем уравнения. 2.Упрощаем уравнения, используя замену эквивалентности и инверсии эквивалентности. 3.Определяем количество вариантов решения для веденных переменных. 4.Определяем количество комбинаций исходных переменных для одного варианта. 5.Определяем итоговое количество вариантов решения Решаем самостоятельно

14 Введем обозначение сложных переменных: 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 ) = 1 (Y 2 Y 3 ) (¬ Y 2 ¬ Y 3 ) = 1 (Y 3 Y 4 ) (¬ Y 3 ¬ Y 4 ) = 1 (Y 4 Y 5 ) (¬ Y 4 ¬ Y 5 ) = 1 Cистема имеет 2 варианта решения. Y5Y5 Y4Y4 Y3Y3 Y2Y2 Y1Y Упростим уравнения : Y 1 Y 2 = 1 Y 2 Y 3 = 1 Y 3 Y 4 = 1 Y 4 Y 5 = 1 Y 1 = 0 Y 2 = 0 Y 1 = 1 Y 2 = 1 Кол-во комбинаций для одного варианта решений: N=2 5 =32 Всего решений: 32*2=64

15 Сколько различных решений имеет система уравнений (X 2 X 1 ) (X 2 X 3 ) (¬X 2 ¬ X 3 )= 1 (X 3 X 1 ) (X 3 X 4 ) (¬X 3 ¬ X 4 )= 1... (X 9 X 1 ) (X 9 X 10 ) (¬X 9 ¬ X 10 )= 1 (X 10 X 1 ) = 0 где x 1, x 2, …, x 10 – логические переменные? Используется закон замены эквивалентности: (X 2 X 1 ) (X 2 X 3 ) = 1 (X 3 X 1 ) (X 3 X 4 ) = 1... (X 9 X 1 ) (X 9 X 10 )= 1 (X 10 X 1 ) = 0

16 X 2 X 1 =0 X 2 X 3 =1 X 2 X 1 =1 X 2 X 3 =0 X 2 X 1 =1 X 2 X 3 =1 X 1 =0 X 2 =1 X 3 =1 X 1 =1 X 2 =0 X 3 =0 X 1 =1 X 3 =1 X 4 =0 X 1 =0 X 2 =0 X 3 =1 X 1 =1 X 2 =1 X 3 =1 X 1 =0 X 2 =0 X 3 =0 (X 2 X 1 ) (X 2 X 3 ) = 1 X1X1 X3X3 X2X Решаем второе уравнение: (X 3 X 1 ) (X 3 X 4 ) = 1 X 3 X 1 =0 X 3 X 4 =1 X 3 X 1 =1 X 3 X 4 =0 X 3 X 1 =1 X 3 X 4 =1 X 1 =0 X 3 =1 X 4 =1 X 1 =1 X 3 =0 X 4 =0 X 1 =1 X 2 =1 X 3 =0 X 1 =0 X 3 =0 X 4 =1 X 1 =1 X 3 =1 X 4 =1 X 1 =0 X 3 =0 X 4 =0 X1X1 X4X4 X3X3 X2X Кол-во пере- менных Кол-во вариантов решений Решаем первое уравнение:

17 (X 10 X 1 ) = 0 X 10 X 1 Подключаем последнее уравнение: X1X1 X4X4 X3X3 X2X Ответ: Кол-во решений = 20-2=18

18 VI. Сколько различных решений имеет система уравнений (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... (X 8 X 9 ) (¬X 8 ¬X 9 ) (X 8 X 10 ) = 1 где x 1, x 2, …, x 10 – логические переменные? Решаем самостоятельно Применим закон замены эквивалентности: (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 )=1

19 X 1 X 2 =0 X 1 X 3 =1 X 1 =0 X 2 =1 X 3 =0 X 1 =1 X 2 =0 X 3 =1 X 1 =0 X 2 =0 X 3 =1 X 1 =1 X 2 =1 X 3 =1 X 1 =0 X 2 =0 X 3 =0 X 1 =1 X 2 =1 X 3 =0 Решаем первое уравнение: (X 1 X 2 ) (X 1 X 3 )=1 X 1 X 2 =1 X 1 X 3 =0 X 1 X 2 =1 X 1 X 3 =1 X3X3 X2X2 X1X Решаем второе уравнение: (X 2 X 3 ) (X 2 X 4 )=1 X 2 X 3 =0 X 2 X 4 =1 X 2 X 3 =1 X 2 X 4 =0 X 2 X 3 =1 X 2 X 4 =1 X 2 =0 X 3 =1 X 4 =0 X 2 =1 X 3 =0 X 4 =1 X 2 =0 X 3 =0 X 4 =1 X 2 =1 X 3 =1 X 4 =1 X 2 =0 X 3 =0 X 4 =0 X 2 =1 X 3 =1 X 4 =0 X4X4 X3X3 X2X2 X1X X4X4 X3X3 X2X2 X1X

20 X3X3 X2X2 X1X X4X4 X3X3 X2X2 X1X Кол-во переменных Кол-во вариантов решений Ответ: 20 вариантов i X i =X i-1 X i X i-1 всего решений = = = = = = =1820

21 (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 )=1 Решение при помощи графа: дерево 10 X1X1 X2X2 1 X3X X4X Ответ: 20 вариантов X 1 =0 X 2 =1 X 3 =0 X 1 =1 X 2 =0 X 3 =1 X 1 =0 X 2 =0 X 3 =1 X 1 =1 X 2 =1 X 3 =1 X 1 =0 X 2 =0 X 3 =0 X 1 =1 X 2 =1 X 3 =0 X 2 =0 X 3 =1 X 4 =0 X 2 =1 X 3 =0 X 4 =1 X 2 =0 X 3 =0 X 4 =1 X 2 =1 X 3 =1 X 4 =1 X 2 =0 X 3 =0 X 4 =0 X 2 =1 X 3 =1 X 4 =0

22 Сколько различных решений имеет система уравнений (X 1 X 2 ) (¬X 1 ¬X 2 ) (X 2 X 3 ) (¬X 2 ¬X 3 ) = 1 (X 2 X 3 ) (¬X 2 ¬X 3 ) (X 3 X 4 ) (¬X 3 ¬X 4 ) = 1... (X 8 X 9 ) (¬X 8 ¬X 9 ) (X 9 X 10 ) (¬X 9 ¬X 10 ) = 1 где x 1, x 2, …, x 10 – логические переменные? Применим закон замены эквивалентности: (X 1 X 2 ) (X 2 X 3 )=1 (X 2 X 3 ) (X 3 X 4 )=1... (X 8 X 9 ) (X 9 X 10 )=1 Решаем самостоятельноОтвет: 178 вариантов 10 X1X1 X2X2 1 X3X X4X X5X5 16 X 1 X 2 =1 X 2 X 3 =1 X 1 =0 X 2 =0 X 3 =0 X 1 =1 X 2 =1 X 3 =1 X 2 =1 X 3 =0 X 4 =0 X 1 =1 X 2 =1 X 3 =0 X 1 =0 X 2 =0 X 3 =1 X 1 =0 X 2 =1 X 3 =1 X 1 X 2 =0 X 2 X 3 =1 X 1 X 3 =1 X 2 X 3 =0 X 2 =0 X 3 =0 X 4 =0 X 2 =1 X 3 =1 X 4 =1 X 2 =0 X 3 =1 X 4 =1 X 1 =1 X 2 =0 X 3 =0 X 2 =1 X 3 =1 X 4 =0 X 2 =0 X 3 =0 X 4 =1

23 i всего решений = = = = = = =

24 Сколько различных решений имеет система уравнений ((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 где x 1, x 2, …, x 10 – логические переменные? Получается 2 варианта решения. Каждая переменная Y имеет две пары значений (0, 1), т. е. число комбинаций исходных переменных в одном варианте равно 2 5 =32. Кол-во вариантов решений = 32*2=64 X 1 X 2 =Y 1 X 3 X 4 =Y 2 X 5 X 6 =Y 3 X 7 X 8 =Y 4 X 9 X 10 =Y 5 Перепишем систему: (Y 1 Y 2 ) (¬ Y 1 ¬Y 2 ) = 0 (Y 2 Y 3 ) (¬ Y 2 ¬Y 3 ) = 0 (Y 3 Y 4 ) (¬ Y 3 ¬Y 4 ) = 0 (Y 4 Y 5 ) (¬ Y 4 ¬Y 5 ) = 0 Применим закон замены эквивалентности: Y 1 Y 2 = 0 Y 2 Y 3 = 0 Y 3 Y 4 = 0 Y 4 Y 5 = 0 Введем обозначения:

25 Сколько различных решений имеет система уравнений (X 1 X 2 ) (X 1 X 10 ) (¬X 1 ¬ X 10 )= 1 (X 2 X 3 ) (X 2 X 10 ) (¬X 2 ¬ X 10 )= 1... (X 9 X 10 ) (X 9 X 10 ) (¬X 9 ¬ X 10 )= 1 (X 1 X 10 ) = 0 где x 1, x 2, …, x 10 – логические переменные? Применим закон замены эквивалентности: (X 1 X 2 ) (X 1 X 10 ) = 1 (X 2 X 3 ) (X 2 X 10 )= 1... (X 9 X 10 ) = 1 (X 1 X 10 ) = 0

26 X 1 X 2 =0 X 1 X 10 =1 X 1 =0 X 2 =1 X 10 =0 X 1 =1 X 2 =0 X 10 =1 X 1 =0 X 2 =0 X 10 =1 X 1 =1 X 2 =1 X 10 =1 X 1 =0 X 2 =0 X 10 =0 X 1 =1 X 2 =1 X 10 =0 Решаем первое уравнение: (X 1 X 2 ) (X 1 X 10 ) = 1 X 1 X 2 =1 X 1 X 10 =0 X 1 X 2 =1 X 1 X 10 =1 X 10 X2X2 X1X Решаем второе уравнение: (X 2 X 3 ) (X 2 X 10 )=1 X 2 X 3 =0 X 2 X 10 =1 X 2 X 3 =1 X 2 X 10 =0 X 2 X 3 =1 X 2 X 10 =1 X 2 =0 X 3 =1 X 10 =0 X 2 =1 X 3 =0 X 10 =1 X 2 =0 X 3 =0 X 10 =1 X 2 =1 X 3 =1 X 10 =1 X 2 =0 X 3 =0 X 10 =0 X 2 =1 X 3 =1 X 10 =0 X 10 X3X3 X2X2 X1X

27 X4X4 X3X3 X2X2 X1X X 3 X 4 =0 X 3 X 10 =1 X 3 =0 X 4 =1 X 10 =0 X 3 =1 X 4 =0 X 10 =1 X 3 =0 X 4 =0 X 1 0 =1 X 3 =1 X 4 =1 X 10 =1 X 3 =0 X 4 =0 X 10 =0 X 3 =1 X 4 =1 X 10 =0 Решаем предпоследнее и последнее уравнения: (X 3 X 4 ) (X 3 X 10 ) = 1 X 3 X 4 =1 X 3 X 10 =0 X 3 X 4 =1 X 3 X 10 =1 Кол-во переменных Кол-во вариантов решений (X 1 X 10 ) = 0 исключает варианты с X 1 = X 10 (X 9 X 10 ) = 1 нет таких вариантов в оставшихся ответах Решения нет

28 X 1 X 2 =0 X 1 X 10 =1 X 1 =0 X 2 =1 X 10 =0 X 1 =1 X 2 =0 X 10 =1 X 1 =0 X 2 =0 X 10 =1 X 1 =1 X 2 =1 X 10 =1 X 1 =0 X 2 =0 X 10 =0 X 1 =1 X 2 =1 X 10 =0 Решаем первое уравнение: (X 1 X 2 ) (X 1 X 10 ) = 1 X 1 X 2 =1 X 1 X 10 =0 X 1 X 2 =1 X 1 X 10 =1 X 10 X2X2 X1X Решаем второе уравнение: (X 2 X 3 ) (X 2 X 10 )=1 Исходя из данных в таблице, учитываем только вариант, когда X 2 X 10 =0 X 2 X 3 =1 X 2 X 10 =0 X 2 =0 X 3 =0 X 10 =1 X 2 =1 X 3 =1 X 10 =0 X 10 X3X3 X2X2 X1X Учитывая последнее уравнение, исключим варианты с : X 1 = X 10 Т. о. получаем, что X 10 всегда будет отлична от остальных переменных, что противоречит уравнению (X 9 X 10 ) = 1. Вывод: решения нет

29 Сколько различных решений имеет система уравнений ((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 где x 1, x 2, …, x 10 – логические переменные? Решаем самостоятельно Введем обозначение сложных переменных: 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 ) = 1 (Y 2 Y 3 ) (¬ Y 2 ¬ Y 3 ) = 1 (Y 3 Y 4 ) (¬ Y 3 ¬ Y 4 ) = 1 (Y 4 Y 5 ) (¬ Y 4 ¬ Y 5 ) = 1

30 Cистема имеет 2 варианта решения. Y5Y5 Y4Y4 Y3Y3 Y2Y2 Y1Y Упростим уравнения : ¬ (Y 1 Y 2 ) = 1) ¬(Y 2 Y 3 ) = 1 ¬(Y 3 Y 4 ) = 1 ¬(Y 4 Y 5 ) = 1 Y 1 = 0 Y 2 = 1 Y 1 = 1 Y 2 = 0 Кол-во комбинаций для одного варианта решений: N=2 5 =32 Всего решений: 32*2=64 (Y 1 ¬ Y 1 ) (Y 1 ¬Y 2 ) (Y 2 ¬Y 1 ) (Y 2 ¬ Y 2 ) = 1 (Y 1 ¬Y 2 ) (Y 2 ¬Y 1 ) = 1 ¬ (A B) = (¬ A B) (A ¬ B ) Y 2 = 0 Y 3 = 1 Y 2 = 1 Y 3 = 0 Y 4 = 1 Y 3 = 1 Y 4 = 0 Решение Y 4 = 0 Y 5 = 1 Y 4 = 1 Y 5 = 0

31 a ¬ b ¬c d = 1 c ¬ d ¬e f = 1 e ¬ f ¬g h = 1 g ¬ h ¬i j = 1 1. Приведем уравнения к единому виду, применив закон Де Моргана (a ¬ b) ¬(c ¬d) = 1 (c ¬ d) ¬(e ¬f) = 1 (e ¬ f) ¬(g ¬ h) = 1 (g ¬ h) ¬(i ¬ j) = 1 2. Решаем первое уравнение (см. след. слайд)

32 ¬(c ¬d) = 1 a ¬ b = 1 (a ¬ b) ¬(c ¬d) = 1 ¬(c ¬d) = 1 a ¬ b = 0 ¬(c ¬d) = 0 a ¬ b = 1 a = 0 ¬ b = 1 a = 1 ¬ b = 1 a = 1 ¬ b = 1 a = 0 b = 0 a = 1 b = 1 a = 1 b = 0 ¬(c ¬d) = 1 a ¬ b = 0 a = 0 ¬ b = 0 a = 0 b = 1 ¬(c ¬d) = 1 a ¬ b = ¬(c ¬d) = 0 a = 0 b = 0 a = 1 b = 1 a = 1 b = 0 ¬(c ¬d) = 0 2. Решаем первое уравнение 3. Записываем решение уравнения в таблицу. 4. Решаем второе уравнение ab ¬(c ¬d) ИТОГО: 7 вариантов решения

33 с ¬ d = 0 ¬(e ¬f) = 1 c ¬ d = 1 ¬(e ¬f) = 0 c ¬ d = 1 ¬(e ¬f) = Решаем второе уравнение 6. Записываем решение уравнения в таблицу. Видно, что при решении второго уравнения добавляется три строки, т. к. при ¬ (с ¬ d)=0 выражение ¬(e ¬f) принимает значения 0 и 1 ab ¬(c ¬d)¬(e ¬f) (c ¬ d) ¬(e ¬f) = 1 ¬ (с ¬ d)=1 5. Приведем выражение (с ¬ d) в соответствие с первым уравнением, применив инверсию ¬(e ¬f) = 1 ¬ (с ¬ d)=0 ¬(e ¬f) = 1 ¬ (с ¬ d)=0 ¬(e ¬f) = 0 7. Рассуждая аналогично для следующего уравнения, получаем еще плюс 3 решения, так как количество 0 в последнем столбце 3. Итого, каждое уравнение системы прибавляет 3 варианта решения. 7+3*3=16.