9-2_Математическая логика задачи (1)

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

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

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

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

3. Таблицы истинности

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

4. Задачи

Математическая логика, 9 класс
4
Задачи
Для каких значений числа X истинно
высказывание:
(X < 5) и не (X < 1) ?
(X < 5) и (X >= 1)
1
2
3
4
5
1, 2, 3, 4
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

5.

Задание 3 № 10877
Напишите наименьшее целое число X, для которого истинно высказывание:
НЕ (X < = 8) И НЕ (X > = 15) И (X чётное)
Решение:
Запишем выражение в виде
(X >8) И (X < 15) И (X чётное)
Значит, наименьшее число, для которого высказывание будет истинным это 10.
Ответ: 10

6.

Задание 3 № 18186
Напишите наименьшее целое число, для которого истинно высказывание:
НЕ (Число < 100) И НЕ (Число нечётное)
Решение:
Запишем выражение в виде
(Число >= 100) И (Число чётное)
Значит, наименьшее число, для которого высказывание будет истинным это 100.
Ответ: 100

7.

Задание 3 № 18227
Напишите наибольшее двузначное число, для которого истинно высказывание:
(первая цифра нечётная) И НЕ (число делится на 3)
Решение:
Запишем выражение в виде
(первая цифра нечётная) И (число не делится на 3)
Значит, наибольшее число, для которого высказывание будет истинным - это
98.
Ответ: 98

8.

Задание 3 № 12852
Напишите наибольшее целое число X, для которого истинно высказывание:
(X < 17) И НЕ (X > 44)
Решение:
Запишем выражение в виде
(X < 17) И (X < = 44)
Значит, наибольшее число, для которого высказывание будет истинным - это
16.
Ответ: 16

9. Задачи

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

10. Задачи

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

11. Задачи (ЛОЖНО  ИСТИННО)

Математическая логика, 9 класс
11
Задачи (ЛОЖНО ИСТИННО)
! Для перехода от ложного условия к равносильному
истинному нужно:
– заменить все простые условия на обратные
– заменить И ИЛИ
– заменить ИЛИ И
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

12. Задачи

Математическая логика, 9 класс
12
Задачи
Для каких из приведённых имён ЛОЖНО
высказывание:
НЕ(Первая буква гласная) или
A+B=0
(Последняя буква гласная) ?
(Первая буква гласная) и
(Последняя буква согласная)
Никита
Антон
Даниил
Инна
К.Ю. Поляков, Е.А. Ерёмин, 2018
A·B=1
Кирилл
Егор
Мефодий
Игнат
http://kpolyakov.spb.ru

13. Задачи

Математическая логика, 9 класс
13
Задачи
Для каких из приведённых имён ЛОЖНО
высказывание:
НЕ(Первая буква гласная) и
(Последняя буква гласная) ?
A·B=0
(Первая буква гласная) или
(Последняя буква согласная)
Никита
Антон
Даниил
Инна
К.Ю. Поляков, Е.А. Ерёмин, 2018
A+B=1
Кирилл
Егор
Мефодий
Игнат
http://kpolyakov.spb.ru

14. Задачи

Математическая логика, 9 класс
14
Задачи
Для каких значений числа X ЛОЖНО
высказывание:
(НЕ (X ≥ 3) и не (X = 8)) или (X ≤ 5) ?
ЛОЖНО ( (X < 3) и (X <> 8)) или (X ≤ 5)
И ИЛИ,
обратные условия
ИСТИННО ( (X ≥ 3) или (X = 8)) и (X > 5)
3
К.Ю. Поляков, Е.А. Ерёмин, 2018
5
6
7 8
9
6, 7, 8, …
http://kpolyakov.spb.ru

15. Задачи

Математическая логика, 9 класс
15
Задачи
Напишите наибольшее число x, для которого
истинно высказывание:
(x < 42) и не (в числе x нет одинаковых цифр)
(x < 42) и не (в числе x ЕСТЬ одинаковые цифры)
33
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

16. Задачи

Математическая логика, 9 класс
16
Задачи
Напишите наименьшее число x, для которого
ЛОЖНО высказывание:
(x < 42) или (x не делится на 14) A + B = 0
(x 42) и (x не делится на 14)
A·B=1
42
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

17.

Для какого из приведённых чисел ложно высказывание:
НЕ (число < 80) ИЛИ (число нечётное)?
1) 29
2) 52
3) 80
4) 91
1. Проверяем высказывание: число < 80.
2. Проверяем высказывание: НЕ < 80.
3. Проверяем высказывание: число нечётное.
4. Проверяем высказывание: ИЛИ.
5. Ложное высказывание для числа 52. Значит ответ 2.
29
< 80
1
НЕ < 80
0
нечётное
1
ИЛИ
52
1
0
0
1
0
80
0
1
0
1
91
0
1
1
1
Ответ: 2

18.

Для какого из приведённых чисел истинно высказывание:
НЕ (число чётное) И (число >25)?
1) 17
2) 25
3) 31
4) 42
1. Проверяем высказывание: число чётное.
2. Проверяем высказывание: НЕ чётное.
3. Проверяем высказывание: число > 25.
4. Проверяем высказывание: И.
5. Истинное высказывание для числа 31. Значит ответ 3.
17
чётное
0
НЕ чётное
1
число >25
0
И
25
0
1
0
0
0
31
0
1
1
1
42
1
0
1
0
Ответ: 3

19.

Для какого из приведённых чисел ложно высказывание:
НЕ (число <50) ИЛИ (число чётное)?
1) 48
2) 49
3) 50
4) 51
1. Проверяем высказывание: число <50.
2. Проверяем высказывание: число НЕ <50.
3. Проверяем высказывание: чётное.
4. Проверяем высказывание: ИЛИ.
5. Ложное высказывание для числа 49. Значит ответ 2.
48
число <50
1
НЕ <50
0
чётное
1
ИЛИ
49
1
0
0
1
0
50
0
1
1
1
51
0
1
0
1
Ответ: 2

20.

Для какого из приведённых чисел истинно высказывание:
НЕ (число >45) И (число нечётное)?
1) 44
2) 45
3) 46
4) 47
1. Проверяем высказывание: число > 45.
2. Проверяем высказывание: число НЕ > 45.
3. Проверяем высказывание: нечётное.
4. Проверяем высказывание: И.
5. Истинное высказывание для числа 45. Значит ответ 2.
44
число > 45
0
НЕ > 45
1
нечётное
0
И
45
0
1
1
0
1
46
1
0
0
0
47
1
0
1
0
Ответ: 2

21.

Для какого из приведённых названий птиц истинно высказывание:
НЕ ((первая буква гласная) ИЛИ (последняя буква согласная))?
1) Пингвин
2) Дрофа
3) Иволга
4) Ястреб
1. Проверяем высказывание: первая буква гласная.
2. Проверяем высказывание: последняя буква согласная.
3. Проверяем высказывание: ИЛИ.
4. Проверяем высказывание: НЕ.
5. Истинное высказывание для названия Дрофа. Значит ответ 2.
первая гласная
последняя согласная
ИЛИ
НЕ
Пингвин
0
1
1
0
Дрофа
0
0
0
1
Иволга
1
0
1
0
Ястреб
1
1
1
0
Ответ: 2

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

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

23. Что такое множество?

Математическая логика, 9 класс
23
Что такое множество?
Множество – некоторый набор элементов, каждый из
которых отличается от остальных.
пустое множество:
конечное число элементов: буквы русского алфавита
бесконечное число элементов: натуральные числа
Как задать множество?
• перечислением элементов
{Вася, Петя, Коля}
• логическим выражением:
{x: x > 0}
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

24. Изображение множеств

Математическая логика, 9 класс
24
Изображение множеств
Диаграммы Эйлера-Венна
A
пересечение
A
A
B
B
не A
A
AиB
A или B
A
A
B
A и (не B)
К.Ю. Поляков, Е.А. Ерёмин, 2018
объединение
B
(не A) или B
B
(не A) и (не B)
http://kpolyakov.spb.ru

25. Количество элементов множеств

Математическая логика, 9 класс
25
Количество элементов множеств
Поисковые запросы в Интернете:
& = и (and)
| = или (or)
NA – количество элементов множества A
? Что больше?
? NA & B
NA
NA
?
A
A
A &B
B
NA | B
B
A|B
! & всегда сужает область, | - расширяет!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

26. Задачи

Математическая логика, 9 класс
26
Задачи
В таблице приведены запросы к поисковому серверу.
Расположите номера запросов в порядке возрастания
количества страниц, которые найдет поисковый сервер
по каждому запросу.
А: принтеры & сканеры & продажа
Б: принтеры | продажа
В: принтеры & продажа
Г: принтеры | сканеры | продажа
АВБГ
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

27. Использование диаграмм

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

28. Задачи

Математическая логика, 9 класс
28
Задачи
В таблице приведены запросы к поисковому серверу.
Расположите номера запросов в порядке убывания
количества страниц, которые найдет поисковый сервер
по каждому запросу.
А: принтеры & сканеры & продажа
Б: (принтеры & сканеры) | продажа
В: (принтеры | сканеры) & продажа
Г: принтеры | сканеры | продажа
ГБВА
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

29. Количество элементов множеств

Математическая логика, 9 класс
29
Количество элементов множеств
Известно количество сайтов, которых находит
поисковый сервер по следующим запросам :
Запрос
огурцы
помидоры
огурцы & помидоры
Количество сайтов
N
A
100
200
50
NB
NA&B
Сколько сайтов будет найдено по запросу
огурцы | помидоры
NA|B
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

30. Количество элементов множеств

Математическая логика, 9 класс
30
Количество элементов множеств
В общем виде:
A
B
A|B
A
NA&B = 0?
NA | B = NA + NB
NA&B =
B
NA | B =
NA + NB =
+
NA | B = NA + NB – NA & B
К.Ю. Поляков, Е.А. Ерёмин, 2018
+
+
= NA | B +
Формула включений
и исключений
http://kpolyakov.spb.ru

31. Задачи с тремя областями

Математическая логика, 9 класс
31
Задачи с тремя областями
Известно количество сайтов, которых находит
поисковый сервер по следующим запросам:
Запрос
собаки & лемуры
кошки & лемуры
(кошки | собаки) & лемуры
Количество
сайтов
320
280
430
Сколько сайтов будет найдено по запросу
собаки & кошки & лемуры
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

32. Задача с тремя областями

Математическая логика, 9 класс
32
Задача с тремя областями
собаки
кошки
лемуры
A = собаки & лемуры
B = кошки & лемуры
A
B
NA&B = NA+ NB – NA|B
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

33. Задачи с тремя областями

Математическая логика, 9 класс
33
Задачи с тремя областями
Известно количество сайтов, которых находит
поисковый сервер по следующим запросам:
Запрос
A
собаки & лемуры
B
кошки & лемуры
A | B
(кошки | собаки) & лемуры
Количество
сайтов
320
280
430
A & B
Сколько сайтов будет найдено по запросу
собаки & кошки & лемуры
! Общее условие с & можно отбросить !
NA&B = NA+ NB – NA|B = 320 + 280 – 430 = 170
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

34. Задачи с тремя областями

Математическая логика, 9 класс
34
Задачи с тремя областями
Известно количество сайтов, которых находит
поисковый сервер по следующим запросам:
Запрос
Количество сайтов
сканер
принтер
монитор
принтер | сканер
принтер & монитор
сканер & монитор
200
250
450
450
40
50
Сколько сайтов будет найдено по запросу
(принтер | сканер) & монитор
! Обычно две области не пересекаются!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

35. Задачи с тремя областями

Математическая логика, 9 класс
35
Задачи с тремя областями
А (сканер) B (принтер) 450
принтер | сканер
0
NA|B = NA+ NB – NA&B
сканер
сканер
200
принтер
250
принтер
50
40
принтер & монитор = 40
сканер & монитор = 50
монитор
(принтер | сканер) & монитор
К.Ю. Поляков, Е.А. Ерёмин, 2018
40 + 50 = 90
http://kpolyakov.spb.ru

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

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

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

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