Перетворення булевої функції та синтез комбінаційної схеми

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

Размещено на http:///

Вступ

Втілення в життя електронно-обчислювальних машин розпочалося приблизно в середині 20-го століття. Перша релейна обчислювальна машина Z3 побудована Конрадом Цузе в 1941 р. в Німеччині. Перша електронна обчислювальна машина на радіолампах ENIAC винайдена в 1946 р. в США під керівництвом Д. Маучлі і Д. Еккерта. З того часу почались активно розглядатися нові методи обробки і використання цифрової інформації, чому сприяв науково-технологічний прогрес. Саме тому до нашого часу існує потреба в теоретичному обґрунтуванні принципів роботи цифрових автоматів.

Прикладна теорія цифрових автоматів - предмет, що дає змогу освоїти загальні принципи аналізу та синтезу цифрових автоматів.

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

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

1. Теоретичні відомості

1.1 Основні поняття алгебри логіки

Логічною основою цифрових автоматів (комп'ютерів) є алгебра логіки (булева алгебра) - одна з основних частин математичної логіки.

Функція f(x₁, x₂, ..., x_n) називається логічною (перемикальною), чи булевою, якщо вона, так само як і її аргументи x_i, може приймати тільки два значення: 0 чи 1.

Логічна (булева) змінна - це така величина x, що може приймати тільки два значення: 0 чи 1.

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

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

Сукупність значень аргументів логічної функції називається набором (або точкою) і може позначатися, зокрема, як х₁, х₂,..., х_n, де x_i дорівнює нулю чи одиниці (i = 1, 2, ..., n). Очевидно, що набір значень аргументів фактично являє собою деяке двiйкове число. Кожному набору значень аргументів приписується номер, який дорівнює двiйковому числу, що відповідає значенню даного набору.

Таким чином, логічна функція (функція алгебри логіки - ФАЛ) це функція f(x₁, x₂, ..., x_n) яка приймає значення 0 чи 1 на наборі логічних змінних x₁, x₂, ..., x_n. Кожній логічній функції даного набору аргументів також прийнято приписувати номер: 0, 1, 2,....

Будь-яка логічна функція n аргументів визначена на 2ⁿ наборах, тобто може мати 2ⁿ наборів. Число різних логічних функцій n аргументів скінченне і дорівнює 2.

1.2 Властивості елементарних функцій алгебри логіки

Основні закони алгебри логіки.

· Закон комутативності (закон переміщення):

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₃;

(x₁x₂)x₃ = (x₁x₃)(x₂x₃);

Аксіоми алгебри логіки:

· Інверсія:

0 = 1, 1 = 0.

· Незмінність:

x0 = x, x1 = x.

· Універсальна і нульова множина:

x1 = 1, x0 = 0.

· Ідемпотентності (виключення повторень):

xx = x, xx = x.

· Доповнення:

xx=1, xx = 0.

· Склеювання:

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₁x₂.

1.3 Способи представлення ФАЛ

Існує багато способів завдання логічної функції. Один з них це табличний спосіб завдання логічної функції (таблиця 1.1).

Таблиця 1.1 Табличний спосіб завдання логічної функції

x1	x2	x3	ц(x1,x2,x3)
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	0

Але така форма запису не є компактною. Простіше виглядає аналітична форма запису, у вигляді формул.

Функція, яка набуває значення 0 або 1 на наборі змінних x₁,x₂...x_n, називається термом. Існує диз'юнктивний (макстерм) та кон'юнктивний (мінтерм) терм. Ранг терма визначається по кількості змінних які входять в терм.

Будь-яка ФАЛ, задана за допомогою таблиці, може бути представлена аналітично у вигляді:

f(x₁, x₂,..., x_n) = F₁ F₂ ... F_n = F_i.

Об'єднання термів називають нормальною формою.

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

f_ДНФ(x₁,x₂,x₃) = (x₁x₂x₃) (x₁x₂x₃) (x₁x₂x₃) (x₁x₂x₃);

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

f_КНФ(x₁,x₂,x₃) = (x₁x₂x₃) (x₁x₂x₃) (x₁x₂x₃) (x₁x₂x₃);

Нормальні форми не дають однозначного уявлення про функцію, так як вони включають в себе терми різного рангу. Існують досконалі нормальні форми (ДНФ). ДНФ - функція, яка містить в собі тільки терми максимального рангу. По аналогії існують: ДДНФ та ДКНФ.

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

Вибрати в таблиці істинності функції, всі набори аргументів, на яких функція дорівнює одиниці.

Виписати кон'юнкці...