АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Карти Карно

Читайте также:
  1. Вклад кибернетики в научную картину мира
  2. Внутренняя картина болезни
  3. Возникновение новых научных картин мира.
  4. Географічна основа карти
  5. Групи зчеплення. Генетичні карти організмів.
  6. Закони збереження в мікросвіті. Сучасна фізична картина світу. Досягнення та проблеми сучасної фізики. Роль українських вчених у розвитку фізики
  7. Как СТРУКТУРНАЯ БЕЗДНА Мироздания порождает Ведическую картину Мира.
  8. Какая у меня картинка
  9. Картина 1.
  10. Картина 17. Смерть девчат
  11. Картина 2.

Означення 3.1. Диз’юнкція всіх простих імплікант називається скороченою ДНФ функції.

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

Прикладом скороченої ДНФ є .

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

Скорочену ДНФ можна отримати з довільної ДНФ, використовуючи процедуру, що називається методом Блейка:

1. Застосовувати, скільки можливо, закон поглинання

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

2. Застосовувати, скільки можливо, правило поглинання

Потім видалити повторні входження кон'юнкцій.

ТЕОРЕМА 3.1. У результаті використання методу Блейка для довільної ДНФ через скінченне число кроків буде отримана еквівалентна їй скорочена ДНФ.

Приклад 3.1. Використовуючи метод Блейка для досконалої ДНФ функції f (p, q, r), що приймає значення TRUE для (F,F,T), (F,T,F), (F,T,T), (T,F,T), побудувати скорочену.

Досконала ДНФ:

.

Застосуємо закон поглинання:

Застосуємо правило поглинання:

.

Отже, скороченою ДНФ для функції f є .

Означення 3.3. Тупикова диз’юнктивна нормальна форма – це ДНФ, у якій відкидання будь-якої кон’юнкції приводить до нееквівалентної ДНФ. Мінімальна ДНФ є тупиковою, але не всяка тупикова є мінімальною.

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

Картою Карно є матриця розмірності (n = k + l) з 2 n клітинками, у якій кожен рядок однозначно відповідає деякій елементарній кон’юнкції перших k змінних, а кожний стовпчик – елементарній кон’юнкції решти l змінних, таким чином, що сусідні елементи (мають спільну границю, перший і останній рядки (стовпці) вважаються сусідніми) в кожному рядку та в кожному стовпчику відрізняються лише одним літералом. Кожна клітинка відповідає деякій елементарній кон’юнкції. Нуль або одиниця у клітинці таблиці визначає значення функції на даній інтерпретації.

Приклад 3.2. Структура карт Карно для функцій від двох n =2, k =1, l =1 (табл. 3.1) і трьох n =3, k =1, l =2 (табл. 3.2) змінних наведена нижче.

Таблиця 3.1

Карта Карно для функції двох змінних

p q    
 
 

Таблиця 3.2

Карта Карно для функції троьх змінних


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)