4.2 Основні аксіоми та закони алгебри логіки.

Аксіоми алгебри логіки

1 V А = 1;

0 Λ А = 0;

А V А = А;

А Λ А = А;

0 V А = А;

1 Λ А = А;

А V А = 1;

А Λ А = 0.

Аксіома подвійного заперечення

(А) = А.

Закони комутативності

А V В = В V А;

А Λ В = В Λ А.

Закони асоціативності

А V В V С = А V (В V С);

А Λ В Λ С = А Λ (В Λ С).

Закони дистрибутивності

А V (В V С) = (А Λ В) V ( А Λ С);

А Λ (В Λ С) = (А V В) Λ ( А V С);

Закони де Моргана

А V В = В Λ А; ( А В ) – стрілка Пірса; !!!

А Λ В = В V А. ( А В ) – штрих Шефера. !!!

Закони поглинання

А V А V В = А;

А Λ А Λ В = А.

3. Нормальні форми. Тотожні формули.

Бувають диз’юктивна та кон’юктивна нормальні форми (ДНФ та КНФ). Формула алгебри висловлювань задано диз’юктивно - кон’юктивній формі. ДНФ тоді, якщо вона представлена у вигляді диз’юкції кон’юкцій елементарних висловлювань та їх заперечень.

Формула задана в кон’юкції диз’юкцій (КНФ), якщо вона представлена у вигляді в кон’юкцій диз’юктивних змінних та їх заперечень. Наприклад,

ДНФ (диз’юкції кон’юкцій та їх заперечень)

Z V XY V XYZ

КНФ (кон’юкції диз’юкцій та їх заперечень)

(ХY V Z)(Х V ХYZ)

Приведемо алгоритм приведення будь-яких формул до ДНФ і КНФ.

• на першому етапі позбуваються від зв’язок імплікації та еквівалентності

імплікація X  Y = X V Y;

еквівалентність X  Y = (X V Y) (X V Y).

• приводимо заперечення до незалежних до незалежних змінних. Розглянемо заперечення до кон’юкції і диз’юкції двох змінних (до добутку XY).

(XY) = X V Y;

(X V Y) = X Λ Y.

• розкриваємо дужки згідно першого закону (розподільного) для переведення до ДНФ або навпаки перетворюємо суми в добутки по другому розподільному закону для приведення до КНФ.

(X V Y) Z = XZ V YZ;

XY V Z = (X V Z) (Y V Z).

• при наявності двох заперечень кожен раз від них позбавляємося. Наприклад,

(z  t) (x V z) V (x(y V z))t. Привести даний вираз використавши правила алгебри логічних змінних до ДНФ.

(z V t) (x V z) V (x(y V z))t = (z V t) (x V z) V (x V (y V z))t = (z V t) (x V z) V (x V y Λ z)t = (zx V zz V tx V tz) V (x V (y Λ z))t = (zx V zz V tx V tz) V (xt V yt zt) = zx V tx V tz V xt V yzt = zx V t (x V x) V tz V yzt = zx V t V tz V yzt = zx V t (1 V z V yz) = zx V t.

4. Досконалі нормальні форми

ДНФ є: ДДНФ і ДКНФ.

ДДНФ – алгебри висловлювань називається така диз’юктивна нормально форма (ДНФ), яка:

• всі доданки вміщують співмножником всі змінні без заперечень або з запереченням, але не разом;

X Y V X Y

• відсутні повторення складових та співмножників.

ДКНФ називається така кон’юктивна нормальна форма (КНФ), в якій:

• кожний співмножник вміщує складову без заперечень, або з запереченнями, але не разом;

• відсутні повторення співмножників та складових.

(X V Y V Z) (X V Y V Z) (X V Y V Z)

5. Алгоритм приведення до дднф

а) Приведення до ДДНФ.

Алгоритм представлений таким чином:

5. спочатку приводимо до ДНФ;

6. складові, яких співмножниками входять не всі змінні помножують на одиниці, які представлені у вигляді диз’юкцій кожної недостатньої змінної з її запереченням;

7. розкриваємо дужки згідно першого розподільного законі. Приклад,

X V YZ = X (Y V Y)(Z V Z) V YZ(X V X) = XYZ V XYZ V XYZ V XYZ V XYZ V XYZ = XYZ V XYZ V XYZ V XYZ V XYZ V XYZ.

б) Приведення до ДКНФ.

Алгоритм представлений таким чином:

5. спочатку приводимо до КНФ;

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

7. згідно другого розподільного закону приводять всі співмножники до сум першого ступені виключаючи повторення співмножників. Приклад,

(X V Y)(X V Z) = (X V Y V ZZ)(X V YY V Z) = (X V YZ)(X V Y V Z)(X V Y V Z).