23. Логические уравнения — продолжение
23. Логические уравнения — продолжение — Сколько различных решений имеет система уравнений
(X1 ∨ X2) ∧ (¬X3 ∨ ¬X4) = 0
(X3 ∨ X4) ∧ (¬X5 ∨ ¬X6) = 0
(X5 ∨ X6) ∧ (¬X7 ∨ ¬X8) = 0
(X7 ∨ X8) ∧ (¬X9 ∨ ¬X10) = 0
где x1, x2, …, x10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
Решение:
x1 | x2 | x3 | x4 |
0 | 0 | 0 | 0 |
1 | |||
1 | 0 | ||
1 | |||
1 | 1 | 1 | |
1 | 0 | 1 | 1 |
1 |
x1x2 | x3x4 | 5x6 | x7x8 | x9x10 | |
00 | 1 | 1 | 1 | 1 | 1 |
01 | 1 | 1 | 1 | 1 | 1 |
10 | 1 | 1 | 1 | 1 | 1 |
11 | 1 | 4 | 7 | 10 | 13 |
16 |
Ответ: 16
Сколько различных решений имеет система уравнений
(X1 ≡ X2) → (X2 ≡ X3) = 1
(X2 ≡ X3) → (X3 ≡ X4) = 1
(X5 ≡ X6) → (X6 ≡ X7) = 1
где x1, x2, …, x7 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
Решение:
x1 | x2 | x3 |
0 | 0 | 0 |
1 | 0 | |
1 | ||
1 | 0 | 0 |
1 | ||
1 | 1 |
x1x2 | x2x3 | x3x4 | x4x5 | x5x6 | x6x7 | |
00 | 1 | 2 | 3 | 4 | 5 | 6 |
01 | 1 | 1 | 1 | 1 | 1 | 1 |
10 | 1 | 1 | 1 | 1 | 1 | 1 |
11 | 1 | 2 | 3 | 4 | 5 | 6 |
14 |
Ответ: 14
Сколько различных решений имеет система логических уравнений
(x1 ∧ x2 → x3) ∧ (x1 ∨ y1) = 1
(x2 ∧ x3 → x4) ∧ (x2 ∨ y2) = 1
(x3 ∧ x4 → x5) ∧ (x3 ∨ y3) = 1
(x4 ∧ x5 → x6) ∧ (x4 ∨ y4) = 1
(x5 ∧ x6 → x7) ∧ (x5 ∨ y5) = 1
x6 ∨ y6 = 1
где x1, …, x6, y1, …, y6, – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
Решение:
x1x2 | x2x3 | x3x4 | x4x5 | x5x6 | x6x7 | ||
00 | 1 | 3 | 5 | 11 | 21 | 43 | |
01 | 1 | 3 | 5 | 11 | 21 | 43 | |
10 | 1 | 1 | 3 | 5 | 11 | 21 | 42 |
11 | 1 | 3 | 9 | 23 | 57 | 135 | 270 |
Ответ: 398
Сколько различных решений имеет система логических уравнений
(x1 → y1) ∧ ((x2 ∨ y2) → (x1 ≡ y1)) = 1
(x2 → y2) ∧ ((x3 ∨ y3) → (x2 ≡ y2)) = 1
(x6 → y6) ∧ ((x7 ∨ y7) → (x6 ≡ y6)) = 1
x7 ≡ y7 = 1
где x1,x2,…,x7, у1,у2,…,у7 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполняются данные равенства. В качестве ответа нужно указать количество таких наборов.
Решение:
x1 | y1 | x2 | y2 |
0 | 0 | 0 | 0 |
1 | |||
1 | 0 | ||
1 | |||
1 | 0 | 0 | |
1 | 1 | 0 | 0 |
1 | |||
1 | 0 | ||
1 |
x1y1 | x2y2 | x3y3 | x4y4 | x5y5 | x6y6 | x7y7 | |
00 | 1 | 3 | 7 | 17 | 41 | 99 | 239 |
01 | 1 | 2 | 5 | 12 | 29 | 70 | 169 |
10 | 0 | 2 | 5 | 12 | 29 | 70 | 169 |
11 | 1 | 2 | 5 | 12 | 29 | 70 | 169 |
408 |
Ответ: 408
Сколько существует различных наборов значений логических переменных x1, x2, … x8, y1, y2, … y8, которые удовлетворяют всем перечисленным ниже условиям?
(x1→x2) /\ (x1→y1) = 1
(x2→x3) /\ (x2→y2) = 1
…
(x7→x8) /\ (x7→y7) = 1
(x8→y8) = 1
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, … x8, y1, y2, … y8, при которых выполнена данная система равенств.
В качестве ответа Вам нужно указать количество таких наборов.
Источник: СтатГрад 2017−2018
Решение:
(x1→x2) = 1
(x2→x3) = 1
…
(x7→x8) = 1
(x8→y8) = 1
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | (x1→y1) для каждого 0’а, y может 0 или 1 | |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 2 8 =256 | |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 2 7 =128 | |
0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 2 6 =64 | |
0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 2 5 =32 | |
0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 2 4 =16 | |
0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 2 3 =8 | |
0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 2 2 =4 | |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 2 =2 | |
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 0 =1 | |
256+128+64+32+16+8+4+2+1=511 |
Ответ: 511
Сколько существует различных наборов значений логических переменных x1 , x2 , … x8 , y1 , y2 , … y8 , которые удовлетворяют всем перечисленным ниже условиям?
(x1 ∨ x2) ∧ (x1 ∧ x2 → x3) ∧ (¬x1 ∨ y1) = 1
(x2 ∨ x3) ∧ (x2 ∧ x3 → x4) ∧ (¬x2 ∨ y2) = 1
…
(x6 ∨ x7) ∧ (x6 ∧ x7 → x8) ∧ (¬x6 ∨ y6) = 1
(x7 ∨ x8) ∧ (¬x7 ∨ y7) = 1
¬x8 ∨ y8 = 1
Решение:
(x1+x2) · (¬x1+¬x2+x3) · (¬x1+y1) = 1
x1 | x2 | x3 | y1 |
0 | 1 | 0 | 0-1 |
1 | |||
1 | 0 | 0 | 1 |
1 | |||
1 | 1 | 1 | 1 |
x1x2 | x2x3 | x3x4 | x4x5 | x5x6 | x6x7 | x7x8 | ||
00 | 0 | 1 | 2 | 2 | 4 | 4 | 8 | 0 |
01 | 1 | 1 | 2 | 2 | 4 | 4 | 8 | 8·2=16 |
10 | 1 | 2 | 2 | 4 | 4 | 8 | 8 | 8·2=16 |
11 | 1 | 3 | 5 | 9 | 13 | 21 | 29 | 29 |
61 |
(x7 ∨ x8) ∧ (¬x7 ∨ y7) = 1
¬x8 ∨ y8 = 1
x7 | x8 | y7 | y8 |
0 | 1 | 0-1 | 1 |
1 | 0 | 1 | 0-1 |
1 | 1 |
Ответ: 6 1
Сколько существует различных наборов значений логических переменных x1, x2, … x8, y1, y2, … y8, которые удовлетворяют всем перечисленным ниже условиям?
(x1→x2) /\ (y1→y2) /\ (y1→x1) = 1
(x2→x3) /\ (y2→y3) (y2→x2) = 1
…
(x7→x8) /\ (y7→y8) /\ (y7→x7) = 1
(y8→x8) = 1
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, … x8, y1, y2, … y8, при которых выполнена данная система равенств.
В качестве ответа Вам нужно указать количество таких наборов.
Задача №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)
Эквивалентность истинна, только если оба операнда равны. Решениями этого уравнения будут два набора:
z1 | z2 | z3 | z4 | z5 | z6 | z7 | z8 | z9 |
0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
Т.к. 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) переменных:
Ni+1 = Ni + 1. Тогда для десяти переменных получим 11 наборов.
Решение систем логических уравнений различного типа
Сколько существует различных наборов значений логических переменных x1, . x4, y1. y4, z1. z4, которые удовлетворяют всем перечисленным ниже условиям?
В ответе не нужно перечислять все различные наборы значений переменных x1, . x4, y1, . y4, z1, . z4, при которых выполнена данная система равенств.
В качестве ответа Вам нужно указать количество таких наборов.
Заметим, что три уравнения системы одинаковы на различных независимых наборах переменных.
Рассмотрим первое уравнение. Конъюнкция истинна (равна 1) только тогда, когда все ее операнды истинны (равны 1). Импликация равна 1 на всех наборах, кроме (1,0). Значит, решением первого уравнения будут такие наборы x1, x2, x3, x4, в которых 1 не стоит левее 0 (5 наборов):
Решение систем логических уравнений
Обращаем Ваше внимание, что в соответствии с Федеральным законом 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
http://ege-study.ru/ru/ege/materialy/informatika/zadanie-23/
http://infourok.ru/reshenie-sistem-logicheskih-uravneniy-3141907.html