10u-3_Логика

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

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

2. Вспомним известное…

Логические основы компьютеров, 10 класс
2
Вспомним известное…
Логическое выражение — это символическая
запись высказывания, которая может
содержать логические переменные и знаки
логических операций.
Логическая функция — это правило
преобразования входных логических значений
в выходные. Логическая функция задаётся
таблицей истинности.
Выражения:
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

3. Функции с двумя аргументами

Логические основы компьютеров, 10 класс
3
Функции с двумя аргументами
? Сколько их?
F2 – И
F8 – ИЛИ
F10 – эквиваленция
F7 – исключающее ИЛИ
F14 – импликация
? Сколько логических функций с n
аргументами?
К.Ю. Поляков, Е.А. Ерёмин, 2018
2n
2
http://kpolyakov.spb.ru

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

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

5. Стрелка Пирса, «ИЛИ-НЕ»

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

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

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

7. Логические уравнения

Логические основы компьютеров, 10 класс
7
Логические уравнения
? Как решать?
((B C) A) ( A C D) 0
Способ 1. Построить таблицу истинности…
16 строк!
Способ 2. Свойство импликации:
(B C) A 1, A = 1 A C D 0
B C A 1 B = C = 0
D=0
Способ 3. Упрощение:
( B C A) ( A C D) 0
B C A ( A C D) 0
B C A A C D 0
B C A D 0
К.Ю. Поляков, Е.А. Ерёмин, 2018
A=1
B=C=D=0
http://kpolyakov.spb.ru

8. Логические уравнения

Логические основы компьютеров, 10 класс
8
Логические уравнения
A B C B C D 0
? Сколько может быть
решений?
Решение. Найдём число решений для
16
A B C B C D 1
A B C 1 или
B C D 1
(A, B, C, D):
(1, 1, 1, 0)
(1, 1, 1, 1)
нет повторяющихся!
К.Ю. Поляков, Е.А. Ерёмин, 2018
(0, 0, 0, 1)
(1, 0, 0, 1)
Ответ: 16 – 4 = 12
http://kpolyakov.spb.ru

9. Логические уравнения

Логические основы компьютеров, 10 класс
9
Логические уравнения
x1 x2 x3 x4 x5 0
00000
Запрещены 1!
x1 x2 x3 x4 x5 1
Ответ: 31
x1 x2 x3 x4 x5 1
Запрещены 0!
x1 x2 x3 x4 x5 0
? Сколько
решений?
11111
? Сколько
решений?
Ответ: 31
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

10. Логические уравнения

Логические основы компьютеров, 10 класс
10
Логические уравнения
( x1 x2 ) ( x3 x4 ) 1
Запрещены 00** и **00!
x1 x2 x3 x4
пары битов:
3 3
0101 1001 1101
0110 1010 1110
0111 1011 1111
9 решений!
3
01, 10, 11
( x1 x2 ) ( x3 x4 ) 0
4 переменные – всего 24 = 16 вариантов
для уравнения с 1 в правой части – 9 решений
16 – 9 = 7 решений!
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru