Студопедия  
Главная страница | Контакты | Случайная страница

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

Нормальные формы булевых функций

Читайте также:
  1. B) Количественная определенность относительной формы стоимости
  2. I Справка по содержанию аргументов финансовых функций
  3. I. Основные формы исследования ППО
  4. IV. Формы контроля за исполнением Административного регламента
  5. Microsoft Excel. Назначение и синтаксис функций ВПР, ИНДЕКС.
  6. Microsoft Excel. Назначение и синтаксис функций ДАТА, ВРЕМЯ, ТДАТА, СЕГОДНЯ.
  7. Quot;Великие реформы" 60-х – 70-х гг. XIX века.
  8. VI. ВИДЫ И ФОРМЫ ОРГАНИЗАЦИИ
  9. VII. Разделите следующие явления на общие и частичные нарушения функций мозга
  10. VII.II. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО выполнению контрольных работ для студентов заочной формы обучения

Теорема. Пусть f (x 1, x 2,…, xn) – произвольная булева функция. Тогда

f (x 1, x 2,…, xn) = x 1× f (1, x 2,…, xn) Ú x 1’× f (0, x 2,…, xn);

f (x 1, x 2,…, xn) = (x 1Ú f (0, x 2,…, xn))(x 1’Ú× f (1, x 2,…, xn)).

Последовательно применяя данное разложение по переменным x 1, x 2,…, xn, можно получить формулу, содержащую лишь дизъюнкции, конъюнкции и отрицания. Например,

f (x, y) = f (1,1) xy Ú f (1,0) xy ’Ú f (0,1) xy Ú f (0,0) xy ’, (7)

f (x, y) = (f (1,1)Ú x ’Ú y ’)(f (1,0)Ú x ’Ú y)(f (0,1)Ú x Ú y ’)(f (0,0)Ú x Ú y). (8)

Разложение вида (7) называют совершенной дизъюнктивной нормальной формой (СДНФ), а разложение вида (8) — совершенной конъюнктивной нормальной формой (СКНФ). Нетрудно видеть, что в СДНФ (7) можно отбросить те слагаемые, для которых f (a, b)=0, а в СКНФ (8) — сомножители, где f (a, b)=1.

Элементарной конъюнкцией (конъюнктом) называют конъюнкцию переменных, быть может с их отрицаниями, в которой каждая переменная встречается не более одного раза.

Дизъюнкцию конечного числа конъюнктов называют дизъюнктивной нормальной формой (ДНФ). Таким образом, разложение (7) представляет собой ДНФ. Отличие СДНФ от ДНФ заключается в том, что в совершенной форме каждое слагаемое (конъюнкт) содержит все переменные и/или их отрицания.

Аналогичные определения со взаимной заменой дизъюнкций на конъюнкции приводят к понятиям: э лементарная дизъюнкция (дизъюнкт) и конъюнктивная нормальная форма (КНФ).

Принцип двойственности имеет место и для булевых функций. Двойственной к булевой функции f (x, y,…, z) называется функция

f *(x, y,…, z)= f ’(x ’, y ’,…, z ’).

Теорема. Если f (x, y,…, z) представлена формулой, содержащей лишь дизъюнкции, конъюнкции и отрицания, то двойственная функция f *(x, y,…, z) получается заменой в исходной формуле дизъюнкций на конъюнкции, а конъюнкций на дизъюнкции.

Примеры

1. Найти СДНФ и СКНФ для следующей функции:

xy | f

0 0 | 0

0 1 | 1

1 0 | 0

1 1 | 0

Решение. Воспользуемся разложениями (7) и (8):

f (x, y)= f (1,1) xy Ú f (1,0) xy ’Ú f (0,1) xy Ú f (0,0) xy ’=

=0 xy Ú0 xy ’Ú1 xy Ú0 xy ’= xy, (СДНФ)

f (x, y)=(f (1,1)Ú x ’Ú y ’)(f (1,0)Ú x ’Ú y)(f (0,1)Ú x Ú y ’)(f (0,0)Ú x Ú y)=

=(0Ú x ’Ú y ’)(0Ú x ’Ú y)(1Ú x Ú y ’)(0Ú x Ú y)=)=(x ’Ú y ’)(x ’Ú y)(x Ú y). (СКНФ)

2. Построить СДНФ двойственной функции к f (x, y, z)= x ’→ yz.

Решение. Способ I. Воспользуемся определением двойственной формулы:

f *(x, y, z)= f ’(x ’, y ’, z ’)=(x ’’→ yz ’)’=(xyz ’)’=(x ’Ú yz ’)’=

=x ’’(yz ’)’= x (y Ú z)= xy Ú xz.

Способ II. Воспользуемся теоремой двойственности. Исключим тождественными преобразованиями импликацию:

f (x, y, z)= x ’→ yz = x Ú yz.

Далее, заменим символы конъюнкции и дизъюнкции друг на друга:

f *(x, y, z)= x (y Ú z)= xy Ú xz.

Вопросы и упражнения для самостоятельной работы

4. Построить СДНФ и СКНФ для функций f 1, f 2, f 3 и f 4, заданных таблицей

x y z | f 1 f 2 f 3 f 4

0 0 0 | 0 1 1 1

0 0 1 | 0 0 1 1

0 1 0 | 1 1 0 1

0 1 1 | 1 1 0 1

1 0 0 | 1 0 1 1

1 0 1 | 1 0 0 1

1 1 0 | 1 1 0 1

1 1 1 | 1 0 0 1

5. Построить СДНФ и СКНФ для следующих функций:

а) x | y, б) xy, в) (x Å y)↓ z, г) x «(y Ú z), д) xy Å yz Å xz.

6. Построить двумя способами СКНФ и СДНФ двойственных функций f * для следующих функций:

а) x | y, б) xy, в) x Å y г) x Å yz, д) x |(y Å z).




Дата добавления: 2015-04-11; просмотров: 22 | Поможем написать вашу работу | Нарушение авторских прав

1 | 2 | <== 3 ==> | 4 | 5 |


lektsii.net - Лекции.Нет - 2014-2024 год. (0.01 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав