Основы информатики / 1.3. Алгебра логики




Базовые операторы
Базовыми элементами, которыми оперирует алгебра логики, являются высказывания.
Высказывания строятся над множеством {B, -, ⋀, ⋁, 0, 1}, где B — непустое множество, над элементами которого определены три операции:
- отрицание (унарная операция),
⋀ конъюнкция (бинарная),
⋁ дизъюнкция (бинарная),
а логический ноль 0 и логическая единица 1 — константы.
Аксиомы:
1. -(-x)=x
2. x⋁(-x)=1
3. x⋁1=1
4. x⋁x=x
5. x⋁0=x
6. x⋀(-x)=0
7. x⋀x=x
8. x⋀0=0
9. x⋀1=x
Свойства:
1. Коммутативность: x*y=y*x, где * это одна из операций
2. Идемпотентность: x*x=x, где * это ⋀ или \/
3. Ассоциативность: (x*y)*z=x*(y*z), где * это одна из операций
4. Дистрибутивность:
x⋀(y⋁z)=(x⋀y)⋁(x⋀z)
x⋁(y⋀z)=(x⋁y)⋀(x⋁z)
5. Законы де Моргана:
-(x⋀y)=(-x)⋁(-y)
-(x⋁y)=(-x)⋀(-y)
6. Законы поглощения:
x⋀(x⋁y)=x
x⋁(x⋀y)=x