Решение систем логических уравнений В15 (ЕГЭ-2012, 2013) В10 (ЕГЭ-2011)

Продолжите ряд: Последовательность Фибоначчи Последовательность Фибоначчи *2 Последовательность Фибоначчи +1

Для решения логических уравнений нужно знать: A B импликация( ложна, если А=1, В=0) A B = ¬ A B A B, эквиваленция (истинна, если А=1 и В=1 или А=0 и В=0) A B = ¬ A ¬ B A B А B, исключающее или (разделительная дизъюнкция, истинна А=1, В=0 и наоборот) А B= ¬ A B A ¬B А B= ¬ (A B) A B = ¬B ¬A

Решить логическое уравнение: ¬X1 + X2 = 1 Значения переменных Количество комбинаций-решений X1 X2 Решения уравнения – пары чисел (1,1), (0,1), (0,0)

x+y=6x-y=10 2x=16 x=8 y=-2 Ответ: (8, -2) Решить систему уравнений – это значит найти такие значения переменных, которые обращают КАЖДОЕ уравнение системы в верное равенство. Решить систему уравнений – это значит найти такие значения переменных, которые обращают КАЖДОЕ уравнение системы в верное равенство.

Решить систему логических уравнений: ¬X1 + X2 = 1 ¬X2 + X3 = 1 Значения переменных Количество комбинаций-решений X1 X2 X3 Решения уравнения – тройки чисел (1,1,1), (0,1,1), (0,0,1), (0,0,0)

Сколько различных решений имеет система уравнений ¬X1 X2 = 1 ¬X2 X3 = 1... ¬X9 X10 = 1 где x1, x2, …, x10 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

¬X1 + X2 = 1 ¬X2 + X3 = 1... ¬X9 + X10 = 1 Решениями будут являться двоичные цепочки длиной 10 символов (по количеству переменных), например, возможным решением может быть (0,0,0,1,1,1,1,1,1,1). Максимальное количество двоичных комбинаций 2 10 =1024. Задача состоит в том, чтобы найти только те из 1024 цепочек (их количество!), которые обращают все равенства в верные.

¬ X1 + X2 = 1 ¬X2 + X3 = 1 ¬X3 + X4 = 1... ¬X9 + X10 = 1 Дерево значений переменных Количество решений X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 Кроме пар (1,0)

ОтветОтвет: m+1 Сколько различных решений имеет система уравнений

Решения – двоичные цепочки: ¬X1 + X2 = 1 ¬X2 + X3 = 1... ¬X9 + X10 = 1 Перечислять не нужно! Ответ: 11

Сколько решений имеют системы логических уравнений: ¬X1 Λ X2 = 0 ¬X2 Λ X3 = 0... ¬X9 Λ X10 = 0 ¬X1 X2 = 1 ¬X2 X3 = 1... ¬X9 X10 = решения

Уравнения сводятся к следующим: X1 +¬ X2 = 1 X2 +¬ X3 = 1... X9 +¬ X10 = 1 X1 + X2 = 1 X2 + X3 = 1... X9 + X10 = 1 11 решений 144 решения

Х1+Х2=1 Х2+Х3=1… Х9+Х10=1 Дерево значений переменных Количество комбинаций X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 Ответ: 144

(Х1 Х2)+(Х2 Х3)=1 (Х2 Х3)+(Х3 Х4)=1 … (Х8 Х9)+(Х9 Х10)=1 Эквиваленция – операция симметричная. Поэтому можно построить неполное дерево (например для Х1=0). Для Х1=1 будет столько же решений. Рассмотрим полное и неполное дерево и сравним результаты. Найдите количество решений:

(Х1 Х2)+(Х2 Х3)=1 (Х2 Х3)+(Х3 Х4)=1 … (Х8 Х9)+(Х9 Х10)=1 Дерево значений переменных Количество комбинаций X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 АВ А В Ответ: 178

(Х1 Х2)+(Х2 Х3)=1 (Х2 Х3)+(Х3 Х4)=1 … (Х8 Х9)+(Х9 Х10)=1 Дерево значений переменных Количество комбинаций X1 X2 X3 X4 X5 X6 X7 X8 X9 X1 0 АВ А В Ответ: 178 Аналогично для Х1=1 Симметричная операция 89 * 2 = 178

Сколько различных решений имеет система уравнений ¬(x1 x2) Λ ¬(x2 x3) =1 ¬(x2 x3) Λ ¬(x3 x4) =1... ¬(x7 x8) Λ ¬(x8 x9) =1 где x1, x2,..., x9 – логические переменные? В ответе не нужно перечислять все различные наборы значений x1, x2,..., x9, при которых выполнена данная система равенств. В качестве ответа вам нужно указать количество таких наборов. Решите самостоятельно:

(x1 x2) Λ (x2 x3) =1 (x2 x3) Λ (x3 x4) =1... (x7 x8) Λ (x8 x9) =1 (x1 x2) =1 (x2 x3) =1 (x2 x3) =1... (x8 x9) =1 Решение Ответ: 2 решения В каждом уравнении истинна только одна из переменных, таким образом получаем, что решениями системы являются наборы: (1,0,1,0,1,0,1,0,1) и (0,1,0,1,0,1,0,1,0)

(X1 X2) (¬X1 ¬X2) (X1 X3) = 1 (X2 X3) (¬X2 ¬X3) (X2 X4) = 1... (X8 X9) (¬X8 ¬X9) (X8 X10) = 1 (X1 X2) (X1 X3) = 1 (X2 X3) (X2 X4) = 1... (X8 X9) (X8 X10) = 1 Ответ: 20 АВ+ ¬ А¬В = А В Сколько различных решений имеет система уравнений

переходя к отрицаниям по законам де Моргана (x1 x2) Λ (x1 x3) =0 (x2 x3) Λ (x2 x4) = (x7 x8) Λ (x7 x9) =0 (x8 x9) Λ (x8 x10) =0 Уравнения системы имеют вид: (a b) Λ (a c) =0 решение

abc 000| Составим таблицу истинности, в последнем столбце приведены возможные значения переменной С (x1 x2) Λ (x1 x3) =0 (x2 x3) Λ (x2 x4) =0... (x7 x8) Λ (x7 x9) =0 (x8 x9) Λ (x8 x10) =0 X1=0X1= ………… ……… решений

(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) = 0 Преобразовать и решить

¬X1 X2 X3 = 1 ¬X2 X3 X4 = 1 … ¬X8 X9 X10 = 1 ¬X1 + X2 + X3 = 1 ¬X2 + X3 + X4 = 1 … ¬X8 + X9 + X10 = 1 Кроме троек (1,0,0) Найти количество решений:

Дерево значений переменных Количество комбинаций X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 ¬X1 + X2 + X3 = 1 ¬X2 + X3 + X4 = 1 … ¬X8 + X9 + X10 = 1 Кроме троек (1,0,0) Ответ: 232

(X1 X2) + (X1 X3) = 1 (X2 X3) + (X2 X4) = 1... (X8 X9) + (X8 X10) = 1 Импликация – операция несимметричная. Поэтому нужно строить полное дерево (для Х1=0 и Х1=1). Найти количество решений:

(X1 X2) + (X1 X3) = 1 (X2 X3) + (X2 X4) = 1... (X8 X9) + (X8 X10) = 1 Дерево значений переменных Количество комбинаций X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 Ответ: 232 См. предыдущую задачу

(X1 X2) + (X1 X3) = 1 (X2 X3) + (X2 X4) = 1... (X8 X9) + (X8 X10) = 1 ¬X1 + X2 + X3 = 1 ¬X2 + X3 + X4 = 1 … ¬X8 + X9 + X10 = 1 А В= ¬А+В

Системы уравнений с ограничением

(Х1 Х2)+(Х2 Х3)=1 (Х2 Х3)+(Х3 Х4)=1 (Х3 Х4)+(Х4 Х5)=1 (Х4 Х5)+(Х5 Х6)=1 … (Х8 Х9)+(Х9 Х10)=1 X4 X5=1

Дерево значений переменных Количество комбинаций X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 (Х1 Х2)+(Х2 Х3)=1 (Х2 Х3)+(Х3 Х4)=1 (Х3 Х4)+(Х4 Х5)=1 (Х4 Х5)+(Х5 Х6)=1 … (Х8 Х9)+(Х9 Х10)=1 X4 X5=1 Кроме троек (1,1,0) (0,0,1) Ответ: 8

¬(X1 X2) + X1 · X3 + ¬X1 · ¬X3 = 1 ¬(X2 X3) + X2 · X4 + ¬X2 · ¬X4 = 1... ¬(X8 X9) + X8 · X10 + ¬X8 · ¬X10 = 1 X4 X5 = 0 (X1 X2) + (X1 X3) = 1 (X2 X3) + (X2 X4) = 1... (X8 X9) + (X8 X10) = 1 X4 X5 = 1 ¬(А В)= А В

¬(X1 X2) + (X1 X3) = 1 ¬(X2 X3) + (X2 X4) = 1... ¬(X8 X9) + (X8 X10) = 1 X5 X6 = 0 Решите самостоятельно:

¬(X1 X2) + (X1 X3) = 1 ¬(X2 X3) + (X2 X4) = 1... ¬(X8 X9) + (X8 X10) = 1 X6 X8 = 0 ¬(X1 X2) + (X1 X3) = 1 ¬(X2 X3) + (X2 X4) = 1... ¬(X8 X9) + (X8 X10) = 1 X1 X10 = 0 Решите самостоятельно:

Системы уравнений с разделенными переменными

(x1 x2) (x2 x3) = 1 Дерево значений переменных Количество комбинаций X1 X2 X3 Решите уравнение: АВ А В

(x1 x2) (x2 x3) (x3 x4) (x4 x5) = 1 Дерево значений переменных Количество комбинаций X1 X2 X3 X4 X5 Решите уравнение:

(x1 x2) (x2 x3) (x3 x4) (x4 x5) = 1 (у1 у2) (у2 у3) (у3 у4) (у4 у5) = 1 Дерево значений переменных Количество комбинаций X1 X2 X3 X4 X5 Найти количество решений: Для 2-го уравнения решение аналогичное

(x1 x2) (x2 x3) (x3 x4) (x4 x5) = 1 (у1 у2) (у2 у3) (у3 у4) (у4 у5) = 1 Для каждого уравнения – по 6 решений. К каждому решению 1-го уравнения можно приписать одно из 6 решений 2-го уравнения: Ответ: 36

(¬x1 x2) (x2 x3) (x3 x4) (x4 x5) = 1 (¬у1 у2) (у2 у3) (у3 у4) (у4 у5) = 1 x1 у1 = 1 Дерево значений переменных Количество комбинаций X1 X2 X3 X4 X5 Найти количество решений: Ограничение Ответ: 25

(x1 x2) (x2 x3) (x3 x4) = 1 ¬ ¬ ¬ (¬у1 у2) (¬у2 у3) (¬у3 у4) = 1 (у1 x1) (у2 x2) (у3 x3) (у4 x4) = 1 Найти количество решений: Представим третье уравнение в виде системы: 11 =1 22 =1 33 =1 44 =1

( 11) =1 x1x2x3x4 y1y2y3y Матрица решений

22 =1 x1x2x3x4 y1y2y3y Матрица решений

33 =1 x1x2x3x4 y1y2y3y Матрица решений

33 =1 x1x2x3x4 y1y2y3y Матрица решений

x1x2x3x4 y1y2y3y Ответ: 15 решений

Сколько существует различных наборов значений логических переменных x 1, x 2, … x 9, x 10, которые удовлетворяют всем перечисленным ниже условиям ((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 7 ) \/ ¬(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 Общая формула замены (k=1, 2, 3, 4, 5): t k = (x 2k-1 x 2k ) Получим: (t 1 \/ t 2 ) /\ (¬t 1 \/ ¬ t 2 ) =1 (t 2 \/ t 3 ) /\ (¬t 2 \/ ¬ t 3 ) =1 (t 3 \/ t 4 ) /\ (¬t 3 \/ ¬ t 4 ) =1 (t 4 \/ t 5 ) /\ (¬t 4 \/ ¬ t 5 ) =1

(tk \/ tk+1) /\ (¬tk \/ ¬ tk+1 ) =1 ¬(t1 t2 ) =1 ¬(t2 t3 ) =1 ¬(t3 t4 ) =1 ¬(t4 t5 ) =1 В любом решении последней системы значения переменных чередуются. Поэтому такая система имеет ровно два решения: и (первая цифра – значение переменной t1, вторая значение t2 Подсчет числа решений Каждому из двух решений системы для переменных t соответствует 2 5 = 32 решения исходной системы. Поэтому исходная система имеет 232 = 64 решения. Ответ:64

(x1 x2) (x2 x3) (x3 x4) (x4 x5) = 1 (у1 у2) (у2 у3) (у3 у4) = 1 (x1 x2) (x2 x3) (x3 x4) (x4 x5 ) = 1 (y5 y4) (y4 y3) (y3 y2) (y2 y1 ) = 1 x3 y3 =1 Решите самостоятельно: Ответ: 30 Ответ: 9 (x1 x2) (x2 x3) (x3 x4) (x4 x5 ) = 1 (y1 y2) (y2 y3) (y3 y4) (y4 y5 ) = 1 (x1 y1 ) (x2 y2) =1 Ответ: 27

Список источников Матвеенко Л.В.,презентация, г. Брянск, 2012 Матвеенко Л.В.,презентация, г. Брянск, 2012 Поляков К.Ю. Логические уравнения // Информатика, 14, 2011, с Поляков К.Ю. Логические уравнения // Информатика, 14, 2011, с Логические уравненияЛогические уравнения Демидова М.В. Решение заданий типа В10 КИМов ЕГЭ по информатике 2011 года посредством построения дерева. n.ru/attachment.aspx?id= Демидова М.В. Решение заданий типа В10 КИМов ЕГЭ по информатике 2011 года посредством построения дерева. n.ru/attachment.aspx?id=123369http:// n.ru/attachment.aspx?id=123369http:// n.ru/attachment.aspx?id= Демовариант ЕГЭ по информатике 2012 // ФИПИ, Демовариант ЕГЭ по информатике 2012 // ФИПИ, 2011.