4.Мінімізація булевих функцій. Карти Карно

Мінімізацією булевої функції називають відмикання найпростішого її подання у вигляді суперпозиції функцій якоїсь функціонально повної системи. МінДНФ булевої функції називають її ДНФ, що містить найменшу можливу кількість букв, при цьому кожну букву враховують стільки разів, скільки вона зустрічається в ДНФ. Елементарну кон’юнкцію називають імплікантою булевої функції f, якщо на довільному наборі значень змінних, на якому К=1 значення функції також дорівнює одиниці. Елементарну кон’юнкцію К називають простою імплікантою булевої функції f, якщо k-імпліканта, а якщо з k вилучити будь-яку змінну, то вона не є імплікантою. Скороченою ДНФ називають ДНФ, в якій містяться всі прості імпліканти. Т3: Мінімальну ДНФ будевої функції можна одеражати з її СДНФ вилученням деяких елементарних кон’юнкцій. Для знаходження мінДНФ використовують карти Карно. Карта Карно для ДНФ є ана­логом таблиці істинності, зображеній у спеціальній формі. Зна­чення змінних розташовані у заголовках рядків і стовпців карти. Кожній конституенті одиниці функції відповідає одна клітка (комірка) таблиці. Нуль або одиниця в клітці визначає значення функції на даній інтерпретації. Значення змінних розташовані так, щоб сусідні (що мають спільну межу) рядки і стовпці таблиці відрізнялись значенням тільки однієї змін­ної.

7. Реалізація булевих функцій по формулам.

Функцію, яка отримана з функцій f₁,f₂,…f_n якимись підстановами одна в одну називають суперпозиціею функцій. Вираз, який описує функцію та містить функціональні знаки, думки та символи змінних називають формулою. Пріорітет операцій: 1) Кон’юнкція 2)Всі інші операції. Символ заперечення відіграє роль дужок. Перетворення при яких ми отримуємо рівносильні формули називаються тотожними або рівносильними.

5.Предикати. Квантори. Формули логіки предикатів.

Існують речення, які містять змінні і не являються висловленням. Для того, щоб перетворити їх у висловлення необхідно змінним надати певних значень. Змінну х називають предметом, а властивість предмета називають предикатом Р(х). Логіка предикатів – це логіка висловлювань, до якої додаються такі типи символів: Індивідні символи – це імена об’єктів , які пишуться з великої літери та сталі. Предметні символи – це імена, якими позначаються змінні, вони записуються маленькими літерами. Предикатні символи – це імена, якими позначають предикати (Р, Q, R) або змістовні слова, що записують великими литерами. Предикат, який містить n змінних називається n-містним і записується Р(х₁,х₂…х_т)

Предметною областю будь-якого предиката називається множина D значень всіх його предметів. Для того, щоб перетворити предикат на висловлення існує ще один спосіб – квантифікація. Ква́нтор — логічний оператор, що перетворює всякий предикат на предикат меншої місності, зв’язуючи деякі змінні початкового предиката. Розрізняють такі квантори: - квантор загальності (для всіх, для кожного). – квантор існування (існує, знайдеться). Для пошуку значення істинності висловлювання отриманого з пропозиційної функції зв’язуванням її змінних кванторами потрібно знати предметну область.