Рассмотрим один из наиболее распространенных методов минимизации систем переключательных функций.

Пусть задана система полностью определенных переключательных функций, представленных в дизъюнктивной нормальной форме, например:

f₁(x₁,x₂,x₃) = x₁/x₃ v x₁/x₂ v /x₁x₃,

f₂(x₁,x₂,x₃) = x₁/x₂ v /x₁x₃ v /x₁x₂,

f₃(x₁,x₂,x₃) = x₁x₂ v /x₁/x₂/x₃.

Полным множеством элементарных конъюнкций cистемы переключательных функций назовем множество всех различных элементарных конъюнкций функций данной системы:

А = {x₁/x₃; x₁/x₂; /x₁x₃; /x₁x₂; x₁x₂; /x₁/x₂/x₃}.

Удобным критерием оценки сложности системы переключательных функций является сумма рангов (число букв) элементарных конъюнкций множества А.

Минимизация системы полностью определенных переключательных функций может производиться по приведенному далее алгоритму, аналогичному алгоритму метода Квайна, с небольшими отличиями.

Этап 1.

Представить каждую из функций минимизируемой системы переключательных функций в СДНФ.

Построить полное множество элементарных конъюнкций минимизируемой системы переключательных функций.

Каждой конституенте единицы указанного множества присвоить признак, содержащий номера функций системы, в которые входит данная конституента.

Этап 2.

Произвести минимизацию СДНФ такой функции f, конституентами единицы которой являются все элементы полного множества элементарных конъюнкций.

При выполнении склеивания двух конституент единицы, каждой вновь образуемой элементарной конъюнкции следует присвоить признак, состоящий из номеров функций, общих для двух склеиваемых конституент.

Последнее справедливо и для двух склеиваемых элементарных конъюнкций с признаками.

Если признаки склеиваемых конституент единицы не содержат общих номеров, то склеивание не производится.

Поглощение производится только для элементарных конъюнкций с одинаковыми признаками.

Полученные в результате склеивания и поглощения конъюнкции называются простыми импликантами системы функций.

Этап 3.

Построить импликантную матрицу функции f, аналогичную матрице Квайна, с той разницей, что для каждой конституенты единицы выделяется столько столбцов, сколько различных номеров функций содержит ее признак.

Покрытие матрицы импликантами производится аналогично методу Квайна.

Рассмотрим пример.

Пусть требуется найти минимальную ДНФ системы переключательных функций, заданной таблицей истинности 21.

 

Таблица 21

 

x1x2x3	f1	f2

 

Этап 1. Представим каждую из функций системы в СДНФ:

f₁ = /x₁/x₂/x₃ v x₁/x₂x₃ v x₁x₂/x₃ v x₁x₂x₃,

f₂ = /x₁/x₂/x₃ v /x₁x₂/x₃ v /x₁x₂x₃ v x₁/x₂x₃.

Построим полное множество элементарных конъюнкций полученной системы, приписывая каждой конституенте единицы признак вхождения в функции f₁ и f₂:

A = {/x₁/x₂/x₃(1,2); /x₁x₂/x₃(2); /x₁x₂x₃(2); x₁/x₂x₃(1,2); x₁x₂/x₃(1); x₁x₂x₃(1)}.

Этап 2. Построим СДНФ функции f:

f = /x₁/x₂/x₃(1,2) v /x₁x₂/x₃(2) v /x₁x₂x₃(2) v

v x₁/x₂x₃(1,2) v x₁x₂/x₃(1) v x₁x₂x₃(1).

Для удобства выполнения склеивания, пронумеруем каждую конституенту единицы из СДНФ функции f и выполним все склеивания:

 

f =	/x1/x2/x3(1,2) v	/x1x2/x3(2) v	/x1x2x3(2) v	x1/x2x3(1,2) v	x1x2/x3(1) v	x1x2x3(1);

 

1 - 2: /x₁/x₃(2) v /x₁x₂x_/3(2) v /x₁/x₂/x₃(1,2);

2 - 3: /x₁x₂(2) v /x₁x₂x₃(2) v /x₁x₂x₃(2);

4 - 6: x₁x₃(1) v x₁/x₂x₃(1,2) v x₁x₂x₃(1);

5 - 6: x₁x₂(1) v x₁x₂/x₃(1) v x₁x₂x₃(1).

После проведения всех поглощений, с учетом признака каждой конъюнкции, получим следующее:

f = /x₁/x₃(2) v x₁x₃(1) v /x₁x₂(2) v x₁x₂(1) v x₁/x₂x₃(1,2) v /x₁/x₂/x₃(1,2).

Дальнейшие склеивания и поглощения невозможны.

Получены простые импликанты минимизируемой системы булевых функций.

Этап 3. Строим импликантную матрицу (таблица 22):

- столбцы матрицы помечаем конституентами единицы из СДНФ функции f (для каждой конституенты единицы, отводим столько столбцов матрицы, сколько различных номеров функций содержит признак данной конституенты);

- строки матрицы помечаем простыми импликантами системы переключательных функций;

- заполнение матрицы производим аналогично методу Квайна.

Таблица 22

 

Простые импликанты системы функций	Конституенты единицы функции f
/x1/x2/x3	/x1x2/x3	/x1x2x3	x1/x2x3	x1x2x3	x1x2/x3
/x1/x3 (2)		X	X
x1x3 (1)					X		X
/x1x2 (2)			X	X
x1x2 (1)							X	X
x1/x2x3 (1,2)					X	X
/x1/x2/x3 (1,2)	X	X

 

Ядром функции f являются те простые импликанты, где для соответствующих конституент единицы функции f имеется единственная отметка на пересечении столбца и строки импликантной матрицы.

Таким образом, ядро функции f составят следующие простые импликанты: /x₁/x₂/x₃(1,2), /x₁x₂(2), x₁/x₂x₃(1,2), x₁x₂(1).

Выделенное ядро покрывает все конституенты единицы из СДНФ функции f.

В соответствии с вышеуказанным, получим следующее выражение:

f = /x₁/x₂/x₃(1,2) v x₁/x₂x₃(1,2) v /x₁x₂(2) v x₁x₂(1).

Выделив для функций вида f_i импликанты с признаком, включающим i, получим следующую минимальную дизъюнктивную нормальную форму системы функций:

f₁ = /x₁/x₂/x₃ v x₁/x₂x₃ v x₁x₂;

f₂ = /x₁/x₂/x₃ v x₁/x₂x₃ v /x₁x₂.

К недостаткам изложенного метода следует отнести достаточно большую трудоемкость проведения операций склеивания и поглощения с признаками.

1.8 Методи факторизації перемикальних функцій

 

Розглянемо питання про факторний алгоритм знахождення форми, близької до абсолютно мінімальної.

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

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

Наприклад, з наслідку методу Блейка випливає, що перемикальна функцiя = xy Ú xz є МДНФ, представленою за допомогою трьох операцій: Якщо винести х за дужки, то знайдемо для вказаної перемикальної функцiї вираз, в якому використовуються лише дві операції: = х (y Ú z). Остання форма не є ДНФ, але її реалізація приводить до простішої комбінаційної схеми, а пошук подібних форм являє собою велику практичну цінність.

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

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

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

У загальному випадку, проблему факторизації також не вирішено, але для булевого базису в ряді випадків, використовуючи операції винесення за дужки спільних множників, можна отримати форму, простішу за МДНФ даної перемикальної функцiї.

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

Розглянемо роботу факторного алгоритму на прикладі. Нехай мднф перемикальної функцiї f має вигляд

Етап 1. Позначаємо кожну елементарну кон’юнкцію заданого виразу лiтерами A, B, C i D, відповідно, та знаходимо всі попарні перетини елементарних кон’юнкцій: , , A ∩ D, ,…. ,

Етап 2. Обираємо ту пару елементарних кон’юнкцій, перетин яких дає елементарну кон’юнкцію найбільшої довжини. У даному прикладі, можна вибрати одну з наступних пар: {A, C}, {A, D}, {B, D}, {C, D}. Для визначеності, вибираємо пару {C, D}.

Етап 3. Записуємо перемикальну функцiю аналітично, виносячи спільний множник за дужки відносно пари {C, D}. У пiдсумку, отримаємо наступний вираз: .

Етап 4. Позначаємо через А₁, В₁, С₁ диз’юнктивні члени виразу ₁ і знаходимо всі їхні перетини: ,….. ,…..

Етап 5. Знову вибираємо ту пару елементів, перетин яких дає елемен-тарну кон’юнкцію найбільшої довжини (для визначеності, пару {A₁, C₁}).

Етап 6. Записуємо перемикальну функцiю ₂ аналітично, виносячи спільний елемент за дужки відносно пари {A₁, C₁}:

.

Етап 7. Позначаємо через А₂ і В₂ диз’юнктивні члени перемикальної функцiї і знаходимо їх перетин: .

Етап 8. Виходячи з отриманих на попереднiх етапах результатiв, остаточно маємо наступне:

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

 

1. Назвати особливостi методу Карно-Вейча.

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

3. У чому полягає побудова поліному Жегалкина для заданої перемикальної функції за допомогою карт Карно-Вейча?

4. У чому полягають методи мiнiмiзацiї кон`юнктивних нормальних форм перемикальних функцiй?

5. Охарактеризувати методи мiнiмiзацiї частково визначених перемикальних функцiй.

6. Сформулювати суть мiнiмiзацiї систем перемикальних функцiй;

7. Пояснити особливостi методiв факторизації перемикальних функцій.

3 ІНДИВІДУАЛЬНІ КОНТРОЛЬНІ ЗАВДАННЯ

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

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

ЗАВДАННЯ 2. Знайти поліном Жегалкіна для однієї з наведених нижче формул за допомогою методу дiаграм Карно-Вейча, та побудувати вiдповiдну комбiнацiйну схему. Варiанти формул:

ЗАВДАННЯ 3.

Виконати мiнiмiзацiю перемикальної функцiї iз застосуванням одного з методiв мiнiмiзацiї кон`юнктивних нормальних форм перемикальних функцiй. Побудувати вiдповiднi комбiнацiйнi схеми.

Варiанти перемикальних функцiй:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10)

ЗАВДАННЯ 4. Запропонувати свою версiю частково визначеної перемикальної функції, заданої однi є ю з таблиць, представлених в основних теоретичних вiдомостях до лабораторної роботи, та здiйснити її мiнiмiзацiю:

ЗАВДАННЯ 5. Визначити iндивiдуальний варіант перемикальних функцій: перевести до двійкової системи числення номер варіанту за списком академiчної студентської групи та записати шість його молодших розрядів у вигляді слова h1h2h3h4h5h6; отриманi значення hi підставити до таблицi 11; на основi iнформацiї, отриманої з таблицi 25, сформувати перемикальнi функцiї F1, F2, F3, F4. Виконати спільну мінімізацію функцій F1, F2, F3, F4.

Таблиця 25 – Параметри перемикальних функцiй

 

X4	X3	X2	X1	F1	F2	F3	F4
						h1	h4
				h1		h2
				h2	h1	h3
				h3	h2	h4
				h4	h3		h4
					h4	h5
				h5			h4
					h5	h6	h5
				h6		h1
				h1	h6
					h1	h2
				h2			h5
					h2		h6
						h3	h6
				h3			h6
					h3		h6

 

ЗАВДАННЯ 6. Визначити індивiдуальний варіант перемикальної функції: номер варіанту за списком академiчної студентської групи перевести до двійкової системи числення та записати шість його молодших розрядів у вигляді слова h1h2h3h4h5h6; отриманi значення hi підставити до таблицi 12; на основi iнформацiї, отриманої з таблицi 26, сформувати перемикальну функцiю f(x,y,z,u). Знайти МДНФ функції f(x,y,z,u) та виконати її факторизацію.

 

 

Таблиця 26 - Параметри перемикальної функції

x	y	z	u	f
				h 6
				h 5
				h 4
				h 3
				h 2
				h 1

Додаток А

Вимоги до оформлення, захисту та оцінювання

лабораторних робіт

 

Під час захисту лабораторної роботи, студент повинен здійснити:

− коротке викладення теоретичних основ і змісту визначальних етапів виконання роботи;

− демонстрацію результатів роботи;

− відповіді на питання викладача;

− подання підсумкового звіту про виконання роботи.

Звіт з лабораторної роботи повинен містити такі складові частини:

− титульний аркуш (зразок оформлення знаходиться далі, в Додатку Б);

− формулювання теми та мети лабораторної роботи;

− постановка індивідуального контрольного завдання на лабораторну роботу;

− покроковий опис ходу виконання роботи;

− опис результатів, отриманих у процесі виконання роботи;

− висновки;

− перелік використаної літератури.

Звіт про виконання лабораторної роботи може бути оформлений у наступній формі:

− письмовий (рукописний, друкований, електронний тощо);

− усний (доповідь, прокоментований показ на комп’ютері, озвучений слайдовий показ тощо);

− письмово-усний.

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

 

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

− за національною шкалою, тобто за чотирибальною системою („відмінно/5”, „добре/4”, „задовільно/3”, „незадовільно/2”);

− за європейською шкалою ECTS, тобто за семибальною системою (“відмінно/A”, “добре/B,C”, “задовільно/D,E”, “незадовільно/FX,F”);

− за стобальною шкалою ХНТУ.

 

Основними критеріями оцінювання лабораторної роботи є:

− повнота та правильність виконання завдань;

− здатність студента до творчого застосування набутих ним знань, умінь і навичок (диференціації, інтеграції та уніфікації знань; застосування правил, методів, принципів і законів у конкретних ситуаціях; інтерпретації схем, графіків, діаграм; встановлювання різниці між причинами та наслідками; аналізу та оцінювання фактів і подій, прогнозування очікуваних результатів від прийнятих рішень тощо);

− здатність студента викладати матеріал на папері логічно, послідовно, з дотриманням вимог ЄСКД та ЄСТД.

 

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

− „відмінно” виставляють у тому разі, якщо студент виявив: всебічні, систематизовані, глибокі знання програмного матеріалу; вміння вільно виконувати завдання; засвоєння основної та додаткової літератури, що передбачена програмою, на рівні творчого використання;

− „добре” виставляють у тому разі, якщо студент виявив: повне знання програмного матеріалу; вміння виконання завдань; засвоєння основної літератури, що передбачена програмою, на рівні аналогічного відтворення;

− „задовільно” виставляють у тому разі, якщо студент виявив: повне знання основного програмного матеріалу в обсязі, що є необхідним для подальшого навчання та роботи; здатність упоратися з виконанням завдань, які передбачено програмою, на рівні репродуктивного відтворення.

 

Виконання лабораторної роботи на найвищий бал (оцінку “Відмінно/5/A”) передбачає обов`язкову наявність у звіті з лабораторної роботи елементів творчої роботи над матеріалом (порівняльного огляду, аналізу, формулювання та обгрунтування раціональних пропозицій, створення презентаційних матеріалів тощо), наведення прикладів практичного використання технологій комп'ютерної логіки.

Рекомендовано наступні види завдань творчої та практичної спрямованості:

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

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

Виконання лабораторної роботи на оцінку “Добре/4/B,C”) передбачає розкриття поставленого завдання з наведенням прикладів практичного використання операційної системи.

Виконання лабораторної роботи на оцінку “Задовільно/3/D,E”) передбачає достатність розкриття поставленого завдання на основі репродуктивного відтворення матеріалів із запропонованого переліку літератури.

 

 

Таблиця А.1

 

Правила переведення балів внутрішньої 100-бальної шкали ХНТУ

в національну та європейську шкали

 

№ з/п	Оцінка за шкалою МОН України	Оцінка за національною шкалою	Оцінка за шкалою ECTS	Пояснення оцінки за шкалою ECTS
	90-100	Відмінно (5)	А	excellent	відмінно – відмінне вико- нання лише з незначною кількістю помилок
	75-89	82-89	Добре (4)	В	very good	дуже добре – вище середнього рівня з кількома помилками
	75-81	С	good	добре – в загальному вірне виконання з певною кіль- кістю суттєвих помилок
	60-74	67-74	Задовільно (3)	D	satisfactory	задовільно – непогано, але зі значною кількістю недоліків
	60-66
E	sufficient	достатньо – виконане за- вдання задовольняє міні-мальним критеріям
	1-59	35-59	Незадовільно (2)	FX	fail (із правом перескладання)	незадовільно з можливістю повторного складання
	1-34
F	fail (повторний курс)	незадовільно з обов’язковим повторним курсом

 

 

Додаток Б