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

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

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

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

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

3. Обозначение высказываний

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

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

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

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

Логические основы компьютеров, 10 класс
5
Операция И (логическое умножение, конъюнкция)
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

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

Логические основы компьютеров, 10 класс
6
Операция ИЛИ (логическое сложение, дизъюнкция)
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

7. Задачи

Логические основы компьютеров, 10 класс
7
Задачи
В таблице приведены запросы к поисковому серверу.
Расположите номера запросов в порядке возрастания
количества страниц, которые найдет поисковый
сервер по каждому запросу. Для обозначения логической
операции «ИЛИ» в запросе используется символ |, а для
логической операции «И» – &.
1) принтеры & сканеры & продажа
2) принтеры & продажа
3) принтеры | продажа
4) принтеры | сканеры | продажа
1234
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

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

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

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

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

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

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

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

12.

Импликацию можно выразить через
дизъюнкцию и отрицание:
A B A B

13.

Эквиваленцию можно выразить
через отрицание, дизъюнкцию и
конъюнкцию:
A B ( A B) & ( B A)

14. Формализация

Логические основы компьютеров, 10 класс
14
Формализация
Прибор имеет три датчика и может работать, если два из
них исправны. Записать в виде формулы ситуацию
«авария».
A – «Датчик № 1 неисправен».
B – «Датчик № 2 неисправен».
Формализация – это
переход к записи на
C – «Датчик № 3 неисправен».
формальном языке!
Аварийный сигнал:
X – «Неисправны два датчика».
X – «Неисправны датчики № 1 и № 2» или
«Неисправны датчики № 1 и № 3» или
«Неисправны датчики № 2 и № 3».
логическая
формула
X A B A C B C
!
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

15. Вычисление логических выражений

Логические основы компьютеров, 10 класс
15
Вычисление логических выражений
1
4
2
5
3
X A B A C B C
+
Порядок вычислений:
•скобки
•НЕ
•И
•ИЛИ, исключающее ИЛИ
•импликация
•эквивалентность
A
К.Ю. Поляков, Е.А. Ерёмин, 2013
+
B
A
B
C
С
http://kpolyakov.spb.ru

16. Порядок выполнения логических операций

1. Действия в скобках.
2. Инверсия, конъюнкция,
дизъюнкция, импликация,
эквивалентность,
сложение по модулю 2.

17. Построение таблиц истинности для логических функций

Алгоритм построения таблицы истинности:
1. Определить количество наборов входных
переменных - всевозможных сочетаний значений
переменных, входящих в выражения, по формуле:
Q=2n , где n - количество входных переменных.
Оно определяет количество строк таблицы.
2. Внести в таблицу все наборы входных
переменных.
3. Определить количество логических операций и
последовательность их выполнения.
4. Заполнить столбцы результатами выполнения
логических операций в обозначенной
последовательности.

18. Размеры таблицы

n
1. Количество строк = 2 ,
где n – количество логических
переменных.
2. Количество столбцов =
количество переменных +
количество логических операций.

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

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

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

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

21. Задание: составить таблицы истинности

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

22. Задание: составить таблицы истинности

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

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

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

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

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

25. Диаграмма с тремя переменными

Логические основы компьютеров, 10 класс
25
Диаграмма с тремя переменными
Хочу
Могу
3
2
5
1
6
4
7
8
1 M X H
5 M X H
2 M X H
6 M X H
3 M X H
7 M X H
4 M X H
8 M X H
Надо
3 4 M X H M X H
!
3 4 X H
Логические выражения можно упрощать!
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

26. Задачи

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

27. Задачи

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

28. Задачи

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

29. Задачи

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

30. Задачи

Логические основы компьютеров, 10 класс
31
Законы алгебры логики
название
для И
для ИЛИ
A A
двойного отрицания
A A 0
A A 1
операции с
константами
A 0 0, A 1 A
A 0 A, A 1 1
повторения
A A A
A A A
исключения третьего
поглощения
переместительный
A ( A B) A
A A B A
A B B A
A B B A
сочетательный
A (B C) ( A B) C A (B C) ( A B) C
распределительный
A B C ( A B) ( A C)
A (B C) A B A C
законы де Моргана
A B A B
A B A B
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

31. Законы алгебры логики

Логические основы компьютеров, 10 класс
32
Упрощение логических выражений
Шаг 1. Заменить операции на их выражения
через И, ИЛИ и НЕ:
A B A B A B
A B A B
A B A B A B
Шаг 2. Раскрыть инверсию сложных выражений по
формулам де Моргана:
A B A B,
A B A B
Шаг 3. Используя законы логики, упрощать выражение,
стараясь применять закон исключения третьего.
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

Логические основы компьютеров, 10 класс
33
Упрощение логических выражений
Q M X H M X H (M M ) X H X H
X (B A) (A B) (A C)
( B A) (A B) (A C)
формула де Моргана
( B A) A B (A C)
( B A A A ) B (A C)
B A B (A C)
B A (A C)
B A
К.Ю. Поляков, Е.А. Ерёмин, 2013
раскрыли
распределительный
исключения третьего
повторения
поглощения
http://kpolyakov.spb.ru

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

Логические основы компьютеров, 10 класс
34
Задачи (упрощение)
Какое логическое выражение равносильно выражению
A ¬(¬B C)?
1) ¬A ¬B ¬C
1)A B C
2) A ¬B ¬C
2) A B C
3) A B ¬C
3) A B C
4) A ¬B C
4) A B C
A ( B C) A B C A B C
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru