LEC07.Алгебра логики
.pdf
НИУ ИТМО. Кафедра ВТ
Информатика (2014/2015)
Группы 1100, 1101, 1103, 1105, 1106, 1652. Балакшин П.В., Соснин В.В.
Лекция 7
Алгебра двоичной логики
1
Обзор аннотаций студентов
1.Роботы: дроиды, теннисисты, плантоиды.
2.Еnglish annotation is хорошо.
3.Умные вещи: кольца, браслеты, пластыри.
4.Прозрачные солнечные батареи.
5.Бесплатный сыр для студентов.
6.Эффективность онлайн-курсов (плюсы
реального университета: генератор знакомств,
заменитель силы воли).
7. Игры, игры, игры…
2
Требования к аннотациям на второй модуль
1.Объём > 15000 символов (более 1 часа видео).
2.Можно онлайн-курсы (Edx, Coursera, Intuit, Ifmo).
3.Указание ФИО автора или его почты – обязательное требование.
4.Допустимая тематика: IT (реклама, экономика, ламер-обзоры), игры (как устроены изнутри, какие технические решения использованы).
5.Размер аннотации – строго одна страница А4.
3
Гуру алгебры логики
Алгебра двоичной логики —
раздел математики, изучающий логические операции над двоичными переменными.
Джордж Буль
(1815-1864)
4
Основные определения
Логическая (булева) переменная – такая переменная, значения которой могут быть лишь "1" или "0".
В естественном языке:
«булева переменная» = «высказывание».
Высказывание – утверждение, про которое можно однозначно сказать, истинно оно или ложно.
Обозначения:
"истина" и "ложь", "true" и "fаlse" или "1" и "0".
5
Логическая функция
Логическая (булева) функция f(х, y, z, …):
в результате выполнения логических операций над логическими переменными х, y, z,… получается значение 0 или 1.
Основные логические операции:
x
x y x y
–отрицание или инверсия
–логическое умножение или конъюнкция
–логическое сложение или дизъюнкция
6
Таблицы истинности (ТИ)
Существует только 4 разные логические функции одной переменной F(X). Любая другая самая сложная функция (F(X) = ) будет иметь одну из четырёх ТИ:
X |
F1(X) = 0 |
F2(X) = X |
F3(X) = |
F4(X) = 1 |
0 |
0 |
0 |
1 |
1 |
|
|
|
|
|
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
Всегда истиные функции называются тавтологиями.
Логическая функция двух переменных: F(X, Y). Сколько существует разных Fi(X, Y)?
X |
Y |
F1(X,Y) = X v Y |
F2(X,Y) = X ^ Y |
Fi(X,Y) = … |
0 |
0 |
0 |
0 |
… |
|
|
|
|
|
0 |
1 |
1 |
0 |
… |
|
|
|
|
|
1 |
0 |
1 |
0 |
… |
|
|
|
|
|
1 |
1 |
1 |
1 |
… |
7
Количество булевых функций
L штук
(от 000..0 до 111..1
сверху вниз)
Значения К штук булевых |
Значение булевых функций |
|||||||
|
операндов |
|
|
вида F(A1, A2, … AK-1, AK) |
||||
A1 |
A2 |
… AK-1 |
AK |
FK,0 |
FK,1 |
… |
FK,N |
|
|
|
|
|
|
|
|
|
|
0 |
0 |
… |
0 |
0 |
0 |
1 |
… |
1 |
|
|
|
|
|
|
|
|
|
0 |
0 |
… |
0 |
1 |
0 |
0 |
… |
1 |
|
|
|
|
|
|
|
|
|
0 |
0 |
… |
1 |
0 |
0 |
0 |
… |
1 |
|
|
|
|
|
|
|
|
|
… |
… |
… |
… |
… |
… |
… |
… |
… |
|
|
|
|
|
|
|
|
|
1 |
1 |
… |
1 |
1 |
0 |
0 |
… |
1 |
|
|
|
|
|
|
|
|
|
N штук (от 00..0 до 11..1 слева направо)
= 2 , = 2 = ( )
Пример: количество булевых функций одной переменной равно 4,
количество булевых функций двух переменных равно 16 и т.д. |
8 |
|
Обобщенная таблица истинности
X |
1 |
1 |
0 |
0 |
Обозначение |
Название |
|
Y |
1 |
0 |
1 |
0 |
|
||
|
|
|
|||||
F |
0 |
0 |
0 |
1 |
F2,1 = x ↓ y = x NOR y = NOR(x,y) = x |
стрелка Пи́рса |
|
НЕ-ИЛИ y = НЕ-ИЛИ(x,y) |
|
||||||
|
|
|
|
|
|
|
|
F |
0 |
1 |
1 |
0 |
F2,6 = x y = x XOR y = XOR(x,y) = x |
сложение по модулю 2, |
|
исключающее «или», сумма |
|
||||||
>< y = x <> y = x NE y = NE(x,y) |
|
||||||
|
|
|
|
|
|
Жегалкина[5], не равно |
|
F |
0 |
1 |
1 |
1 |
F2,7 = x | y = x NAND y = NAND(x,y) = |
штрих Ше́ффера, НЕ-И, пунктир |
|
x НЕ-И y = НЕ-И(x,y) |
Чулкова |
|
|||||
|
|
|
|
|
|
||
F |
1 |
0 |
0 |
0 |
F2,8 = x y = x · y = xy = x & y = x AND |
|
|
y = AND(x,y) = x И y = И(x,y) = |
конъюнкция |
|
|||||
|
|
|
|
|
min(x,y) |
|
|
F |
1 |
0 |
0 |
1 |
F2,9 = (x ≡ y) = x ~ y = x ↔ y = x EQV |
эквивалентность, равенство, |
|
y = EQV(x,y) |
эквиваленция |
|
|||||
|
|
|
|
|
|
||
F |
1 |
0 |
1 |
1 |
F2,11 = x → y = x y = x ≤ y = x LE y = |
импликация, следование |
|
LE(x,y) |
|
||||||
|
|
|
|
|
|
|
|
F |
1 |
1 |
1 |
0 |
F2,14 = x y = x + y = x OR y = OR(x,y) |
дизъюнкция |
|
= x ИЛИ y = ИЛИ(x,y) = max(x,y) |
9 |
||||||
|
|
|
|
|
|
|
|
Обозначение на электрической схеме булевых функций
&
ИЛИ |
И |
НЕ |
XOR |
Какая это функция?
10