Перемикальні функції

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

Функціонування цифрових пристроїв комбінаційного типу (без пам’яті, логічні пристрої), які мають n входів і m виходів, у загальному випадку описуються системою функції

; (14)

де значення функції – визначають значення вихідних сигналів, а набори аргументів відповідають вхідним сигналам (i=1..m). Функції і аргументи можуть приймати кінцеву кількість значень (зазвичай , належать {0,1}. Функції вигляду (14) називають перемикальними (Болеві, двозначні, логічні). Перемикальні функції зазвичай задають за допомогою таблиць відповідності (таблиць істинності) шляхом наведення їх значень на всіх наборах аргументів. Для спрощення набори аргументів нумерують. Якщо функція залежить від n аргументів, то кількість різних наборів аргументів складає 2ⁿ. Дві функції відрізняються між собою, якщо вони приймають різні значення навіть на одному наборі аргументів. Кількість різних функцій від n аргументів дорівнює . Для ілюстрацій комбінацій двох змінних x₁, x₂ розглянемо діаграму Венна. У прямокутнику, який представляє множину всіх змінних, подано дві підмножини x₁, x₂ у вигляді двох кругів (рисунок 2). Чотири можливі комбінації двох змінних показано областями на рисунку 2, які помічені відповідною цифрою, а саме

Докладно досліджено перемикальні функції від однієї та двох змінних. При збільшенні n кількість двійкових функцій різко зростає (при n=3 – 256, а при n=5 вже перевищує 4 мільярди). Множину функцій від n змінних можна подати за допомогою таблиці відповідності (таблиці істинності), стовпці якої відводяться для 2_n слів довжиною n, а рядки – для функцій.

Таблиця істинності для Булевих функцій однієї змінної y=f(x) має такий вигляд (таблиця 4).

Таблиця 4

x1	0 1	Позначення	Назва функції	Читання	Булєві формули
y0	0 0	0	Константа 0	Будь-яке 0	y0=0
y1	0 1	x1	Повторення x1	Як x1	y1=x1
y2	1 0		Заперечення (інверсія) x1	Не x1	y2=«5»
y3	1 1	1	Константа 1	Будь-яке 1	y4=1

З 4-х перемикальних функцій, які залежать від одного аргументу, 3 є тривіальними (найпростіші, елементарні). Єдиною нетривіальною є функція y₂ (заперечення, інверсія).

Таблиця 5

Набір	0 1 2 3	Позначення	Назва функції	Читання	Булєві формули
x1 x2	0 0 1 1 0 1 0 1
y0	0 0 0 0	0	Константа 0	Будь-яке 0	0
y1	0 0 0 1	x1x2,	Кон’юнкція, логічне множення	x1 і x2	x1x2
y2	0 0 1 0	←	Заперечення імплікації, заборона по	, але не
y3	0 0 1 1		Повторення , змінна	Як
y4	0 1 0 0	→	Заперечення зворотної імплікації, заборона по	але не
y5	0 1 0 1		Повторення , змінна	Як
y6	0 1 1 0	, + (mod2)	Сума за модулем 2, нерівнозначна	Або , або	+, (+)( )
y7	0 1 1 1	,	Диз’юнкція, логічне додавання	або
y8	1 0 0 0	x1↓x2	Стрілка Пірса, заборона диз’юнкції	Не , не	,
y9	1 0 0 1	,	Еквіваленція, рівнозначність	як
y10	1 0 1 0		Заборона , інверсія	Не
y11	1 0 1 1	→	Зворотна імплікація, імплікація	Якщо , то
y12	1 1 0 0		Заборона , інверсія	Не
y13	1 1 0 1	→	Імплікація по	Якщо , то
y14	1 1 1 0	/	Штрих Шиффера, заборона кон’юнкції	Не або не
y15	1 1 1 1	1	Константа 1	Будь-яке 1	1

З 16-ти Булєвих функцій двох змінний оригінальними є тільки 8: y₁, y ₂, y₆, y₇, y₈, y₉, y₁₃, y₁₄. Функції від будь-якої кількості змінних можна отримати за допомогою супер позиції, тобто заміщення змінних деякими функціями.

Приклад: Розписати, підставивши у вираз замість a – , b – , c – . Отримаємо . Таблиця істинності для функції записується на базі таблиці елементарних функцій (таблиця 5) так:

	0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1
	0 0 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 0 0 1 0 1 1 1 0

Приклад: Скласти діаграми Вена для функцій.

Функціональна повнота.

З стану 5 видно, що всі функції по парно зв’язані між собою через заперечення

, (15)

Отже будь-яку функцію двох змінних можна подати в аналітичній формі сукупністю певних елементарних операцій.

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

Таблиця 6.

Функція	Позначення	Властивості
Не збереження нуля	Не збереження одиниці	Не самоподвійність	Не лінійність	Не монотонність
Константа 0	0		*	*
Константа 1	1	*
Заперечення		*	*			*
Кон’юнкція	x1x2			*	*
Дизюнкція	+			*	*
Імплікація	→	*		*	*
Еквіваленція		*		*		*
Заперечення імплікації	←		*	*	*	*
Сума за модулем 2			*	*
Штрих Шеффера	/	*	*	*	*	*
Стілка Пірса	x1↓x2	*	*	*	*	*

Функціонально повними є такі системи функцій:

1)x₁+x₂, x₁x₂,

2)x₁↓x₂, x₁x₂

3)x₁/x₂, x₁+x₂

4)x₁↓x₂, x₁+x₂

5)x₁/x₂, x₁x₂

6)x₁/x₂

7)x₁↓x₂

8)«10» , x₁x_2,

Системи 1-5 є надлишково повними.

Булєва алгебра.

Логічні функції, які подані у таблиці 5 можна розглядати, як елементарні операції над однією або двома двійковими змінними. Функціонально повна система таких операцій утворює на множині двозначних змінних алгебру логіки. Таких алгебр може бути стільки, скільки є придатних повних функціональних систем. Найбільш розповсюдженою є Булєва алгебра в якій в якості базових операцій використовується: кон’юнкція (І), диз’юнкція (АБО), заперечення (НІ). Для наочності на рисунку 3 (а-в) показано визначення операцій І, АБО, НІ на діаграмах Вена.

З визначення Булєвих операцій визивають основні властивості Булєвої алгебри (Таблиця 7), які можна довести методом індукції, тобто перевіркою для всіх можливих комбінацій значень змінної. Будь-які властивості Булєвої алгебри можна довести також аналітично без звернення до таблиці істинності на основі перших п’яти властивостей, які є аксіомами.

Таблиця 7

Властивості	Перша форма (`) (диз’юнкція)	Друга форма (“) (кон’юнкція)
1. Комутативність	x+y=y+x	xy=yx
2. Асоціативність	x+(y+z)=(x+y)+z	x(yz)=(xy)z
3. Дистрибутивність	x(y+z)=xy+xz	x+yz=(x+y)(x+z)
4. Доповнення
5. Повтор змінної
6. Повтор константи
7. Подвійне заперечення
8. Ідемпотентность
9. Закони де Моргана
10. Склеювання
11. Поглинання
12. Заміщення
13. Виявлення

Приклад доведення. Властивість ідемпотентності диз’юнкції можна довести таким чином.

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

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

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

Представлені в таблиці 7 пари властивостей мають специфічну симетрію, яка представляє принцип дуальності алгебри логіки. У кожній парі одну форму можна отримати іншої заміною операцій І, АБО, а також констант 0, 1. У зв’язку з цим операції І, АБО і константи 0, 1 називають дуальними. З принципом дуальності пов’язане узагальнення законів де Моргана на будь-яку кількість змінних.

Закон де Моргана.

Якщо функція «1» дуальна функції «2», то «3», тобто заперечення деякої функції можна замінити у дуальній функції кожної змінної на її заперечення. З формули (16) випливає, що «4».

Приклади.

«5»

«6»

«7»

«8»

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

Приклад.

01010011

(АБО)

00111011

01111011

01101010

(І)

01100101

01100000

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

Таблиця 8.

Логічна операція, назва вентиля	Графічне зображення логічного елементу	Таблиця істинності	Булєві формули та позначення
НІ (заперечення) (інвертор)	«10»	x y 0 1 1 0	«11» Інверсія
І (кон’юнкція) (кон’юнктор)	«12»	x1x2 Y 0 0 0 0 1 0 1 0 0 1 1 1	«13» Логічне множення
АБО (диз’юнкція) (диз’юнктор)	«14»	x1x2 y 0 0 0 0 1 1 1 0 1 1 1 1	«15» Логічне додавання
І – НІ (штрих Шеффера) (І – НІ)	«16»	x1x2 y 0 0 1 0 1 1 1 0 1 1 1 0	«17»
АБО – НІ (стрілка Пірса)	«18»	x1x2 y 0 0 1 0 1 0 1 0 0 1 1 0	«19»
ВИКЛЮЧНЕ АБО (сума за модулем 2) (нерівнозначність)	«20»	x1x2 y 0 0 0 0 1 1 1 0 1 1 1 0	«21»

Канонічні форми представлення перемикальних функцій.

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

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

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

Термін «досконала» – вказує на те, що мінтерми формуються з аргументів функції.

Термін «диз’юнктивна» – вказує на те, що зовнішньою функцією розкладання є диз’юнкція, а внутрішньою – кон’юнкція.

Термін «нормальна» – вказує на те, що форма є дворівневою, тобто диз’юнкція кон’юнкцій.

Форма ДДНФ називається ще формою І – АБО.

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

Приклад: записати стандартні форми за заданою таблицею істинності.

x1	0	0	0	0	1	1	1	1
x2	0	0	1	1	0	0	1	1
x3	0	1	0	1	0	1	0	1
y	0	1	1	0	1	1	0	1

«22» – ДДНФ

«23» – ДКНФ

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

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

2) на базі властивостей дистрибутивності виконуються перетворення до однієї з форм – суми добутків або добутку сум.

3) використовуються властивості доповнення («24», «25») для введення відсутніх змінних у мінтерми і макстерми.

4) використовуються властивості ідемпотентності («26») для виключення доданків і співмножників, що повторються.

Приклад: записати стандартні форми для функції вигляду

«27»

Розв’язок.

1)«28»

2)«29»

3)«30»

4)«31» – ДДНФ, канонічна сума мінтермів.

Або

3)«32»

4)«33» – ДКНФ, канонічний добуток макстермів.

Відповідна таблиця істинності має такий вигляд:

x	0	0	0	0	1	1	1	1
y	0	0	1	1	0	0	1	1
z	0	1	0	1	0	1	0	1
ν	0	1	1	1	0	1	0	1

В якості стандартних форм розглядаються також нормальні форми, мінтерми (максиерми) яких на відміну від досконалих нормальних (канонічних форм) на обов’язково містять ті змінні даної функції. В залежності від кількості n змінних їх називають мінтермами (макстермами) n-го рангу. Конкретна функція має єдину канонічну форму і різну кількість еквівалентних нормальних форм.

Перетворення і спрощення формул.

Процес спрощення зводиться до використання загальних властивостей для зменшення загальної кількості входжень до кожної формули змінних і символів логічних операцій. Зазвичай перетворення виконують у диз’юнктивний нормальній формі (ДДНК) (суми мінтермів), а використовують властивості вклеювання, поглинання і виявлення. Вклеювання «1», дозволяє замінити два мінтерма, які відрізняються однією змінною (з інверсією і без) одним мінтермом більш низького рівня і рангом. Поглинання «2» дозволяє виключити всі співмножники, в який в якості співмножника входить інший мін терм більш низького рівня. Процедура склеювання не забезпечую отримування мінімальних форм, а приводить до скороченої форми, мінтерми якої називаються простими імплікантами. Серед простих імплікантів можуть бути такі імпліканти, які покриваються іншими імплікантами, тобто є надлишковими. Після вилучення надлишкових імплікант отримують тупикові форми, серед яких знаходяться і мінімальні форми. Пошук мінімальних форм серед нормальних форм конкретної функції є головною задачею синтезу логічних схем.

Для мінімізації Булевих форм розроблено ряд методів серед яких найбільш відомими є алгоритм Квайна-МакКласкі і графічні методи, які базуються на картах Карно і картах Дейча. Карти Карно представляють собою спеціально організовані таблиці відповідності, на яких зручно виконувати операції вклеювання при мінімізації. Рядки і стовбці таблиці відповідають всім можливим наборам значень змінних, причому кожні сусідні набори відрізняються однією змінною. Крайні комірки таблиці також вважаються змінними і мають таку властивість. На рисунку 4 показано карти Карно для 2-х, 3-х і 4-х змінних.

Рис. 4

1. Кожному набору значень змінних по рядках і стовбцях відповідає своя комірка, яка знаходиться на їх перетині.

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

3. Відмічені комірки відповідають мінтермам, а невідмічені макстермам канонічних форм.

4. Операції склеювання двох мін термів n-го рангу початкової формули відповідає на карті Карно об’єднання двох сусідніх комірок, відмічених одиницями. Ця пара комірок представляє собою результуючий мін терм n-1-го рангу.

5. Аналогічне склеювання 2-х мінтермів n-1-го рангу у мінтерм n-2-го рангу представляє собою об’єднання відповідних пар комірок у прямокутну групу 4-х сусідніх комірок і т.д.

Приклад: перетворити початкову Булєву функцію у мінімальну форму: «3»

Розв’язок:

1. Заповнимо карту Карно (рисунок 5а).

2. Виконаємо склеювання мінтермів функції. Серед тупикових покриттів одне є мінімальним (рисунок 5б).

Зчитування мінтермів з карти Карно виконується в процесі послідовного розгляду груп комірок. У мінтерм входять тільки ті змінні, які зберігають свої значення у даній групі, причому значенням 1 відповідає сама змінна, а значенню нуль її заперечення (інверсія). Змінні, які приймають в даній групі різні значення (нуль і один), є вільними і у даному мінтермі відсутні. Серед тупикових покритів мінімальним є на рисунку 5в. Найпростішій формі відповідає мінімальне покриття, кількість груп в якому найменша, а самі групи крупніші, ніж в аналогічних покриттях. Чим менше груп у покриті, тим менше мінтермів у формулі, чим більше розмір групи, тим нижче ранг мінтерму, тобто менша кількість … у мінтермів.

Знаходження мінімального покриття на карті Карно.

1. Вибираю помічені комірки, які входять у таку найбільшу групу, яка покриває інші комірки.

2. За цією-ж ознакою вибирається інша, ще не покрита комірка і формується її найбільша група.

3. Цей процес продовжується до тих пір, поки всі відмічені комірки не увійдуть до певної групи.

4. З можливих варіантів вибирають ті, які забезпечуються мінімальне покриття.

Переваги карт Карно: простота, наочність.

Недоліки карт Карно: цей метод практично обмежений функціями 4-х змінних. При 5-ти змінних використовують дві карти для 4-х змінних, одна з яких відповідає інверсії 5-ї змінної, а друга – в цій змінній без інверсії. При цьому вони або розмічають аналогічно і порівнюються накладанням (рисунок 6а) або симетрично і порівнюються відносно вісі симетрії (рисунок 6б).

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