Алгебра логики. Решение задач с элементами алгебры логики - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Алгебра логики и логические основы компьютера Алгебра логики 1 37.92kb.
Билет №3 Формулы алгебры логики 1 29.93kb.
Вопросы по курсу: Математическая логика и теория алгоритмов (2 курс) 1 30.21kb.
Программа аттестационного испытания по дисциплине «математика для... 1 49.34kb.
Программа аттестационного испытания по дисциплине «математика для... 1 48.86kb.
Программа аттестационного испытания по дисциплине «математика для... 1 49.34kb.
"Основы логики, таблицы истинности" 1 40.8kb.
"наука логики" Гегеля 15 2345.39kb.
Практикум по решению задач в курсе информатики. Лебедева Э. 1 262.58kb.
Законы алгебры логики Название закона 1 58.04kb.
Запишите суждение на языке логики предикатов: Некоторые законы логики... 1 114.24kb.
Закон тождества: А=а закон двойного отрицания Переместительный (коммутативный) 1 17.8kb.
Направления изучения представлений о справедливости 1 202.17kb.

Алгебра логики. Решение задач с элементами алгебры логики - страница №1/1

ГОУ ВПО «Чувашский государственный педагогический университет

им. И. Я. Яковлева»

Конспект урока

Тема: Алгебра логики.



Решение задач с элементами алгебры логики.

Выполнила: студентка ФМФ ИМ-5

Гаврилова Е.В.

Андреева Е.Г.

Бакшаева Н.В.

Чебоксары 2010



Тема: Алгебра логики. Решение задач с элементами алгебры логики.

Класс: 11 «А» (физико-математический) в МОУ «Гимназия №1»

Возраст: 15-17 лет

Тип урока: комбинированный

Цели урока:

Образовательная: Сформировать у учащихся знания о законах логики, умение применять полученные знания на практике. Повторить материал пройденный на предыдущих уроках.

Воспитательная: Воспитание внимательности, аккуратности, умений анализировать, сравнивать и делать выводы.

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

Средства обучения: проектор, доска, презентация в MS PowerPoint.

Ход урока

Время (мин)

Организационный момент (приветствие и проверка отсутствующих)

3

Определение целей и плана работы на уроке

2

Закрепление изученного материала

5

Изучение нового материала

10

Практическая работа

20

Подведение итогов, выставление оценок и домашнее задание

5

Всего

45


Содержание урока

  • повторение логических операций;

  • основные законы логики;

  • применение логических операций и законов на практике;

  • подведение итогов.

Урок идет параллельно с презентацией.

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

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

Вопросы:

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

2. Основоположник алгебры логики? (Джордж Буль)

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

Ответ:

¬ отрицание (инверсия)



&, /\ конъюнкция (“И”)

I, V дизъюнкция (“ИЛИ”)

логическое следование (импликация)

http://festival.1september.ru/articles/508395/img2.gifравнозначность (эквивалентность)


  1. Основные законы логики.



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

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

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

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

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

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

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



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

A V A = A

A /\ A = A



  1. Закон исключения третьего.

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

A V ¬А= 1



  1. Закон противоречия.

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

A /\ ¬А= 0



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

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

A V 1 = 1

A V 0 = A

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

A /\ 1 = A

A /\ 0 = 0



  1. Выражение импликации через дизъюнкцию.

А img1.gif (71 bytes)В = ¬A V В

  1. Закон повторения.

А /\ А=А

A V А = A



  1. Закон поглощения.

А /\ (А V В)=А

А V (А/\ В)=А



  1. Закрепление изученного материала.

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

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

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

1) ЕЛЕНА

2) ВАДИМ

3) АНТОН

4) ФЕДОР

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

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

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

¬ (А http://festival.1september.ru/articles/508395/img1.gifВ) = ¬ (¬A V В) = (¬ (¬А) /\ ¬B) = A /\ ¬B

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

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

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

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

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

Ответ: 3

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

Какое логическое выражение равносильно выражению ¬ (А \/ ¬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 http://festival.1september.ru/articles/508395/img1.gifB)

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

¬ (B /\ C) V (A/\C http://festival.1september.ru/articles/508395/img1.gifB)

2 1 5 3 4

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

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



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

Решение:

A

B

C

(B /\ C)

¬ (B /\ C)

A/\C

(A/\C ? B)

¬ (B /\ C) V (A/\C http://festival.1september.ru/articles/508395/img1.gifB)

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 http://festival.1september.ru/articles/508395/img1.gifB)= (применим формулу для импликации)

¬ (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, а для логической операции “И” – символ &.

А

Законы & Физика

Б

Законы I (Физика & Биология)

В

Законы & Физика & Биология & Химия

Г

Законы I Физика I Биология

Решение:

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



Ответ: ВАБГ.

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



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

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



Фамилия

Пол

Математика

Русский язык

Химия

Информатика

Биология

Аганян

ж

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. (Задание А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. Домашнее задание.

Задание 1.

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

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

А

волейбол | баскетбол | подача

Б

волейбол | баскетбол | подача | блок

В

волейбол | баскетбол

Г

волейбол & баскетбол & подача

Задание 2

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

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

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

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

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

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

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



III. Итог урока.

Обобщить пройденный материал, оценить работу активных учеников.



Список используемой литературы

  1. Информатика и информационные технологии. Учебник для учащихся 10-11 классов. Угринович Н.Д., - М. Лаборатория Базовых Знаний, 2004.

  2. Практикум по информатике и информационным технологиям. Учебное пособие для общеобразовательных учреждений. Угринович Н.Д., Босова Л.Л., Михайлова Н.И. - М. Лаборатория Базовых Знаний, 2001.

  3. Логика в информатике. Лыскова В.Ю., Ракитина Е.А. - М. Лаборатория Базовых Знаний, 2001.

  4. Материалы для подготовки к ЕГЭ-2011 по информатике - http://kpolyakov.narod.ru/school/ege.htm





Без фанатизма ничего не добьешься. Эва Перон
ещё >>