Основные теоремы и положения алгебры логики
Для преобразования формул алгебры логики с целью их минимизации используются, как и в обычной алгебре, скобки, а если их нет, то сначала выполняется отрицание (инверсия) над отдельными переменными, затем логическое умножение (конъюнкция) и наконец логическое сложение (дизъюнкция). Однако если черта (знак инверсии) стоит над совокупностью букв и знаков, то она выполняется в последнюю очередь… Читать ещё >
Основные теоремы и положения алгебры логики (реферат, курсовая, диплом, контрольная)
Принцип двойственности.
Запишем правила выполнения операций ИЛИ и И, расположив строчки И в обратном (снизу вверх) порядке:
Сравним построчно операции ИЛИ и И. Нетрудно видеть, что если заменить в строках ИЛИ и И все 0 на 1, все 1 на 0 и знаки дизъюнкции на знаки конъюнкции, то правила меняются местами: строка ИЛИ превращается в строку И и наоборот.
В этом состоит принцип двойственности, который в общем виде записывается так: 
Для преобразования формул алгебры логики с целью их минимизации используются, как и в обычной алгебре, скобки, а если их нет, то сначала выполняется отрицание (инверсия) над отдельными переменными, затем логическое умножение (конъюнкция) и наконец логическое сложение (дизъюнкция). Однако если черта (знак инверсии) стоит над совокупностью букв и знаков, то она выполняется в последнюю очередь.
В процессе преобразования формул используются также теоремы алгебры логики.
Теоремы для одной переменной (легко проверяемые подстановкой Л = 1
и А = 0): | ||
1. A v 0 — А; | 4. Л v Л = 1; | 7. Л • Л = Л; |
2. A v 1 = 1; | 5. Л 0 = 0; | 8. Л • Л = 0; |
3. ЛуЛ = Л; | 6. Л • 1 = Л; | 9. Л = Л. |
Заметим, что эти теоремы (как и последующие) остаются справедливыми и для случая, если под А понимать не только одну переменную, но и целое выражение.
Теоремы для двух и более переменных:
- 10а. A v В = В v А; 106. АВ = В, А — переместительный закон;
- 1 la. A v В v С = A v (В v С) = (A v В) v С;
- 116. АВС — А (ВС) = (АВ) С — сочетательный закон;
- 12а. А (В v С) = АВ v АС; 126. A v ВС = (A v В) • (A v С) — распределительный закон.
Если теоремы 10, И очевидны и совпадают с правилами обычной алгебры, то очевидность теоремы 126 (как и ряда следующих теорем) следует из принципа двойственности.
В самом деле, заменим в левой и правой частях теоремы 12а все переменные их отрицаниями и_номеняем_знаки конъюнкции и дизъюнкции друг на друга, получим: AvBC = (AvB)(Av С). Введем новые обозначения: А = D; В = Е и С = G. Получим D v EG = (D v E) • (D v G), а это и есть теорема 126;
13а. A v АВ = А; 136. A (A v В) = А — закон поглощения (читается «А поглощает В»).
Доказательство теоремы 13а: A v ЛВ = Л (1 v В) = А • 1 = Л (используя теоремы 2 и 6); доказательство теоремы 136 следует из принципа двойственности; _.
14а. (Л v В) В = АВ; 14.6 АВ v В = A v В.
Доказательство^георемы 14а:
- (Л vВ)В = ABvВВ = ЛBvO = АВ (используя теоремы 8 и 1), доказательство теоремы_14б следует из принципа двойственности;
- 15а. АВ v АВ = В: 156. (Л v В) (A v В) = Взакон склеивания (читается «склеивание по Л»).
Доказательство теоремы 15а: ABvАВ = B (AvА) = В- 1 = В (используя теоремы 4 и 6); доказательство теоремы 156 следует из принципа двойственности.____ _ _ _.
16а. Л v? vCv… = А В С …; 166. A B C…- A vBvCv… — теорема де Моргана, представляющая наиболее общую формулировку принципа двойственности.