Логические элементы

1. Математическая логика

1
Математическая
логика
§ 8. Логика и компьютеры
§ 9. Логические элементы
§ 10. Другие логические операции
§ 11. Логические выражения
§ 12. Множества и логика
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

2. Математическая логика

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

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

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

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

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

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

Математическая логика, 9 класс
Логика и компьютер
5
двоичная логика
! Любое высказывание может быть ложно (0)
или истинно (1).
Логика изучает операции между 0 и 1!
! Связь с двоичным кодированием!
Алгебра логики — это математический
аппарат, с помощью которого
записывают, упрощают и преобразуют
логические высказывания, вычисляют
их значения.
Алгебра высказываний,
булева алгебра
К.Ю. Поляков, Е.А. Ерёмин, 2018
Джордж Буль
http://kpolyakov.spb.ru

6. Простые и составные высказывания

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

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

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

8. Операция И

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

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

Математическая логика, 9 класс
9
Операция И (логическое умножение, конъюнкция)
0
1
2
3
A
B
АиB
0
0
1
1
0
1
0
1
0
0
0
1
также A·B, A and B
? Почему
умножение?
конъюнкция – от лат. conjunctio — соединение
A и B = min(A, B)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

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

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

Математическая логика, 9 класс
11
Операция ИЛИ (логическое сложение, дизъюнкция)
A
B
А или B
0
0
1
1
0
1
0
1
0
1
1
1
также: A+B, A or B
? Почему
сложение?
! 1+1=1
дизъюнкция – от лат. disjunctio — разъединение
A и B = max(A, B)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Математическая логика, 9 класс
12
Упрощение логических выражений
Aи0=A∙0=0
Aи1=A∙1=A
A или 0 = A + 0 = A
A или 1 = A + 1 = 1
A и не A = A ∙ A = 0
A или (не A) = A + A = 1
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

13. Построить таблицу истинности

Математическая логика, 9 класс
13
Построить таблицу истинности
¬( x ∨ ¬y & z)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

14. Доказать тождества

Математическая логика, 9 класс
14
Доказать тождества
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

15. Построить таблицу истинности

Математическая логика, 9 класс
15
Построить таблицу истинности
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

16. Построить таблицу истинности

Математическая логика, 9 класс
16
Построить таблицу истинности
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

17. Доказать тождество

Математическая логика, 9 класс
17
Доказать тождество
x & y z x & y x & z
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

18. Задание 1

Математическая логика, 9 класс
18
Задание 1
Дан фрагмент таблицы истинности выражения F.
Какое выражение соответствует F?
1) x1 ¬x2 x3 ¬x4 x5 x6 ¬x7
2) ¬x1 x2 ¬x3 x4 ¬x5 ¬x6 x7
3) ¬x1 x2 ¬x3 x4 x5 x6 x7
4) x1 ¬x2 x3 ¬x4 ¬x5 ¬x6 ¬x7
К.Ю. Поляков, Е.А. Ерёмин, 2018
x1
x2
0
1
x3 x4 x5 x6 x7
1 1 1 1
0
1
0
1
0
1
1
0
0
0
1
0
1
1
0
1
1
F
1
http://kpolyakov.spb.ru

19. Задание 2

Математическая логика, 9 класс
19
Задание 2
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

20. Задание 3

Математическая логика, 9 класс
20
Задание 3
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

21. Задание 4

Математическая логика, 9 класс
21
Задание 4
Дан фрагмент таблицы истинности для выражения F:
Каким выражением может быть F?
1) x1 ¬x2 x3 ¬x4 x5 x6 ¬x7 ¬x8
2) x1 x2 x3 ¬x4 ¬x5 ¬x6 ¬x7 x8
3) ¬x1 x2 ¬x3 x4 x5 ¬x6 ¬x7 ¬x8
4) x1 ¬x2 ¬x3 ¬x4 ¬x5 ¬x6 ¬x7 ¬x8
x1
x2
X3
0
x4
1
x6
х7
1
x8
1
1
К.Ю. Поляков, Е.А. Ерёмин, 2018
x5
0
F
1
1
0
http://kpolyakov.spb.ru

22. Задание 5

Математическая логика, 9 класс
22
Задание 5
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

23. Математическая логика

23
Математическая
логика
§ 7. Другие логические
операции
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

24. Операции с двумя переменными

Математическая логика, 9 класс
24
Операции с двумя переменными
? Сколько всего?
A
0
0
1
1
B
0
1
0
1
К.Ю. Поляков, Е.А. Ерёмин, 2018
F
?
?
?
?
0 или 1
24 = 16
http://kpolyakov.spb.ru

25. Импликация

Математическая логика, 9 класс
25
Импликация
A
X=A B
X = Если идёт дождь, то
Лена раскрывает зонтик.
B
Импликация A → B истинна, если не исключено,
что из A следует B.
A
0
0
1
1
B
0
1
0
1
К.Ю. Поляков, Е.А. Ерёмин, 2018
F
1
1
0
1
Идёт дождь, но Лена
не раскрыла зонтик.
http://kpolyakov.spb.ru

26. Эквиваленция

Математическая логика, 9 класс
26
Эквиваленция
Высказывание «A B» истинно тогда и только
тогда, когда А и B равны.
A
0
0
1
1
К.Ю. Поляков, Е.А. Ерёмин, 2018
B
0
1
0
1
А B
1
0
0
1
http://kpolyakov.spb.ru

27. Порядок вычисления

Математическая логика, 9 класс
27
Порядок вычисления
• скобки
• НЕ
•И
• ИЛИ , исключающее ИЛИ
• импликация
• эквиваленция
X A B (A B B )
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

28. Построить таблицу истинности

Математическая логика, 9 класс
28
Построить таблицу истинности
¬x→ (y → ¬z)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

29. Составьте таблицы истинности

Математическая логика, 9 класс
29
Составьте таблицы истинности
p q q q p
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

30. Составьте таблицы истинности

Математическая логика, 9 класс
30
Составьте таблицы истинности
x y x& y
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

31. Какое выражение соответствует F?

Математическая логика, 9 класс
31
Какое выражение соответствует F?
1) (A → ¬B) C
2) (¬A B) C
3) (A B) → C
4) (A B) → C
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

32. Какое выражение соответствует F?

Математическая логика, 9 класс
32
Какое выражение соответствует F?
1) X → Z Y
2) ¬Z →(X → Y)
3) ¬(X Y) Z
4) ¬X ¬(Y Z)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

33. Какое выражение соответствует F?

Математическая логика, 9 класс
33
Какое выражение соответствует F?
1) (X ≡ Z) (¬X → Y)
2) (¬X ≡ Z) (¬X → Y)
3) (X ≡ ¬Z) (¬X → Y) 4) (X ≡ Z) ¬(Y → Z)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

34. Математическая логика

34
Математическая
логика
§ 8. Логические выражения
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

35. ОГЭ1

Математическая логика, 9 класс
35
ОГЭ1
Для скольких значений числа X истинно
высказывание:
R = (X < 5) И НЕ (X < 1) ?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

36. ОГЭ2

Математическая логика, 9 класс
36
ОГЭ2
Для каких из указанных значений числа X
ЛОЖНО высказывание:
(НЕ (X ≥ 3) И НЕ (X = 8)) ИЛИ (X ≤ 5) ?
X = 4:
X = 1:
X = 8:
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

37. ОГЭ3

Математическая логика, 9 класс
37
ОГЭ3
Для каких из приведённых имён ЛОЖНО
высказывание:
(Первая буква согласная)
НЕ(Первая буква гласная) ИЛИ
(Последняя буква гласная) ?
Результат
Никита
Антон
Даниил
Инна
Кирилл
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

38. ОГЭ4

Математическая логика, 9 класс
38
ОГЭ4
Напишите наибольшее целое число x, для которого
истинно высказывание:
НЕ (X чётное) И НЕ (X >= 7)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

39. ОГЭ5

Математическая логика, 9 класс
39
ОГЭ5
Напишите наименьшее целое число x, для которого
истинно высказывание:
НЕ (X <= 8) И НЕ (X >= 15) И (X чётное).
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

40. ОГЭ6

Математическая логика, 9 класс
40
ОГЭ6
Напишите наименьшее число x, для которого
истинно высказывание:
НЕ (x < 45) И НЕ (в числе x нет одинаковых цифр)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

41. ОГЭ7

Математическая логика, 9 класс
41
ОГЭ7
Напишите наибольшее число x, для которого ложно
высказывание:
НЕ (x ≤ 71) ИЛИ (x не делится на 7)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

42. ОГЭ 8

Математическая логика, 9 класс
42
ОГЭ 8
Напишите наименьшее число x, для которого истинно
высказывание:
(x не равно 16) И (x кратно 16) И НЕ (x имеет не
менее 3 цифр)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

43. ОГЭ 9

Математическая логика, 9 класс
43
ОГЭ 9
Напишите сумму наименьшего и наибольшего числа x,
для которого ложно высказывание:
НЕ (x трехзначное число) ИЛИ НЕ (x четное число)
ИЛИ (x оканчивается на 8) ИЛИ (x кратно 3)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

44. ОГЭ 10

Математическая логика, 9 класс
44
ОГЭ 10
Напишите наименьшее натуральное число x, для
которого истинно высказывание:
((X < 5) → (X < 3)) /\ ((X < 2) → (X > 1))
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

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

Математическая логика, 9 класс
45
Самостоятельно
I вариант
Напишите наибольшее целое число x, для
которого истинно высказывание:
НЕ (X <= 11) И НЕ (X >= 17) И (X нечётное).
II вариант
Напишите наименьшее целое число x, для
которого истинно высказывание:
НЕ (X <= 8) И НЕ (X >= 15) И (X чётное).
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

46. Конец фильма

Математическая логика, 9 класс
46
Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г. Санкт-Петербург
[email protected]
ЕРЕМИН Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной
дидактики и ИТО ПГГПУ, г. Пермь
[email protected]
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

47. Источники иллюстраций

Математическая логика, 9 класс
47
Источники иллюстраций
1.
2.
иллюстрации художников издательства «Бином»
авторские материалы
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru