Системи базових (елементарних) операцій

З визначення булевих функцій (2, п. 3) можна переконатися в справедливості рівностей

(1)

На підставі цього можна записати такі тотожності:

, ; (2)

; (3)

, ; (4)

, ; (5)

, ; (6)

, . (7)

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

Прикладом (одним із найважливіших) систем елементарних операцій є

(8)

Ця система елементарних операцій є надлишковою. Це випливає з того, що справедливими є такі співвідношення

, (9)

, (10)

Ці рівності доводяться з використанням таблиці істинності:

Таким чином з врахуванням рівностей (9) і (10) можна дійти висновку, що система елементарних операцій (8) може бути скорочена (наприклад) до

( (11)

Система елементарних операцій (11) має значні зручності і широко використовуються на практиці. Проте і вона є надлишковою. Це випливає із справедливості рівностей

, (12)

. (13)

Тому систему елементарних операцій (11) можна скоротити до

, (14а)

або

. (14б)

Останнє означає що будь-яку логічну операцію можна виразити через заперечення і диз’юнкцію або заперечення і кон’юнкцію. Проте і ці системи є надлишковими якщо врахувати, що справедливі рівності

, (15)

, (16)

. (17)

З цих формул випливає, що системи (14а) і (14б) можуть бути скорочені до

(18)

або

. (19)

Втім, особливого практичного значення останнє не має.

При обчисленні значень формул з операціями (8) необхідно врахувати їх пріоритети:

1. заперечення ;

2. кон’юнкція

3. диз’юнкція

4. імплікація

5. еквівалентність

(першими виконуються операції з меншим порядком (більшим пріоритетом) у цьому списку).

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

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

Приклад 1. Обчислити значення виразу

при , , , .

Виконання:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. .

Поиск по сайту: