Алгебра логики

1.

Алгебра логики

2.

Алгебра логики
Алгебра, образованная множеством B = {0,1}
вместе со всеми операциями на нем
называется алгеброй логики.
Функцией алгебры логики от n переменных
называется n-местная операция, задающая
отображение Bn на B.

3.

Функции алгебры логики
Отрицание:
ഥ
¬А А
А
0
1
¬А
1
0

4.

Функции алгебры логики
Конъюнкция:
А⋀В А&В АB
Дизъюнкция:
А⋁В А + В
A
0
0
1
1
B
0
1
0
1
А⋀В А⋁В
0
0
0
1
0
1
1
1

5.

Функции алгебры логики
Импликация:
А→В
Эквиваленция:
А↔В А≡В
A
0
0
1
1
B
0
1
0
1
А→В А↔В
1
1
0
1
1
0
0
1

6.

Функции алгебры логики
Сложение по модулю:
А⊕В
Стрелка Пирса:
А↓В
Штрих Шеффера:
А|В
A B А⊕В А↓В
0 0 0
1
0 1 1
0
1 0 1
0
1 1 0
0
А|В
1
1
1
0

7.

Пропозициональные формулы
Формулой являются…
… пропозициональные переменные:
x, y, z, x1, x2, x3, …
… либо сочетания вида:
(¬А), (А⋀В), (А⋁В), (А → В), (А ↔ В),
где A и B – пропозициональные формулы.

8.

Соглашение о порядке операций.
Операции выполняются в следующем порядке
1.
2.
3.
4.
5.
6.
Скобки
Отрицания
Конъюнкция
Дизъюнкция
Импликация
Эквиваленция
Внутри группы операции выполняются слева
направо

9.

Соглашение о порядке операций
Восстановление скобок: