Презентация на тему: Задачи ЕГЭ по информатике

Логика в задачах ГИА и ЕГЭ по информатике Вишневская М.П., учитель информатики МАОУ «Гимназия №3» г. Саратова 10.02.2014

Кодификатор и спецификация ГИА_2014 Кодификатор: Раздел 1. Информационные процессы Раздел 1.3.3 Логические значения, операции, выражения Спецификация: На уровне воспроизведения знаний проверяется такой фундаментальный теоретический материал, как: ………………………………………………………. основные элементы математической логики; ……………………………………………………….

Задания ГИА НЕ (число >50) ИЛИ (число чётное) = 0 0 0 число >50 число нечётное Решение: Ответ: 123

Задания ГИА Ответ: 5 1 1 1 1 0 1 0 1 1 0 1 0 1 0 0 1 1 1 1 1 1 1 0 0

Задания ГИА Ответ: АГБВ

Кодификатор и спецификация ЕГЭ_2014 Кодификатор: Раздел 1. Информация и информационные процессы 1.5.1 Высказывания, логические операции, кванторы, истинность высказывания Спецификация: В КИМ ЕГЭ по информатике не включены задания, требующие простого воспроизведения знания терминов, понятий, величин, правил (такие задания слишком просты для итогового экзамена). …………………………………………………………………………… формировать для логической функции таблицу истинности и логическую схему; формулировать запросы к базам данных и поисковым системам.

Задания ЕГЭ

Задания ЕГЭ

Задания ЕГЭ

Задания ЕГЭ

Задания ЕГЭ - ГИА Прослеживается преемственность между заданиями: №2 и А3 (Умение применять логические операции НЕ, И, ИЛИ); №18 и В12 (поиск в Интернете); возможно, между №12 и А6 (поиск в базах данных). Наибольшую сложность представляют задания А10 и В15 (!)

Задание ЕГЭ А10 Логические операции с утверждениями о множествах связаны с операциями над множествами (теоретико-множественными операциями). Пусть А, В – некоторые множества. Их элементы принадлежат некоторому универсальному множеству U (в зависимости от задачи это может быть, например, множество целых чисел, множество точек на прямой и т.д.). Тогда верно следующее: Пусть X - произвольный элемент универсального множества U. Тогда следующие высказывания эквивалентны ( ):

Задание ЕГЭ А10 2. Пусть А В, т.е. А – подмножество В, х – произвольный элемент универсального множества U. Тогда истинно высказывание: (x A) (x B). Обратно, пусть высказывание (x A) (x B) истинно при любом x U. Тогда А В. Обозначения: A B – пересечение множеств А и В A B – объединение множеств А и В U \ A – дополнение множества А до универсального множества U

Задание ЕГЭ А10 На числовой прямой даны два отрезка: P = [2, 10] и Q = [6, 14]. Выберите такой отрезок A, что формула тождественно истинна, то есть принимает значение 1 при любом значении переменной х.   1) [0, 3]          2) [3, 11]         3) [11, 15]       4) [15, 17]

Решение Преобразуем формулу. По определению, (F G) ( F \/ G) Из формулы (1) получаем: (x A) \/ (х Р) \/ (х Q) (2) Далее, (х Р) \/ (х Q) x (P Q) при любых x, P, Q. По условию, P = [2,10], Q = [6,14]. Т.о. P Q = [2,14]. Перепишем формулу (2): (x A) \/ (х [2,14]) 2 6 10 14

Решение 1) [0, 3]            2) [3, 11]           3) [11, 15]         4) [15, 17] Вернемся к импликации: (x A) (х [2,14]) Эта формула истинна тогда и только тогда, когда принадлежность числа х отрезку А влечет принадлежность числа х отрезку [2,14]. Т.е. отрезок А должен быть подмножеством отрезка [2,14]. Из четырех предложенных отрезков этому условию удовлетворяет только отрезок [3,11]. Ответ: 2 2 6 10 14

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

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

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

Условные обозначения конъюнкция :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

Метод замены переменных Сколько существует различных наборов значений логических переменных х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 г.)

Шаг 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 Решение

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

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

Метод исключения части решений Сколько существует различных наборов значений логических переменных х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, y1,y2,…, y5, при которых выполняется данная система равенств. В качестве ответа необходимо указать количество таких наборов.

Решение Первое уравнение – конъюнкция нескольких операций импликации, равна 1, т.е. каждая из импликаций истинна. Импликация ложна только в одном случае, когда 1 0, во всех других случаях (0 0, 0 1, 1 1) операция возвращает 1. Запишем это в виде таблицы: Шаг 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. Последовательное решение уравнений Т.о. получено 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

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

Метод динамического программирования Сколько различных решений имеет логическое уравнение x1 → x2 → x3 → x4 → x5 → x6 = 1, где x1, x2, …, x6 – логические переменные? В ответе не нужно перечислять все различные наборы значений переменных, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.

Решение Шаг 1. Анализ условия Слева в уравнении последовательно записаны операции импликации, приоритет одинаков. Перепишем: ((((X1 → X2) → X3) → X4) → X5) → X6 = 1 NB! Каждая следующая переменная зависит не от предыдущей, а от результата предыдущей импликации!

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

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

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

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

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

Решение Заметим, что 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

Решение Т.к. 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

Решение 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

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