Posted in Подготовка к ЕГЭ

Информатика егэ логика – Решение заданий ЕГЭ по информатике с использованим элементов алгебры логики

Решение заданий ЕГЭ по информатике с использованим элементов алгебры логики

Разделы: Информатика

В настоящее время на вступительных экзаменах по информатике есть много заданий по теме “алгебра логики”. Цель данного урока – закрепление навыков решения заданий ЕГЭ по информатике с использованием элементов алгебры логики.

Цели урока:

  • Формирование умения применять полученные знания на практике;
  • Развитие умения построения таблиц истинности по заданным формулам;
  • Развитие умения решать текстовые задачи с использованием законов логики.

Задачи урока:
  • Воспитательная – развитие познавательного интереса, логического мышления.
  • Образовательная – повторение основ математической логики, выполнение практических заданий.
  • Развивающая –  развитие логического мышления, внимательности.

Ход урока
Повторение логических операций и законов.
  • Применение логических операций и законов на практике.
  • Объяснение домашнего задания.

    • Сегодня мы с вами завершаем тему “Основы логики” и применим основные логические операции, законы преобразования для решения заданий ЕГЭ по информатике.

    Урок идет параллельно с презентацией. <Приложение1>

    1. Повторение логических операций и законов.

    Алгебра логики – раздел математической логики, изучающий строение сложных логических высказываний и способы установления их истинности с помощью алгебраических методов.

    Вопросы:

    1. Основоположник формальной логики?

    Аристотель.

    2. Основоположник алгебры логики?

    Джордж Буль.

    3. Перечислите логические операции:

    ¬ отрицание (инверсия)
    &, /\ конъюнкция (“И”)
    V дизъюнкция (“ИЛИ”)
    логическое следование (импликация)
    равнозначность (эквивалентность)

    4. В чем смысл закона двойного отрицания?

    Двойное отрицание исключает отрицание.

    5. Законы де Моргана (законы общей инверсии).

    Отрицание дизъюнкции является конъюнкцией отрицаний:

    ¬(A V B) = ¬A /\ ¬B

    Отрицание конъюнкции является дизъюнкцией отрицаний:

    ¬(A /\B) = ¬A V ¬B

    6. Закон идемпотентности (одинаковости).

    A V A = A

    A /\ A = A

    7. В чём смысл закона исключения третьего?

    Из двух противоречащих высказываний об одном и том же одно всегда истинно, второе ложно, третьего не дано:

    A V ¬А= 1

    8. О чём закон противоречия?

    Не могут быть одновременно истинны утверждение и его отрицание:

    A /\ ¬А= 0

    9. Закон исключения констант.

    Для логического сложения:

    A V 1 = 1 A V 0 = A

    Для логического умножения:

    A /\ 1 = A A /\ 0 = 0

    10. Как выразить импликацию через дизъюнкцию?

    А В = ¬A V В

    2. Примение логических операций и законов на практике.

    Пример 1. (Задание А11 демоверсии 2004 г.)

    Для какого имени истинно высказывание:

    ¬ (Первая буква имени гласная -> Четвертая буква имени согласная)?

    1) ЕЛЕНА

    2) ВАДИМ

    3) АНТОН

    4) ФЕДОР

    Решение. Сложное высказывание состоит из двух простых высказываний:

    А – первая буква имени гласная,

    В – четвертая буква имени согласная.

    ¬ (А В) = ¬ (¬A V В) = (¬ (¬А) /\ ¬B) = A /\ ¬B

    Применяемые формулы:

    1. Импликация через дизъюнкцию А ? В = ¬A V В

    2. Закон де Моргана ¬(A V B) = ¬A /\ ¬B

    3. Закон двойного отрицания.

    (Первая буква имени гласная /\ Четвертая буква имени гласная)

    Ответ: 3

    Пример 2. (Задание А12 демоверсии 2004 г.)

    Какое логическое выражение равносильно выражению ¬ (А \/ ¬B)?

    1) A \/ B

    2) A /\ B

    3) ¬A \/ ¬B

    4) ¬A /\ B

    Решение. ¬ (А \/ ¬B)= ¬ А \/ ¬ (¬B)= ¬ А \/ B

    Ответ: 4

    Пример 3.

    Составить таблицу истинности для формулы

    ¬ (B /\ C) V (A/\C B)

    Порядок выполнения логических операций:

    ¬ (B /\ C) V (A/\C B)

    2   1   5   3   4

    Составить таблицу истинности.

    Сколько строк будет в вашей таблице? 3 переменных: А, В, С; 23=8

    Сколько столбцов? 5 операций + 3 переменных = 8

    Решение:

    A B
    C    		 (B /\ C) ¬ (B /\ C) A/\C (A/\C ? B) ¬ (B /\ C) V (A/\C B)
    0 0 0 0 1 0 1 1
    0 0 1 0 1
    0    		 1 1
    0 1 0 0 1 0 1 1
    0 1 1 1 0 0 1
    1
    1 0 0 0 1 0 0 1
    1 0 1 0 1 1 1 1
    1
    1    		 0 0 1 0 0 1
    1 1 1 1 0 1 1 1

    Какие ответы получились в последнем столбце?

    Ответ: 1

    Логическое выражение называется тождественно-истинным, если оно принимает значения 1 на всех наборах входящих в него простых высказываний. Тождественно-истинные формулы называют

    тавтологиями.

    Решим этот пример аналитическим методом:

    упрощаем выражение

    ¬ (B /\ C) V (A/\C B)= (применим формулу для импликации)

    ¬ (B /\ C) V ¬ (A /\ C) V B = (применим 1 и 2 законы де Моргана)

    (¬B V ¬C) V (¬A V ¬C) V B = (уберём скобки)

    ¬B V ¬C V ¬A V ¬C V B= (применим переместительный закон)

    ¬B V B V ¬C V ¬C V ¬A = (закон исключения третьего, закон идемпотентности)

    1 V ¬С V ¬A = 1 V ¬A = 1 (закон исключения констант)

    Ответ: 1, означает, что формула является тождественно-истинной или тавтологией.

    Логическое выражение называется тождественно-ложным, если оно принимает значения 0 на всех наборах входящих в него простых высказываний.

    (задание 3 домашнего задания)

    Пример 4.

    В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые найдёт поисковый сервер по каждому запросу.

    Для обозначения логической операции “ИЛИ” в запросе используется символ I, а для логической операции “И” – символ &.

    А Законы & Физика
    Б Законы I (Физика & Биология)
    В Законы & Физика & Биология & Химия
    Г Законы I Физика I Биология

    Решение:

    Первый способ основан на рассуждении. Рассуждая логически, мы видим, что больше всего будет найдено страниц по запросу Г, так как при его исполнении будут найдены и страницы со словом “законы”, и страницы, со словом “физика”, и страницы со словом “биология”. Меньше всего будет найдено страниц по запросу В, так как в нем присутствие всех четырех слов на искомой странице. Осталось сравнить запросы А и Б. По запросу Б будут найдены все страницы, соответствующие запросу А, (так как в последних обязательно присутствует слово “законы”), а также страницы, содержащие одновременно слова “физика” и “биология”. Следовательно по запросу Б будет найдено больше страниц, чем по запросу А. Итак, упорядочив запросы по возрастанию страниц, получаем ВАБГ.

    Ответ: ВАБГ.

    Второй способ предполагает использование графического представления операций над множествами. (Смотри презентацию)

    Пример 5. (Задание А16 демоверсии 2006 г.)

    Ниже в табличной форме представлен фрагмент базы данных о результатах тестирования учащихся (используется стобалльная шкала)

    Фамилия Пол Математика Русский язык Химия Информатика Биология
    Аганян ж 82 56 46 32 70
    Воронин м 43 62 45 74 23
    Григорчук м 54 74 68 75 83
    Роднина ж 71 63 56 82 79
    Сергеенко ж 33 25 74 38 46
    Черепанова ж 18 92 83 28 61

    Сколько записей в данном фрагменте удовлетворяют условию

    “Пол=’м’ ИЛИ Химия>Биология”?

    1) 5

    2) 2

    3) 3

    4) 4

    Решение:

    Выбираем записи: Мальчики (двое) и Химия>Биология (трое, но один мальчик, уже взялся 1 раз). В итоге 4 записи удовлетворяют условию.

    Ответ: 4

    Задание 6. (Задание В4 демоверсии 2007 г)

    В школьном первенстве по настольному теннису в четверку лучших вошли девушки: Наташа, Маша, Люда и Рита. Самые горячие болельщики высказали свои предположения о распределении мест в дальнейших состязаниях.

    Один считает, что первой будет Наташа, а Маша будет второй.

    Другой болельщик на второе место прочит Люду, а Рита, по его мнению, займет четвертое место.

    Третий любитель тенниса с ними не согласился. Он считает, что Рита займет третье место, а Наташа будет второй.

    Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов.

    Какое место на чемпионате заняли Наташа, Маша, Люда, Рита?

    (В ответе перечислите подряд без пробелов числа, соответствующие местам девочек в указанном порядке имен.)

    Решение:

    Обозначим высказывания:

    Н1 = “первой будет Наташа”;

    М2 = “второй будет Маша”;

    Л2 = “второй будет Люда”;

    Р4 = “четвертой будет Рита”;

    Р3 = “третьей будет Рита”;

    Н2 = “второй будет Наташа”.

    Согласно условию:

    из высказываний 1 болельщика следует, что Н1VМ2 истинно;

    из высказываний2 болельщика следует, что Л2VР4 истинно;

    из высказываний 3 болельщика следует, что Р3VН2 истинно.

    Следовательно, истинна и конъюнкция

    (Н1VМ2) /\ (Л2VР4) /\ (Р3VН2) = 1.

    Раскрыв скобки получим:

    (Н1VМ2) /\ (Л2VР4) /\ (Р3VН2) = (Н1/\Л2V Н1/\Р4 V М2/\Л2 V М2/\Р4) /\ (Р3VН2)=

    Н1/\ Л2/\Р3 V Н1/\Р4/\Р3 V М2/\Л2/\Р3 V М2/\Р4/\Р3 V Н1/\Л2/\Н2 V Н1/\Р4/\Н2 V М2/\Л2/\Н2 V М2/\Р4/\Н2 = Н1/\ Л2/\Р3 V 0 V 0 V 0 V 0 V 0 V 0 V= Н1/\ Л2/\Р3

    Наташа-1, Люда-2, Рита-3, а Маша-4.

    Ответ: 1423

    3. Объяснение домашнего задания.

    Задание 1. (Задание В8 демоверсии 2007г)

    В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу.

    Для обозначения логической операции “ИЛИ” в запросе используется символ |, а для логической операции “И” – &.

    А волейбол | баскетбол | подача
    Б волейбол | баскетбол | подача | блок
    В волейбол | баскетбол
    Г волейбол & баскетбол & подача

    Задание 2 (Задание В4 демоверсии 2008г)

    Перед началом Турнира Четырех болельщики высказали следующие предположения по поводу своих кумиров:

    A) Макс победит, Билл – второй;

    B) Билл – третий. Ник – первый;

    C) Макс – последний, а первый – Джон.

    Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов.

    Какое место на турнире заняли Джон, Ник, Билл, Макс?

    (В ответе перечислите подряд без пробелов места участников в указанном порядке имен.)

    Оценки за урок.

    26.02.2008

    xn--i1abbnckbmcl9fb.xn--p1ai

    Использование элементов алгебры логики при решении заданий ЕГЭ по информатике

    Разделы: Информатика

    Организационная часть урока.

    На экране:

    “Всё наше достоинство заключено в мысли. Не пространство, не время, которые мы не можем заполнить, возвышает нас, а именно она, наша мысль. Будем же учиться хорошо мыслить”.

    Французский математик и философ XVII века Блез Паскаль.

    Завершаем тему “Основы логики”, сегодня вспомним основные логические операции, законы логики и правила преобразования, применим их на практике.

    На экране:

    Логика – наука о формах и способах мышления.

    На экране: Цели урока:

    1. Развитие умения построения таблиц истинности по заданным формулам.
    2. Развитие умения применять законы логики и правила преобразования сложных логических выражений.
    3. Формирование умения применять полученные знания на практике.
    4. Алгебра логики – математический аппарат, с помощью которого записывают, упрощают, вычисляют и преобразовывают логические высказывания.

    1 часть урока: актуализация опорных знаний.

    Вспоминаем элементы алгебры логики.

    На экране высвечиваются вопросы, после ответов учеников правильные ответы:

    1. Перечислите логические операции в порядке старшинства:

    2. Какие законы логики имеют аналоги в обычной алгебре?

    Переместительный.

    Сочетательный.

    Распределительный.

    3. В чем смысл закона двойного отрицания?

    Двойное отрицание исключает отрицание.

    4. Законы де Моргана.

    Называют законами общей инверсии.

    Отрицание дизъюнкции является конъюнкцией отрицаний.

    Отрицание конъюнкции является дизъюнкцией отрицаний.

    5. Закон идемпотентности.

    Дословно переводится (равносильный)

    A V A = A
    A & A = A

    6. В чём смысл закона исключения третьего?

    Из двух противоречащих высказываний об одном и том же одно всегда истинно, второе ложно, третьего не дано.

            _
    A V А= 1

    7. О чём закон непротиворечия?

    Не могут быть одновременно истинны утверждение и его отрицание.

            _
    A & А= 0

    8. Закон исключения констант.

    Для логического сложения:

    A V 1 = 1   A V 0 = A

    Для логического умножения:

    A & 1 = A   A & 0 = 0

    9. Как выразить импликацию через дизъюнкцию?

    2 часть урока: примение логических операций и законов на практике: при решении задач и примеров из сборника тренировочных заданий ЕГЭ [4].

    1.72 Для какого имени истинно высказывание:

    ¬ (Первая буква имени гласная —> Четвертая буква имени согласная)

    1) ЕЛЕНА
    2) ВАДИМ
    3) АНТОН
    4) ФЕДОР

    Сложное высказывание состоит из двух простых высказываний:

    А — первая буква имени гласная,

    В — четвертая буква имени согласная

    Ученик работает у доски, остальные в тетрадях, на экране показывается правильное решение по шагам:

    Формулы:

    1. Импликация через дизъюнкцию.

    2. Закон де Моргана.

    3. Закон двойного отрицания.

    Ответ: (Первая буква имени гласная & Четвертая буква имени гласная)

    Задание идёт в первой части тестов ЕГЭ под буквой А. Выбираете только № правильного ответа: 3.

    Задание № 2

    Составить таблицу истинности для формулы

    Что должны сделать в первую очередь?

    Покажите порядок выполнения логических операций:

    Вы будете составлять таблицу истинности.

    Работа в режиме диалога “учитель — ученики”

    Сколько строк будет в вашей таблице?

    3 переменных: А, В, С; 23=8

    Сколько столбцов?

    5 операций + 3 переменных = 8

    Как я вас учила автоматически не задумываясь заполнять значения переменных А, В, С?

    Если одна переменная, то 2 возможных значения: 0 и 1.

    При 2 переменных, колонку 0 1 повторяем вниз, впереди ставим 0 0 1 1. При трёх переменных повторяем ниже все значения, впереди ставим в первой половине 0, во второй половине 1.

    Заготовки раздать ученикам, чтобы не теряли времени на оформление, быстрее заполняли.

    Самостоятельная работа. Для тех, кто сделает быстро, подготовлены карточки с дополнительным заданием (см. Приложение1).

    Какие ответы получились в последнем столбце? Правильный ответ: 1.

    Логическое выражение называется тождественно-истинным, если оно принимает значения 1 на всех наборах входящих в него простых высказываний.
    Тождественно-истинные формулы называют тавтологиями.

    Слово тавтология вы встречали, где? Ученики вспоминают.

    На экране: Из словаря иностранных слов:

    Тавтология (в переводе с греческого tauto – то же самое + logos – слово). Повторение того же самого другими словами.

    Тавтология широко используется как стилистический и художественный приём в народном творчестве и поэзии. Мы заставим здесь природу поклониться нам поклоном до земли. (Исаковский). “Поклониться поклоном” — явная тавтология. В речи следует избегать тавтологий без стилистических задач.

    Есть специальные федеральные тесты для вступительных экзаменов по информатике. В этих тестах много заданий по логике, в том числе такого содержания: тождественно истинными (тавтологиями) являются формулы: и даны 4 сложные формулы. Для того, чтобы правильно ответить, надо для каждой формулы построить таблицу истинности, то что мы с вами сделали. Это занимает много времени. Иногда быстрее бывает решить задачу аналитическим методом.

    Решим пример аналитическим методом: упрощаем выражение.

    Ученик работает у доски, на экране высвечивается правильное решение по шагам:

    3 часть урока: примение логических функций на практике: информационные технологии.

    При изучении каких разделов информатики встречали логические функции?

    Ученики вспоминают, на экране расширенная информация по каждому последующему пункту.

    1. Microsoft Excel
    2. Логические операции в Turbo Pascal
    3. Поиск информации в сети Интернет.

    Задание 2.34 из сборника ЕГЭ [4]

    В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые найдёт поисковый сервер по каждому запросу.

    АЗаконы & Физика
    БЗаконы V (Физика & Биология)
    ВЗаконы & Физика & Биология & Химия
    ГЗаконы VФизика V Биология

    Рассуждаем, каждый запрос рассматриваем как объединения или пересечения множеств, на экране строятся диаграммы Эйлера-Венна.

    Вы научились создавать таблицы базы данных Microsoft Access, умеете связывать их, умеете делать простые запросы. Сегодня вы научитесь применять логические функции в качестве условий отбора в запросе.

    Обратите внимание, операторы пишутся так же, как и логические функции в Turbo Pascal.

    ОператорДействие
    AndЗаписи, удовлетворяющие одному и другому условию одновременно.
    OrЗаписи, удовлетворяющие хотя бы одному из двух условий.
    NotЗаписи, не удовлетворяющие данному условию.

    Рассмотрим задание из тренировочных заданий ЕГЭ [4].

    Задание 2.23. Ниже в табличной форме представлен фрагмент базы данных о результатах тестирования учащихся (используется стобалльная шкала):

    ФамилияПолМатематикаРусский языкХимияИнформатикаБиология
    Аганянж8256463270
    Воронинм4362457423
    Григорчукм5474687583
    Роднинаж7163568279
    Сергеенкож3325743846
    Черепановаж1892832861

    Сколько записей в данном фрагменте удовлетворяют условию

    “Пол=’м’ ИЛИ Химия>Биология”?

    Рассуждают ученики, на экране последовательно выделяются красным цветом отобранные записи.

    Выбираем записи: Мальчики (двое) и Химия>Биология (трое, но один мальчик, уже взялся 1 раз). В итоге 4 записи удовлетворяют условию.

    Ответ: 4

    4 часть урока: работа на компьютере.

    Подготовила для вас базу данных “Погода”, она состоит из одной таблицы.

    Ваша цель сделать два запроса с использованием логических операторов, показываю, как сделала с Or и Not.

    Для тех, кто выполнил задание раньше, на экране высвечиваются задачи, для них подготовлены карточки с дополнительным заданием (Приложение 1).

    Продолжение статьи находится в приложении (Приложение)

    17.03.2008

    xn--i1abbnckbmcl9fb.xn--p1ai

    Логические задачи в ЕГЭ по информатике

    Конъюнкция( логическое умножение) – соединение двух логических выражений (высказываний ) с помощью союза И. Эта операция обозначается символами & и ∧.

    Правила выполнения логической  операции  отражаются в таблице, которая называется таблицей истинности:
    А – У меня есть знания  для сдачи зачета.
    В – У меня есть  желание для сдачи зачета.
    A&B – У меня есть знания и желание для сдачи зачета.

    A

    B

    A&B

    0

    0

    0

    0

    1

    0

    1

    0

    0

    1

    1

    1

    Вывод: Логическая операция конъюнкция истинна только в том случае, если оба простых высказывания истинны, в противном случае она ложна.

    Дизъюнкция (логическое сложение) – соединение двух логических высказываний с помощью союза ИЛИ. Эта операция обозначается значком V.
    Рассмотрим таблицу истинности для данной логической операции.
    Обозначим через A  — летом я поеду в лагерь, B – летом я поеду в к бабушке.
    AVB —  Летом я поеду в лагерь или поеду  к бабушке.

    A

    B

    AVB

    0

    0

    0

    0

    1

    1

    1

    0

    1

    1

    1

    1

    Вывод: логическая операция дизъюнкция  ложна, если оба простых высказывания ложны. В остальных случаях она истинна

    Отрицание  или инверсия – добавляется частица НЕ или слова НЕВЕРНО,ЧТО, обозначается символом  ¬  , ¯.
    Пусть  A –  Сейчас на дворе лето.

    Вывод: если исходное выражение истинно, то результат его отрицания будет ложным, и наоборот, если исходное выражение ложно, то оно будет истинным.

    Последовательность выполнения операций:
    отрицание, конъюнкция, дизъюнкция.
    Кроме того, на порядок выполнения операции влияют скобки, которые можно использовать в логических формулах.

    logikinformatik.blogspot.com

    Author: alexxlab

    Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *