Булеві алгебри

Набір незалежних властивостей операцій Ú, Ù, Ø (замість них використаємо позначення +, ·, ̄) можна вважати аксіомами або незалежними законами булевої алгебри:

1. Комутативність: a + b = b + a, a · b = b · a;

2. Асоціативність: a + (b + с) = (a + b) + c, a · (b · c) = (a · b) · c;

3. Дистрибутивність: a + (b · с) = (a + b) · (a + с), a · (b + с) = (a · b) + (a · с);

4. Закони для нуля, одиниці і заперечення: a + 0 = a; a + =1; a · 0 = 0; a · =0;

Всі інші закони є наслідком перелічених 4-х. Зокрема:

5. Закон ідемпотентності: a + а = a · а = а;

6. Властивості одиниці і нуля: a + 1 = 1; a · 0 = 0;

7. Закони поглинання: a + (а · b) = a · (a + b) = a;

8. Закон інволюції (подвійного заперечення):

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

10. Закон склеювання: ab+ab̅=a(b+b̅)=a, (a+b)(a+b̅)=a - є слідством кількох приведених вже законів.

Якщо в виразі відсутні дужки, то операції будуть виконуватись в такій послідовності: інверсія, кон’юнкція, диз’юнкція, імплікація, еквівалентність.

Нескладно помітити, що логічні операції кон’юнкція і диз’юнкція – симетричні, тобто володіють такою властивістю як двоїстість. Двоїстість визначається як заміна в логічній формулі всіх знаків І на АБО, також знаків АБО на І, всіх нулів на одиницю і одиниці на нуль. Двоїстість є основною властивістю алгебри логіки. Закони де Моргана є однією з ілюстрацій властивості двоїстості: , .

Ця властивість алгебри логіки дає можливість при потребі замінити кон’юнкцію диз’юнкцією і навпаки. Треба замітити, що закони де Моргана справедливі для будь-якої кількості змінних:

,

╔═··· Приклад 1. З урахуванням пріоритету операцій в виразі розставимо дужки:

x ~ z ® x̅ ⋁z = x ~ (z ® ((x̅) ⋁z).

Навпаки, в виразі треба усунути зайві дужки:

(((x ⋁ y) ∧z) ~(x̅) = (x ⋁ y) ∧z ~ x̅

╚═···

Зверніть увагу, що операція інверсії (заперечення) може визначатись не тільки для окремих змінних, але й для цілого виразу:

╔═··· Приклад 2. Спростити вираз:

= застосуємо закон де Моргана

= зайві дужки, асоціативність та комутативність

закон ідемпотентності

закон поглинання.

╚═···

Для самостійної роботи

Критерії оцінювання: Кожне завдання – 4 бали. Максимальна кількість балів – 12.

Завдання 1 Прокоментувати, які закони алгебри логіки використані для приведених перетворень логічних функцій:

Варіант	Перетворення логічної функції

Завдання 2 Спростити за допомогою законів логіки Буля приведені вирази:

Варіант	a) f(x, y, z); b) f(x, y, z, t); c) …..	Варіант	a) f(x, y, z); b) f(x, y, z, t); c) ……
	a) x y z Ú x̅ y z Ú x̅ y̅ z̅Ú x y z̅; b) x̅ y z t Ú x̅ y̅ z t Ú x y z t Ú x y̅ z̅ t̅; c) (x⋁(t̅∧y))∧((x̅∧(y̅⋁t))⋁z̅⋁(x⋁(y∧ t̅)));		a) x y z̅ Ú x̅ y z Ú x̅ y̅ z Ú x̅ y z̅; b) x y z tÚ x̅ y z tÚ x̅ y̅ z̅ t̅Ú x y z̅ t̅; c) ((x⋁z)∧(x⋁t))∧(((z⋁(z∧ y))∧z̅) ⋁x̅);
	a) x y̅ z Ú x̅ y z̅ Ú x y zÚ x̅ y z; b) x̅ y z t̅ Ú x y̅ z t Ú x y̅ z t̅Ú x y z t̅; c) (y̅⋁t)∧((x̅∧z)⋁(x∧z)⋁(t̅∧z̅)⋁ (x∧z̅))∧(y⋁t);		a) x̅ y z Ú x̅ y̅ z Ú x y z Ú x y̅ z̅; b) x y z̅ t Ú x̅ y z t̅ Ú x̅ y̅ z t Ú x̅ y z̅ t; c) ((x̅∧(y̅⋁t))⋁z̅⋁(x⋁(y∧ t̅))) ∧(x⋁(t̅∧y));
	a) x̅ y z Ú x y̅ z Ú x y̅ zÚ x y z; b) x̅ y z̅ t Ú x̅ y z̅ t Ú x y̅ z t Ú x y̅ z t̅; c) ((x̅∧z)⋁(x∧z)⋁(t̅∧z̅)⋁(x∧z̅)) ∧(y⋁t) ∧(y̅⋁t);		a) x̅ y z̅ Ú x̅ y z̅ Ú x y̅ z Ú x y̅ z; b) x y̅ z t Ú x̅ y z̅ t Ú x y z t̅Ú x̅ y z t̅; c) (((z⋁(z∧ y))∧z̅) ⋁x̅)∧((x⋁z) ∧(x⋁t));

Самостійна робота № 11

Тема: Побудова ДДНФ для логічної функції

Мета: Закріпити набуті знання та навички, перевірити їх при виконанні практичних завдань.