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

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

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

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

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

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

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

4. Операция И

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

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

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

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
К.Ю. Поляков, Е.А. Ерёмин, 2013
B
0
1
0
1
А B
1
0
0
1
http://kpolyakov.spb.ru

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

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

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

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

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

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

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

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

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

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

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

Логические основы компьютеров, 10 класс
16
Задачи (таблица истинности)
Символом 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
К.Ю. Поляков, Е.А. Ерёмин, 2013
X
1
0
1
Y
0
0
1
Z
0
0
1
F
1
1
0
http://kpolyakov.spb.ru