Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Минимизации функций

Читайте также:
  1. Аналитическое представление функций
  2. Базовым принципом концепции NGN является отделение друг от друга функций переноса и коммутации, функций управления вызовом и функций управления услугами.
  3. Взаимосвязь финансовых инструментов государства его функций и видов финансовой политики
  4. Вопрос 32. Цели деятельности и характеристика функций Центрального банка Российской Федерации.
  5. Вопрос 43. Инвестиционные риски и направления их минимизации.
  6. Вопрос №6: Понятие и система функций и основных направлений деятельности прокуратуры.
  7. Вычисление значений тригонометрических функций

Для начала вам надо уметь составлять СДНФ и СКНФ, потому что это, скорее всего, тоже будет в контрольной. Что это такое можно прочитать и в материалах, и в других доступных источниках. Если кратко, то СКНФ - совершенно конъюнктивная нормальная форма, а СДНФ - совершенно дизъюнктивная нормальная форма.

Совершенно конъюнктивная НФ - конъюнкция дизъюнкций, причём в каждой дизъюнкции (в каждой скобке) присутствуют все переменные, входящие в формулу, либо их отрицание, нет одинаковых дизъюнкций, в каждой дизъюнкции нет одинаковых слагаемых:

СКНФ:

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

СДНФ:

Теперь рассмотрим пример, в котором по таблице истинности построим СДНФ и СКНФ, а затем уже перейдём к минимизации.

Для примера возьмём функцию с тремя переменными и уже разобранную на занятии.

  F
         
         
         
         
         
         
         
         

 

Рассмотрим по пунктам, как составить СДНФ:

1. Записываем произведение наборов переменных (), если функция равна 1 (F=1);

2. Берём переменную с отрицанием, если её значение равно 0 ();

3. Между каждым произведением набора переменных ставим знак логического сложения ().

Теперь составим СДНФ для нашей таблицы истинности.

СДНФ:

 

 

Рассмотрим по пунктам, как составить СКНФ:

1. Записываем произведение наборов переменных (), если функция равна 0 (F=0);

2. Берём переменную с отрицанием, если её значение равно 1 ();

3. Между каждым произведением набора переменных ставим знак логического сложения ().

Составим СКНФ для таблицы истинности.

СКНФ:

Теперь перейдём к минимизации функций.

Сначала рассмотрим способ, с помощью которого мы будет упрощать СДНФ и СКНФ. Начнём с СДНФ:

Теперь ищем пары слагаемых, которые отличаются только одной переменной, то есть в одном случае она с отрицанием, в другом – без. Выделяем такие пары (тут такие пары будут выделены одинаковыми цветами):

Но стоит заметить, что если разбить слогаемые на пары, то одно из слогаемых останется без пары. И тут мы обращаемся к аксиомам алгебры логики: . Исходя из этого, делаем следующие преобразования:

Теперь делим слогаемые на пары и выносим за скобки одинаковые переменные, после чего содержимое скобок сокращаются (как и почему это происходит, вы должны знать):

Теперь перейдём к минимизации СКНФ. Принцип такой же, как и с СДНФ:

Скорее всего контрольная у нас будет по СДНФ, но к СКНФ тоже надо быть готовым. А теперь то, что точно будет в контрольной. Карты Карно – ещё один способ минимизации.

Работать будем уже с имеющейся у нас таблицей истинности. Для начала рисуем такую таблицу:

0 0 0 1 1 1 1 0
 
 

 

Отдельно нужно отметить нумерацию внутри таблицы. Это вам стоит запомнить.

Теперь заполняем таблицу. Соответствующие клетки заполняем 1, если F=1, и оставляем пустыми либо ставим 0, если F=0:

0 0 0 1 1 1 1 0
  1 ₀ 1 ₁ 1 ₃ 1 ₂
  1 ₄ 0 ₅ 0 ₇ 0 ₆

 

Теперь ищем группы соседних 1, которые зацикливаются. Соседними являются 1, стояие рядом друг с другом по горизонтали и по вертикали. Так же соседними являются крайние 1, то есть 1 из клетки 0 являяется соседней с 1 из клетки 2. Если трудно понять, что значит «зацикливаются», то можете запомнить, что группы единиц могут состоять из 2, 4, 8 и любому другому колличеству единиц равному . А зациклиться такие группы могут только в квадрате или прямоугольнике. Так же в разные группы, при необходимости, могут попадать одни и теже 1. В конце я рассмотрю её пару отдельных случаев, а пока вернёмся к примеру. Итак, выделяем группы:

0 0 0 1 1 1 1 0
0 1 ₀ 1 ₁ 1 ₃ 1 ₂
  1 ₄ 0 ₅ 0 ₇ 0 ₆

 

Пусть группа, выделенная чёрным, будет группой 1, а выделенная красным – группой 2. Смотрим в группах переменные, которые остаются неизменными. В группе 1 это , а в группе два - и . Теперь смотрим, какие значения у этих переменных: если 0, то берём переменную с отрицание, если 1, то без. И у нас получается следующее уравнение:

Теперь ещё немного о картах Карно. У нас в контрольных будут функции с тремя и четырьмя переменными, так что вот таблица для четырёх переменных, её нужно обязательно запомнить, особенно нумерацию.

0 0 0 1 1 1 1 0
0 0
0 1
1 1 ₁₂ ₁₃ ₁₅ ₁₄
1 0 ₁₁ ₁₀

 

А сейчас на такой таблице рассмотрим ещё два случая, связанных с группами из 1:

0 0 0 1 1 1 1 0
0 0 1 ₀ 1 ₁
0 1 1 ₄ 1 ₅ 1 ₇ 1 ₆
1 1 ₁₂ 1 ₁₃ ₁₅ 1 ₁₄
1 0 1 ₈ 1 ₁₁ 1 ₁₀

 

Тут почти все 1 отнесенны к группам. Остальсь только 1 из клеток 14 и 8. Сначала посмотрим на 1 в клетке 14. Она соседня с 1 из клеток 6 и 10. Но, как мы уще знаем, нельзя делать группу из трёх 1. Следовательно, можно объеденить ту 1 в группу с 1 либо из клетки 6, либо из клетки 10. И то, и то будет верно. Но нельзя объединять 1 и с 1 из клетки 6, и из клетки 10. То есть либо так:

0 0 0 1 1 1 1 0
0 0 1 ₀ 1 ₁
0 1 1 ₄ 1 ₅ 1 ₇ 1 ₆
1 1 ₁₂ 1 ₁₃ ₁₅ 1 ₁₄
1 0 1 ₈ 1 ₁₁ 1 ₁₀

Либо так:

0 0 0 1 1 1 1 0
0 0 1 ₀ 1 ₁
0 1 1 ₄ 1 ₅ 1 ₇ 1 ₆
1 1 ₁₂ 1 ₁₃ ₁₅ 1 ₁₄
1 0 1 ₈ 1 ₁₁ 1 ₁₀

Осталась 1 в клетке 8. Тут всё просто. Если 1 не с кем зациклить, то она зацикливается сама на себе. Выглядеть это будет так:

0 0 0 1 1 1 1 0
0 0 1 ₀ 1 ₁
0 1 1 ₄ 1 ₅ 1 ₇ 1 ₆
1 1 ₁₂ 1 ₁₃ ₁₅ 1 ₁₄
1 0 1 ₈ 1 ₁₁ 1 ₁₀

 

Ну, вроде, всё. Будут вопросы, обращайтесь. Успехов всем на контрольной!

 


Дата добавления: 2015-08-17; просмотров: 56 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Незамкнутая магнитная система.| Генетическая предрасположенность.

mybiblioteka.su - 2015-2024 год. (0.01 сек.)