Логические основы компьютеров
Логические основы компьютеров
Логика, высказывания
Высказывание или нет?
Логика и компьютер
Логические основы компьютеров
Обозначение высказываний
Операция НЕ (инверсия)
Операция И
Операция И (логическое умножение, конъюнкция)
Операция ИЛИ (логическое сложение, дизъюнкция)
Операция ИЛИ (логическое сложение, дизъюнкция)
Задачи
Операция «исключающее ИЛИ»
Свойства операции «исключающее ИЛИ»
Импликация («если …, то …»)
Импликация («если …, то …»)
Эквивалентность («тогда и только тогда, …»)
Базовый набор операций
Штрих Шеффера, «И-НЕ»
Стрелка Пирса, «ИЛИ-НЕ»
Формализация
Вычисление логических выражений
Составление таблиц истинности
Составление таблиц истинности
Задачи (таблица истинности)
Задачи (таблица истинности)
Логические основы компьютеров
Диаграммы Венна (круги Эйлера)
Диаграмма с тремя переменными
Задачи
Задачи
Задачи
Задачи
Задачи
Задачи
Задачи
Сложная задача
Логические основы компьютеров
Законы алгебры логики
Упрощение логических выражений
Упрощение логических выражений
Задачи (упрощение)
2.12M
Category: informaticsinformatics

Логические основы компьютеров

1. Логические основы компьютеров

1
Логические основы
компьютеров
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

2. Логические основы компьютеров

2
Логические
основы
компьютеров
Логика и компьютер
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

3. Логика, высказывания

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

4. Высказывание или нет?

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

5. Логика и компьютер

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

6. Логические основы компьютеров

6
Логические
основы
компьютеров
Логические операции
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

7. Обозначение высказываний

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

8. Операция НЕ (инверсия)

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

9. Операция И

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

10. Операция И (логическое умножение, конъюнкция)

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

11. Операция ИЛИ (логическое сложение, дизъюнкция)

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

12. Операция ИЛИ (логическое сложение, дизъюнкция)

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

13. Задачи

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

14. Операция «исключающее ИЛИ»

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

15. Свойства операции «исключающее ИЛИ»

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

16. Импликация («если …, то …»)

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

17. Импликация («если …, то …»)

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

18. Эквивалентность («тогда и только тогда, …»)

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

19. Базовый набор операций

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

20. Штрих Шеффера, «И-НЕ»

Логические основы компьютеров, 10 класс
20
Штрих Шеффера, «И-НЕ»
A | B A B
A
0
0
1
1
А|B
1
1
1
0
B
0
1
0
1
Базовые операции через «И-НЕ»:
A A|A
A B (A | B) | (A | B)
A B (A | A) | (B | B)
К.Ю. Поляков, Е.А. Ерёмин, 2013
?
Как доказать?
http://kpolyakov.spb.ru

21. Стрелка Пирса, «ИЛИ-НЕ»

Логические основы компьютеров, 10 класс
21
Стрелка Пирса, «ИЛИ-НЕ»
A B A B
A
0
0
1
1
B
0
1
0
1
А↓B
1
0
0
0
Базовые операции через «ИЛИ-НЕ»:
!
К.Ю. Поляков, Е.А. Ерёмин, 2013
Самостоятельно…
http://kpolyakov.spb.ru

22. Формализация

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

23. Вычисление логических выражений

Логические основы компьютеров, 10 класс
23
Вычисление логических выражений
1
4
2
5
3
X A B A C B C
+
Порядок вычислений:
•скобки
•НЕ
•И
•ИЛИ, исключающее ИЛИ
•импликация
•эквивалентность
A
К.Ю. Поляков, Е.А. Ерёмин, 2013
+
B
A
B
C
С
http://kpolyakov.spb.ru

24. Составление таблиц истинности

Логические основы компьютеров, 10 класс
24
Составление таблиц истинности
X A B A B B
0
1
2
3
A
B
A·B
A B
B
X
0
0
1
1
0
1
0
1
0
0
0
1
0
1
0
0
1
0
1
0
1
1
1
1
Логические выражения могут быть:
• тождественно истинными (всегда 1, тавтология)
• тождественно ложными (всегда 0, противоречие)
• вычислимыми (зависят от исходных данных)
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

25. Составление таблиц истинности

Логические основы компьютеров, 10 класс
25
Составление таблиц истинности
X A B A C B C
0
1
2
3
4
5
6
7
A
B
C
A∙B
A∙C
B∙C
X
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
1
0
0
0
1
0
0
0
1
0
0
0
1
0
1
1
1
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

26. Задачи (таблица истинности)

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

27. Задачи (таблица истинности)

Логические основы компьютеров, 10 класс
27
Задачи (таблица истинности)
Упрощённый способ подбора:
1) один нуль операция «ИЛИ»
2) получить 0, применив «НЕ» к
слагаемым:
X Y Z 0
1 1 1
1) одна единица операция «И»
2) получить 1, применив «НЕ» к
сомножителям:
X Y Z 1
0 1 0
К.Ю. Поляков, Е.А. Ерёмин, 2013
X
1
0
1
Y
0
0
1
Z
0
0
1
F
1
1
0
X
1
0
1
Y
0
1
1
Z
1
0
1
F
0
1
0
http://kpolyakov.spb.ru

28. Логические основы компьютеров

28
Логические
основы
компьютеров
Диаграммы
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

29. Диаграммы Венна (круги Эйлера)

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

30. Диаграмма с тремя переменными

Логические основы компьютеров, 10 класс
30
Диаграмма с тремя переменными
Хочу
Могу
3
2
5
1
6
4
7
8
1 M X H
5 M X H
2 M X H
6 M X H
3 M X H
7 M X H
4 M X H
8 M X H
Надо
3 4 M X H M X H
!
3 4 X H
Логические выражения можно упрощать!
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

31. Задачи

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

32. Задачи

Логические основы компьютеров, 10 класс
32
Задачи
A
B
NA|B = NA+ NB
50
огурцы & помидоры
A
B
NA|B = NA+ NB – NA&B
огурцы | помидоры
250
К.Ю. Поляков, Е.А. Ерёмин, 2013
огурцы
помидоры
100
200
http://kpolyakov.spb.ru

33. Задачи

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

34. Задачи

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

35. Задачи

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

36. Задачи

Логические основы компьютеров, 10 класс
37
Задачи
(принтер | сканер) & монитор = ?
А (сканер)
B (принтер)
450
принтер | сканер
0
NA|B = NA+ NB – NA&B
сканер
200
принтер
250
принтер
сканер
принтер & монитор = 40
50
40
сканер & монитор = 50
монитор
К.Ю. Поляков, Е.А. Ерёмин, 2013
40 + 50 = 90
http://kpolyakov.spb.ru

37. Задачи

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

38. Сложная задача

39
Логические
основы
компьютеров
Упрощение логических
выражений
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

39. Логические основы компьютеров

Логические основы компьютеров, 10 класс
40
Законы алгебры логики
название
для И
для ИЛИ
A A
двойного отрицания
A A 0
A A 1
операции с
константами
A 0 0, A 1 A
A 0 A, A 1 1
повторения
A A A
A A A
исключения третьего
поглощения
переместительный
A ( A B) A
A A B A
A B B A
A B B A
сочетательный
A (B C) ( A B) C A (B C) ( A B) C
распределительный
A B C ( A B) ( A C)
A (B C) A B A C
законы де Моргана
A B A B
A B A B
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

40. Законы алгебры логики

Логические основы компьютеров, 10 класс
41
Упрощение логических выражений
Шаг 1. Заменить операции на их выражения
через И, ИЛИ и НЕ:
A B A B A B
A B A B
A B A B A B
Шаг 2. Раскрыть инверсию сложных выражений по
формулам де Моргана:
A B A B,
A B A B
Шаг 3. Используя законы логики, упрощать выражение,
стараясь применять закон исключения третьего.
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

41. Упрощение логических выражений

Логические основы компьютеров, 10 класс
42
Упрощение логических выражений
Q M X H M X H (M M ) X H X H
X (B A) (A B) (A C)
( B A) (A B) (A C)
формула де Моргана
( B A) A B (A C)
( B A A A ) B (A C)
B A B (A C)
B A (A C)
B A
К.Ю. Поляков, Е.А. Ерёмин, 2013
раскрыли
распределительный
исключения третьего
повторения
поглощения
http://kpolyakov.spb.ru

42. Упрощение логических выражений

Логические основы компьютеров, 10 класс
43
Задачи (упрощение)
Какое логическое выражение равносильно выражению
A ¬(¬B C)?
1) ¬A ¬B ¬C
1)A B C
2) A ¬B ¬C
2) A B C
3) A B ¬C
3) A B C
4) A ¬B C
4) A B C
A ( B C) A B C A B C
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

43. Задачи (упрощение)

Логические основы компьютеров, 10 класс
44
Логические уравнения
A B A B C 1
A B 1
A=1, B=0, C=1
или
A=0, B=1, C – любое
2 решения: (0, 1, 0), (0, 1, 1)
A B C 1
!
Всего 3 решения!
K L M L N K L M 1
K=1, L=1,
M и N – любые
4 решения
M=1, L=1, N=1,
K – любое
2 решения
L (K M N) 1
К.Ю. Поляков, Е.А. Ерёмин, 2013
K=1, L=1, M=0,
N – любое
2 решения
!
Всего 5 решений!
http://kpolyakov.spb.ru
English     Русский Rules