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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Логическое выражение называется тождественно-истинным, если оно принимает значения 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 домашнего задания)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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