Логические основы компьютеров
Логические основы компьютеров
Логика, высказывания
Высказывание или нет?
Логика и компьютер
Логические основы компьютеров
Обозначение высказываний
Операция НЕ (инверсия)
Операция И
Операция И (логическое умножение, конъюнкция)
Операция ИЛИ (логическое сложение, дизъюнкция)
Операция ИЛИ (логическое сложение, дизъюнкция)
Задачи
Импликация («если …, то …»)
Импликация («если …, то …»)
Эквивалентность («тогда и только тогда, …»)
Базовый набор операций
Составление таблиц истинности
Составление таблиц истинности
Задачи (таблица истинности)
Логические основы компьютеров
Диаграммы Венна (круги Эйлера)
Задачи
Задачи
30
1000
2200
550
Самостоятельно
Задачи
Задачи
Задачи
Задачи
Сложная задача
550
180
324
Логические основы компьютеров
Логические элементы компьютера
3.96M
Категория: ИнформатикаИнформатика

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

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

1
Логические основы
компьютеров
§ 18. Логика и компьютер
§ 19. Логические операции
§ 20. Диаграммы
§ 21. Упрощение логических выражений
§ 22. Синтез логических выражений
§ 23. Предикаты и кванторы
§ 24. Логические элементы компьютера
§ 25. Логические задачи
Задачи ЕГЭ
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

2
Логические
основы
компьютеров
§ 18. Логика и компьютер
К.Ю. Поляков, Е.А. Ерёмин, 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
Логические
основы
компьютеров
§ 19. Логические операции
К.Ю. Поляков, Е.А. Ерёмин, 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
0
0
1
1
B
0
1
0
1
К.Ю. Поляков, Е.А. Ерёмин, 2013
А B
1
1
0
1
A B A B
http://kpolyakov.spb.ru

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

Логические основы компьютеров, 10 класс
15
Импликация («если …, то …»)
«Если Вася идет гулять, то Маша сидит дома».
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

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

Логические основы компьютеров, 10 класс
16
Эквивалентность («тогда и только тогда, …»)
Высказывание «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

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

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

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

Логические основы компьютеров, 10 класс
18
Составление таблиц истинности
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

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

Логические основы компьютеров, 10 класс
19
Составление таблиц истинности
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

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

Логические основы компьютеров, 10 класс
20
Задачи (таблица истинности)
Символом 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
К.Ю. Поляков, Е.А. Ерёмин, 2013
X
1
0
1
Y
0
0
1
Z
0
0
1
F
1
1
0
http://kpolyakov.spb.ru

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

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

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

Логические основы компьютеров, 10 класс
22
Диаграммы Венна (круги Эйлера)
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

23. Задачи

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

24. Задачи

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

25.

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

26. 30

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

27. 1000

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

28. 2200

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

29. 550

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

30. Самостоятельно

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

31.

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

32.

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

33.

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

34. Задачи

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

35. Задачи

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

36. Задачи

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

37. Задачи

Логические основы компьютеров, 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

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

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

39. 550

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

40. 180

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

41. 324

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

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

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

43. Логические элементы компьютера

Логические основы компьютеров, 10 класс
43
Логические элементы компьютера
значок инверсии
A
A
A
&
A
A B
B
НЕ
B
И
A
&
B
A B
A B
1
ИЛИ
A
1
A B
B
И-НЕ
К.Ю. Поляков, Е.А. Ерёмин, 2013
ИЛИ-НЕ
http://kpolyakov.spb.ru
English     Русский Правила