Уравнения по информатике 11 класс

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

Данной материал содержит презентацию, в которой представлены методы решения логических уравнений и систем логических уравнений в задании В15 (№ 23, 2015) ЕГЭ по информатике. Известно, что это задание является одним из самых сложных среди заданий ЕГЭ. Презентация может быть полезна при проведении уроков по теме «Логика» в профильных классах, а также при подготовке к сдаче ЕГЭ.

Скачать:

Предварительный просмотр:

Подписи к слайдам:

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

Задание В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 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).

Шаг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, y 1 ,y2,… , y5, при которых выполняется данная система равенств. В качестве ответа необходимо указать количество таких наборов .

Решение. Шаг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. Запишем это в виде таблицы:

Шаг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 Понадобилась комбинаторика.

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

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

Шаг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, это результат первой операции.

Шаг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)

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

Шаг 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

Метод с использованием упрощений логических выражений Сколько различных решений имеет уравнение ((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 , [ Электронный ресурс ] .

По теме: методические разработки, презентации и конспекты

Конспект урока с презентацией «Решение тригонометрических уравнений» (с использованием логических союзов и кванторов)

Конспект урока «Решение тригонометрических уравнений» и презентация к нему.

статья «Решение системы логических уравнений»

Данная статья знакомит учителей и учеников с некоторыми методами решения систем логических уравнений. Может быть полезна на первоначальном этапе освоения данной темы.

Линейные уравнения и системы линейных уравнений с параметрами

Методическая разработка на тему: «Линейные уравнения и системы линейных уравнений с параметрами».

Решение логических уравнений и систем логических уравнений

Вариант решения задачи 23 ЕГЭ по информатике. «Системы логических уравнений».

Рассмотрен вариант решения задачи 23 демоверсии ЕГЭ по информатике. Применяется метод отображения.

Уравнения и системы уравнений. Рациональные, иррациональные, показательные и тригонометрические уравнения и системы. Равносильность уравнений, неравенств, систем.

Уравнения и системы уравнений. Рациональные, иррациональные, показательные и тригонометрические уравнения и системы. Равносильность уравнений, неравенств, систем.

Конспект урока для 11 класса по теме «Иррациональные уравнения и приемы преобразования уравнений. Методы решения иррациональных уравнений»

Конспект урока для 11 класса пр теме «Иррациональные уравнения и приемы преобразования уравнений. Методы решения иррациональных уравнений&quot.

Варианты ЕГЭ по информатике

Об экзамене

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

Структура

Часть 1 содержит 23 задания с кратким ответом. В этой части собраны задания с кратким ответом, подразумевающие самостоятельное формулирование последовательности символов. Задания проверяют материал всех тематических блоков. 12 заданий относятся к базовому уровню, 10 заданий к повышенному уровню сложности, 1 задание – к высокому уровню сложности.

Часть 2 содержит 4 задания, первое из которых повышенного уровня сложности, остальные 3 задания высокого уровня сложности. Задания этой части подразумевают запись развернутого ответа в произвольной форме.

На выполнение экзаменационной работы отводится 3 часа 55 минут (235 минут). На выполнение заданий части 1 рекомендуется отводить 1,5 часа (90 минут). Остальное время рекомендуется отводить на выполнение заданий части 2.

Пояснения к оцениванию заданий

Выполнение каждого задания части 1 оценивается в 1 балл. Задание части 1 считается выполненным, если экзаменуемый дал ответ, соответствующий коду верного ответа. Выполнение заданий части 2 оценивается от 0 до 4 баллов. Ответы на задания части 2 проверяются и оцениваются экспертами. Максимальное количество баллов, которое можно получить за выполнение заданий части 2, – 12.

Уравнения по информатике 11 класс

Начиная с 2021 года ЕГЭ по информатике и ИКТ проходит в компьютерной форме.

Школьник, сдающий экзамен по информатике и ИКТ, должент выполнить задания, требующие составления и отладки компьютерных программ в выбранной им самим среде программирования, работы с электронными таблицами и умения осуществлять информационный поиск.

Всего демонстрационный вариант ЕГЭ по информатике и ИКТ содержит 27 заданий, из них 9 заданий необходимо выполнить на компьютере. Допускается выполнение заданий по программированию на языках программирования C++, Java, C#, Pascal, Python, Школьный алгоритмический язык. Заданий, связанных с использованием языка Бейсик, в демонстрационном варианте ЕГЭ по информатике и ИКТ нет.

Демонстрационные варианты ЕГЭ по информатике содержат верные ответы ко всем заданиям, а также критерии оценивания.

В демонстрационный вариант ЕГЭ по информатике и ИКТ 2022 года по сравнению с демонстрационным вариантом по информатике и ИКТ 2021 года были внесены следующие изменения:

• Задание 3 нужно выполнять с использованием файла, содержащего простую реляционную базу данных, состоящую из нескольких таблиц
• Задание 17 нужно выполнять с использованием файла, содержащего целочисленную последовательность, предназначенную для обработки с использованием массива.
• Максимальный балл за выполнение задания 25 стал 1 балл.
• Максимальный балл за выполнение всей работы стал 29 баллов.

Приведенные материалы опубликованы на официальном информационном портале Единого Государственного Экзамена.

Демонстрационные варианты ЕГЭ по информатике

Отметим, что демонстрационные варианты ЕГЭ по информатике представлены в формате pdf, и для их просмотра необходимо, чтобы на Вашем компьютере был установлен, например, свободно распространяемый программный пакет Adobe Reader.