Слайд 1Системы логических уравнений
ЕГЭ 23
Слайд 2№ 23_В1
Сколько различных решений имеет система логических уравнений
(x1 x2)
(x3 х4)=1
(x3 x4) (x5 х6)=1
...
(x9 x10) (x11 х12)=1
где x1, …, x12 - логические переменные?
Слайд 3(x1 x2) (x3 х4)=1
F(00)=F(00)+F(01)+F(11)
F(01)=F(00)+F(01)+F(11)
F(10)=F(00)+F(01)+F(10)+F(11)
F(11)=F(00)+F(01)+F(11)
Слайд 4F(00)=F(00)+F(01)+F(11)
F(01)=F(00)+F(01)+F(11)
F(10)=F(00)+F(01)+F(10)+F(11)
F(11)=F(00)+F(01)+F(11)
Слайд 5№ 23 В2
Сколько существует различных наборов значений логических переменных x1 , x2
, ... x6 , которые удовлетворяют всем перечисленным ниже условиям?
(x1 + x2 ≡ x2 * x3) → (x2 + x3 ≡ x3 * x4) = 1
(x2 + x3 ≡ x3 * x4) → (x3 + x4 ≡ x4 * x5) = 1
(x3 + x4 ≡ x4 * x5) → (x4 + x5 ≡ x5 * x6) = 1
Слайд 6(x1 + x2 ≡ x2 * x3) → (x2 + x3 ≡ x3 * x4) = 1
F(000)=F(000)+F(100);
F(001)= F(000)+F(100);
F(010)=F(101); F(011)= F(001)+F(101);
F(100)=F(010)+F(110); F(101)= F(010)+F(110);
F(111)= F(011)+F(111);
Слайд 7F(000)=F(000)+F(100); F(001)= F(000)+F(100);
F(010)=F(101); F(011)= F(001)+F(101);
F(100)=F(010)+F(110);
F(101)= F(010)+F(110);
F(111)= F(011)+F(111);
Слайд 823 В3
Сколько существует различных наборов значений логических переменных x1 , x2 ,
... x7 , y1 , y2 , ... y6 , которые удовлетворяют всем перечисленным ниже условиям:
(x1 ∨ x2) ∧ (x1 ∧ x2 → y1) = 1
(x2 ∨ x3) ∧ (x2 ∧ x3 → y2) = 1
...
(x6 ∨ x7) ∧ (x6 ∧ x7 → y6) = 1
Решение:
(x1x2) =(01, 10, 11)
Если (x1x2) =(11), то y1 = 1, в остальных случаях
y1= (0/1)
Строим отображение x1→ x2
Слайд 9(x1 ∨ x2) ∧ (x1 ∧ x2 → y1) = 1
(x1x2) =(01,
10, 11)
Если (x1x2) =(11), то y1 = 1, в остальных случаях y1= (0/1)
Слайд 11№23
Сколько существует различных наборов значений логических переменных 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
Слайд 12(x1 ∨ x2) ∧ (x1 ∧ x2 → x3) ∧ (¬x1 ∨
y1) = 1
Замечаем, что недопустимо сочетание для хiхi+1 (00), т.е. возможные решения (01, 10, 11). При этом, если xi ∧ xi+1 =1 (11), то xi+2 может принимать только одно значение равное 1. Если xi ∧ xi+1 =0 (01, 10), то x3 может принимать два значения 0 и 1.
Если xi = 1, то yi =1, если xi = 0, то yi =(0,1)
Слайд 13(x1 ∨ x2) ∧ (x1 ∧ x2 → x3) ∧ (¬x1 ∨
y1) = 1
Слайд 14(x1 ∨ x2) ∧ (x1 ∧ x2 → x3) ∧ (¬x1 ∨
y1) = 1
Слайд 15F(00) =F(10)
F(01) =F(10)
F(10)= 2*F(01)
F(11)= 2*F(01)+F(11)
Построим отображение х1х2 в х2х3 с учетом
у (двойная стрелка показывает, что у может принимать два значения, т.о. удваивает решения
Слайд 16Для первых шести уравнений
F(00) =F(10)
F(01) =F(10)
F(10)= 2*F(01)
F(11)= 2*F(01)+F(11)
Слайд 17Подключаем седьмое уравнение
(x7 ∨ x8) ∧ (¬x7 ∨
y7) = 1,
При (x7 x8)=(00) решений нет
При (x7 x8)=(10 , 11) одно решение y7 =1
При (x7 x8)=(01) два решения y7 =1/0
Слайд 18Подключаем восьмое уравнение
(¬x8 ∨ y8) =
1
При (x7 x8)=(00) решений нет
При (x7 x8)=(01 , 11) одно решение y7 =1
При (x7 x8)=(10) два решения y7 =1/0
Слайд 19№23 В4
Сколько различных решений имеет система логических уравнений
(x1 ∧ y1) = (¬x2
∨ ¬y2)
(x2 ∧ y2) = (¬x3 ∨ ¬y3)
...
(x6 ∧ y6) = (¬x7 ∨ ¬y7)
где x1, …, x8, y1, …, y8, - логические переменные?
Слайд 21№23 В5
Сколько различных решений имеет система логических уравнений
(x1 ∧ y1) ≠
(¬x2 ∨ ¬y2)
(x2 ∧ y2) ≠ (¬x3 ∨ ¬y3)
...
(x6 ∧ y6) ≠ (¬x7 ∨ ¬y7)
где x1, …, x7, y1, …, y7, - логические переменные?
Слайд 23№23 В6
((x1 ≡ x2) ∨ (x3 ≡ x4)) ∧ ( ¬((x1
≡ x2) → (x3 ≡ x4))) = 1
((x5 ≡ x6) ∨ (x7 ≡ x8)) ∧ ( ¬((x5 ≡ x6) → (x7 ≡ x8))) = 1
((x1 ≡ x2) ∨ (x7 ≡ x8)) ∧ ( ¬((x1 ≡ x2) → (x7 ≡ x8))) = 1
((x5 ≡ x6) ∨ (x3 ≡ x4)) ∧ ( ¬((x5 ≡ x6) → (x3 ≡ x4))) = 1
(x9 ≠ x10) = 1
Слайд 24Решение
преобразуем первое логическое выражение:
((x1 ≡ x2) ∨ (x3 ≡ x4)) ∧ ( ¬((x1 ≡
x2) → (x3 ≡ x4))) = 1
((x1 ≡ x2) + (x3 ≡ x4)) * ( ¬((x1 ≠ x2) + (x3 ≡ x4))) = 1
((x1 ≡ x2) + (x3 ≡ x4)) * (x1 ≡ x2) * (x3 ≠ x4) = 1
(x1 ≡ x2) * (x1 ≡ x2) * (x3 ≠ x4) + (x3 ≡ x4) * (x1 ≡ x2) * (x3 ≠ x4) = 1
(x1 ≡ x2) * (x3 ≠ x4) = 1
Слайд 25Т.к. первые 4 уравнения однотипны, то все они будут сокращены подобно
первому уравнению и вся система примет вид:
(x1 ≡ x2) * (x3 ≠ x4) = 1
(x5 ≡ x6) * (x7 ≠ x8) = 1
(x1 ≡ x2) * (x7 ≠ x8) = 1
(x5 ≡ x6) * (x3 ≠ x4) = 1
(x9 ≠ x10) = 1
Слайд 26Для того, чтобы первое уравнение было ИСТИННО, необходимо и достаточно, чтобы
первые две переменные были равны, а две последующие разные. Этому условию удовлетворяют 4 набора х:
{0001,0010,1101,1110}
Для того, чтобы второе уравнение было ИСТИННО, необходимо и достаточно, чтобы 5-й и 6-й x были равны, а 7-й и 8-й разные. Этому условию удовлетворяют 4 набора х: {0001,0010,1101,1110}
Итого получили: 4*4=16 наборов
Слайд 27Третье уравнение включает в себя x1 и x2 из 1-го уравнения, а также x7 и x8 из
2-го. Проверим сократит ли третье уравнение найденные наборы х: нужно, чтобы (x1 ≡ x2) и (x7 ≠ x8). В найденных наборах это условие выполняется:
Следовательно, количество наборов не сократилось!
Слайд 28Третье уравнение включает в себя x3 и x4 из 1-го уравнения, а также x5 и x6 из
2-го. Проверим сократит ли третье уравнение найденные наборы х: нужно, чтобы (x5 ≡ x6) и (x3 ≠ x4). В найденных наборах это условие выполняется:
Следовательно, количество наборов не сократилось!
Последнее уравнение: (x9 ≠ x10) = 1 увеличит количество наборов в 2 раза, т.к. условию x9 ≠ x10 соответствуют два набора х {01, 10}
Вывод: 16*2=32
Ответ: 32
Слайд 29№23 В7
(¬x1 ∧ x2 ∧ ¬x3) ∨ (¬x1 ∧ x2 ∧ x3)
∨ (x1 ∧ ¬x2 ∧ ¬x3) = 0
(¬x2 ∧ x3 ∧ ¬x4) ∨ (¬x2 ∧ x3 ∧ x4) ∨ (x2 ∧ ¬x3 ∧ ¬x4) = 0
...
(¬x7 ∧ x8 ∧ ¬x9) ∨ (¬x7 ∧ x8 ∧ x9) ∨ (x7 ∧ ¬x8 ∧ ¬x9) = 0
Слайд 30Решение
Рассмотрим 1-е уравнение:
(¬x1 ∧ x2 ∧ ¬x3) ∨ (¬x1 ∧ x2 ∧ x3) ∨ (x1 ∧
¬x2 ∧ ¬x3) = 0
¬x1 ∧ (x2 ∧ ¬x3 ∨ x2 ∧ x3) ∨ (x1 ∧ ¬x2 ∧ ¬x3) = 0
(¬x1 ∧ x2 )∨ (x1 ∧ ¬x2 ∧ ¬x3) = 0
Построим для 1-го уравнения таблицу истинности:
Слайд 31Рассмотрим 2-е уравнение:
(¬x2 ∧ x3 ∧ ¬x4) ∨ (¬x2 ∧ x3 ∧ x4) ∨ (x2 ∧
¬x3 ∧ ¬x4) = 0
(¬x2 ∧ x3 )∨ (x2 ∧ ¬x3 ∧ ¬x4) = 0
Таблица истинности для него:
Слайд 32F000=F000; F001=F000; F101= F110; F111=F111
Ответ: 5
Слайд 33№23 В8
Сколько существует различных наборов значений логических переменных x1, x2, ...
x10, которые удовлетворяют всем перечисленным ниже условиям?
((x1 ≡ x2) ∨ (x3 ≡ x4)) ∧ ( ¬((x1 ≡ x2) → (x3 ≡ x4))) = 1
((x5 ≡ x6) ∨ (x7 ≡ x8)) ∧ ( ¬((x5 ≡ x6) → (x7 ≡ x8))) = 1
(x9 ≡ x10) = 1
Слайд 34№23 В8
преобразуем первое логическое выражение:
((x1 ≡ x2) ∨ (x3 ≡ x4)) ∧ (
¬((x1 ≡ x2) → (x3 ≡ x4))) = 1
((x1 ≡ x2) + (x3 ≡ x4)) * ( ¬((x1 ≠ x2) + (x3 ≡ x4))) = 1
((x1 ≡ x2) + (x3 ≡ x4)) * (x1 ≡ x2) * (x3 ≠ x4) = 1
(x1 ≡ x2) * (x1 ≡ x2) * (x3 ≠ x4) + (x3 ≡ x4) * (x1 ≡ x2) * (x3 ≠ x4) = 1
(x1 ≡ x2) * (x3 ≠ x4) = 1
Слайд 35(x1 ≡ x2) * (x3 ≠ x4) = 1
(x5 ≡ x6) * (x7 ≠ x8) = 1
(x9 =
x10) = 1
Слайд 36Для того, чтобы первое уравнение было ИСТИННО, необходимо и достаточно, чтобы
первые две переменные были равны, а две последующие разные. Этому условию удовлетворяют 4 набора х:
{0001,0010,1101,1110}
Для того, чтобы второе уравнение было ИСТИННО, необходимо и достаточно, чтобы 5-й и 6-й x были равны, а 7-й и 8-й разные. Этому условию удовлетворяют 4 набора х: {0001,0010,1101,1110}
Итого получили: 4*4=16 наборов
Слайд 37Добавляем последнее уравнение:
(x9 ≡ x10) = 1, т.е. (x9 ≡ x10)
= (00, 11)
Итого решений: 16*2 = 32
Слайд 38№23 В9
Сколько существует различных наборов значений логических переменных x1, x2, ...
x7, y1, y2, ... y7, которые удовлетворяют всем перечисленным ниже условиям?
(x1 ∧ y1) ≡ (¬x2 ∨ ¬y2)
(x2 ∧ y2) ≡ (¬x3 ∨ ¬y3)
...
(x6 ∧ y6) ≡ (¬x7 ∨ ¬y7)
Слайд 39Преобразуем систему уравнений
(x1 ∧ y1) ≡ (¬x2 ∨ ¬y2)
(x2 ∧ y2)
≡ (¬x3 ∨ ¬y3)
...
(x6 ∧ y6) ≡ (¬x7 ∨ ¬y7)
Слайд 4123 В.10
Сколько существует различных наборов значений логических переменных x1, x2, ...
x8, которые удовлетворяют всем перечисленным ниже условиям?
((x1 ≡ x2) ∧ (x3 ≡ x4)) ∨ (¬(x1 ≡ x2) ∧ ¬(x3 ≡ x4)) = 0
((x3 ≡ x4) ∧ (x5 ≡ x6)) ∨ (¬(x3 ≡ x4) ∧ ¬(x5 ≡ x6)) = 0
((x5 ≡ x6) ∧ (x7 ≡ x8)) ∨ (¬(x5 ≡ x6) ∧ ¬(x7 ≡ x8)) = 0
Слайд 42Решение
((x1 ≡ x2) ∧ (x3 ≡ x4)) ∨ (¬(x1 ≡ x2)
∧ ¬(x3 ≡ x4)) = 0
((x1 ≡ x2) ≡ (x3 ≡ x4)=0
(x1 ≡ x2) ≠ (x3 ≡ x4)
(x3 ≡ x4) ≠ (x5 ≡ x6)
(x5 ≡ x6) ≠ (x7 ≡ x8)
Слайд 43Решение
(x1 ≡ x2) ≠ (x3 ≡ x4)
(x3 ≡ x4) ≠ (x5
≡ x6)
Слайд 44Решение
(x1 ≡ x2) ≠ (x3 ≡ x4)
(x3 ≡ x4) ≠ (x5
≡ x6)
(x5 ≡ x6) ≠ (x7 ≡ x8)
F00=F01+F10 F11=F01+F10
F01=F00+F11 F10=F00+F11
Слайд 4523_В11
Сколько существует различных наборов значений логических переменных x1, х2, ..., x10
которые удовлетворяют всем перечисленным ниже условиям?
(x1 → х2) → (хЗ → х4) = 1
(хЗ → х4) → (х5 → хб) = 1
(х5 → хб) → (х7 → х8) = 1
(х7 → х8) → (х9 → х10) = 1
Слайд 47F00
F01 = F00+F01+F10+F11
F10 = F10
F11
Слайд 4823_В12
Сколько существует различных наборов значений логических переменных x1, x2, ... x9,
которые удовлетворяют всем перечисленным ниже условиям?
(x1 ∧ x2) ∨ (¬x1 ∧ ¬x2) ∨ (x1 ≡ x3) = 1
(x2 ∧ x3) ∨ (¬x2 ∧ ¬x3) ∨ (x2 ≡ x4) = 1
...
(x7 ∧ x8) ∨ (¬x7 ∧ ¬x8) ∨ (x7 ≡ x9) = 1
Слайд 49Преобразуем 1 уравнение
(x1 ≡ x2) ∨ (x1 ≡ x3) = 1
Тогда получим
систему:
(x1 ≡ x2) ∨ (x1 ≡ x3) = 1
(x2 ≡ x3) ∨ (x2 ≡ x4) = 1
...
(x7 ≡ x8) ∨ (x7 ≡ x9) = 1
Слайд 50F00=F00
F01=F00+F10
F10=F01+F11
F11=F11
Слайд 51F00=F00
F01=F00+F10
F10=F01+F11
F11=F11