Построение таблиц истинности. Логические основы компьютера

1.

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

2.

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

3.

Логические основы компьютеров, 10 класс
3
Вспомним известное…
Логическое выражение — это символическая
запись высказывания, которая может
содержать логические переменные и знаки
логических операций.
Логическая функция — это правило
преобразования входных логических значений
в выходные. Логическая функция задаётся
таблицей истинности.
Выражения:
A
A+A B
A (A+B)
К.Ю. Поляков, Е.А. Ерёмин, 2018
A
0
0
1
1
B
0
1
0
1
F
0
0
1
1
функция
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
также:
A xor B (Паскаль),
A ^ B (Си)
арифметическое
сложение, 1+1=2
остаток
сложение по модулю 2: А B = (A + B) mod 2
К.Ю. Поляков, Е.А. Ерёмин, 2018
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
К.Ю. Поляков, Е.А. Ерёмин, 2018
B
0
1
0
1
A B
A B A B A B А B
0
0
1
0
0
1
0
0
0
1
1
0
http://kpolyakov.spb.ru
0
1
1
0

11.

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

12.

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

13.

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

14.

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

15.

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

16.

Логические основы компьютеров, 10 класс
16
Стрелка Пирса, «ИЛИ-НЕ»
A B A B
A
0
0
1
1
B
0
1
0
1
А↓B
1
0
0
0
Базовые операции через «ИЛИ-НЕ»:
! Самостоятельно…
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

17.

Логические выражения
Примеры и решение
задач
17

18.

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

19.

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

20.

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

21.

Логические основы компьютеров, 10 класс
21
Составление таблиц истинности
X A B A C B C
0
1
2
3
4
5
6
7
К.Ю. Поляков, Е.А. Ерёмин, 2018
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
http://kpolyakov.spb.ru

22.

Логические основы компьютеров, 10 класс
22
Задачи
Задача 1. При каких значениях логических переменных
истинно выражение:
X1 X 2 X 3 X 4 X 5
Решение. Все сомножители равны 1:
X 1 X 4 1,
X2 X3 X5 1
Задача 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

23.

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

24.

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

25.

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

26.

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

27.

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

28.

Логические основы компьютеров, 10 класс
28
Диаграммы Венна (круги Эйлера)
A
A
A
B
B
A·B
A
A+B
A
A
A
B
B
A B
К.Ю. Поляков, Е.А. Ерёмин, 2018
A B
B
A B
http://kpolyakov.spb.ru

29.

Логические основы компьютеров, 10 класс
29
Диаграмма с тремя переменными
Хочу
Могу
3
2
1
5
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
! Логические выражения можно упрощать!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

30.

Логические основы компьютеров, 10 класс
30
Диаграмма с тремя переменными
F M (X H)
М
Х
M ( X H )
M X
Н
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

31.

Логические основы компьютеров, 10 класс
31
Диаграмма с тремя переменными
F M (X H)
М
Х
M X
M (X H)
К.Ю. Поляков, Е.А. Ерёмин, 2018
Н
http://kpolyakov.spb.ru
M

32.

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

33.

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

34.

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

35.

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

36.

Логические основы компьютеров, 10 класс
38
Задачи
Поисковый сервер в автоматическом режиме составил
таблицу ключевых слов для сайтов некоторого
сегмента Интернета. Вот ее фрагмент:
Ключевое слово
сканер
принтер
монитор
Количество сайтов, для которых
данное слово является ключевым
200
250
450
Сколько сайтов будет найдено по запросу
(принтер | сканер) & монитор
если по трем следующим запросам найдено:
принтер | сканер
– 450 сайтов,
принтер & монитор
– 40 сайтов
сканер & монитор
– 50 сайтов.
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

37.

Логические основы компьютеров, 10 класс
39
Задачи
А (сканер)
B (принтер)
450
принтер | сканер
0
NA|B = NA+ NB – NA&B
сканер
200
принтер
250
(принтер | сканер) & монитор = ?
принтер
сканер
принтер & монитор = 40
50
40
сканер & монитор = 50
монитор
К.Ю. Поляков, Е.А. Ерёмин, 2018
40 + 50 = 90
http://kpolyakov.spb.ru

38.

Логические основы компьютеров, 10 класс
40
Сложная задача
Ниже приведены запросы и количество страниц, которые нашел
поисковый сервер по этим запросам в некотором сегменте
Интернета:
мезозой
500
кроманьонец
600
неандерталец
700
мезозой | кроманьонец
800
мезозой | неандерталец
1000
неандерталец & (мезозой | кроманьонец) 200
Сколько страниц будет найдено по запросу
кроманьонец & (мезозой | неандерталец)
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru