Основные законы булевой алгебры, регламентирующие порядок выполнения операций

Последовательность приминения законов булевой алгебры определяет стратегию преобразования булевых функций, при этом принято следующее старшинство операций:

1. Одноместная операция отрицания

2. Коньюнкция

3. Дизьюнкция

Всякое отклонение от указанного порядка обозначают «()»

Законы:

1. Иденпотентность дизбюнкции и коньюнкции. (a or a=a; b and b=b)

2. Закон комутативности (a and b=b and a; a or b=b or a)

3. Ассациативности ((a or b) or c=a or (b or c); (a and b)and c=a and (b and c))

4. Дистрибутивности коньюнкции относительно дизьюнкции и дизьюнкции относительно коньюнкции (a and (b or c)=(a and b)or(a and c)

5. Закон Деморгана (not (a or b)=not(a)and not(b)

6. Склеивания (a and b) or (a and (not b))=a

7. поглащения (a or (a and b)=a

8. Полецкого (a or ((not(a)) and b))=a or b)

9. двойного отрицания

10. таблица истиности

Введем несколько определений используемых в булевой алгебре и сформулируем некоторые правила с приминением этих определений.

Логическое произведение называется элементарным если сомножетели рдиночные аргументы либо отрицания одиночных аргументов (символ любого аргумента должен встречаться 1 раз)

Логическия сумма называется элементарной если слагаемые в ней одиночные аргументы либо отрицание одиночных аргументов.

Количество сомножителей (слогаемых) в элементарной коньюнкции (дизьюнкции) называется ее рангом и обозначается «r». Два элементарных произведения (суммы) называют соседними если они являются функциями одних и тех же аргументов и отличаются только знаком отрицания одного из сомножителей (слогаемых)

Элементарная логическая сумма являющаяся функцией всех аргументов заданного набора называется конституэнтой 0 (КН).

Элементарная логическая произведение являющаяся функцией всех аргументов заданного набора называется конституэнтой 1 (КЕ).

Из n аргументов можно составить 2^n конституэнт.

Правило склеивания- логическую сумму (произведение) двух соседних элементарных коньюнкций (дизьюнкций) ранга r можно заменить одним элементарным произведением (суммой) ранга (r-1) являющейся общей частью исходных слогаемыз (сомножителей).

Пример: НАЙТИ ПРИМЕР!!!!

Правило поглощения- логическую сумму (произведения) двух элементарных произведений разных рангов у которых одно является частью другого можно заменить слогаемым (сомножителем) имещим меньший ранг.

Пример: НАЙТИ ПРИМЕР!!!!

Правило развертывания- рекомендуют действия обратные склеиванию и представляет логическую функцию в виде логической суммы (произведения) коституент еденици (нуля)

Развертывание элементарной коньюнкции в логическую сумму конституэнт 1. 3 шага:

1. В элементарную коньюнкцию ранга r вводят в качестве дополнительных сомножителей (n-r) единиц, где n- ранг конституэнты.

2. Каждая введенная единица представляется в виде логической суммы отсутствующей переменной и ее отрицания.

3. Раскрываются скобки и исходная коньюнкция ранга r оказывается развернутой в логическую сумму 2^(n-r) конституэнт 1

Пример: НАЙТИ ПРИМЕР!!!!

Развертывание элементарной дизьюнкции в логическое произведение конституэнт 0. 3 шага:

1. В элементарную дизьюнкцию ранга r вводят в качестве дополнительных слогаемых (n-r) 0.

2. Каждый введеный 0 представляют в виде логического произведения отсутствующей переменной и ее отрицания (a and (not(a))

3. Получившееся логическое выражения на основе дистрибютивного закона преобразуют так, чтобы элементарная дизьюнкция ранга r развернулась в логическое произведение 2^(n-r) конституэнт 0

Пример: НАЙТИ ПРИМЕР!!!!

Таким образом любую булевую функцию можно представить в виде дизьюнкции конституэнт единици — СДНФ (совершенная дизьюнктивная нормальная форма) или в виде коньюнкции конституент 0 — СКНФ (совершенная коньюктивная нормальная форма). Эти 2 предельных разложения булефых функций были сформулипованны американским математиком Шенноном в виде теоремы о разложении булевых функций

Дата добавления: 2014-01-06