Тема 22. Формула включення та виключення

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

— кількість предметів із властивостями ₁, ₂, що не мають властивості ₃. Про інші властивості нам невідомо, є вони чи немає.

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

Якщо — комбінація властивостей без урахування їх порядку, знак “+” у формулі ставиться за умови, що кількість властивостей парна, та “-” — якщо непарна. Наприклад, член входить зі знаком “+”, а член — зі знаком “-”.

При вивченні теми необхідно ознайомитися з матеріалом підручників [1, c. 426-431; 2, c. 426-431; 9, c. 116-123; 10, c. 25-27, c. 59; 12, c. 273-276; 17, c. 129-153].

5 Методичні вказівки до тем для самостійного вивчення

Тема 1. Методи мінімізації булевих функцій

Метод мінімізації Квайна – Мак-Класкі реалізує перехід від ДДНФ до мінімальної ДНФ з використанням операцій склеювання та поглинання. Він був запропонований В. Квайном, а потім удосконалений Мак-Класкі.

Недолік методу мінімізації булевих функцій Квайна – Мак-Класкі полягає у необхідності записувати ДДНФ функції, яка вже при семи змінних може містити більше ста конституент одиниці. Наступний метод дозволяє здійснювати диз’юнктивну мінімізацію, вихідну довільну ДНФ функції.

Метод мінімізації Порецького-Блейка реалізує перехід від довільної ДНФ до скороченої ДНФ за допомогою операцій узагальненого склеювання та поглинання.

Метод Порецького-Блейка полягає у застосуванні операцій узагальненого склеювання до ДНФ функції. Потім в одержаній формулі здійснюються всі можливі операції поглинання. Ознайомитися з методами мінімізації булевих функцій та навчитися застосовувати ці знання на практиці [1, c.165-175; 2, c.166-175; 12, c.70-78, c.85-87].

Тема 2. Синтез комбінаційних схем

Логічні схеми у комп’ютерах та інших електронних пристроях оперують з наборами вхідних і вихідних даних, що складаються з нулів та одиниць. Булева алгебра і булеві функції зображують математичний апарат для роботи з такими даними і використовуються для аналізу та синтезу логічних схем (ланцюгів). Основою побудови логічних схем є набір логічних елементів. Кожен логічний елемент реалізує деяку булеву функцію. Його входи відповідають булевим змінним, а вихід – значенню функції.

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

Ознайомитися з правилами побудови перемикальних ланцюгів і навчитися будувати їх на різних елементах комбінаційних схем [1, c. 177-181; 2, c. 177-182].