5. Закони алгебри логіки. Спрощення логічних функцій.

Логічним законом називається тотожність істина логічна формула, тобто така формула, яка істинна завжди на будь – якому наборі.

Рефлексивність коли S =S.

Симетричність S=t, е = S.

Транзитивність якщо S =t,t =y, то S= y.

Закони логічних операцій:

• Комутативність кон’юнкції, або переставний;

• Диз’юнкція;

• Асоціативність (сполучний);

• Асоціативність кон’юнкції і диз’юнкції.

(xy)z = x(yz) кон’юнкція;

(x˅y)˅z = x˅(y˅z) диз’юнкція.

Закони тавтології:

х ˄х≡х тотожно

х˅х≡х істинне

х˄1=х

х˄0=0

х˅1=1

х˅0=х

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

х = х

Ф ормули Деморгана: х˅у=х˄у х˄у=х˅у

Перший дистрибутивний закон:

(х˅у)˄z= x˄z˅y˄z

Другий дистрибутивний закон:

x˄y˅z= (x˅z)˄(y˅z).

Зв'язок між логічними операціями:

х ˅у = х˄у

х ˄у = х˅у

Для того щоб визначити імплікацію через диз’юнкцію:

х →у = х˅у

х →у = х˄у

х↔у≡(х→у)˄(у→х)

Закон поглинання:

х˄(х˅у)=х

х˅х˄у=х

З акон супречності: х˄х=0

Закон виключення третього: х˅х=1

6.Принцип двоїстості булевих функцій.

Змінні , які можуть приймати значення тільки з множини В, називаються логічними або мулевими змінними. Самі значення 0 і 1 булевих змінних називаються булевими константами.

Способи задання мулевих функцій:

1. За допомогою таблиці істинності ( значеннями на кожній з інтерпретацій);

2. Порядковим номером, який має ця функція;

3. Аналогічно (у вигляді формули).

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

В изначення: функція f^*(x₁,…,x_n) називається двоїстою до функції f(x₁,…,x_n), якщо f^*(x₁,…,x_n)= f(x₁,…,x_n).

Визначення: функція двоїста сама собі, тобто f=f^*, називається само двоїстою.

Відношення двоїстості симетрично, можна сказати, що кон’юнкція двоїста диз’юнкції, диз’юнкція двоїста кон’юнкції, функція «0» двоїста функції «1», і навпаки, а заперечення – само двоїста функція.

Звідси виходить так званий принцип двоїстості , що вказує правило одержання двоїстих формул і булевій алгебрі: « Для того щоб одержати двоїсту формулу у булевої алгебри , необхідно замінити в ній всі кон’юнкції на диз’юнкції, диз’юнкції на кон’юнкції, 0 на 1, 1 на 0 і використати дужки, де необхідно, щоб порядок використання операції залишився попереднім».

7.Мінімізація булевих функцій.

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

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

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

Є два методи мінімізації булевих функцій:

1. Мінімізація мулевих функцій методом карт Карно (діаграм Вейна).

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

Карта Карно для ДНФ (діаграма Вейча – для КНФ)є аналогом табиці істиності , зображеній у спеціальній формі.

Для конкретної мулевої функції карта Карно заповняється таким чином. У клітках, що відповідні інтерпретаціям, на яких функція дорівнює одиниці, записуються одиниці. Ці клітки відповідають конституантам одиниці, що присутні у ДДНФ функції. В інші клітки записують нулі.

Для мінімізації мулевої функції на множині КНФ виконується діаграми Вейча. Її побудова аналогічна картам Карно. На карті позначаються клітки , що відповідають інтерпретаціям, на яких функція = 0. Після цього проводиться склеювання кліток, що містять нулі і формуються мінімізацією КНФ. Склеювання кліток здійснюється за тим же правилами, що й при диз’юнктивній мінімізації.

2. Мінімізація функції методом Квайна – Мак – Класкі.

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

Алгоритм Квайна складається з таких кроків:

1. Записати ДДНФ заданої ункції.

2. Виконати всі можливі операції неповного диз’юнктивного склеювання. Результуюча формула є дезюнкцією вісх можливих імплікант даної функції.

3. Виконати вісі можливі операції диз’юнктивного поглинання . Результуюча формула є скороченою ДНФ даної функції.

4. Скласти імплікантну таблицю і знайти диз’юнктивне ядро.

5. Спростити імплікантну таблицю за допомогою видання рядків, що відповідають імплікантам дизюнктивого ядра, і стопців, що відповідають тим конституантам одиниці, які покриваються імплікантами ядра.

6. Знайти всі типові ДНФ даної функції.

7. Знайти мінімальну ДНФ.

Особливим методом є метод мінімізації функції методом Порецького - Блейка.