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

1.

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

2.

Логические основы компьютеров, 10 класс
2
Вспомним известное…
Логическое высказывание – это
повествовательное предложение, относительно
которого можно однозначно сказать, истинно оно
(1) или ложно (0).
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

3.

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

4.

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

5.

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

6.

Логические основы компьютеров, 10 класс
6
Операция И (логическое умножение, конъюнкция)
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 — соединение
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

7.

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

8.

Логические основы компьютеров, 10 класс
8
Операция ИЛИ (логическое сложение, дизъюнкция)
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 — разъединение
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

9.

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

10.

Логические основы компьютеров, 10 класс
10
Свойства операции «исключающее ИЛИ»
A A= 0
(A B) B = ?
A 0= A
A 1= A
A B A B A B
A
0
0
1
1
B
0
1
0
1
A B
A B A B A B А B
0
0
1
0
0
1
0
0
К.Ю. Поляков, Е.А. Ерёмин, 2018
0
1
1
0
0
1
1
0
http://kpolyakov.spb.ru

11.

Логические основы компьютеров, 10 класс
11
Импликация («если …, то …»)
Высказывание «A B» истинно, если не
исключено, что из А следует B.
A – «Работник хорошо работает».
B – «У работника хорошая зарплата».
A
0
0
1
1
B
0
1
0
1
К.Ю. Поляков, Е.А. Ерёмин, 2018
А 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
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

13.

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

14.

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

15.

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

16.

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

17.

Логические основы компьютеров, 10 класс
17
Составление таблиц истинности
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
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

18.

Логические основы компьютеров, 10 класс
18
Задачи
Задача 1. При каких значениях логических переменных
истинно выражение:
X1 X 2 X 3 X 4 X 5
Решение. Все сомножители равны 1:
X 1 X 4 1,
X2 X3 X5 0
Задача 2. При каких значениях логических переменных
ложно выражение:
X1 X 2 X 3 X 4 X 5
Решение. Все слагаемые равны 0:
X 1 X 3 X 5 0,
К.Ю. Поляков, Е.А. Ерёмин, 2018
X2 X4 1
http://kpolyakov.spb.ru

19.

Логические основы компьютеров, 10 класс
19
Задачи
Задача 3. Запишите любое логические выражение,
соответствующее таблице истинности:
в полной
X Y Z F
23 = 8 строк
Полная таблица?
?
1 0 0 1
0 0 0 0
1 1 1 0
К.Ю. Поляков, Е.А. Ерёмин, 2018
истинно при X = 1, Y = Z = 0
X Y Z 1
F X Y Z
http://kpolyakov.spb.ru

20.

Логические основы компьютеров, 10 класс
20
Задачи
Задача 4. Запишите любое логические выражение,
соответствующее таблице истинности:
X
1
0
1
Y
0
0
1
Z
0
0
1
F
0
1
1
К.Ю. Поляков, Е.А. Ерёмин, 2018
ложно при X = 1, Y = Z = 0
X Y Z 0
F X Y Z
http://kpolyakov.spb.ru

21.

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

22.

Логические основы компьютеров, 10 класс
22
Задачи
Задача 6. Запишите любое логические выражение,
соответствующее таблице истинности:
x1
x2
x3
0
0
x4
x5
x6
x7
x8
1
0
0
0
F
1
0
0
«И»
F x1 x 2 x 3 x 4 x 5 x 6 x 7 x 8
могут быть и с инверсиями!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

23.

Логические основы компьютеров, 10 класс
23
Задачи
Задача 7. Задана таблица истинности логической
функции F Z X X Y . Определите, где какой
столбец.
Z
? Y
? X
? F
X Y Z