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

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

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

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

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

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

Задания ЕГЭ

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

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

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

Задание В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 t1t2t3t4t Т.к. tk = x2k-1 x2k (t1 = x1 x2,….), то каждому значению tk соответствует две пары значений x2k-1 и x2k, например: tk=0 соответствуют две пары - (0,1) и (1,0), а tk=1 – пары (0,0) и (1,1).

Шаг 3. Подсчет числа решений. Каждое t имеет 2 решения, количество t – 5. Т.о. для переменных t существует 2 5 = 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, при которых выполняется данная система равенств. В качестве ответа необходимо указать количество таких наборов.

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

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

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

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

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

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

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

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

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

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

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

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

Источники информации: О.Б. Богомолова, Д.Ю. Усенков. В15: новые задачи и новое решение // Информатика, 6, 2012, с. 35 – 39. К.Ю. Поляков. Логические уравнения // Информатика, 14, 2011, с [Электронный ресурс]. [Электронный ресурс].