Автор конспекта:
Автор(ы): — Грушецкая Марина Александровна
Место работы, должность: — МОУ»Куньинская средняя общеобразовательная школа», учитель математики и информатики
Регион: — Псковская область
Характеристики урока (занятия) Целевая аудитория: — Учитель (преподаватель)
Класс(ы): — 10 класс
Класс(ы): — 11 класс
Предмет(ы): — Информатика и ИКТ
Цель урока: — • Формирование умения применять полученные знания на практике; • Развитие умения построения таблиц истинности по заданным формулам; • Развитие умения решать текстовые задачи с использованием законов логики.
Тип урока: — Урок комплексного применения ЗУН учащихся
Краткое описание: — В настоящее время в текстах ЕГЭ по информатике есть много заданий по теме “алгебра логики”. Цель данного занятия – закрепление навыков решения заданий ЕГЭ по информатике с использованием элементов алгебры логики. 1. Повторение логических операций и законов. 2. Примение логических операций и законов на практике. 3. Объяснение домашнего задания. 4. Подведение итогов занятия.
Решение заданий ЕГЭ по информатике с использованием элементов алгебры логики
— В настоящее время в текстах ЕГЭ по информатике есть много заданий по теме “алгебра логики”. Цель данного занятия – закрепление навыков решения заданий ЕГЭ по информатике с использованием элементов алгебры логики.
Цели:
- Формирование умения применять полученные знания на практике;
- Развитие умения построения таблиц истинности по заданным формулам;
- Развитие умения решать текстовые задачи с использованием законов логики.
Сегодня мы с вами завершаем тему “Основы логики” и применим основные логические операции, законы преобразования для решения заданий ЕГЭ по информатике.
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 на всех наборах входящих в него простых высказываний.
Пример 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) Макс – последний, а первый – Джон.
Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов.
Какое место на турнире заняли Джон, Ник, Билл, Макс?
(В ответе перечислите подряд без пробелов места участников в указанном порядке имен.)
Подведение итогов занятия. В настоящее время в текстах ЕГЭ по информатике есть много заданий по теме “алгебра логики”. Цель данного занятия – закрепление навыков решения заданий ЕГЭ по информатике с использованием элементов алгебры логики.
Цели:
- Формирование умения применять полученные знания на практике;
- Развитие умения построения таблиц истинности по заданным формулам;
- Развитие умения решать текстовые задачи с использованием законов логики.
Сегодня мы с вами завершаем тему “Основы логики” и применим основные логические операции, законы преобразования для решения заданий ЕГЭ по информатике.
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 на всех наборах входящих в него простых высказываний.
Пример 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) Макс – последний, а первый – Джон.
Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов.
Какое место на турнире заняли Джон, Ник, Билл, Макс?
(В ответе перечислите подряд без пробелов места участников в указанном порядке имен.)
Подведение итогов занятия.
—
Решение заданий ЕГЭ по информатике с использованием элементов алгебры логики
— В настоящее время в текстах ЕГЭ по информатике есть много заданий по теме “алгебра логики”. Цель данного занятия – закрепление навыков решения заданий ЕГЭ по информатике с использованием элементов алгебры логики.
Цели:
- Формирование умения применять полученные знания на практике;
- Развитие умения построения таблиц истинности по заданным формулам;
- Развитие умения решать текстовые задачи с использованием законов логики.
Сегодня мы с вами завершаем тему “Основы логики” и применим основные логические операции, законы преобразования для решения заданий ЕГЭ по информатике.
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 на всех наборах входящих в него простых высказываний.
Пример 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) Макс – последний, а первый – Джон.
Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов.
Какое место на турнире заняли Джон, Ник, Билл, Макс?
(В ответе перечислите подряд без пробелов места участников в указанном порядке имен.)
Подведение итогов занятия.
Файлы: 8_48.pps
Размер файла: 3653632 байт.