Тема: мінімізація функцій алгебри логіки

 

МЕТА РОБОТИ

1.1. Вивчити і практично закріпити основні правила і закони алгебри логіки

1.2. Закріпити знання про перетворення логічних виразів методами Квайна-МакКласкі і карти Карно (діаграм Вейча).

ОСНОВНІ ТЕОРЕТИЧНІ ВІДОМОСТІ

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

Булеву функцію можна задати трьома способами:

- змістовно (словесний опис);

- таблично (таблиця істинності);

- алгебраїчно.

Алгебраїчний спосіб задання булевої функції представляє собою формулу зв'язану простішими логічними операціями І, АБО, НЕ, І-НЕ, АБО-НЕ (табл. 3.1).

Способи задания булевого виразу.

 

Таблиця 3.1

Логічна операція (назва функції)	Задання функції формулою	Таблиця істинності
входи	виходи
Х2	Х1	f(х1,х2)
І (кон’юнкція, логічне множення)	f(х1,х2)= х1*х2; f(х1,х2)= х1х2 f(х1,х2)= х1Ùх2 f(х1,х2...хn)= х1х2... хn
АБО (диз’юнкція, логічне додавання)	f(х1,х2)= х1+х2 f(х1,х2)= х1Úх2 f(х1,х2...хn)= х1Úх2Ú...Úхn
НЕ (інверсія, заперечення)
І-НЕ (функція Шеффера)
АБО-НЕ (функція Пирса)

 

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

Основні співвідношення алгебри Буля Таблиця 3.2

№ п/п	Логічне додавання (а)	Логічне множення (b)	Співвідношення алгебри Буля
			закон	правило
	х1Úх2= х2Ú х1	х1х2= х2х1	переставний
	(х1Úх2)Úх3= х1Ú(х2Úх3)	(х1х2)х3= х1(х2х3)	сполучний
	(х1Úх2)х3=х1х3Ú х2х3	х1Ú(х2х3)=(х1Úх2)(х1х3)	розподільний
				де Моргана
	хÚ0= х	х*1=х		повторення
	хÚ1= х	х*0=0
	хÚх= х	х*х=х
				склеювання
				поглинання
			інверсія
		подвійне заперечення
	f(x)=x	повторення

 

Розглянемо процес спрощення виразів на прикладах.

Приклад 1. Логічна функція від трьох змінних f(х₁,х₂,х₃)=х₁х₂Ú х₁х₂Ú х₂х₃Úх₁х₂

спрощується наступним способом:

за правилом 7а

за правилом 9а

У результаті перетворення логічна функція має вид

 

Приклад 2. Відома логічна функція

Спрощуємо;

по закону 3а

за правилом 7b

за правилом 13

по закону 6а

У результаті одержуємо

Процес спрощення логічного виразу, який оснований на тотожних перетвореннях носить назву мінімізація.

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

- доскональна диз'юнктивна нормальна форма(ДДНФ);

- доскональна кон'юнктивна нормальна форма(ДКНФ).

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

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

Мінімізація методом Квайна.

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

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

Розглянемо етапи мінімізації логічної функції , заданій в ДДНФ.

В даній функції - об'єднуємо елементарні добути, отримаємо - , маємо .

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

Таким чином, мінімізація функцій Буля проводиться за допомогою законів і теорем алгебри логіки, теореми де Моргана, закона подвійного заперечення і правил поглинання і склеювання.

Мінімізація функцій Буля за допомогою карт Карно (табличний метод).

Карта Карно — це прямокутник, розбитий на квадрати (комірки), число яких дорівнює 2ⁿ, де n- число логічних змінних. Структура карт Карно для 2-х, 3-х, 4-х змінних показана на рис. 3.1.

Рис.3.1. Карти Карно: а) для функції 2-х аргументів;

б) для функції 3-х аргументів;

в) для функції 4-х аргументів;

Комірки карти відповідають значенням вхідних змінних. Наприклад, верхній рядок карти для функції 3-х змінних відповідає "1", тобто значення х₁=1, а нижній рядок - нульовому значенню х₁=0 кожний стовпчик характеризується значенням двух змінних х₂ і х₃.

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

Пошуки мінімальної форми функції зводяться до визначення областей, які містять по 2k комірок, де 2- число, k-ціле число (0, 1, 2...). В області об'єднуються сусідні комірки, які відповідають сусіднім елементарним добуткам рис.3.

Рис. 3.1

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

Рис. 3.2. Карти Карно і мінімальний запис логічних функцій:

а) для 3-х змінних; б),в) для 4-х змінних

 

Аналізуючи карти Карно, рис. 3, бачимо, що одна і таж комірка (наприклад, комірка з координатами х₂х₃) може покриватися два або декілька разів. Таким чином, формула, одержана в результаті мінімізації логічної функції за допомогою карт Карно, містить суму стількох елементарних добутків, скільки областей є в карті. Чим більше комірок в області, тим меньше змінних міститься у відповідному йому симентарному добутку.

 

ДОМАШНЄ ЗАВДАННЯ.

3.1. Вивчити за опорним конспектом способи мінімізації логічних функцій.

3.2.Довести тотожність, відмічаючи закон і правила алгебри логіки застосовувані на кожному кроці перетворення: .

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

А)

1. 2. 3. 4. 5.

Б)

1. 2. 3. 4. 5.

 

ВИКОНАННЯ РОБОТИ.

4.1. Визначити свій варіант логічної функції. Для цього необхідно свій порядковий номер по журналу перевести в двійкову систему числення і записати п'ятьма розрядами у вигляді слова А5А4А3А2А1. Визначивши значення А_і, підставити їх в таблицю 5.

Наприклад, якщо порядковий номер по журналу10₁₀=01010₂, то А₅= 0, А₄= 1, А₃= 0, А₂= 1, А₁ = 0

 

Таблиця 3.3.

Х3	Х2	Х1	У
			А5 А4 А3 А2 А1

4.2. Продовжити роботу по схемі алгоритму

4.3. Порівняти мінімізовані функції отримані в п.4.2, зробити відповідні висновки.

4.4. Дати відповіді на контрольні запитання.

4.5. Зробити висновки по роботі.

 

КОНТРОЛЬНІ ЗАПИТАННЯ.

5.1. Які існують способи задания логічних функцій? Наведіть приклади функцій заданих різними способами.

5.2. Використовуючи основні закони Булевої алгебри, спростити наступні вирази:

a)

б)

в)

5.3. Отримайте заперечення наступних виразів та спростіть їх:

a)

б)

в).

5.4. Мінімізуйте логічні функції

а)

б)

ЗМІСТ ЗВІТУ

6.1. Тема та мета практичної роботи.

6.2. Виконання домашнього завдання.

6.3. Звіт за пунктами виконаної практичної роботи.

6.4. Відповіді на контрольні запитання.

6.5. Висновки.

 

ЛАБОРАТОРНА РОБОТА №4