Робота з логічними функціями

Приватний вищий навчальний заклад „Галицька Академія”

Кафедра комп'ютерної та програмної інженерії

КУРСОВА РОБОТА

з дисципліни “Прикладна теорія цифрових автоматів”

Тема

Робота з логічними функціями

Студент групи КІ-09-1

Січко С.С.

м. Івано-Франківськ

2010

Завдання на курсову роботу

1. Аналітично зобразити логічні функції із даної таблиці істиності у вигляді досконалої диз'юнктивної нормальної функції і досконалої кон'юнктивної нормальної функції. Представлені функції, у вигляді логічних рівнянь, мінімізувати за допомогою законів алгебри логіки, наступним, за мінімізацією кроком, для спрощення логічної формули є зменшення кількості булевих функцій, з яких складаються формули. Синтезувати схеми із базисів І-НЕ, ЧИ-НЕ.

2. Термін здачі студентом закінченого проекту-

3. Зміст пояснювальної записки :

опис способів визначення ДДНФ і ДКНФ;

логічні рівняння ДДНФ і ДКНФ;

спосіби мінімізації логічних функцій;

мінімізовані за допомогою алгебри логіки логічні рівняння;

застосування елементів для синтезу схем;

синтезовані схеми із базисів І-НЕ, ЧИ-НЕ;

Способи утворення ДДНФ

ДДНФ - запис логічної функції у вигляді диз'юнкції кон'юнкцій (суми добутків), для яких логічна функція дорівнює одиниці.

Алгоритм складання ДДНФ:

1) скласти кон'юнкції логічних змінних для стовпців таблиці істиності, де логічна функція дорівнює 1, логічна змінна входить до кон'юнкції інвертованою, якщо її значення в даному стовпці дорівнює 0;

2) скласти диз'юнкцію одержаних кон'юнкцій.

Наприклад, досконала диз'юнктивна нормальна форма логічної функції, таблиця істиності якої наведена в таблиці 1, виглядає наступним чином:

f=x₁ x₂ x₃ x₄ x₁ x₂ x₃ x₄ x₁ x₂ x₃ x₄

Таблиця 1

Завдання ДДНФ аналітичним способом:

Способи утворення ДКНФ

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

Алгоритм складання ДКНФ:

1) скласти диз'юнкції логічних змінних для стовпців таблиці істиності, де логічна функція дорівнює 0, логічна змінна входить до кон'юнкції інвертованою, якщо її значення в даному стовпці дорівнює 1;

2) скласти кон'юнкцію одержаних диз'юнкцій.

Наприклад, досконала кон'юнктивна нормальна форма логічної функції, таблиця істиності якої наведена в таблиці 1, виглядає наступним чином:

f=x₁x₁x₂x₁x₃x₁x₄x₂x₁x₂x₂x₃x₂x₄x₃x₁x₃x₂x₃x₄x₄x₁x₄x₂

x₄x₃x₄

Таблиця 1

Завдання ДКНФ аналітичним способом:

(

((((

((((

((((

Мінімізація рівняння ДДНФ на основі законів алгебри логіки

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

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

Існує декілька законів:

1. Аналітичний.

2. Графічний.

Закони алгебри логіки

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

1. Комутативності:

X?Y=Y?X, X?Y=Y?X;

2. Асоціативності:

X?(Y?Z)=(X?Y)?Z, X? (Y?Z)=(X?Y)? Z;

3. Дистрибутивності:

X? (Y?Z) =(X?Y)?(X?Z),

X? (Y?Z) =(X?Y)? (X?Z);

4. Операції з константами:

=1,, X?1=X, X?1=1, X?0=0, X?0=X;

5. Операції з інверсією:

?X=0, 1=X?^;

6. Подвійна інверсія:

X=

7. Закон ідемпотентності

X?X?X…?X=X, X?X?X…?X=X;

8. Правила де Моргана

9. Закони склеювання

10. Закони поглинання

X?X?Y=X, X?(X?Y)=X;

11. Наслідок із законів 3-5

Мінімізація рівняння ДДНФ

=

Мінімізація рівняння ДКНФ на основі законів алгебри логіки

(((

((((

((((=)(

Поняття базису логічних функцій. Переведення логічного рівняння до базису “і-не”

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

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

1) І,ЧИ,НЕ;

2) І,НЕ;

3) ЧИ,НЕ;

4) І-НЕ;

5) ЧИ-НЕ;

6) ВИНЯТКОВЕ І,ЧИ,НЕ.

Базис 1 є надлишково повним(за допомогою правил де Моргана він перетворюється до базисів 2 або 3, але найбільш прийнятим для переведення логічних перетворень. Базаси 4 та 5 є найбільш широко вживаними в цифровій техніці, що обумовлено наявністю в базисах тільки однієї функції, а також максимальною простотою технічної реалізації елементів І-НЕ, ЧИ-НЕ. Базис 6, основою якого є функція ВИНЯТКОВЕ ЧИ, розглянутий в алгебрі Жегалкіна.

Переведення логічного рівняння до базису “і-не”

Для переведення в базис І-НЕ застосуємо мінімізовану ДДНФ:

f=

За допомогою правил де Моргана позбавимось логічної функції ЧИ :

f=

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

Залишається перетворити до функції І-НЕ тільки одномістну функцію НЕ. Для цього можна використати перший закон ідемпотентності:

f=

Переведення логічного рівняння до базису “чи-не”

Для переведення в базис ЧИ-НЕ застосуємо мінімізовану ДКНФ:

f=

За допомогою правил де Моргана позбавимось логічної функції І:

f=

Визначимо, що змінні та в одержаному виразі логічно додаються функцією ЧИ-НЕ, а ось змінна додається до них функцією ЧИ, яка також має бути перетворена. Перетворення функції ЧИ до функції ЧИ-НЕ здійснюється за допомогою операції подвійної інверсії:

f=

після чого використаємо шосту операцію з константами:

f=

Синтез логічних схем

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

1) Складання таблиці істиності логічної схеми згідно із функціональним призначенням схеми;

2) Запис аналітичного виразу, що відповідає таблиці істиності, тобто логічного рівняння в базисі І, ЧИ, НЕ;

3) Мінімізація логічного рівняння в базисі І, ЧИ, НЕ;

4) Перетворення логічного рівняння до базису І-НЕ або ЧИ-НЕ

5) Синтез логічної схеми.

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

Для синтезу логічних схем в базисах І-НЕ, ЧИ-НЕ необхідно на базі відповідних елементів реалізувати інвертори, що здійснюється за допомогою законів алгебри логіки одним із двох шляхів (Мал. 1):

1) Об'єднання входів логічних елементів;

2) Підключення до одного з входів логічної 1 (для елементів І-НЕ) або логічного 0 (для елементів ЧИ-НЕ)

Мал.1 Утворення інверторів з елементів І-НЕ, ЧИ-НЕ.

Синтез логіної схеми в базисі І-НЕ:

Синтез логіної схеми в базисі ЧИ-НЕ:

Перелік використаних літературних джерел

1. Глушаков С.В., Коваль А.В., Смирнов С.В. Язык программирования С++. - Х.: Фолио,2002.

2. Прата С. Язык программирования С++. - М .- СПб.- К. : Diasoft, 2003.

3. Кораблев В. С и С++. - К.: BHV, 2002.

4. Спірідонов В.І., Войтков В.Г., Обчислювальна техніка і програмування. - Хмельницький: ХТІб 1992.

5. Єжова Л.Ф. Алгоритмізація і програмування процедур обробки інформації. - К.: КНАУ, 2000.

6. Г. Шилдт. Самоучитель C++: Пер. с англ. - Санкт-Петербург: BHV-Санкт-Петербург, 1998. 620с.

7. К. Джамса. Учимся программировать на языке C++: Пер. с англ. - Москва: Мир, 1997. 320с.