1.1 Тема: "Мінімізація перемикаючих функцій".
1.2 Мета роботи: для функції чотирьох змінних скласти МДНФ і подати її в операторській формі І-НІ(И-НЕ).
1.3 Короткі теоретичні відомості.
Одна й та ж логічна функція може бути подана в різноманітних
формах запису. Доведено, що будь-яку функцію можливо реалізувати у
вигляді логічної суми елементарних логічних добутків її змінних,
тобто добутків, множниками котрих є окремі змінні або їх заперечен-
ня. Така форма називається диз'юнктивною нормальною формою (ДНФ).
Для кожної логічної функції існує множина ДНФ, але серед них ї така,
в котрій в елементарних добутках змінна зустрічається рівно один раз
в прямому чи інверсному вигляді. Така форма носить назву досконалої
ДНФ. Якщо ї таблиця істинності функції, то для написання СДНФ необ-
хідно для всіх комбінацій вхідних змінних, при котрих функція пе-
ретворюється в одиницю, записати елементарні добутки, інвертуючи
змінні, приймаючи нульові значення. Після цього отримані добутки
треба логічно додати. Наприклад, по таблиці істинності, поданій на
мал.1 , по наведеному вище правилу, була записана СНДФ наступного
вигляду:
__ __ __ __ __ __ __ __
y = x1*x2*x3 \/ x1*x2*x3 \/ x1*x2*x3 \/ x1*x2*x3 .
--------T-------T-------T---------
¦ X1 ¦ X2 ¦ X3 ¦ Y ¦
+-------+-------+-------+---------+
¦ 0 ¦ 0 ¦ 0 ¦ 1 ¦
¦ 0 ¦ 0 ¦ 1 ¦ 0 ¦
¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦
¦ 0 ¦ 1 ¦ 1 ¦ 0 ¦
¦ 1 ¦ 0 ¦ 0 ¦ 1 ¦
¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦
¦ 1 ¦ 1 ¦ 0 ¦ 1 ¦
¦ 1 ¦ 1 ¦ 1 ¦ 0 ¦
L-------+-------+-------+----------
Мал.1. Приклад таблиці істинності.
Перехід від СНДФ до мінімізованої форми робиться застосуванням
двох функцій :
1. Зклеювання;
2. Поглинання.
Для спрощення процесу мінімізації використовують карти Карно. Вони
являють собою ті ж таблиці істинності, але в графічному вигляді.
Це дозволяє зручно проводити операції зклеювання тому, що в сусідніх
ділянках карти завжди знаходяться значення функції , що
відрізняються значенням лише одної змінної. Процес мінімізації поля-
гає в формуванні на карті прямокутників , що містять 2m(m=1,2...n)
ділянок. Змінні, котрі міняються в межах прямокутника, зникають із
відповідних елементарних добутків. Для прикладу розглянемо карту Кар-
но для трьох змінних:
X2 X3
0 0 0 1 1 1 1 0
г=======T=======T=======T=======
¦ ¦ ------+----- ¦ ¦
0 ¦ 0 ¦ ¦ 1 ¦ 1 ¦ ¦ 0 ¦
¦ ¦ L-----+------ ¦ ¦ __
X1 ¦=======+=======+=======+=======¦ = X1X3 \/ X1X2
¦ ¦ ¦ ------+----- ¦
1 ¦ 0 ¦ 0 ¦ ¦ 1 ¦ 1 ¦ ¦
¦ ¦ ¦ L-----+------ ¦
L=======¦=======¦=======¦=======-
Мал.2. Карта Карно.
Правила роботи з картами Карно:
1. Одна і та ж ділянка може використовуватись в різних прямокутниках.
2. Краї карти можливо складати.
3. При мінімізації не повністю визначених функцій , карту можливо
доповнювати нулями або одиницями для більш зручного її викорис-
тання.
1.4 Порядок виконання роботи.
1.4.1 Визначити свій варіант перемикальної функції. Для цього необ-
хідно номер варіанту перевести в двійкову систему числення і
записати шість його молодших розрядів в вигляді слова
A6 A5 A4 A3 A2 A1. Визначивши значення A , підставити їх в
табл.1. Наприклад , варіант 19 . Двійковий код 010011 , звідси
А6=0, А5=1, А4=0, А3=0, А2=1, А1=1.
1.4.2 Записати таблицю істинності перемикальної функції.
1.4.3 Скласти карту Карно для даної перемикальної функції.
1.4.4 Подати МДНФ у відповідності з картою Карно.
Табл.1.
-----T----T----T----T------T----T----T----T----T------
¦ X4 ¦ X3 ¦ X2 ¦ X1 ¦ Y ¦ X4 ¦ X3 ¦ X2 ¦ X1 ¦ Y ¦
+----+----+----+----+------+----+----+----+----+------+
¦ 0 ¦ 0 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 0 ¦ 0 ¦ 0 ¦ A 3 ¦
¦ 0 ¦ 0 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 0 ¦ 1 ¦ A 4 ¦
¦ 0 ¦ 0 ¦ 1 ¦ 0 ¦ A 1 ¦ 1 ¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦
¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 0 ¦ 1 ¦ 1 ¦ 0 ¦
¦ 0 ¦ 1 ¦ 0 ¦ 0 ¦ A 2 ¦ 1 ¦ 1 ¦ 0 ¦ 0 ¦ 0 ¦
¦ 0 ¦ 1 ¦ 0 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 0 ¦ 1 ¦ 1 ¦
¦ 0 ¦ 1 ¦ 1 ¦ 0 ¦ 0 ¦ 1 ¦ 1 ¦ 1 ¦ 0 ¦ A 5 ¦
¦ 0 ¦ 1 ¦ 1 ¦ 1 ¦ 0 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ A 6 ¦
L----+----+----+----+------+----+----+----+----+-------
1.4.5 Подати МДНФ в операторній формі:
а) І-НІ
1.5 Зміст звіту.
1.5.1 Тема роботи.
1.5.2 Порядок виконання роботи.
1.5.3 Виконані обчислення і коментарій до кожної дії.
1.5.4 Короткі висновки.
1.6 Контрольні питання.
1.6.1 Що називають досконалою і мінімізованою ДНФ ?
1.6.2 Як робиться перехід від ДДНФ до МДНФ ?
1.6.3 Спробуйте реалізувати функцію нерівнозначності на елементах
І-НІ , АБО-НІ.