17 ноября 2009 г. Васинькина Н.Н., учитель информатики и ИКТ МОУ «СОШ 51» г. Саратова 1 Логика Подготовка к государственной итоговой аттестации по информатике. - презентация

1 17 ноября 2009 г. Васинькина Н.Н., учитель информатики и ИКТ МОУ «СОШ 51» г. Саратова 1 Логика Подготовка к государственной итоговой аттестации по информатике в 9 классе

2 Содержание 2 Содержание Логические выражения и логические операции –ВысказыванияВысказывания –ИнверсияИнверсия –КонъюнкцияКонъюнкция –ДизъюнкцияДизъюнкция –Приоритет выполнения логических операцийПриоритет –Составление таблиц истинностиСоставление таблиц истинности Задачи А9: Примеры 1, 2, 3, 4Задачи А91234 Задачи А7: Варианты 3, 4, 6, 7, 8, ifmoЗадачи А734678ifmo Круги Эйлера Задачи В10: работа поискового сервера. Варианты 1, 2, 3, 4, 6, 8Задачи В Задачи А12: Цепочки бусин. Варианты 1, 2, 5, 6, 7Задачи А Законы де Моргана Упрощение логических выражений: Примеры 1, 2, 3, 4, ifmoУпрощение логических выражений1234ifmo Особенности формирования запросов. ПримерОсобенности формирования запросовПример Задачи А23: Результаты работы запросов в Базах данных Примеры 1 сп1, 1 сп2, 2 сп1, 2 сп2, 3Задачи А231 сп11 сп22 сп12 сп23 Источники информации По фрагменту Табл.Ист. определить Какое выражение соответствует F? Какое из названий удовлетворяет логическому условию

3 Содержание 3 математический аппарат, с помощью которого записывают, вычисляют, упрощают и преобразовывают логические высказывания Булева алгебра (Алгебра логики) – это: Джордж Буль ( английский математик, XIX век) разработал основы алгебры, в которой используются только 0 и 1 (алгебра логики, булева алгебра). Результат выполнения логической операции можно представить как истинность (1) или ложность (0) некоторого высказывания.

4 Содержание 4 Логическое высказывание – это повествовательное предложение, про которое однозначно можно сказать: истинно оно или ложно. Будут ли высказыванием следующие предложения? Дважды два – четыре. Рим – столица Франции. Математика – любимый предмет. Да здравствует Первое Мая! Прелестно! У неё зелёные глаза. Ты сегодня пойдёшь в кино или в театр? Логические высказывания

5 Содержание 5 A – Это утро ясное. B – Это утро тёплое. простые высказывания (элементарные) Составные высказывания строятся из простых с помощью логических связок (операций) "и", "или", "не"... A и B A и не B не A или B Это утро ясное и тёплое. Это утро ясное и оно не тёплое. Это утро не ясное или оно тёплое. Обозначение высказываний Любое высказывание либо ложно (0) либо истинно (1)

6 Содержание 6 Если высказывание A истинно, то "не А" ложно,и наоборот. Ане А таблица истинности операции НЕ также:, not A (Паскаль), Таблица истинности логического выражения Х – это таблица, где в левой части записываются все возможные комбинации значений исходных данных, а в правой – значение выражения Х для каждой комбинации. Операция НЕ (инверсия, отрицание)

7 Содержание 7 ABА и B 1 0 также: A·B, A B, AB, А&В, A and B (Паскаль) также: A·B, A B, AB, А&В, A and B (Паскаль) конъюнкция – от лат. conjunctio соединение Высказывание "A и B" истинно тогда и только тогда, когда А и B одновременно истинны. Операция И (логическое умножение, конъюнкция)

8 Содержание 8 ABА или B дизъюнкция – от лат. disjunctio разъединение Высказывание "A или B" ложно тогда и только тогда, когда А и B одновременно ложны Операция ИЛИ (логическое сложение, дизъюнкция) также: A+B, A|B, A B, A or B (Паскаль),

9 Содержание 9 Приоритет выполнения операций Выражение в скобках Инверсия Конъюнкция Дизъюнкция Операции отношения (,,, =, )

10 Содержание 10 AB Составление таблиц истинности

11 Содержание 11 ABCABACBCX Составление таблиц истинности

12 12 Содержание Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F: Какое выражение соответствует F? XYZF ) ¬X/\¬Y/\Z2) ¬X\/¬Y\/Z3) X\/Y\/¬Z4) X\/Y\/Z 1)2)2)3)4) Можно записать компактнее Пр.1 А9

13 13 Какое выражение соответствует F? XYZF ) ¬X/\¬Y/\Z2) ¬X\/¬Y\/Z3) X\/Y\/¬Z4) X\/Y\/Z 1)2)2)3)4) XYZ Содержание

14 14 Какое выражение соответствует F? XYZF )2)3)4) XYZ ) ¬X/\¬Y/\Z2) ¬X\/¬Y\/Z3) X\/Y\/¬Z4) X\/Y\/Z Содержание

15 15 Какое выражение соответствует F? XYZF )4) XYZ ОТВЕТ 1) ¬X/\¬Y/\Z2) ¬X\/¬Y\/Z3) X\/Y\/¬Z4) X\/Y\/Z Содержание

16 16 Ответ найден, но… Для самоконтроля можно перепроверить случай 4) Содержание

17 17 XYZF ) X\/Y\/Z 4) XYZ Содержание

18 18 Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F: Чему равно F? XYZF ) X/\Y/\Z2) ¬X\/¬Y\/Z3) X/\Y/\¬Z4) ¬X/\¬Y/\¬Z Пр.2

19 Содержание 19 1)2)2)3)4) 1) X/\Y/\Z2) ¬X\/¬Y\/Z3) X/\Y/\¬Z4) ¬X/\¬Y/\¬Z Ответ: 4 XYZF

20 Содержание 20 Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F: Какое выражение соответствует F? 1)¬X \/ ¬Y \/ ¬Z 2)X /\ ¬Y /\ ¬Z 3)X \/ Y \/ Z 4)X /\ Y /\ Z Пр.3 XYZF

21 Содержание 21 Какое выражение соответствует F? Пр.3 XYZF X /\ Y /\ Z X \/ Y \/ Z X /\ ¬Y /\ ¬Z ¬X \/ ¬Y \/ ¬Z 4) 3) 2) 1) Ответ: 3

22 Содержание 22 Пр.4 Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F: FZYX Какое выражение соответствует F? 1)¬X \/ Y \/ ¬Z 2)X /\ Y /\ ¬Z 3)¬X /\ ¬Y /\ Z 4)X \/ ¬Y \/ Z Ответ: 2

23 Содержание FZYX Какое выражение соответствует F? X \/ ¬Y \/ Z4) ¬X /\ ¬Y /\ Z3) X /\ Y /\ ¬Z2) ¬X \/ Y \/ ¬Z1) Ответ: 2

24 Содержание 24 А7 Вариант 3 Какое из приведённых названий животных удовлетворяет логическому условию: В слове 5 букв /\ Четвёртая буква гласная? Ответ: 3 1) Зебра 2) Слон 3) Кабан 4) Олень !

25 Содержание 25 А7 Вариант 4 Для какого имени ложно высказывание: Первая буква гласная \/ Четвёртая буква согласная? 1) Петр 2) Алексей 3) Наталья 4) Елена Ответ: 3

26 Содержание 26 А7 Вариант 6 Какое из приведённых имён удовлетворяет логическому условию: Первая буква гласная /\ Четвёртая буква согласная \/ В слове 4 буквы? 1) Сергей 2) Вадим 3) Антон 4) Илья Ответ: 4

27 Содержание 27 А7 Вариант 7 Для какого из названий животных ложно высказывание: В слове 4 гласных буквы /\ ¬(Пятая буква гласная) \/ В слове 5 согласных букв? 1) Шиншилла 2) Кенгуру 3) Антилопа 4) Крокодил

28 Содержание 28 1) Шиншилла 2) Кенгуру 3) Антилопа 4) Крокодил 4 гласных 5С5С & 5 согласных результат Дизъюнкция … ложна, когда оба высказывания ложные Ответ: 2 ! А7 Вариант 7

29 Содержание 29 А7 Вариант 8. Для какого символьного набора истинно высказывание: Вторая буква согласная /\ (В слове 3 гласных буквы \/ Первая буква согласная)? 1) АББЕЖК 2) КАИЕЖЖ 3) ЖАБВЕИ 4) ИККРОЕ Ответ: 4

30 Содержание 30 Из интернет-олимпиады для 9 классов: Для какого символьного выражения неверно высказывание: «первая буква гласная ИЛИ пятая буква согласная»? 1.dbaac 2.abcab 3.babas 4.abcde 5.becde Ответ: 5 Удобно использовать закон де Моргана!

31 Содержание 31 С импликацией. 10 класс A11 Для какого имени истинно высказывание: ¬ (Первая буква имени гласная Четвертая буква имени согласная)? 1)ЕЛЕНА 2)ВАДИМ 3)АНТОН 4)ФЕДОР

32 Содержание 32 A B A A /\ B А B A B A \/ B А U B Круги Эйлера (Диаграммы Вена)

33 Содержание 33 В10 В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке возрастания количества страниц, которые найдёт поисковый сервер по каждому запросу. Для обозначения логической операции «ИЛИ» в запросе используется символ |, а для логической операции «И» &.

34 Содержание 34 1живопись & литература 2живопись | литература 3живопись | литература | графика 4живопись & литература & графика В10 Вариант1 …номера запросов в порядке возрастания… Ответ:

35 Содержание 35 В10 Вар2 для 11 класса Ответ: барокко | классицизм 2барокко | (классицизм & модерн) 3(барокко & ампир) | (классицизм & модерн) 4барокко | ампир | классицизм | модерн … номера запросов в порядке убывания количества страниц …

36 Содержание 36 1 живопись & литература & графика 2 живопись | литература | графика 3 живопись | литература 4 живопись & литература В10 Вариант3 …номера запросов в порядке возрастания количества страниц … Ответ:

37 Содержание 37 1 графика | литература 2 живопись | литература | графика 3 живопись & литература & графика 4 живопись & графика В10 Вариант4 …номера запросов в порядке возрастания количества страниц … Ответ:

38 Содержание 38 1 живопись & литература & графика 2 живопись | литература | графика 3 графика | литература 4 живопись & литература В10 Вариант6 …номера запросов в порядке убывания количества страниц … Ответ:

39 Содержание 39 В10 Вар8 для 11 класса Ответ: барокко | (классицизм & ампир) 2 барокко | классицизм ) 3 (классицизм & ампир) | (барокко & модерн) 4 барокко | ампир | классицизм … номера запросов в порядке возрастания количества страниц …

40 Содержание 40 А12 Вариант1 Цепочка из трех бусин, помеченных латинскими буквами, формируется по следующему правилу. В конце цепочки стоит одна из бусин A, B, D, E. В середине – одна из бусин B, C, E, которой нет на последнем месте. На первом месте - одна из бусин A, B, D, не стоящая на втором месте. Какая из перечисленных цепочек создана по этому правилу? 1) ABB2) DED3) BAD4) DEC Ответ: 2

41 Содержание 41 Цепочка из трех бусин, помеченных латинскими буквами, формируется по следующему правилу. В середине цепочки стоит одна из бусин A, D, E. На третьем месте – одна из бусин A, B, C, E, которой нет на втором месте. На первом месте - одна из бусин A, B, D, не стоящая на третьем месте. Какая из перечисленных цепочек создана по этому правилу? А12 Вариант2 Ответ: 3 1) BEE 2) ADA 3) BAC 4) BCE

42 Содержание 42 Цепочка из трех бусин, помеченных латинскими буквами, формируется по следующему правилу. В конце цепочки стоит одна из бусин W, X, Y, Z. На середине – одна из бусин V, W, Z, которой нет на последнем месте. На первом месте - одна из бусин X, Y, Z, не стоящая на втором месте. Какая из перечисленных цепочек создана по этому правилу? А12 Вариант5 Ответ: 4 1) XZZ 2) ZXY 3) YWV 4) YWY

43 Содержание 43 Цепочка из трех бусин, помеченных латинскими буквами, формируется по следующему правилу. В начале цепочки стоит одна из бусин A, B, E. На втором месте – одна из бусин B, D, E, которой нет на третьем месте. На третьем месте - одна из бусин A, B, C, D, не стоящая на первом месте. Какая из перечисленных цепочек создана по этому правилу? А12 Вариант6 Ответ: 3 1) ADE 2) AAE 3) BED 4) ADA

44 Содержание 44 Цепочка из трех бусин, помеченных латинскими буквами, формируется по следующему правилу. В середине цепочки стоит одна из бусин A, C, D, E. На первом месте – одна из бусин A, B, D, E, не стоящая в конце. На третьем месте - одна из бусин B, C, E, которой нет на втором месте. Какая из перечисленных цепочек создана по этому правилу? А12 Вариант7 Ответ: 1 1) AAB 2) BEB 3) ACC 4) DCA

45 Содержание 45 Законы алгебры логики названиедля Идля ИЛИ правила де Моргана Закон двойного отрицания:

46 Содержание 46 Упрощение логических выражений Какое логическое выражение равносильно выражению ¬ (А \/ ¬B) ? 1)A \/ B2)A /\ B3)¬A \/ ¬B4)¬A /\ B Ответ: 4 Решение. ¬ (А \/ ¬B) = Пр.1

47 Содержание 47 Укажите, какое логическое выражение равносильно выражению ¬ (¬А /\ B) 1)A \/¬B 2)¬A \/ B 3)B /\ ¬A 4)A /\ ¬B Упрощение логических выражений Пр.2 Ответ: 1 Решение. ¬ (¬ А /\ B) =

48 Содержание 48 Какое логическое выражение равносильно выражению ¬ (¬A \/ B) \/ ¬C ? 1)(A /\ ¬B) \/ ¬C 2)¬A \/ B \/ ¬C 3)A \/ ¬B \/ ¬C 4)(¬A /\ B) \/ ¬C Пр.3

49 Содержание 49 Для какого из указанных значений числа X истинно выражение (X>2) & ((X 4))? 1)1 2)2 3)3 4)4 (X>2)(X4)((X 4) результат Ответ: 3 Пр.4

50 Содержание класс Для какого числа X истинно высказывание X>1 /\ ((X

51 Содержание 51 Особенности формирования запросов Формализация условий поиска: создание логических выражений. Например, Выбрать всех неуспевающих по физике: Физика

52 Содержание 52 Каким условием нужно воспользоваться для поиска в сети Интернет информации о цветах, растущих на острове Тайвань или Хонсю ? Пример 1)цветы&(Тайвань|Хонсю) 2)цветы&Тайвань&Хонсю 3)цветы|Тайвань|Хонсю 4)цветы&(остров|Тайвань|Хонсю) Ответ: 1

53 Содержание 53 1)5 2)2 3)3 4) Пират Химик Звезда Опушка Авангард Боец1 МПМЗОПНВКомандаМесто A23 Сколько записей в нижеследующем фрагменте турнирной таблицы удовлетворяют условию «Место 4 ИЛИ MЗ>12)» ? Ответ: 4 ! ! ! ! Пр.1 1 способ

54 Содержание 54 «Место 4 ИЛИ MЗ>12)» 1.«И» - ПЕРЕСЕЧЕНИЕ множеств I и II выполняется в послед очередь => 2.Ищем записи множества II только в первых 5 строках множества I (где Место 4.Необязательно рассматривать оба поля, если условие первого поля уже истинно Пр.1 2 способ I II

55 Содержание 55 1)5 2)2 3)3 4) Пират Химик Звезда Опушка Авангард Боец1 МПМЗОПНВКомандаМесто A23 Сколько записей в нижеследующем фрагменте турнирной таблицы удовлетворяют условию «Место 4 ИЛИ MЗ>12)» ? Ответ: 4 ! ! ! ! Пр.1 2 способ

56 Содержание 56 Сколько записей в нижеследующем фрагменте турнирной таблицы удовлетворяют условию «Место 2 ИЛИ О>6)»? МестоУчастникВНПО 1Силин5316 ½ 2Клеменс6036 3Холево5145 ½ 4Яшвили3515 ½ 5Бергер3334 ½ 6Численко3244 1)5 2)2 3)3 4)4 Ответ: 2 ! ! Пр.2 1 способ Пр.2

57 Содержание 57 «Место 2 ИЛИ О>6)»? МестоУчастникВНПО 1Силин5316 ½ 2Клеменс6036 3Холево5145 ½ 4Яшвили3515 ½ 5Бергер3334 ½ 6Численко3244 1)5 2)2 3)3 4)4 Ответ: 2 ! ! 2 способ Пр.2

58 Содержание 58 В табличной форме представлен фрагмент базы данных о результатах тестирования учащихся (используется стобалльная шкала): ФамилияПолМатема тика Русский язык ХимияИнформати ка Биологи я Аганянж Воронинм Григорчукм Роднинаж Сергеенкож Черепановаж Сколько записей в данном фрагменте удовлетворяют условию «Пол=м ИЛИ Химия>Биология»? ! ! 1)5 2)2 3)3 4)4 Ответ: 4 ! ! Пр.3

59 Содержание 59 Источники информации «Преподавание базового курса информатики в средней школе»: Методическое пособие/ И.Г.Семакин, Т.Ю. Шеина. – 3-е изд, испр. – М.: БИНОМ. Лаборатория знаний, «ЕГЭ Информатика. Типовые тестовые задания / П.А. Якушкин, В.Р. Лещинер, Д.П. Кириенко». – М.: Издательство «Экзамен», 2010 Информатика: Учеб. Пособие для кл. общеобразоват. Учреждений / Л.З. Шауцукова. – М.: Просвещение, Презентация Полякова К.Ю. «Логические основы компьютеров». 2007г. Демоверсии ЕГЭ 2004, 2005, 2006, 2007, 2008, 2009 г.г.