Булевы ґрати

Дистрибутивні ґрати

ВЛАСТИВОСТІ ҐРАТ

У будь-якій у-безлічі для операцій перетинання й об'єднання виконуються (при визначених у них вираженнях) наступні закони:

x Ù x = x, L 1.

x Ú x = x — идемпотентность;

x Ú y = y Ú x, L 2.

x Ù y = y Ù x — коммутативность;

x Ù (y Ù z) = (x Ù y) Ù z, L 3.

x Ú (y Ú z) = (x Ú y) Ú z — ассоциативность;

x Ù (x Ú y) = x, L 4.

x Ú (x Ù y) = x — поглинання.

Крім того, нерівність x £ y рівносильна кожному з умов:

x Ù y = x і x Ú y = y — умова сумісності.

Можна виділити ґрати, що володіють додатковими властивостями, і визначити типи ґрат, згідно з цими властивостями. Так, наприклад, для будь-яких ґрат виконуються нерівності дистрибутивности (5) і (5¢), однак існують і такі, для яких здійсненні строгі рівності.

Визначення. Ґрати називаються дистрибутивної, якщо в ній виконуються тотожності:

x Ù (y Ú z) = (x Ù y) Ú (x Ù z) " x, y, z, L 6 '

x Ú (y Ù z) = (x Ú y) Ù (x Ú z) " x, y, z. L 6 "

Визначення. Булевой ґратами називаються дистрибутивні ґрати з доповненнями.

По теоремі 6.7: c Ú x = c Ú y і c Ù x = c Ù y Þ x = y, тобто кожен елемент дистрибутивних ґрат з доповненнями має не більш одного доповнення.

У булевой ґратам будь-який елемент х має одне і тільки одне доповнення х'. При цьому:

x Ù x' = 0, x Ú x' = I, L 8

(x') ' = x, L 9

(x Ù y) ' = x' Ú y', (x Ú y) ' = x' Ù y'. L 10

Оскільки доповнення в булевой алгебрі єдині, її можна розглядати як алгебру з двома бінарними операціями й однієї унарной операцією: B = < L, Ú, Ù, ¢>.

Рис. 1Булевы ґрати.

Визначення. Булевой алгеброю L = < B, Ú, Ù, ¢> називається алгебра з операціями Ù, Ú, ', що задовольняють умовам L 1 — L 10.

Приклад. На мал. 6.2 показані булевы ґрати 2, 2², 2³, 2⁴.

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