Логические основы компьютеров (Тема 3)

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

Учебник
1
Поляков К.Ю., Еремин Е.А. Информатика
углубленный уровень Часть 1
§ 18. Логика и компьютер
§ 19. Логические операции
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

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

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

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

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

Логические основы компьютеров, 10 класс
Логика и компьютер
Двоичное кодирование – все виды информации
кодируются с помощью 0 и 1.
Задача – разработать оптимальные правила
обработки таких данных.
Почему «логика»?
Результат выполнения операции можно
представить как истинность (1) или ложность (0)
некоторого высказывания.
Джордж Буль разработал основы алгебры,
в которой используются только 0 и 1
(алгебра логики, булева алгебра).
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru
4

5. Обозначение логических высказываний

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

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

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

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

Логические основы компьютеров, 10 класс
Операция И (логическое умножение, конъюнкция)
конъюнкция – от лат. conjunctio — соединение
A
B
АиB
0
0
1
1
0
1
0
1
0
0
0
1
также: A·B, A B,
A and B (Паскаль),
A && B (Си)
B
A
A B
A B
К.Ю. Поляков, Е.А. Ерёмин, 2013
220 В
http://kpolyakov.spb.ru
7

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

Логические основы компьютеров, 10 класс
Операция ИЛИ (логическое сложение, дизъюнкция)
дизъюнкция – от лат. disjunctio — разъединение
A
B
0
0
1
1
0
1
0
1
А или B
0
1
1
1
также: A+B, A B,
A or B (Паскаль),
A || B (Си)
B
A
A B
A
B
220 В
К.Ю. Поляков, Е.А. Ерёмин, 2013
A или B
http://kpolyakov.spb.ru
8

9. Задачи

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

10. Операция «исключающее ИЛИ»

Логические основы компьютеров, 10 класс
10
Операция «исключающее ИЛИ»
Высказывание «A B» истинно тогда, когда истинно А
или B, но не оба одновременно (то есть A B).
A
0
0
1
1
B
0
1
0
1
А B
0
1
1
0
К.Ю. Поляков, Е.А. Ерёмин, 2013
также:
A xor B (Паскаль),
A ^ B (Си)
A B A B A B
http://kpolyakov.spb.ru

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

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

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

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

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

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

14. Штрих Шеффера, «И-НЕ»

Логические основы компьютеров, 10 класс
Штрих Шеффера, «И-НЕ»
A B A B
Стрелка Пирса, «ИЛИ-НЕ»
A
0
0
1
1
B А↓B
0
1
1
0
0
0
1
0
К.Ю. Поляков, Е.А. Ерёмин, 2013
14
A
0
0
1
1
B
0
1
0
1
А|B
1
1
1
0
A B A B
http://kpolyakov.spb.ru

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

Логические основы компьютеров, 10 класс
Формализация
Задача.
!
15
Формализация – это переход к
записи на формальном языке!
Прибор имеет три датчика и может работать, если два из них
исправны. Записать в виде формулы ситуацию «авария».
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

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

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

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

Логические основы компьютеров, 10 класс
17
Составление таблиц истинности
X A B A B B
0
1
2
3
Кол-во высказываний – 2 ( А и В)
Кол-во сочетаний
– 22=4
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

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

Логические основы компьютеров, 10 класс
18
Составление таблиц истинности
X A B A C B C
0
1
2
3
4
5
6
7
Кол-во высказываний – 3 ( А, В, С)
Кол-во сочетаний
– 23=8
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

19. Задачи (таблица истинности)

Логические основы компьютеров, 10 класс
19
Задачи (таблица истинности)
Символом F обозначено одно из указанных ниже
логических выражений от трех аргументов: X, Y, Z. Дан
фрагмент таблицы истинности выражения F. Какое
выражение соответствует F?
1) ¬X ¬Y ¬Z
1) X Y Z
2) X Y Z
2) X Y Z
3) X Y Z
3) X Y Z
4) ¬X ¬Y ¬Z
4) X Y Z
X
1
0
1
Y
0
0
1
Z
0
0
1
F
1
1
0
К.Ю. Поляков, Е.А. Ерёмин, 2013
X Y Z X Y Z X Y Z X Y Z
0
1
0
0
0
1
1
0
1
1
1
0
http://kpolyakov.spb.ru

20. Практическая работа №11 Логические операции

Логические основы компьютеров, 10 класс
Практическая работа №11 Логические операции
20
1. Составить обобщенную таблицу истинности для
всех изученных логических операций ( кроме НЕ)
А
В
А+В
0
0
1
1
А·В A B
A B A
A B
B
A B
A B A B A B
0
1
0
1
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

21. Домашнее задание

Логические основы компьютеров, 10 класс
21
Домашнее задание
2. Используя образцы слайдов 16 -18 и построить
дерево и таблицу истинности логического выражения
3. Самостоятельно разобрать решение задачи.
Записать в тетрадь ее условие и краткое решение.
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru