Содержание

Слайд 2

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

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

Математическая логика § 5. Логика и компьютер

Слайд 3

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

Логика (др.греч. λογικος) – это наука о том, как правильно рассуждать,

Логика, высказывания Логика (др.греч. λογικος) – это наука о том, как правильно
делать выводы, доказывать утверждения.

Формальная логика отвлекается от конкретного содержания, изучает только истинность и ложность высказываний.

Логическое высказывание – это повествовательное предложение, относительно которого можно однозначно сказать, истинно оно или ложно.

Слайд 4

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

Сейчас идет дождь.
Жирафы летят на север.
История – интересный предмет.
У квадрата

Высказывание или нет? Сейчас идет дождь. Жирафы летят на север. История –
– 10 сторон и все разные.
Красиво!
В городе N живут 2 миллиона человек.
Который час?

Слайд 5

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

Логика изучает операции между 0 и 1!

Джордж Буль

Алгебра логики —

Логика и компьютер Логика изучает операции между 0 и 1! Джордж Буль
это математический аппарат, с помощью которого записывают, упрощают и преобразуют логические высказывания, вычисляют их значения.

Алгебра высказываний,
булева алгебра

двоичная логика

Слайд 6

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

A – Сейчас идет дождь.
B – Форточка открыта.

простые высказывания

Простые и составные высказывания A – Сейчас идет дождь. B – Форточка
(элементарные)

Составные высказывания строятся из простых с помощью логических связок (операций) «и», «или», «не», «если … то», «тогда и только тогда» и др.

A и B
A или не B
если A, то B
A тогда и только
тогда, когда B

Сейчас идет дождь и открыта форточка.
Сейчас идет дождь или форточка закрыта.
Если сейчас идет дождь, то форточка открыта.
Дождь идет тогда и только тогда, когда открыта форточка.

Слайд 7

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

Если высказывание A истинно, то «не А» ложно, и наоборот.

1

0

0

1

таблица

Операция НЕ (инверсия) Если высказывание A истинно, то «не А» ложно, и
истинности операции НЕ

Таблица истинности логического выражения Х – это таблица, где в левой части записываются все возможные комбинации значений исходных данных, а в правой – значение выражения Х для каждой комбинации.

Слайд 8

Разные операции с одной переменной

1

0

0

1

1

0

А

0

0

1

1

22 = 4

Разные операции с одной переменной 1 0 0 1 1 0 А

Слайд 9

Операция И

Высказывание «A и B» истинно тогда и только тогда, когда А

Операция И Высказывание «A и B» истинно тогда и только тогда, когда
и B истинны одновременно.

A и B

A

B

Слайд 10

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

1

0

также A·B, A and B

0

0

конъюнкция – от лат.

Операция И (логическое умножение, конъюнкция) 1 0 также A·B, A and B
conjunctio — соединение

A и B = min(A, B)

Слайд 11

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

Высказывание «A или B» истинно тогда, когда истинно

Операция ИЛИ (логическое сложение, дизъюнкция) Высказывание «A или B» истинно тогда, когда
А или B, или оба вместе.

A или B

A

B

Слайд 12

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

1

0

также: A+B, A or B

1

1

дизъюнкция – от лат.

Операция ИЛИ (логическое сложение, дизъюнкция) 1 0 также: A+B, A or B
disjunctio — разъединение

A или B = max(A, B)

Слайд 13

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

A и 0 = A ∙ 0 =
A и 1

Упрощение логических выражений A и 0 = A ∙ 0 = A
= A ∙ 1 =

A

0

A или 0 = A + 0 =
A или 1 = A + 1 =

1

A

A и не A = A ∙ A =
A или (не A) = A + A =

0

1

Слайд 14

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

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

Математическая логика § 6. Логические элементы

Слайд 15

Элемент «НЕ»

значок инверсии

?

?

не A

не A

Элемент «НЕ» значок инверсии ? ? не A не A

Слайд 16

Элементы «И» и «ИЛИ»

A и B

A или B

Двойные элементы:

«ИЛИ-НЕ»

«И-НЕ»

не (A и B)

не

Элементы «И» и «ИЛИ» A и B A или B Двойные элементы:
(A или B)

«И»

«ИЛИ»

Слайд 17

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

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

Слайд 18

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

§ 7. Другие логические операции

Математическая логика § 7. Другие логические операции

Слайд 19

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

?

?

?

?

0 или 1

24 = 16

Операции с двумя переменными ? ? ? ? 0 или 1 24 = 16

Слайд 20

Импликация

X = Если идёт дождь, то Лена раскрывает зонтик.

X = A →

Импликация X = Если идёт дождь, то Лена раскрывает зонтик. X =
B

Импликация A → B истинна, если не исключено, что из A следует B.

1

1

0

1

Идёт дождь, но Лена не раскрыла зонтик.

Слайд 21

Постройте таблицы истинности

B → A ≠ A → B

X = B →

Постройте таблицы истинности B → A ≠ A → B X = B → A
A

Слайд 22

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

Высказывание «A ↔ B» истинно тогда и только тогда, когда А и

Эквиваленция Высказывание «A ↔ B» истинно тогда и только тогда, когда А и B равны.
B равны.

Слайд 23

Постройте таблицы истинности

Постройте таблицы истинности

Слайд 24

Исключающее «ИЛИ»

Высказывание «A ⊕ B» истинно тогда, когда истинно А или B,

Исключающее «ИЛИ» Высказывание «A ⊕ B» истинно тогда, когда истинно А или
но не оба одновременно (A ≠ B).
«Либо пан, либо пропал».

0

0

1

1

сложение по модулю 2: А ⊕ B = (A + B) mod 2

арифметическое сложение, 1+1=2

остаток

Слайд 25

Постройте таблицы истинности

Постройте таблицы истинности

Слайд 26

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

A ⊕ 0 =
A ⊕ 1 =
A ⊕ A =
(A

Упрощение логических выражений A ⊕ 0 = A ⊕ 1 = A
⊕ B) ⊕ B =

A

0

A

операция обратима

Слайд 27

Шифрование

(A ⊕ B) ⊕ B = A

данные

шифровка

дешифровка

A = 1 0 0

Шифрование (A ⊕ B) ⊕ B = A данные шифровка дешифровка A
1

B = 0 1 0 1

(A ⊕ B) = 1 1 0 0

B = 0 1 0 1

1 0 0 1

= A

Слайд 28

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

§ 8. Логические выражения

Математическая логика § 8. Логические выражения

Слайд 29

Логические выражения

Логическое выражение — это выражение, результат вычисления которого — логическое значение

Логические выражения Логическое выражение — это выражение, результат вычисления которого — логическое
(истина или ложь).

Авария = вышли из строя 2 из 3-х двигателей.
A – «Двигатель № 1 неисправен».
B – «Двигатель № 2 неисправен».
C – «Двигатель № 3 неисправен».
Аварийный сигнал:
X = «Неисправны два двигателя»

= (A и B) или (A и C) или (B и C)

логическое выражение

Слайд 30

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

скобки
НЕ
И
ИЛИ
импликация
эквиваленция

1

2

3

4

5

6

, исключающее ИЛИ

Порядок вычисления скобки НЕ И ИЛИ импликация эквиваленция 1 2 3 4

Слайд 31

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

Логические выражения могут быть:
вычислимыми (зависят от исходных данных)
тождественно истинными (всегда 1,

Таблицы истинности Логические выражения могут быть: вычислимыми (зависят от исходных данных) тождественно
тавтология)
тождественно ложными (всегда 0, противоречие)

Слайд 32

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

Если два выражения принимают одинаковые значения при всех значениях переменных, они

Таблицы истинности Если два выражения принимают одинаковые значения при всех значениях переменных,
называются равносильными (определяют одну и ту же логическую функцию).

Слайд 33

Неполные таблицы истинности

23 = 8

один ноль в таблице

по 1-й строке

по 2-й строке

25

Неполные таблицы истинности 23 = 8 один ноль в таблице по 1-й
= 32

Слайд 34

Сколько нулей и единиц?

в таблице истинности функции от 3-х переменных:

1

7

7

1

7

1

1

7

5

3

Сколько нулей и единиц? в таблице истинности функции от 3-х переменных: 1

Слайд 35

Неполные таблицы истинности

один ноль, две единицы

по 1-й строке

по 2-й строке

только 1 единица,
все

Неполные таблицы истинности один ноль, две единицы по 1-й строке по 2-й
строки разные!

Слайд 36

Составление условий

(x ≥ 3) и (x ≤ 6)

(3 ≤ x) и (x

Составление условий (x ≥ 3) и (x ≤ 6) (3 ≤ x)
≤ 6)

(1 ≤ x) и (x ≤ 3) или (5 ≤ x) и (x ≤ 8)

Слайд 37

Составление условий

левая граница:

x ≥ – 1

нижняя граница:

y ≥ – 1

верхняя граница:

y ≤

Составление условий левая граница: x ≥ – 1 нижняя граница: y ≥
– x

(x ≥ – 1)

и (y ≥ – 1)

и (y ≤ – x)

Слайд 38

Составление условий

(x2+y2 ≤ 1)

и (x ≤ 0)

левая

правая

(x ≥ 0)

и (x2+y2 ≤ 1)

левая

нижняя

и

Составление условий (x2+y2 ≤ 1) и (x ≤ 0) левая правая (x
(y ≤ – x)

верхняя

Слайд 39

Составление условий

=

+

((x2+y2 ≤ 1) и (x ≤ 0))

или

((x2+y2 ≤ 1) и (x

Составление условий = + ((x2+y2 ≤ 1) и (x ≤ 0)) или
≥ 0) и (y ≤ – x))

Слайд 40

Определение истинности выражений

Для каких из указанных значений числа X истинно высказывание:
(X

Определение истинности выражений Для каких из указанных значений числа X истинно высказывание:
< 5) и не (X < 1) ?

X = 2:

( 1 ) и не ( 0 )

X = 4:

( 1 ) и не ( 0 )

X = 8:

( 0 ) и не ( 0 )

( 0 и 1)

= 0

( 1 и 1 )

= 1

( 1 и 1 )

= 1

можно не вычислять!

Слайд 41

Табличный метод

Для каких из указанных значений числа X истинно высказывание:
R =

Табличный метод Для каких из указанных значений числа X истинно высказывание: R = (X
(X < 5) и не (X < 1) ?

Слайд 42

Задачи

Для каких из указанных значений числа X ЛОЖНО высказывание:
(не (X ≥ 3)

Задачи Для каких из указанных значений числа X ЛОЖНО высказывание: (не (X
и не (X = 8)) или (X ≤ 5) ?

X = 4:

(не (1) и не (0)) или (1)

= 1

X = 1:

(не (0) и не (0)) или (1)

= 1

X = 8:

(не (1) и не (1)) или (0)

( 0 и 0 ) или (0)

= 0

? + 1

Слайд 43

Задачи

Для каких значений числа X истинно высказывание:
(X < 5) и не (X

Задачи Для каких значений числа X истинно высказывание: (X (X = 1) 1, 2, 3, 4
< 1) ?

(X < 5) и (X >= 1)

1, 2, 3, 4

Слайд 44

Задачи

Для каких из приведённых имён ЛОЖНО высказывание:
НЕ(Первая буква гласная) или
(Последняя буква

Задачи Для каких из приведённых имён ЛОЖНО высказывание: НЕ(Первая буква гласная) или
гласная) ?

(Первая буква согласная)

Слайд 45

Задачи (ЛОЖНО → ИСТИННО)

ЛОЖНО A или B

ЛОЖНО A или B

ИСТИННО не A

Задачи (ЛОЖНО → ИСТИННО) ЛОЖНО A или B ЛОЖНО A или B
и не B

?

A + B = 0

Слайд 46

Задачи (ЛОЖНО → ИСТИННО)

ЛОЖНО A и B

ЛОЖНО A и B

ИСТИННО не A

Задачи (ЛОЖНО → ИСТИННО) ЛОЖНО A и B ЛОЖНО A и B
или не B

?

A ⋅ B = 0

Слайд 47

Задачи (ЛОЖНО → ИСТИННО)

Задачи (ЛОЖНО → ИСТИННО)

Слайд 48

Задачи

Для каких из приведённых имён ЛОЖНО высказывание:
НЕ(Первая буква гласная) или
(Последняя буква

Задачи Для каких из приведённых имён ЛОЖНО высказывание: НЕ(Первая буква гласная) или
гласная) ?

(Первая буква гласная) и
(Последняя буква согласная)

Никита
Антон
Даниил
Инна

Кирилл
Егор
Мефодий
Игнат

A + B = 0

Слайд 49

Задачи

Для каких из приведённых имён ЛОЖНО высказывание:
НЕ(Первая буква гласная) и
(Последняя буква

Задачи Для каких из приведённых имён ЛОЖНО высказывание: НЕ(Первая буква гласная) и
гласная) ?

(Первая буква гласная) или
(Последняя буква согласная)

Никита
Антон
Даниил
Инна

Кирилл
Егор
Мефодий
Игнат

A · B = 0

Слайд 50

Задачи

Для каких значений числа X ЛОЖНО высказывание:
(НЕ (X ≥ 3) и не

Задачи Для каких значений числа X ЛОЖНО высказывание: (НЕ (X ≥ 3)
(X = 8)) или (X ≤ 5) ?

ЛОЖНО ( (X < 3) и (X <> 8)) или (X ≤ 5)

6, 7, 8, …

ИСТИННО ( (X ≥ 3) или (X = 8)) и (X > 5)

И ↔ ИЛИ,
обратные условия

Слайд 51

Задачи

Напишите наибольшее число x, для которого истинно высказывание:
(x < 42) и не

Задачи Напишите наибольшее число x, для которого истинно высказывание: (x (x 33
(в числе x нет одинаковых цифр)

(x < 42) и не (в числе x ЕСТЬ одинаковые цифры)

33

Слайд 52

Задачи

Напишите наименьшее число x, для которого ЛОЖНО высказывание: (x < 42) или

Задачи Напишите наименьшее число x, для которого ЛОЖНО высказывание: (x (x ≥
(x не делится на 14)

(x ≥ 42) и (x не делится на 14)

42

Слайд 53

Логические схемы

Логические схемы

Слайд 54

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

§ 12. Множества и логика

Математическая логика § 12. Множества и логика

Слайд 55

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

Множество – некоторый набор элементов, каждый из которых отличается от

Что такое множество? Множество – некоторый набор элементов, каждый из которых отличается
остальных.

пустое множество: ∅
конечное число элементов: буквы русского алфавита
бесконечное число элементов: натуральные числа

Как задать множество?
перечислением элементов
{Вася, Петя, Коля}
логическим выражением:
{x: x > 0}

Слайд 56

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

Диаграммы Эйлера-Венна

A и B

A или B

(не A) или B

пересечение

объединение

A и (не

Изображение множеств Диаграммы Эйлера-Венна A и B A или B (не A)
B)

не A

(не A) и (не B)

Слайд 57

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

Поисковые запросы в Интернете:
& = и (and) | =

Количество элементов множеств Поисковые запросы в Интернете: & = и (and) |
или (or)

NA – количество элементов множества A

NA NA & B


?

NA NA | B


?

Слайд 58

Задачи

В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке

Задачи В таблице приведены запросы к поисковому серверу. Расположите номера запросов в
возрастания количества страниц, которые найдет поисковый сервер по каждому запросу.
А: принтеры & сканеры & продажа
Б: принтеры | продажа
В: принтеры & продажа
Г: принтеры | сканеры | продажа

АВБГ

Слайд 59

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

принтеры

сканеры

продажа

принтеры & сканеры & продажа

Использование диаграмм принтеры сканеры продажа принтеры & сканеры & продажа

Слайд 60

Задачи

В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке

Задачи В таблице приведены запросы к поисковому серверу. Расположите номера запросов в
убывания количества страниц, которые найдет поисковый сервер по каждому запросу.
А: принтеры & сканеры & продажа
Б: (принтеры & сканеры) | продажа
В: (принтеры | сканеры) & продажа
Г: принтеры | сканеры | продажа

ГБВА

Слайд 61

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

Известно количество сайтов, которых находит поисковый сервер по следующим запросам

Количество элементов множеств Известно количество сайтов, которых находит поисковый сервер по следующим
:
Сколько сайтов будет найдено по запросу
огурцы | помидоры

NA

NB

NA&B

NA|B

Слайд 62

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

A

B

В общем виде:

NA&B = ?

0

NA | B = NA +

Количество элементов множеств A B В общем виде: NA&B = ? 0
NB

A

B

NA | B = + +

NA + NB =

NA&B =

NA | B = NA + NB – NA & B

Формула включений
и исключений

+ = NA | B +

A | B

Слайд 63

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

Известно количество сайтов, которых находит поисковый сервер по следующим

Задачи с тремя областями Известно количество сайтов, которых находит поисковый сервер по
запросам:
Сколько сайтов будет найдено по запросу
собаки & кошки & лемуры

Слайд 64

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

собаки

кошки

лемуры

B = кошки & лемуры

A

B

NA&B = NA+ NB –

Задача с тремя областями собаки кошки лемуры B = кошки & лемуры
NA|B

A = собаки & лемуры

Слайд 65

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

Известно количество сайтов, которых находит поисковый сервер по следующим

Задачи с тремя областями Известно количество сайтов, которых находит поисковый сервер по
запросам:
Сколько сайтов будет найдено по запросу
собаки & кошки & лемуры

A

B

A | B

A & B

Слайд 66

Известно количество сайтов, которых находит поисковый сервер по следующим запросам:
Сколько сайтов будет

Известно количество сайтов, которых находит поисковый сервер по следующим запросам: Сколько сайтов
найдено по запросу
(принтер | сканер) & монитор

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

Слайд 67

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

А (сканер)

B (принтер)

NA|B = NA+ NB – NA&B

принтер |

Задачи с тремя областями А (сканер) B (принтер) NA|B = NA+ NB
сканер

450

сканер

принтер

200

250

0

сканер

принтер

монитор

90

40 + 50 =

принтер & монитор = 40

сканер & монитор = 50

50

40

(принтер | сканер) & монитор

Слайд 68

Конец фильма

ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики
ГБОУ СОШ № 163, г. Санкт-Петербург
[email protected]
ЕРЕМИН

Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики ГБОУ СОШ № 163,
Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО ПГГПУ, г. Пермь
[email protected]
Имя файла: slides9-2.pptx
Количество просмотров: 30
Количество скачиваний: 0