Логические уравнения и системы логических уравнений в ЕГЭ
презентация к уроку по информатике и икт (11 класс) по теме

Слайд 1

Решение задания В15 (системы логических уравнений) Вишневская М.П., МАОУ «Гимназия №3» 18 ноября 2013 г., г. Саратов

Слайд 2

Задание В15 - одно из самых сложных в ЕГЭ по информатике!!! Проверяются умения: преобразовывать выражения, содержащие логические переменные; описывать на естественном языке множество значений логических переменных, при которых заданный набор логических переменных истинен; подсчитывать число двоичных наборов, удовлетворяющих заданным условиям. Самое сложное , т.к. нет формальных правил, как это сделать, требуется догадка.

Слайд 3

Без чего не обойтись!

Слайд 4

Без чего не обойтись!

Слайд 5

Условные обозначения конъюнкция : A /\ B , A  B , AB , А &B, A and B дизъюнкция: A \ / B , A + B , A | B , А or B отрицание:  A , А, not A эквиваленция : A  В, A  B, A  B исключающее «или»: A  B , A xor B

Слайд 6

Метод замены переменных Сколько существует различных наборов значений логических переменных х1, х2, …, х9, х10, которые удовлетворяют всем перечисленным ниже условиям: ((x1 ≡ x2) \/ (x3 ≡ x4)) /\ (¬(x1 ≡ x2) \/ ¬(x3 ≡ x4)) = 1 ((x3 ≡ x4) \/ (x5 ≡ x6)) /\ (¬(x3 ≡ x4) \/ ¬(x5 ≡ x6)) = 1 ((x5 ≡ x6) \/ (x7 ≡ x8)) /\ (¬(x5 ≡ x7) \/ ¬(x7 ≡ x8)) = 1 ((x7 ≡ x8) \/ (x9 ≡ x10)) /\ (¬(x7 ≡ x8) \/ ¬(x9 ≡ x10)) = 1 В ответе не нужно перечислять все различные наборы х1, х2, …, х9, х10, при которых выполняется данная система равенств. В качестве ответа необходимо указать количество таких наборов (демо-версия 2012 г.)

Слайд 7

Решение Шаг 1. Упрощаем, выполнив замену переменных t1 = x1  x2 t2 = x3  x4 t3 = x5  x6 t4 = x7  x8 t5 = x9  x10 После упрощения: (t1 \/ t2) /\ (¬t1 \/ ¬ t2 ) =1 (t2 \/ t3) /\ (¬t2 \/ ¬ t3 ) =1 (t3 \/ t4) /\ (¬t3 \/ ¬ t4 ) =1 (t4 \/ t5) /\ (¬t4 \/ ¬ t5 ) =1 Рассмотрим одно из уравнений: (t1 \/ t2) /\ (¬t1 \/ ¬ t2 ) =1 Очевидно, оно =1 только если одна из переменных равна 0, а другая – 1. Воспользуемся формулой для выражения операции XOR через конъюнкцию и дизъюнкцию: (t1 \/ t2) /\ (¬t1 \/ ¬ t2 ) = t1  t2 = ¬(t1 ≡ t2 ) =1 ¬(t1 ≡ t2 ) =1 ¬(t2 ≡ t3 ) =1 ¬(t3 ≡ t4 ) =1 ¬(t4 ≡ t5 ) =1

Слайд 8

Шаг2. Анализ системы ¬(t1 ≡ t2 ) =1 ¬(t2 ≡ t3 ) =1 ¬(t3 ≡ t4 ) =1 ¬(t4 ≡ t5 ) =1 t1 t2 t3 t4 t5 0 1 0 1 0 1 0 1 0 1 Т.к. tk = x2k-1 ≡ x2k ( t1 = x1  x2 ,…. ), то каждому значению tk соответствует две пары значений x2k-1 и x2k , например: tk =0 соответствуют две пары - (0,1) и (1,0) , а tk =1 – пары (0,0) и (1,1).

Слайд 9

Шаг3. Подсчет числа решений. Каждое t имеет 2 решения, количество t – 5. Т.о. для переменных t существует 2 5 = 32 решения. Но каждому t соответствует пара решений х , т.е. исходная система имеет 2*32 = 64 решения. Ответ: 64

Слайд 10

Метод исключения части решений Сколько существует различных наборов значений логических переменных х1, х2, …, х5, y1,y2,… , y5 , которые удовлетворяют всем перечисленным ниже условиям: (x1→ x2)∧(x2→ x3)∧(x3→ x4)∧(x4→ x5) =1; ( y1→ y2)∧( y2→ y3)∧( y3→ y4) ∧( y4→ y5) =1; y5→ x5 =1. В ответе не нужно перечислять все различные наборы х1, х2, …, х5, y 1 ,y2,… , y5, при которых выполняется данная система равенств. В качестве ответа необходимо указать количество таких наборов .

Слайд 11

Решение. Шаг1. Последовательное решение уравнений х1 1 0 х2 1 0 1 х3 1 0 1 1 х4 1 0 1 1 1 х5 1 0 1 1 1 1 Первое уравнение – конъюнкция нескольких операций импликации, равна 1, т.е. каждая из импликаций истинна. Импликация ложна только в одном случае, когда 1  0, во всех других случаях (0  0, 0  1, 1  1) операция возвращает 1. Запишем это в виде таблицы:

Слайд 12

Шаг1. Последовательное решение уравнений Т.о. получено 6 наборов решений для х1,х2,х3,х4,х5: (00000), (00001), (00011), (00111), (01111), (11111). Рассуждая аналогично, приходим к выводу, что для y1, y2, y3, y4, y5 существует такой же набор решений. Т.к. уравнения эти независимы, т.е. в них нет общих переменных, то решением этой системы уравнений (без учета третьего уравнения) будет 6*6= 36 пар «иксов» и «игреков». Рассмотрим третье уравнение: y5→ x5 =1 Решением являются пары: 0 0 0 1 1 1 Не является решением пара: 1 0

Слайд 13

Сопоставим полученные решения Там, где y5 =1, не подходят x5=0. таких пар 5. Количество решений системы : 36-5= 31 . Ответ: 31 Понадобилась комбинаторика!!!

Слайд 14

Метод динамического программирования Сколько различных решений имеет логическое уравнение x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1, где x 1, x 2, …, x 6 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количеств о таких наборов.

Слайд 15

Решение Шаг1. Анализ условия Слева в уравнении последовательно записаны операции импликации, приоритет одинаков. Перепишем: ((((X 1 → X 2 ) → X 3 ) → X 4 ) → X 5 ) → X 6 = 1 NB! Каждая следующая переменная зависит не от предыдущей, а от результата предыдущей импликации!

Слайд 16

Шаг2. Выявление закономерности Рассмотрим первую импликацию, X 1 → X 2. Таблица истинности: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 Из одного 0 получили 2 единицы, а из 1 получили один 0 и одну 1. Всего один 0 и три 1, это результат первой операции.

Слайд 17

Шаг2. Выявление закономерности Подключив к результату первой операции x 3 , получим: F(x 1 ,x 2 ) x 3 F(x 1 ,x 2 )  x 3 0 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 Из двух 0 – две 1, из каждой 1 (их 3) по одному 0 и 1 (3+3)

Слайд 18

Шаг 3. Вывод формулы Т.о. можно составить формулы для вычисления количества нулей N i и количества единиц E i для уравнения с i переменными: ,

Слайд 19

Шаг 4. Заполнение таблицы Заполним слева направо таблицу для i = 6, вычисляя число нулей и единиц по приведенным выше формулам; в таблице показано, как строится следующий столбец по предыдущему: : число переменных 1 2 3 4 5 6 Число нулей N i 1 1 3 5 11 21 Число единиц E i 1 2*1+1= 3 2*1+3= 5 11 21 43 Ответ: 43

Слайд 20

Метод с использованием упрощений логических выражений Сколько различных решений имеет уравнение ((J → K) → ( M  N  L))  (( M  N  L ) → (¬ J  K ))  ( M → J ) = 1 где J , K, L, M, N – логические переменные? В ответе не нужно перечислять все различные наборы значений J , K, L, M и N, при которых выполнено данное равенство. В качестве ответа Вам нужно указать количество таких наборов.

Слайд 21

Решение Заметим, что J → K = ¬ J  K Введем замену переменных: J → K=А, M  N  L =В Перепишем уравнение с учетом замены: (A → B)  (B → A)  (M → J)=1 4. (A  B)  (M → J)= 1 5. Очевидно, что A  B при одинаковых значениях А и В 6. Рассмотрим последнюю импликацию M → J =1 Это возможно, если: M=J=0 M=0, J=1 M=J=1

Слайд 22

Решение Т.к. A  B , то При M=J=0 получаем 1 + К=0. Нет решений. При M=0, J=1 получаем 0 + К=0, К=0, а N и L - любые , 4 решения : ¬ J  K = M  N  L K N L 0 0 0 0 0 1 0 1 0 0 1 1

Слайд 23

Решение 10. При M=J=1 получаем 0+К=1 *N * L , или K=N*L, 4 решения: 11. Итого имеет 4+4=8 решений Ответ: 8 K N L 0 0 0 0 0 1 0 1 0 1 1 1

Слайд 24

Источники информации: О.Б. Богомолова, Д.Ю. Усенков. В15: новые задачи и новое решение // Информатика, № 6, 2012, с. 35 – 39. К.Ю. Поляков. Логические уравнения // Информатика, № 14, 2011, с. 30-35. http://ege-go.ru/zadania/grb/b15/ , [ Электронный ресурс ] . http://kpolyakov.narod.ru/school/ege.htm , [ Электронный ресурс ] .