Презентация «Логические основы компьютеров»

Тема урока: «Логические основы компьютеров». Далее

ПЛАН ИЗУЧЕНИЯ ТЕМЫ «ЛОГИКА» ПЛАН ИЗУЧЕНИЯ ТЕМЫ «ЛОГИКА» алгебра логики высказывание логическая операция логическое выражение таблица истинности законы логики

Клод Шеннон (1916-2001). Его исследования позволили применить алгебру логики в вычислительной технике Логика Аристотель (384-322 до н.э.). Основоположник формальной логики (понятие, суждение, умозаключение). Джордж Буль (1815-1864). Создал новую область науки - Математическую логику (Булеву алгебру или Алгебру высказываний).

Алгебра логики это наука о формах и способах мышления. Алгебра логики это наука о формах и способах мышления. Она оперирует логическими высказываниями. Высказывание - это предложение на любом языке, содержание которого можно однозначно определить как истинное или ложное. В русском языке высказывания выражаются повествовательными предложениями. Побудительные и вопросительные предложения высказываниями не являются.

Простые и сложные высказывания Простое высказывание - логическое высказывание, состоящее из одного утверждения. Сложное высказывание - логическое высказывание, состоящее из нескольких утверждения, объединенных с помощью "связок": союзов "и", "или (либо)", частицы "не", связки "если, то" и др.

Высказывание или нет? Зимой идет дождь. Снегири живут в Крыму. Кто к нам пришел? У треугольника 5 сторон. Как пройти в библиотеку? Переведите число в десятичную систему. Запишите домашнее задание

Из следующих предложений выбрать те, которые являются высказываниями, объясните свой ответ: Какой длины эта лента? Прослушайте сообщение! Делайте утреннюю зарядку! Назовите устройства ввода/вывода информации. Кто отсутствует? Париж – столица Англии Число 11 является простым 4 + 5 = 10 Без труда не вытащишь и рыбку из пруда Некоторые медведи живут на севере Все медведи – бурые Чему равно расстояние от Москвы до Питера? Картины Пикассо слишком абстрактны. Решение задачи – информационный процесс.

В алгебре логики высказывания обозначают буквами и называют логическими переменными. Если высказывание истинно, то значение соответствующей ему логической переменной обозначают единицей (А = 1), а если ложно - нулём (В = 0). 0 и 1 называются логическими значениями.

Конъюнкция - логическая операция, ставящая в соответствие каждым двум высказываниям новое высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны. Другое название: логическое умножение. Обозначения:  , , &, И. А В А&В 0 0 0 0 1 0 1 0 0 1 1 1 Логические операции Таблица истинности: Графическое представление A B А&В

Дизъюнкция - логическая операция, которая каждым двум высказываниям ставит в соответствие новое высказывание, являющееся ложным тогда и только тогда, когда оба исходных высказывания ложны. Другое название: логическое сложение. Обозначения: V, |, ИЛИ, +. А В АVВ 0 0 0 0 1 1 1 0 1 1 1 1 Таблица истинности: Графическое представление A B АVВ

Инверсия - логическая операция, которая каждому высказыванию ставит в соответствие новое высказывание, значение которого противоположно исходному. Другое название: логическое отрицание. Обозначения: НЕ, ¬ , ¯ . А Ā 0 1 1 0 Таблица истинности:

Импликация («если …, то …») Высказывание «A  B» истинно, если не исключено, что из А следует B. A – «Работник хорошо работает». B – «У работника хорошая зарплата». A B А  B 0 0 1 0 1 1 1 0 0 1 1 1

Эквивалентность («тогда и только тогда, …») Высказывание «A  B» истинно тогда и только тогда, когда А и B равны. A B А  B 0 0 1 0 1 0 1 0 0 1 1 1

Вычисление логических выражений Порядок вычислений: скобки НЕ И ИЛИ, импликация эквивалентность

Задание Определите истинность составного высказывания, состоящего из простых высказываний: А = {Принтер – устройство вывода информации}, В = {Процессор – устройство хранения информации}, С = {Монитор – устройство вывода информации}, D = {Клавиатура – устройство обработки информации}.

Решение А = 1, В = 0, С = 1, D = 0

Задание 1. Для какого из указанных значений числа X истинно высказывание ((X < 5)→(X < 3))  ((X < 2)→(X < 1)) 1) 1 2) 2 3) 3 4) 4

Задание 2. Для какого имени истинно высказывание: ¬ (Первая буква имени гласная → Четвертая буква имени согласная)? ЕЛЕНА 2) ВАДИМ 3) АНТОН 4) ФЕДОР

Задание 3. Найти значения выражений для А=0 и В= 0

Задание 4. Найдите значения логических выражений: ((1V0)&(1&1))&(0V1); ((1&0)V (1&0)) ≈1; ((1V(0&0)) 1;

Задание 5

Логические операции при формировании поисковых запросов Список поисковых запросов Запросы с операцией И будут располагаться в начале списка (по ним будет найдено мало сайтов) Требуется расположить запросы по количества найденных сайтов возрастанию Запросы с операцией ИЛИ будут располагаться в конце списка (по ним будет найдено много сайтов) В середине списка – смешанные запросы (операции И и ИЛИ) Сначала идут запросы, где операция И стоит вне скобок Потом идут запросы, где операция И стоит в скобках

Решение задач (выстроить запросы по возрастанию количества найденных сайтов) A чемпионы | (бег & плавание) Б чемпионы & плавание В чемпионы | бег | плавание Г чемпионы & Европа & бег & плавание Запросы с операцией И располагаются в начале списка. Чем больше операндов, тем ближе к началу A чемпионы | (бег & плавание) Г чемпионы & Европа & бег & плавание Б чемпионы & плавание Смешанный запрос – в середине списка Запрос с операцией ИЛИ располагается в конце списка. В чемпионы | бег | плавание Ответ: ГБАВ

Решение задач (выстроить запросы по возрастанию количества найденных сайтов) А разведение & содержание & меченосцы & сомики Б содержание & меченосцы В (содержание & меченосцы) | сомики Г содержание & меченосцы & сомики Запросы с операцией И располагаются в начале списка. Чем больше операндов, тем ближе к началу А разведение & содержание & меченосцы & сомики Г содержание & меченосцы & сомики Б содержание & меченосцы Так как запросов с операцией ИЛИ нет, смешанный запрос будет расположен в конце списка В (содержание & меченосцы) | сомики Ответ: АГБВ

Решение задач (выстроить запросы по возрастанию количества найденных сайтов) А волейбол | баскетбол | подача Б волейбол | баскетбол | подача | блок В волейбол | баскетбол Г волейбол & баскетбол & подача Запрос с операцией И располагается в начале списка Г волейбол & баскетбол & подача Запросы с операцией ИЛИ располагаются в конце списка. Чем больше операндов, тем ближе к концу В волейбол | баскетбол А волейбол | баскетбол | подача Б волейбол | баскетбол | подача | блок Ответ: ГВАБ

Решение задач (выстроить запросы по возрастанию количества найденных сайтов) А физкультура Б физкультура & подтягивания & отжимания В физкультура & подтягивания Г физкультура | фитнес Запросы с операцией И располагаются в начале списка. Чем больше операндов, тем ближе к началу Б физкультура & подтягивания & отжимания В физкультура & подтягивания Запрос из одного операнда можно считать запросом ИЛИ с наименьшим числом операндов. Тогда он в списке будет перед всеми запросами с ИЛИ А физкультура Запрос с операцией ИЛИ располагается в конце списка Г физкультура | фитнес Ответ: БВАГ

Решение задач на вычисление количества найденных сайтов В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет. Запрос Найдено страниц (в тысячах) Крейсер | Линкор 7000 Крейсер 4800 Линкор 4500 Какое количество страниц (в тысячах) будет найдено по запросу Крейсер & Линкор ? Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.

Решение задач на вычисление количества найденных сайтов Решение: Построим примерную диаграмму Венна. крейсер линкор    Считаем порядковые номера областей диаграммы (цифры в кружочках) своеобразными переменными. Запишем уравнения:  +  +  = 7000; - по запросу «крейсер | линкор»  +  = 4800; - по запросу «крейсер»  +  = 4500. - по запросу «линкор»  - искомый запрос «крейсер & линкор»

Решение задач на вычисление количества найденных сайтов Решение: крейсер линкор    Решаем систему уравнений:  +  +  = 7000;  +  = 4800;  +  = 4500. Ответ: по запросу «крейсер & линкор» будет найдено 2300 сайтов.  = 7000 – 4800 = 2200  = 4500 – 2200 = 2300.

Решение задач на вычисление количества найденных сайтов Тренировочная работа №2. Вариант 1 В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет. Какое количество страниц (в тысячах) будет найдено по запросу Торты ? Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов. Запрос Найдено страниц (в тысячах) Торты | Пироги 12000 Торты & Пироги 6500 Пироги 7700

Решение задач на вычисление количества найденных сайтов Решение: Построим примерную диаграмму Венна. торты пироги    Считаем порядковые номера областей диаграммы (цифры в кружочках) своеобразными переменными. Запишем уравнения:  +  +  = 12000; - по запросу «торты | пироги»  = 6500; - по запросу «торты & пироги»  +  = 7700. - по запросу «пироги»  +  - искомый запрос «торты»

Решение задач на вычисление количества найденных сайтов Решение: торты пироги    Решаем систему уравнений: Ответ: по запросу «торты» будет найдено 10800 сайтов.  +  +  = 12000;  = 6500;  +  = 7700.  +  = 12000 – 6500 = 5500;  = 7700 – 6500 = 1200;  = 5500 – 1200 = 4300;  +  = 4300 + 6500 = 10800

Решение задач на вычисление количества найденных сайтов Тренировочная работа №2. Вариант 2 В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет. Какое количество страниц (в тысячах) будет найдено по запросу Выпечка ? Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов. Запрос Найдено страниц (в тысячах) Пирожное & Выпечка 5100 Пирожное 9700 Пирожное | Выпечка 14200

Решение задач на вычисление количества найденных сайтов Решение: Построим примерную диаграмму Венна. пирожное выпечка    Считаем порядковые номера областей диаграммы (цифры в кружочках) своеобразными переменными. Запишем уравнения:  +  +  = 14200. - по запросу «пирожное & выпечка»  = 5100; - по запросу «пирожное»  +  = 9700; - по запросу «пирожное | выпечка»  +  - искомый запрос «выпечка»

Решение задач на вычисление количества найденных сайтов Решение: Решаем систему уравнений: пирожное выпечка     +  +  = 14200.  = 5100;  +  = 9700;  = 5100 – 9700 = 4600;  +  = 14200 – 4600 = 9600. Ответ: по запросу «выпечка» будет найдено 9600 сайтов.

Определите какой операции соответствует каждая таблица истинности А В А ? В 0 0 0 0 1 0 1 0 0 1 1 1 А В А ? В 0 0 0 0 1 1 1 0 1 1 1 1 А В А ? B 0 0 1 0 1 1 1 0 0 1 1 1 А В А ? B 0 0 1 0 1 0 1 0 0 1 1 1

Проверьте себя А В АВ 0 0 0 0 1 0 1 0 0 1 1 1 А В АВ 0 0 0 0 1 1 1 0 1 1 1 1 А В АB 0 0 1 0 1 1 1 0 0 1 1 1 А В А  B 0 0 1 0 1 0 1 0 0 1 1 1