Нормальна форма представлення елементів булевої алгебри

Теорема 1. Кожний ненульовий елемент булевої алгебри є верхньою гранню деякої кількості конституент, побудованих за даною породжуючою системою .

Доведення. Згідно з лемою 3, твердження теореми випливає для елементів . Покажемо, що якщо довільні елементи представляються у вигляді верхньої грані деякої кількості конституент, то й , , , якщо вони не нульові, також представляються у вигляді верхньої грані конституент.

Нехай , , тоді

та

,

де, у випадку, коли С_aa ¹ С_bb, С_aa С_bb =0, інакше С_aa=С_bb. Отже, або дорівнює 0, або є верхньою гранню конституент.

Нарешті, покажемо, що також представляється у вигляді верхньої грані конституент. Згідно закону де Моргана одержимо:

.

Розкриваючи дужки і, враховуючи, що , , одержимо представлення множини у вигляді верхньої грані конституент.

Теорема 2. Існує не більше ніж елементів булевої алгебри A =á М,, ,ñ, які породжуються твірною системою .

Доведення. Кожний елемент породжуваний твірною системою згідно з теоремою 1, є верхньою гранню конституент, кількість яких не перевищує . Отже, кількість різних верхніх граней не перевищує . При цьому, якщо елементи твірної системи незалежні, тобто всі конституенти відмінні від нульового елемента, то кількість різних конституент дорівнює , а, отже, елементів алгебри (з урахуванням нульового), що можна утворити з цих конституент дорівнює .

Отже, нехай твірна система незалежних елементів, тоді довільний елемент m з A =á М,, ,ñ можна задати у вигляді деякої верхньої грані конституент:

. (1)

Довільному елементу m з алгебри A =á М,, ,ñ можна співставити двійковий вектор довжиною 2ⁿ, в якому i -тому розряду відповідає конституента з десятковим еквівалентом, що дорівнює і. Вектор , що визначає елемент m з A =á М,, ,ñ має десятковий еквівалент , Вектор визначається за правилом , якщо конституента з номером i входить до представлення , і , якщо конституента з номером i не входить до представлення . Отже, довільний елемент m з A =á М,, ,ñ визначається своїми двійковим та десятковим еквівалентами.

Відмітимо, що представлення елемента m з A =á М,, , ñ можна розглядати, як відображення множини усіх двійкових векторів довжини n в множину усіх двійкових векторів довжини 2ⁿ, а саме:

Виходячи з цього представлення елемнта з алгебри A =á М,, , ñ визначається у вигляді двійкової таблиці, в рядках якої записуються двійкові еквіваленти конституент. Множина рядків таблиці впоряд­кована за зростанням десяткових еквівалентів конституент. В останньому стовпчику записується значення двійкового вектора довжини . Одиниця в цьому стовпчику вказує на те, що відповідна конституента входить до представленняя даного відображення.

Представлення елемента у вигляді верхньої грані деякої кількості конституент називається нормальною формою (НФ) відображення.

Для графічного зображення нормальної форми представлення відображень використовується n -вимірний гіперкуб.

Означення 3. Гіперкубом називається граф Н, кожна вершина якого взаємно однозначно відповідає певній конституенті, а ребра з’єднують ті вершини, двійковий код яких відрізняється лише в одному розряді.

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