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

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

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

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

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

Простые и составные высказывания
A – Сейчас идет дождь.
B – Форточка открыта.
простые высказывания (элементарные)
Составные высказывания строятся из простых с помощью логических связок (операций) «и», «или», «не», «если … то», «тогда и только тогда» и др.
A и B
A или не B
если A, то B
A тогда и только
тогда, когда B
Сейчас идет дождь и открыта форточка.
Сейчас идет дождь или форточка закрыта.
Если сейчас идет дождь, то форточка открыта.
Дождь идет тогда и только тогда, когда открыта форточка.

Операция НЕ (инверсия)
Если высказывание A истинно, то «не А» ложно, и наоборот.
1
0
0
1
таблица истинности операции НЕ
Таблица истинности логического выражения Х – это таблица, где в левой части записываются все возможные комбинации значений исходных данных, а в правой – значение выражения Х для каждой комбинации.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Исключающее «ИЛИ»
Высказывание «A ⊕ B» истинно тогда, когда истинно А или B, но не оба одновременно (A ≠ B).
«Либо пан, либо пропал».
0
0
1
1
сложение по модулю 2: А ⊕ B = (A + B) mod 2
арифметическое сложение, 1+1=2
остаток

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

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

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

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

Логические выражения
Логическое выражение — это выражение, результат вычисления которого — логическое значение (истина или ложь).
Авария = вышли из строя 2 из 3-х двигателей.
A – «Двигатель № 1 неисправен».
B – «Двигатель № 2 неисправен».
C – «Двигатель № 3 неисправен».
Аварийный сигнал:
X = «Неисправны два двигателя»
= (A и B) или (A и C) или (B и C)
логическое выражение

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

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

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

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

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

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

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

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

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

Составление условий
=
+
((x2+y2 ≤ 1) и (x ≤ 0))
или
((x2+y2 ≤ 1) и (x ≥ 0) и (y ≤ – 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
можно не вычислять!

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

Задачи
Для каких из указанных значений числа X ЛОЖНО высказывание:
(не (X ≥ 3) и не (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

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

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

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

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

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

Задачи
Для каких из приведённых имён ЛОЖНО высказывание:
НЕ(Первая буква гласная) или
(Последняя буква гласная) ?
(Первая буква гласная) и
(Последняя буква согласная)
Никита
Антон
Даниил
Инна
Кирилл
Егор
Мефодий
Игнат
A + B = 0

Задачи
Для каких из приведённых имён ЛОЖНО высказывание:
НЕ(Первая буква гласная) и
(Последняя буква гласная) ?
(Первая буква гласная) или
(Последняя буква согласная)
Никита
Антон
Даниил
Инна
Кирилл
Егор
Мефодий
Игнат
A · B = 0

Задачи
Для каких значений числа X ЛОЖНО высказывание:
(НЕ (X ≥ 3) и не (X = 8)) или (X ≤ 5) ?
ЛОЖНО ( (X < 3) и (X <> 8)) или (X ≤ 5)
6, 7, 8, …
ИСТИННО ( (X ≥ 3) или (X = 8)) и (X > 5)
И ↔ ИЛИ,
обратные условия

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

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

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

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

Что такое множество?
Множество – некоторый набор элементов, каждый из которых отличается от остальных.
пустое множество: ∅
конечное число элементов: буквы русского алфавита
бесконечное число элементов: натуральные числа
Как задать множество?
перечислением элементов
{Вася, Петя, Коля}
логическим выражением:
{x: x > 0}

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

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

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

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

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

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

Количество элементов множеств
A
B
В общем виде:
NA&B = ?
0
NA | B = NA + NB
A
B
NA | B = + +
NA + NB =
NA&B =
NA | B = NA + NB – NA & B
Формула включений
и исключений
+ = NA | B +
A | B

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

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

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

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

Задачи с тремя областями
А (сканер)
B (принтер)
NA|B = NA+ NB – NA&B
принтер | сканер
450
сканер
принтер
200
250
0
сканер
принтер
монитор
90
40 + 50 =
принтер & монитор = 40
сканер & монитор = 50
50
40
(принтер | сканер) & монитор

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