КОЛЕДЖ ІНФОРМАЦІЙНИХ СИСТЕМ І ТЕХНОЛОГІЙ

ДЕРЖАВНОГО ВИЩОГО НАВЧАЛЬНОГО ЗАКЛАДУ

“КИЇВСЬКИЙ НАЦІОНАЛЬНИЙ ЕКОНОМІЧНИЙ УНІВЕРСИТЕТ імені Вадима Гетьмана”

Інструкція до лабораторної роботи №3

з дисципліни: „Комп’ютерна схемотехніка”

для студентів спеціальностей:

5.05010301 –	Розробка програмного забезпечення
5.05010101 –	Обслуговування програмних систем і комплексів

Розробив викладач Повхліб В.С.
	Розглянуто на засіданні циклової комісії Обчислювальної техніки
	Протокол № _______ від "____"________2012 р. Голова комісії ____________

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

1. Мета роботи

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

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

2.Основні теоретичні відомості

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

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

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

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

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

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

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

Таблиця 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	0 0 1 1	0 1 0 1	0 0 0 1
АБО (диз’юнкція, логічне додавання)	f(х1,х2)= х1+х2 f(х1,х2)= х1х2 f(х1,х2...хn)= х1х2...хn	0 0 1 1	0 1 0 1	0 1 1 1
НЕ (інверсія, заперечення)			0 1	1 0
І-НЕ (функція Шеффера)		0 0 1 1	0 1 0 1	1 1 1 0
АБО-НЕ (функція Пирса)		0 0 1 1	0 1 0 1	1 0 0 0

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

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

№ п/п	Логічне додавання (а)	Логічне множення (b)	Співвідношення алгебри Буля
			закон	правило
1	х1х2= х2 х1	х1х2= х2х1	переставний
2	(х1х2)х3= х1(х2х3)	(х1х2)х3= х1(х2х3)	сполучний
3	(х1х2)х3=х1х3 х2х3	х1(х2х3)=(х1х2)(х1х3)	розподільний
4				де Моргана
5	х0= х	х*1=х		повторення
6	х1= х	х*0=0
7	хх= х	х*х=х
8
9				склеювання
10				поглинання
11			інверсія
12			подвійне заперечення
13	f(x)=x		повторення

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

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

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

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

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

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

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

Спрощуємо;

по закону 3а

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

за правилом 13

по закону 6а

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

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

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

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

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

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

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