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

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

Цели урока:

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

Задачи урока:

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

Ход урока

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

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

Урок идет параллельно с презентацией. <Приложение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 переменных: А, В, С; 2³=8

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

Решение:

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

Ответ: 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 г.)

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

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

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

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) Макс – последний, а первый – Джон.

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

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

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

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