Бульова алгебра і форми зображення логічних функцій

__

__

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

Формули і тотожності алгебри логіки

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

Символи змінних А, В, Х₁, Х₂ … вважають формулами ___________ нуль. Формулами є і вирази виду Ā, АŸВ, A V B,...

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

____

АŸВ, ((A V B)~С)Ÿ(((A®B)®С)ŸС)

Операція суперпозиції допомагає побачити якісний перехід від кількості аргументів n=1 до n=2. Справді, суперпозиція функцій одного аргументу породжує функції одного аргументу. Суперпозиція функцій двох аргументів дає змогу побудувати функції з будь-якою кількістю аргументів.

Дві різні формули, котрі задають одну і ту ж саму істинну функцію, називають рівносильними. Відношення рівносильності позначають символом “≡”. _

((АŸВ)~С) V ((B®С)®A) ≡ A V С

Таким чином формули рівносильні, коли їх значення істинності за будь-якого набору значень істинності змінних, що їх містять, збігаються. Відношення рівносильності має властивості рефлективності, симетричності і транзитивності.

Побудова таблиць істинності для різних формул і порівняння цих таблиць завжди дає змогу з’ясувати, чи є розглядувані формули рівносильні. Проте, такий метод 2Ÿ2 ⁿ обчислень (коли вважати, що обидві формули залежать від n змінних, а тому дуже громіздкий). Тому для з’ясування рівносильності формул, перетворення й одержання нових формул доцільніше застосовувати закони, властивості і тотожності алгебри логіки, справджуваність яких можна перевірити за допомогою таблиці істинності.

1. Властивості заперечення:

А V Ā ≡ 1

А Ÿ Ā ≡ 0

2. Властивості констант:

АŸ0 ≡ 0, АŸ1 ≡ А, А V 0 ≡А, А V 1 ≡1

3. Властивості комутативності:

АŸВ ≡ ВŸА, А V В ≡ В V А

4. Властивості асоціативності:

(АŸВ) ŸС ≡ АŸ(ВŸС), (А V В) V С ≡ А V (В V С)

5. Властивості дистрибутивності:

АŸ(В V С) ≡ (АŸВ) V (AŸС), А V (ВŸС) ≡ (А V В)Ÿ(A V С)

6. Властивості “поглинання”:

АŸ(А V В) ≡ А, А V (АŸВ) ≡ А

7. Властивості склеювання:

___ ___

(АŸВ) V (АŸВ) ≡ А, (А V В)Ÿ(А V В) ≡ А

8. Закон подвійного заперечення:

Ā ≡ А.

9. Закони іденпотентності:

АŸА ≡ А, А V А ≡ А.

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

________ __ __ ________ __ __

А V В ≡ АŸВ, А Ÿ В ≡ А V В.

11. Закон тотожності:

А®А ≡ 1.

12. Закон суперечності:

________

А Ÿ Ā ≡ 1.

13. Закон виключення третього:

А V Ā ≡ 1.

14. Закон подвійного заперечення:

Ā ~ А≡ 1.

Перетворення формули, які дають змогу, використовуючи рівносильні співвідношення, отримувати інші формули, еквівалентні даній, називаються еквівалентними. Такі перетворення є ефективним засобом доведення рівносильності формул.

Сукупність логічних операцій називають функціонально повною, коли вона дає змогу будь-яку логічну функцію зобразити формулою.

Строго доведено, що сукупність операцій ר, &, V, (інверсія, кон’юкція і диз’юкція) — функціонально повна система логічних операцій. Це означає, що кожну формулу, яка містить будь-які догічні операції, можна за допомогою рівносильних пертворень звести до вигляду, коли вона містить тільки операції ר, &, V.

Функція, котра залежить від n змінних, і кожен з її аргументів набуває значень тільки з множини {0,1}, називається бульовою.

Множина всіх бульових функцій разом з операціями ר, &, V, утворюють бульову алгебру. Базисну систему логічних функцій також утворюють (ר, V,), (|), (â).

Використовуючи властивості, закони алгебри логіки, будь-яку формулу можна перетворити, звівши до відповідного вигляду, як правило до деякого стандартного — диз’юктивної чи кон’юктивної нормальних форм.

Диз’юктивна нормальна форма (ДНФ) — це диз’юнкція скінченної кількості різних членів, кожен з яких являє собою кон’юкцію окремих змінних, котрі даний член формули містить не більше ніж один раз.

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

ДНФ – це формула, яка має вигляд диз’юнкції елементарних кон’юкцій:

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