К.Ю. Поляков, Е.А. Ерёмин, 2013 1 Логические основы компьютеров § 18. Логика и компьютерЛогика и компьютер § 19. Логические операцииЛогические операции. - презентация

1 К.Ю. Поляков, Е.А. Ерёмин, Логические основы компьютеров § 18. Логика и компьютер Логика и компьютер § 19. Логические операции Логические операции § 20. Диаграммы Диаграммы

2 К.Ю. Поляков, Е.А. Ерёмин, Логические основы компьютеров § 18. Логика и компьютер

3 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Логика, высказывания Аристотель ( до н.э.) Логика (др.греч. λογικος) – это наука о том, как правильно рассуждать, делать выводы, доказывать утверждения. Формальная логика отвлекается от конкретного содержания, изучает только истинность и ложность высказываний. Логическое высказывание – это повествовательное предложение, относительно которого можно однозначно сказать, истинно оно или ложно.

4 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Высказывание или нет? Сейчас идет дождь. Жирафы летят на север. История – интересный предмет. У квадрата – 10 сторон и все разные. Красиво! В городе N живут 2 миллиона человек. Который час?

5 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Логика и компьютер Двоичное кодирование – все виды информации кодируются с помощью 0 и 1. Задача – разработать оптимальные правила обработки таких данных. Почему «логика»? Результат выполнения операции можно представить как истинность (1) или ложность (0) некоторого высказывания. Джордж Буль разработал основы алгебры, в которой используются только 0 и 1 (алгебра логики, булева алгебра).

6 К.Ю. Поляков, Е.А. Ерёмин, Логические основы компьютеров § 19. Логические операции

7 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Обозначение высказываний A – Сейчас идет дождь. B – Форточка открыта. простые высказывания (элементарные) Составные высказывания строятся из простых с помощью логических связок (операций) «и», «или», «не», «если … то», «тогда и только тогда» и др. Любое высказывание может быть ложно (0) или истинно (1). ! A и B A или не B если A, то B A тогда и только тогда, когда B Сейчас идет дождь и открыта форточка. Сейчас идет дождь или форточка закрыта. Если сейчас идет дождь, то форточка открыта. Дождь идет тогда и только тогда, когда открыта форточка.

8 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Операция НЕ (инверсия) Если высказывание A истинно, то «не А» ложно, и наоборот. Ане А таблица истинности операции НЕ также,, not A (Паскаль), ! A (Си) Таблица истинности логического выражения Х – это таблица, где в левой части записываются все возможные комбинации значений исходных данных, а в правой – значение выражения Х для каждой комбинации.

9 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Операция И Высказывание «A и B» истинно тогда и только тогда, когда А и B истинны одновременно. 220 В A и B A B

10 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Операция И (логическое умножение, конъюнкция) ABА и B 1 0 также: A·B, A B, A and B (Паскаль), A && B (Си) конъюнкция – от лат. conjunctio соединение A B

11 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Операция ИЛИ (логическое сложение, дизъюнкция) Высказывание «A или B» истинно тогда, когда истинно А или B, или оба вместе. 220 В A или B AB

12 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Операция ИЛИ (логическое сложение, дизъюнкция) ABА или B 1 0 также: A+B, A B, A or B (Паскаль), A || B (Си) дизъюнкция – от лат. disjunctio разъединение

13 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 13 В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. Для обозначения логической операции «ИЛИ» в запросе используется символ |, а для логической операции «И» – &. 1) принтеры & сканеры & продажа 2) принтеры & продажа 3) принтеры | продажа 4) принтеры | сканеры | продажа

14 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Операция «исключающее ИЛИ» Высказывание «A B» истинно тогда, когда истинно А или B, но не оба одновременно (то есть A B). «Либо пан, либо пропал». AB А B 0 0 также: A xor B (Паскаль), A ^ B (Си) сложение по модулю 2: А B = (A + B) mod 2 арифметическое сложение, 1+1=2 остаток

15 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Свойства операции «исключающее ИЛИ» A A = (A B) B = A 0 = A 1 = A 0 ? AB А B A

16 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Импликация («если …, то …») Высказывание «A B» истинно, если не исключено, что из А следует B. A – «Работник хорошо работает». B – «У работника хорошая зарплата». ABА B

17 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Импликация («если …, то …») «Если Вася идет гулять, то Маша сидит дома». A – «Вася идет гулять». B – «Маша сидит дома». Маша может пойти гулять (B=0), а может и не пойти (B=1)! ABА B А если Вася не идет гулять? ?

18 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Эквивалентность («тогда и только тогда, …») Высказывание «A B» истинно тогда и только тогда, когда А и B равны. ABА B

19 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Базовый набор операций С помощью операций И, ИЛИ и НЕ можно реализовать любую логическую операцию. ИЛИИ НЕ базовый набор операций Сколько всего существует логических операции с двумя переменными? ?

20 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Штрих Шеффера, «И-НЕ» ABА | B Базовые операции через «И-НЕ»: Как доказать? ?

21 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Стрелка Пирса, «ИЛИ-НЕ» ABА B Базовые операции через «ИЛИ-НЕ»: Самостоятельно… !

22 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Формализация Прибор имеет три датчика и может работать, если два из них исправны. Записать в виде формулы ситуацию «авария». A – «Датчик 1 неисправен». B – «Датчик 2 неисправен». C – «Датчик 3 неисправен». Аварийный сигнал: X – «Неисправны два датчика». X – «Неисправны датчики 1 и 2» или «Неисправны датчики 1 и 3» или «Неисправны датчики 2 и 3». логическая формула Формализация – это переход к записи на формальном языке! !

23 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Вычисление логических выражений Порядок вычислений: скобки НЕ И ИЛИ, исключающее ИЛИ импликация эквивалентность AB + + BC AС

24 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Составление таблиц истинности ABCABACBCX

25 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Составление таблиц истинности ABA·BA·BX Логические выражения могут быть: тождественно истинными (всегда 1, тавтология) тождественно ложными (всегда 0, противоречие) вычислимыми (зависят от исходных данных)

26 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи (таблица истинности) 26 Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F. Какое выражение соответствует F? 1) ¬X ¬Y ¬Z 2) X Y Z 3) X Y Z 4) ¬X ¬Y ¬Z XYZF ) 2) 3) 4) 1) 2) 3) 4) Упрощённый способ подбора:

27 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи (таблица истинности) 27 XYZF Упрощённый способ подбора: 1)один нуль операция «ИЛИ» 2)получить 0, применив «НЕ» к слагаемым: 111 XYZF )одна единица операция «И» 2)получить 1, применив «НЕ» к сомножителям: 010

28 К.Ю. Поляков, Е.А. Ерёмин, Логические основы компьютеров § 20. Диаграммы

29 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Диаграммы Венна (круги Эйлера) A B A B A A·BA·B A B A+B A B A B A B

30 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Диаграмма с тремя переменными Х очу М огу Н адо Логические выражения можно упрощать! !

31 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Известно количество сайтов, которых находит поисковый сервер по следующим запросам : Сколько сайтов будет найдено по запросу огурцы | помидоры Задачи 31 Запрос Количество сайтов огурцы 100 помидоры 200 огурцы & помидоры 50

32 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 32 N A|B = N A + N B AB A B N A|B = N A + N B – N A&B огурцы | помидоры 50 огурцы помидоры огурцы & помидоры 250

33 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Известно количество сайтов, которых находит поисковый сервер по следующим запросам : Сколько сайтов будет найдено по запросу Динамо & Спартак & Рубин Задачи 33 Запрос Количество сайтов Динамо & Рубин 320 Спартак & Рубин 280 (Динамо | Спартак) & Рубин 430 Общее условие с & можно отбросить ! !

34 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Известно количество сайтов, которых находит поисковый сервер по следующим запросам : Сколько сайтов будет найдено по запросу Динамо & Спартак Задачи 34 Запрос Количество сайтов Динамо 320 Спартак 280 Динамо | Спартак 430 Ответ: – 430 = 170

35 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 35 Динамо Спартак Рубин Динамо & Рубин = = 320 Спартак & Рубин = = 280 (Динамо | Спартак) & Рубин = = 430 Динамо & Спартак & Рубин = 2 = ( ) – 430 = 170

36 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Некоторый сегмент сети Интернет состоит из 1000 сайтов. Поисковый сервер в автоматическом режиме составил таблицу ключевых слов для сайтов этого сегмента. Вот ее фрагмент: Сколько сайтов будет найдено по запросу (принтер | сканер) & монитор если по трем следующим запросам найдено: принтер | сканер – 450 сайтов, принтер & монитор – 40 сайтов сканер & монитор – 50 сайтов. Задачи 36 Ключевое слово Количество сайтов, для которых данное слово является ключевым сканер 200 принтер 250 монитор 450

37 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Задачи 37 А (сканер) B (принтер) N A|B = N A + N B – N A&B принтер | сканер 450 сканер принтер сканер принтер монитор = принтер & монитор = 40 сканер & монитор = (принтер | сканер) & монитор = ?

38 Логические основы компьютеров, 10 класс К.Ю. Поляков, Е.А. Ерёмин, Сложная задача 38 Ниже приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета: мезозой 500 кроманьонец 600 неандерталец 700 мезозой | кроманьонец 800 мезозой | неандерталец 1000 неандерталец & (мезозой | кроманьонец) 200 Сколько страниц будет найдено по запросу кроманьонец & (мезозой | неандерталец)