Основні аксіоми і тотожності алгебри логіки Аналітична форма подання булевих функцій

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Білоруський державний університет інформатики і радіоелектроніки
КАФЕДРА РЕЗ
РЕФЕРАТ
НА ТЕМУ:
«Основні аксіоми і тотожності алгебри логіки. Аналітична форма подання булевих функцій »
МІНСЬК, 2009

Основні аксіоми і тотожності алгебри логіки
Булева алгебра дозволяє не тільки математично описувати переключательние функції, а й перетворювати їх, даючи можливість реалізовувати ці функції на різних функціонально повних системах. Оскільки переключательние функції в кінцевому рахунку відображають певні логічні зв'язки між різними вузлами цифрових пристроїв, то тим самим булева алгебра дозволяє перетворювати ці зв'язки і, отже, вона є апаратом, що дозволяє розробнику здійснювати вибір оптимального варіанту.
В даний час найбільш повно розроблені методи перетворення виразів, які містять переключательние функції ОФПН (основного функціонально повного набору). Стосовно до такого набору булева алгебра своєму розпорядженні ряд аксіом і законів, основними з яких є:
Система аксіом:

Аксіома (1) є твердженням того, що в алгебрі логіки розглядаються тільки двійкові змінні, аксіоми (2) ... (5) визначають операції диз'юнкції і кон'юнкції, а аксіома (5) - операцію заперечення. Якщо в аксіоми (2) ... (5), заданих парами, зробити взаємну заміну операцій диз'юнкції і кон'юнкції, а також елементів 0 і 1, то з однієї аксіоми пари вийде інша. Це властивість називається принципом двоїстості.
Теореми і тотожності алгебри логіки
За допомогою аксіом алгебри логіки можна довести цілий ряд теорем і тотожностей. Одним з ефективних методів доказу теорем є метод перебору всіх значень змінних: якщо теорема істинна, то з урахуванням (2) ... (5) рівняння, формулює твердження теореми, має бути істинно при підстановці будь-яких значень змінних в обидві його частини.
Метод перебору не занадто трудомісткий, так як змінні можуть мати тільки два значення: 0 і 1.
Так, методом перебору легко переконатися у справедливості таких теорем:
Ідемпотентний закони (закони тотожності):
(6)
Комутативні закони (переместительное):
(7)
Асоціативні закони (сочетательних):
(8)

Дистрибутивні закони:
(9)
Закони заперечення:
(10)
(11)
(12)
Закони подвійності (Теореми де Моргана):
(13)
Закон подвійного заперечення:
(14)

Закони поглинання (абсорбція):
(15)
Операції склеювання:
(16)
Операції узагальненого склеювання:
(17)
(18)
Теореми (6) ... (13) і (15) ... (18) записані парами, причому кожна з теорем пари двоїста інший, так як з однієї теореми пари можна отримати іншу на підставі принципу подвійності, тобто шляхом взаємної заміни операцій диз'юнкції і кон'юнкції , а також елементів 0 і 1, якщо вони є. Теорема (14) самодвойственна, так як вона не змінюється за принципом двоїстості (відсутні елементи 0 і 1 і операції диз'юнкції і кон'юнкції). Всі теореми можуть бути доведені аналітично або методом перебору. Як приклад наведемо доказ тотожності (13) методом перебору (табл. 1).

Таблиця 1
x
y


0
0


0
1


1
0


1
1


Якщо в логічне вираження входять операції диз'юнкції і кон'юнкції, то слід дотримуватися порядок виконання операцій: спочатку виконується операція кон'юнкції, а потім - операція диз'юнкції. Цим встановлюється ієрархія операцій: кон'юнкція - старша операція, диз'юнкція - молодша.
У складних логічних виразах для завдання порядку виконання операцій використовуються дужки. Для спрощення запису виразів прийнято опускати ті дужки, які є тільки підтвердженням ієрархії операцій, наприклад:
.
Але дужки можна опустити у виразі , Оскільки
.
Деякі теореми і тотожності алгебри логіки мають особливе значення, оскільки дозволяють спрощувати логічні вирази. Наприклад, у співвідношеннях (6), (10) ... (12) і (15) ... (18) права частина простіше лівою, тому, зробивши в логічних виразах відповідні перетворення, можна домогтися суттєвого їх спрощення. З цією метою особливо часто використовуються тотожності (15) ... (18).
Перераховані формули наводяться без доказів, але переконатися в їх справедливості можна, підставивши в праві і ліві частини рівностей значення змінних 0 і 1. Ці формули не вичерпують можливих булевих рівностей, але вони є основними при перетворенні булевих функцій.
Операції диз'юнкції, кон'юнкції і заперечення легко реалізувати досить простими контактами (релейними) ланцюгами і електронними схемами з односторонньою провідністю, що мають кінцеве число входів і один вихід. Найпростіші електронні схеми, що реалізують елементарні булеві функції (НЕ, І, АБО, АБО-НЕ, І-НЕ), називаються логічними елементами (ЛЕ).
Аналітична форма подання булевих функцій
При вирішенні конкретних технічних завдань булеві функції, що відбивають логічні зв'язки, найбільш часто задаються в табличній формі. Проте така форма завдання функцій при всій її наочності не дозволяє відповісти на запитання, яким чином реалізувати і якщо можна, то спростити цю функцію. Для реалізації і подальшого спрощення булеву функцію слід представити в аналітичній формі в одному з функціонально повних наборів. Оскільки в даний час методи подання і мінімізації функцій найбільш повно розроблені в базисі ОФПН, то саме цей базис в подальшому і буде розглядатися.
Припустимо, що в ході виконання завдання потрібно реалізувати переключательную функцію, задану таблицею 2.

Таблиця 2
Номер
набору
Аргументи
Значення функції на i-му наборі



0
0
0
0
0
1
0
0
1
0
2
0
1
0
0
3
0
1
1
1
4
1
0
0
0
5
1
0
1
0
6
1
1
0
1
7
1
1
1
1
Як видно з таблиці, функція повинна приймати значення 1 тільки на 3-му, 6-му та 7 наборах. На всіх інших наборах її значення дорівнює 0. Виникає питання, яким чином записати цю функцію аналітично, тобто представити у вигляді формули. Стосовно до основного базису, який містить елементи диз'юнкції, кон'юнкції і заперечення, доведено, що будь-яка Переключательная функція, попередньо задана в табличній формі, може бути записана аналітично в двох формах, які отримали назву канонічних (нормальних): у диз'юнктивній досконалої нормальної формі (ДСНФ) і у кон'юнктивній досконалої нормальної формі (КСНФ).
Аналітична запис функцій у вигляді ДСНФ і КСНФ передбачає представлення цих функцій за допомогою суперпозиції спеціально вводяться допоміжних функцій: минтермов і макстермов.
Минтерм часто називають конституентами одиниці, а макстерми - конституентами нуля. Минтерм називають булево твір (кон'юнкцію) від n змінних, в якому кожна змінна входить один раз на прямий мул інверсної формі. Макстермом називають булеву суму від n змінних, в якій кожна змінна входить один раз в прямій або інверсної формі.
Звідси випливає, що Переключательная функція від n змінних має число минтермов і макстермов, яка дорівнює кількості наборів, на яких вона визначена, тобто минтермов і макстермов.
Як приклад наведемо минтерм і макстерми двох змінних X 1 і X 2 (табл. 3 та 4).
Таблиця 3.
Аргументи
Минтерм






0
0
1
0
0
0
0
1
0
1
0
0
1
0
0
0
1
0
1
1
0
0
0
1
Таблиця 4.
Аргументи
Макстерми






0
0
0
1
1
1
0
1
1
0
1
1
1
0
1
1
0
1
1
1
1
1
1
0
Згідно з наведеними визначеннями минтерм і макстерми двох аргументів виражаються формулами:

Запис перемикача функції у вигляді ДСНФ означає, що будь-яка Переключательная функція, задана табличним способом, може бути представлена ​​у вигляді логічної суми кон'юнктивні членів. При цьому кожен з цих членів являє собою твір значення функції на i-му наборі на i-ий минтерм. Оскільки Переключательная функція має минтермов, то аналітична запис функції в ДСНФ має вигляд:
.
Таким чином, функція, задана таблицею станів (табл. 1.8), запишеться аналітично наступним чином:

Терміни скороченого представлення функції у вигляді ДСНФ зокрема означають: термін «диз'юнкція» вказує на те, що зовнішньою функцією розкладання є диз'юнкція, а внутрішньою - кон'юнкція.
Термін «досконала» вказує на те, що диз'юнктивні члени формуються з усіх аргументів X 1 ... X n, тобто на основі минтермов.
Термін «нормальна» вказує на те, що форма запису є дворівневою, тобто диз'юнкція кон'юнкція.
Аналітична запис функції у вигляді КСНФ означає, що Переключательная функція, задана табличним способом, може бути представлена ​​у вигляді логічного твору (кон'юнкція) диз'юнктивних членів. При цьому кожен з цих членів є сумою значень функції на i-му наборі і i-ого макстерма.
Оскільки від n аргументів існує макстермов, то аналітична запис функції в КСНФ має вигляд:


У результаті для розглянутого прикладу (табл. 1.8):

або

Зіставляючи дві форми запису однієї і тієї ж перемикача функції легко переконатися, що запис функції у вигляді КСНФ більш громіздка, оскільки містить більше число членів. Це пояснюється тим, що кількість наборів, на яких Переключательная функція дорівнює 0, значно більше числа наборів, на яких функція дорівнює 1. Для випадку, коли число наборів, на яких функція дорівнює 0, було б менше числа наборів, на яких функція дорівнює 1, більш кращим виявляється представлення функції у вигляді КСНФ. Звідси випливає, що обидві форми представлення функцій фактично еквівалентні. Однак при мінімізації функцій більш зручною виявляється запис їх у вигляді ДСНФ. Тому надалі будемо розглядати тільки такі форми.

ЛІТЕРАТУРА
1. Новіков Ю.В. Основи цифрової схемотехніки. Базові елементи і схеми. Методи проектування. М.: Світ, 2001. - 379 с.
2. Новіков Ю.В., Скоробогатов П.К. Основи мікропроцесорної техніки. Курс лекцій. М.: ІНТУІТ.РУ, 2003. - 440 с.
3. Пухальський Г.І., Новосельцева Т.Я. Цифрові пристрої: Учеб. посібник для Втузов. СПб.: Політехніка, 2006. - 885 с.
4. Преснухін Л.М., Воробйов Н.В., Шішкевіч А.А. Розрахунок елементів цифрових пристроїв. М.: Вищ. шк., 2001. - 526 с.
5. Букрєєв І.М., Горячев В.І., Мансуров Б.М. Мікроелектронні схеми цифрових пристроїв. М.: Радіо і зв'язок, 2000. - 416 с.
6. Соломатін Н.М. Логічні елементи ЕОМ. М.: Вищ. шк., 2000. - 160 с.
Додати в блог або на сайт

Цей текст може містити помилки.

Комунікації, зв'язок, цифрові прилади і радіоелектроніка | Реферат
67.4кб. | скачати


Схожі роботи:
Системи булевих функцій
Повні системи булевих функцій
Функції алгебри логіки Логічний базис
Вивчення функцій та їх графіків на елективної курсі з алгебри у 9 класі
Генетика і еволюція Основні аксіоми біології
Основні поняття алгебри множин
Розвиток функціональної лінії в курсі алгебри 7-9 класів на прикладі підручників з алгебри під ред
Розвиток функціональної лінії в курсі алгебри 9 липня класів на прикладі підручників з алгебри під ред
Основні етапи історії логіки
© Усі права захищені
написати до нас