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

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

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

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

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

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

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

7. Операция И

Логические основы компьютеров, 10 класс
7
Операция И
Высказывание «A и B» истинно тогда и только тогда,
когда А и B истинны одновременно.
AиB
A
B
220 В
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

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

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

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

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

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

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

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

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

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

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

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

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

Логические основы компьютеров, 10 класс
14
Эквивалентность («тогда и только тогда, …»)
Высказывание «A B» истинно тогда и только
тогда, когда А и B равны.
A
0
0
1
1
К.Ю. Поляков, Е.А. Ерёмин, 2013
B
0
1
0
1
А B
1
0
0
1
http://kpolyakov.spb.ru

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

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

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

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

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

Логические основы компьютеров, 10 класс
17
Задание 1 Составление таблиц истинности
X A B A C B C
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

18. Задание 2. Какие из приведенных слов удовлетворяют логическому условию:

Логические основы компьютеров, 10 класс
18
Задание 2. Какие из приведенных слов
удовлетворяют логическому условию:
(первая буква согласная→вторая буква согласная)
& (последняя буква гласная → предпоследняя
буква гласная)?
1) Тренаж
2) Мафия
3) Озон
4) Игра
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

19. Задание 3 Построить таблицу истинности

Логические основы компьютеров, 10 класс
19
Задание 3 Построить таблицу истинности
a ∧ ¬b ∨ (a ∨ b) ∧ c
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

20. Задание 4 Построить таблицу истинности

Логические основы компьютеров, 10 класс
20
Задание 4 Построить таблицу истинности
((a ∧ b) ≡ ¬c) ∧ (b → d).
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru