Правило склеювання

Закони заперечення

Закон додаткових елементів.

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

Подвійне заперечення

Закон негативної логіки

Закон негативної логіки справедливий для будь-якого числа змінних. Цей закон дозволяє реалізовувати логічну функцію “І” за допомогою логічних елементів “АБО” і навпаки: реалізовувати логічну функцію “АБО” за допомогою логічних елементів “І”. Це особливо корисно в ТТЛ схемотехніці, оскільки там легко реалізувати логічні елементи “І”, але при цьому досить складний логічні елементи “АБО”. Завдяки закону негативної логіки можна реалізовувати елементи “АБО” на логічних елементах “І”

Комбінаційні закони

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

закон тавтології (багатократне повторення)

X+X+X+X=X
X*X*X*X=X

Цей закон дозволяє використовувати логічні елементи з великою кількістю входів як елементи з меншою кількістю входів.

Для зменшення числа входів в логічному елементі краще скористатися законом одинарних елементів, як це було показано вище.

закон переместітельності

A+B+C+D=A+C+B+D

закон сполучності

A+B+C+D=A+(B+C)+D=A+B+(C+D)

закон распределітельності

X1(X2+X3)= X1X2 + X1X3

Правило поглинання

X1+X1X2 X3 =X1(1+X2 X3)=X1

Правило склеювання

Також як в звичайній математиці в алгебрі логіки є старшинство операцій. При цьому першим виконується:

1.Дія в дужках

2.Операція з одним операндом (одномісна операція) – НЕ

3.Кон'юнкція - І

4.Диз'юнкція - АБО

5.Сума по модулю два.

Операції одного рангу виконуються зліва направо в порядку написання логічного вираження. Алгебра логіки лінійна і для неї справедливий принцип суперпозиції.

4.Логічний елемент виключне АБО.Застосування

Пропозиція «Якщо я отримаю спадок або виграю в лотерею, то поїду в кругосвітню подорож» містить в собі операцію логічного складання АБО. Подорож стає можливою при істинності умови А (спадок) або умови В (лотерея), або при виконанні обох умов одночасно. Сказане ілюструє таблиця істинності на мал. 2.4 (стан 1 означає «істина», стан 0 означає «помилково»).

Мал. 2.4. Таблиця істинності Мал. 2.5. Або-елемент.

логічного складання і або-елементу.

Електронна схема, на виході X якою з'являється сигнал 1, якщо на вході А або вході В або на обох входах присутній сигнал 1, називається логічним елементом АБО. Елемент АБО може бути реалізований за схемою на мал. 2.5.

Релейна схема приведена для наочності. Сьогодні елементи АБО майже завжди використовуються у вигляді інтегрованих напівпровідникових мікросхем.

Будь-яка схема, що задовольняє таблиці істинності логічного складання, є логічним елементом АБО.

Для позначення операції АБО в алгебрі логіки використовується символ V.

X = А V В

Також в літературі зустрічається знак + для позначення логічного складання.

Х= А + В

Мал. 2.6. Умовні позначення або-елементів з двома входами.

Умовне позначення логічного елементу АБО з двома входами показано на мал. 2.6. Символ ^ 1 означає, що хоч би на одному з входів має бути сигнал 1 для появи одиниці на виході.

На виході логічного елементу АБО сигнал 1 з'явиться лише тоді, коли хоч би на одному з його входів присутній сигнал 1.

5.Мінімізація логічних схем

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

Мінімізація за допомогою карт Карно

Карта Карно - графічне представлення таблиці істинності. Кожній клітці карти Карно відповідає рядок таблиці істинності. По осях карти розставляються поєднання змінних, а усередині карти - значення функції. Призначення карти Карно - знайти логічні суми прямого і інверсного значення змінних. Для будь-якої змінної, наприклад, а, така сума рівна при будь-якому значенні а: при а=0 це буде 0 + 1 = 1, при а=1 це 1 + 0 = 1. Т Тому при винесенні за дужки у вираженні: - суму можна відкинути, при цьому результат вираження не зміниться. У цьому і полягає мінімізація логічних виразів за допомогою карт Карно. Для досягнення поставленої мети мінімізації потрібно дотримувати правила розмітки осей карти:

1. Вертикальна вісь розмічається незалежно від горизонтальної.

2. Починати розмітку можна з будь-якого поєднання змінних.

3. Всі поєднання змінних мають бути перераховані.

4. Для сусідніх кліток карти поєднання змінних повинне відрізнятися не більше ніж одним знаком, причому сусідніми є крайні клітки рядка (стовпця).

Для функції два змінних карта Карно - це квадрат 2x2 клітки. У цих клітках розміщуються 4 значення функції з останнього стовпця таблиці істинності (мал. 2.2).

Мал. 2.2. Таблиця істинності (а) і карта Карно (б) для функції 2 змінних.

Карти Карно

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

У першій таблиці показаний приклад розмітки карти Карно для функції, залежної від трьох змінних. Нижні чотири клітки карти відповідають двійковим наборам, в яких змінна x набуває значення 1, чотири верхні клітки відповідають наборам, в яких змінна x набуває значення 0. Чотирьом кліткам складовим праву половину карти, відповідають набори, в яких змінна в; набуває значення 1 і так далі У другій таблиці приведена розмітка карти Карно для n=4 змінних.

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

Процес склеювання "1" зводиться до об'єднання в групи одиничних кліток карти Карно, при цьому необхідно виконувати наступні правила:

1. Кількість кліток, що входять до однієї групи, повинна виражатися числом кратним 2, тобто 2m де m=0,1,2...

2. Кожна клітка, що входить до групи з 2m кліток, повинна мати m сусідніх в групі.

3. Кожна клітка повинна входити хоч би до однієї групи.

4. До кожної групи повинне входити максимальне число кліток, тобто жодна група не повинна міститися в іншій групі.

5. Число груп має бути мінімальним.

Призначення

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

---

Дата добавления: 2015-12-08