Алгебра логики. Решение задач с элементами алгебры логики - umotnas.ru o_O
Алгебра логики. Решение задач с элементами алгебры логики - umotnas.ru o_O
|
страница 1
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Похожие работы
|
Алгебра логики. Решение задач с элементами алгебры логики - страница №1/1
ГОУ ВПО «Чувашский государственный педагогический университет им. И. Я. Яковлева» Конспект урока Тема: Алгебра логики. Решение задач с элементами алгебры логики. Выполнила: студентка ФМФ ИМ-5 Гаврилова Е.В. Андреева Е.Г. Бакшаева Н.В. Чебоксары 2010 Тема: Алгебра логики. Решение задач с элементами алгебры логики. Класс: 11 «А» (физико-математический) в МОУ «Гимназия №1» Возраст: 15-17 лет Тип урока: комбинированный Цели урока: Образовательная: Сформировать у учащихся знания о законах логики, умение применять полученные знания на практике. Повторить материал пройденный на предыдущих уроках. Воспитательная: Воспитание внимательности, аккуратности, умений анализировать, сравнивать и делать выводы. Развивающая: Развитие умения построения таблиц истинности по заданным формулам. Развитие умения решать текстовые задачи с использованием законов логики. Развитие логического мышления. Средства обучения: проектор, доска, презентация в MS PowerPoint.
Содержание урока
Урок идет параллельно с презентацией.
Алгебра логики – раздел математической логики, изучающий строение сложных логических высказываний и способы установления их истинности с помощью алгебраических методов. Вопросы: 1. Основоположник формальной логики? (Аристотель) 2. Основоположник алгебры логики? (Джордж Буль) 3. Перечислите логические операции. Ответ: ¬ отрицание (инверсия) &, /\ конъюнкция (“И”) I, V дизъюнкция (“ИЛИ”) логическое следование (импликация) равнозначность (эквивалентность)
Двойное отрицание исключает отрицание.
Отрицание дизъюнкции является конъюнкцией отрицаний: ¬(A V B) = ¬A /\ ¬B Отрицание конъюнкции является дизъюнкцией отрицаний: ¬(A /\B) = ¬A V ¬B
A V A = A A /\ A = A
Из двух противоречащих высказываний об одном и том же одно всегда истинно, второе ложно, третьего не дано: A V ¬А= 1
Не могут быть одновременно истинны утверждение и его отрицание: A /\ ¬А= 0
Для логического сложения: A V 1 = 1 A V 0 = A Для логического умножения: A /\ 1 = A A /\ 0 = 0
А В = ¬A V В
А /\ А=А A V А = A
А /\ (А V В)=А А V (А/\ В)=А
Пример 1. (Задание А7 демоверсии 2010 г.) Для какого имени истинно высказывание: ¬ (Первая буква имени гласная -> Четвертая буква имени согласная)? 1) ЕЛЕНА 2) ВАДИМ 3) АНТОН 4) ФЕДОР А – первая буква имени гласная, В – четвертая буква имени согласная. ¬ (А В) = ¬ (¬A V В) = (¬ (¬А) /\ ¬B) = A /\ ¬B Применяемые формулы: 1. Импликация через дизъюнкцию А ? В = ¬A V В 2. Закон де Моргана ¬(A V B) = ¬A /\ ¬B 3. Закон двойного отрицания. (Первая буква имени гласная /\ Четвертая буква имени гласная) Какое логическое выражение равносильно выражению ¬ (А \/ ¬B)? 1) A \/ B 2) A /\ B 3) ¬A \/ ¬B 4) ¬A /\ B Решение. ¬ (А \/ ¬B)= ¬ А \/ ¬ (¬B)= ¬ А \/ B Ответ: 4 Пример 3. (Задание А9 демоверсии 2010 г.) Составить таблицу истинности для формулы ¬ (B /\ C) V (A/\C B) Порядок выполнения логических операций: ¬ (B /\ C) V (A/\C B) 2 1 5 3 4 Составить таблицу истинности. Сколько строк будет в вашей таблице? 3 переменных: А, В, С; возможное количество комбинаций 23=8, то есть строк 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 на всех наборах входящих в него простых высказываний. Пример 4. (Задание В10 демоверсии 2010 г.) В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые найдёт поисковый сервер по каждому запросу. Для обозначения логической операции “ИЛИ” в запросе используется символ I, а для логической операции “И” – символ &.
Решение: Первый способ основан на рассуждении. Рассуждая логически, мы видим, что больше всего будет найдено страниц по запросу Г, так как при его исполнении будут найдены и страницы со словом “законы”, и страницы, со словом “физика”, и страницы со словом “биология”. Меньше всего будет найдено страниц по запросу В, так как в нем присутствие всех четырех слов на искомой странице. Осталось сравнить запросы А и Б. По запросу Б будут найдены все страницы, соответствующие запросу А, (так как в последних обязательно присутствует слово “законы”), а также страницы, содержащие одновременно слова “физика” и “биология”. Следовательно по запросу Б будет найдено больше страниц, чем по запросу А. Итак, упорядочив запросы по возрастанию страниц, получаем ВАБГ. Ответ: ВАБГ. Второй способ предполагает использование графического представления операций над множествами. (Смотри презентацию) Пример 5. (Задание А12 демоверсии 2010 г.) Ниже в табличной форме представлен фрагмент базы данных о результатах тестирования учащихся (используется стобалльная шкала)
Сколько записей в данном фрагменте удовлетворяют условию “Пол=’м’ ИЛИ Химия>Биология”? 1) 5 2) 2 3) 3 4) 4 Решение: Выбираем записи: Мальчики (двое) и Химия>Биология (трое, но один мальчик, уже взялся 1 раз). В итоге 4 записи удовлетворяют условию. Ответ: 4 Задание 6. (Задание А12 демоверсии 2010 г) В школьном первенстве по настольному теннису в четверку лучших вошли девушки: Наташа, Маша, Люда и Рита. Самые горячие болельщики высказали свои предположения о распределении мест в дальнейших состязаниях. Один считает, что первой будет Наташа, а Маша будет второй. Другой болельщик на второе место прочит Люду, а Рита, по его мнению, займет четвертое место. Третий любитель тенниса с ними не согласился. Он считает, что Рита займет третье место, а Наташа будет второй. Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов. Какое место на чемпионате заняли Наташа, Маша, Люда, Рита? (В ответе перечислите подряд без пробелов числа, соответствующие местам девочек в указанном порядке имен.) Решение: Обозначим высказывания: Н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
Задание 1. В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. Для обозначения логической операции “ИЛИ” в запросе используется символ |, а для логической операции “И” – &.
Задание 2 Перед началом Турнира Четырех болельщики высказали следующие предположения по поводу своих кумиров: A) Макс победит, Билл – второй; B) Билл – третий. Ник – первый; C) Макс – последний, а первый – Джон. Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов. Какое место на турнире заняли Джон, Ник, Билл, Макс? (В ответе перечислите подряд без пробелов места участников в указанном порядке имен.) III. Итог урока. Обобщить пройденный материал, оценить работу активных учеников. Список используемой литературы
|
|
|