- •Розділ 1. Математичні основи синтезу логічних схем
- •1.1. Деякі поняття і визначення булевої алгебри
- •1.2. Способи задання булевих функцій
- •1.3. Булеві функції від однієї і двох змінних
- •1.4. Принцип суперпозиції логічних функцій. Пріоритет операцій
- •1.5. Аксіоми та закони булевої алгебри
- •Аксіоми кон’юнкції, диз’юнкції і заперечення:
- •1.7. Аксіоми та закони алгебри Жегалкіна
- •1. Комутативний закон
- •2. Сполучний закон
- •3. Розподільний закон по відношенню до додавання за модулем 2
- •1.8. Аксіоми та закони для функцій Шеффера та Пірса
- •1.9. Аналітичне подання булевих функцій
- •1.10. Класи булевих функцій. Теорема про повноту
- •1.11. Розвинення логічних функцій за змінними
- •1.12. Зв’язок між дднф і дкнф. Канонічні нормальні форми
1.7. Аксіоми та закони алгебри Жегалкіна
У деяких випадках, перетворення над формулами булевих функцій зручно виконувати користуючись алгеброю Жегалкіна.
В алгебрі Жегалкіна розглядають функції: , та . Тут справедливі такі еквівалентності, які називаються аксіомами алгебри Жегалкіна:
1. ; 2. ; 3. ; 4. .
На рис. 4 а) і 4. б) наведено схеми реалізації аксіом алгебри Жегалкіна та результати моделювання, відповідно.
Рис.
4 б)
Рис. 4 а)
За допомогою наведених аксіом можна довести справедливість таких законів:
1. Комутативний закон
.
2. Сполучний закон
.
3. Розподільний закон по відношенню до додавання за модулем 2
.
На основі аксіом і законів можна вивести правила перетворення функцій заперечення, кон’юнкцію і диз’юнкцію через функцію додавання за модулем 2:
1. ; 2. ;
3. ;
На рис. 5 а) і 5 б) наведено схеми реалізації булевих функцій та результати моделювання на базі елемента додавання за модулем 2: операція НЕ (notx), операція І (xiy), операція АБО (xory).
Рис.
5 б)
Рис. 5 а)
1.8. Аксіоми та закони для функцій Шеффера та Пірса
Функція Шеффера (/) – функція, яка виражається співвідношенням .
Для неї характерні аксіоми:
, 2. , 3. , 4. , 5. , 6. .
Для функції Шеффера справедливий тільки закон комутативності і то тільки для : .
Виходячи з означення функції Шеффера та наведених аксіом, можна одержати наступні формули:
1. ,
2. ,
3. .
На рис. 6 а), 6 б) наведено схеми реалізації булевих функцій на базі елемента АБО–НЕ: операція НЕ (notx), операція І (xandy), операція АБО (xory).
Рис. 6 а) Рис. 6 б)
Функція Пірса (Вебба) () – функція, яка виражається співвідношенням .
Для неї характерні аксіоми:
1. , 2. , 3. , 4. .
На основі аксіом можна показати, що для функції Пірса (Вебба) справедливий закон комутативності: . Однак для цей закон не справджується.
Функції заперечення, кон’юнкцію і диз’юнкцію виражаються через функцію Пірса (Вебба) наступним чином:
1. ,
2. ,
3. .
На рис. 7 а), 7 б) наведено схеми реалізації булевих функцій на базі елемента І–НЕ: операція НЕ (notx); б) операція АБО (xory); операція І (xandy).
Рис. 7 а) Рис. 7 б)исР
1.9. Аналітичне подання булевих функцій
Вище згадувалось, що існує аналітичний спосіб (форма) задання булевих функцій, були розглянуті прості приклади. Тут розглянемо універсальні (канонічні) форми представлення, які дають можливість одержати аналітичну форму безпосередньо виходячи з таблиці істинності для довільної булевої функції. Ця форма у подальшому може бути спрощена. Оскільки між множиною аналітичних представлень і множиною цифрових схем, які реалізують булеву функцію, існує взаємно однозначна відповідність, то відшукання канонічних форм представлення булевої функції являється початковим етапом синтезу цифрової схеми, яка її реалізує. Найбільш широкого застосування набула досконала диз’юнктивна нормальна форм (ДДНФ).
Розглянемо, як можна здійснити перехід від табличного задання булевої функції до аналітичного її представлення.
Звертаємо увагу, що надалі, з метою спрощення записів, замість символу диз’юнкції “ ” будемо вживати символ “+” і трактувати його як логічне додавання, символ кон’юнкції ” ” будемо опускати або замінювати символом ”∙” і трактувати це як логічне множення задане за замовчуванням або явне, а операцію інверсії будемо позначати символом ”¯”.
10. Диз’юнктивна форма. Припустимо, що маємо булеву функцію від n аргументів (змінних), тобто n-місну булеву функцію. Так як будь-яка змінна може приймати одне із двох значень 0 або 1, то двійкові набори значень змінних (як уже відмічалось) можна розглядати як записи деяких цілих чисел у двійковій системі числення, тобто записи вигляду . Кожному такому запису можна поставити у відповідність десяткове число , яке одержується за формулою
.
Це число, як відомо, є номером відповідного набору. Так, для чотиримісної булевої функції номером набору 1101 є число
.
Нагадаємо, що номери наборів n-місної булевої функції змінюються від 0 до .
Розглянемо деякий фіксований набір змінних , на якому задана функція алгебри логіки.
Означення 1. Кон’юнкція змінних з набору X або їх заперечень вигляду , де означає або , або (j=0,1,...,k), називається елементарною кон’юнкцією, якщо в ній кожна змінна зустрічається не більше одного разу.
До елементарних кон’юнкцій відносять також вирази, що складаються з однієї змінної (в прямій або інверсній формі), розглядаючи їх як одномісні елементарні кон’юнкції. Константу 1 зручно розглядати як 0-місну елементарну кон’юнкцію. Наприклад, елементарними кон’юнкціями є: , а вирази , елементарними кон’юнкціями не являються.
Означення 2. Диз’юнкція елементарних кон’юнкцій вигляду:
,
де – елементарні кон’юнкції – називається диз’юнктивною нормальною формою (ДНФ).
Наприклад, функція , де , – є диз’юнктивною нормальною формою (ДНФ).
Означення 3. Елементарна n-місна кон’юнкція, що включає в себе всі змінні набору X (в прямій або інверсній формі), називається мінтермом (кон’юнктивним термом) або конституентою одиниці.
Таким чином мінтерми для n-місної функції являють собою логічний добуток вигляду , де кожна із змінних може входити в прямій або інверсній формі. З цього випливає, що максимальне число різних мінтермів для набору з n змінних дорівнює . Неважко встановити, що кожний конкретний мінтерм приймає значення 1 тільки на єдиному наборі, а на всіх інших наборах – приймає значення 0.
Наприклад, логічні добутки (кон’юнкції): являються мінтермами змінних які приймають значення 1 на наборах: 0000, 1010, 1111, яким відповідають десяткові номери: 0, 10, 15. Зрозуміло, що на інших 12 наборах, кожний із розглянутих мінтермів приймає значення 0.
Означення 4. Диз’юнкція вигляду:
,
де – усі конституанти одиниці функції називається досконалою диз’юнктивною нормальною формою (ДДНФ).
Якщо прийняти до уваги, що диз’юнкція вигляду дорівнює 1, коли хоча би одна зі змінних приймає значення 1, то можна легко виразити будь-яку булеву функцію як диз’юнкцію мінтермів (конституант одиниці), які відповідають тим наборам, на яких функція дорівнює 1.
Теорема. Будь-яку булеву функцію (тотожно) можна єдиним способом представити у вигляді досконалої диз’юнктивної нормальної форми.
Доведення. Розглянемо логічну формулу
(1)
Формула (1) є диз’юнкцією елементарних кон’юнкцій. Перший член формули – це кон’юнкція значення функції на нульовому наборі: та заперечень усіх змінних цього набору. Другий член формули – кон’юнкція значення функції на першому наборі: , заперечень перших аргументів цього набору та аргументу без заперечення. В останньому члені маємо кон’юнкцію значення функції на останньому наборі аргументів та цих аргументів без заперечення.
З наведеної формули бачимо, що коли в наборі аргумент набуває значення 0, то в елементарну кон’юнкцію, яка знаходиться в квадратних дужках, він входить із запереченням, а якщо 1 – то без заперечення.
Справедливість цієї формули очевидна. Якщо, наприклад, візьмемо набір , то в лівій частині матимемо . У правій частині всі елементарні кон’юнкції, крім другої, дорівнюють нулю, а друга набуде вигляду
,
тобто те саме, що і в лівій частині.
Таким чином, при будь-яких наборах, в лівій і правій частинах завжди будемо мати одинакові вирази.
З доведеної теореми випливає, що будь-яку булеву функцію можна однозначно представити в аналітичному вигляді
, (2)
де символ “ ” означає логічну суму мінтермів, на яких функція дорівнює 1. Одержана форма і є ДДНФ.
Приклад 5. Записати ДДНФ для функцій, заданих таблицею істинності (табл. 12).
Таблиця 12
0
0
0
0
0
0
0
1
1
0
0
1
0
1
0
0
1
1
0
1
1
0
0
1
0
1
0
1
0
1
1
1
0
0
1
1
1
1
1
1
. .
Легко бачити, що функція є не що інше як сума за модулем 2 трьох змінних, тобто .
Функція називається мажоритарною (вона приймає значення, яке приймає більшість змінних) і позначається .
Приклад 6. В кімнаті є три вимикачі освітлення. Розробити схему, яка дає можливість здійснювати вмикання і вимикання освітлення будь-яким вимикачем незалежно від положення інших двох вимикачів. Одне положення вимикача будемо вважати нульоваим (0), а друге одиничним (1). Оскільки є три вимикачі, то схема повинна реалізувати булеву функцію від трьох аргументів. Складемо таблицю істинності цієї функції при умові, що всі три вимикачі знаходяться в стані 0. Тоді зміна положення будь-якого вимикача повинно викликати вмикання освітлення. Тобто на наборах 001, 010 і 100 функція повинна дорівнювати 1. Подальша зміна положення будь-якого вимикача повинно приводити до вимикання освітлення. Тобто на наборах 011, 101 і 110 функція повинна дорівнювати 0. Подальша зміна положення будь-якого вимикача повинно приводити до вмикання освітлення, що дає F(1,1,1)=1. Таблицю значень функції , наведено в (табл. 13).
Представимо одержану булеву функцію у формі (1)
|
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
Р
Рис.
9
На рис. 8 наведено комбі-наційну схему, виконану в системі проектування MAX+plus II , яка реа-лізовує побудовану булеву функцію.
На рис. 9 наведено результати моделювання, що свідчить про правильність роботи схеми.
20. Кон’юнктивна форма – це друга відома форма представлення функцій, яка будується аналогічно до диз’юнктивної форми.
Означення 5. Логічна сума будь-якої кількості різних змінних, що входять із запереченням або без нього, називається елементарною диз’юнкцією.
Наприклад, елементарними диз’юнкціями є:
, , .
Означення 6. Кон’юнкція елементарних диз’юнкцій вигляду:
,
– називається кон’юнктивною нормальною формою (КНФ).
Наприклад, функція
,
де , , – є кон’юнктивною нормальною формою (КНФ).
Означення 7. Конституентою нуля (макстермом) для функції n аргументів, називають елементарну диз’юнкцію n аргументів, яка набуває значення 0 тільки на одному наборі, а на всіх інших – значення 1.
Наприклад, набору 0110, змінних відповідає конституента нуля вигляду . Легко переконатись, що даний макстерм приймає значення 0 тільки на вказаному наборі, – на всіх інших наборах приймає значення 1.
Означення 8. Кон’юнкція вигляду:
,
де – усі конституенти нуля функції , називається досконалою кон’юнктивною нормальною формою (ДКНФ).
Приклад 7. Для розглянутих у прикладі 3 функцій (табл. 11) побувати ДКНФ.
Розв’язання. Маємо:
30. Досконала поліноміальна нормальна форма. Легко переконатись, що в ДДНФ можна замінити операцію диз’юнкцію на операцію додавання за модулем 2, причому рівність зберігається. Ця форма називається досконалою поліноміальною нормальною формою (ДПНФ). Для функцій з прикладу 3, маємо:
.
40. Канонічний поліном Жегалкіна – це поліном вигляду
де
Теорема Жегалкіна. Будь-яка логічна функція може бути представлена у вигляді канонічного полінома Жегалкіна.
Приклад 8. Виразити у вигляді полінома Жегалкіна функцію .
Розв’язання. Заданий вираз будемо шукати у вигляді полінома з невизначеними коефіцієнтами вигляду
.
При маємо ; при дістанемо ; при дістанемо ; при дістанемо , звідки . Таким чином, .
Якщо у ДПНФ усі змінні в інверсній формі замінити у відповідності з співвідношенням (див. аксіоми алгебри Жегалкіна), то розкривши дужки і звівши подібні члени, одержимо функцію у вигляді суперпозиції функцій з набору або канонічного полінома Жегалкіна.
Приклад 9. Для розглянутих вище функцій і (табл. 10) побудувати канонічний поліном Жегалкіна.
Розв’язання. Маємо:
При спрощені функцій і використана властивість функції додавання за модулем 2, що .