Сокращённая и минимальная ДНФ — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Сокращенная ДНФ)
Строка 1: Строка 1:
 
== Сокращенная ДНФ ==
 
== Сокращенная ДНФ ==
Запишем известную функцию ''<x,y,z>'' (медиана) в СДНФ:
+
Запишем известную [[Определение булевой функции|функцию]] ''<x,y,z>'' (медиана) в [[СДНФ]]:
<tex>(x \wedge y \wedge z) \vee (x \wedge y \wedge \neg z) \vee (x \wedge \neg y \wedge z) \vee (\neg x \wedge y \wedge z)</tex>. Известно, что это выражение равносильно следующему: <tex>((x \wedge y \wedge z) \vee (x \wedge y \wedge \neg z)) \vee ((x \wedge \neg y \wedge z) \vee (x \wedge y \wedge z)) \vee ((\neg x \wedge y \wedge z) \vee (x \wedge y \wedge z))</tex>. Вынесем в каждой скобке общий конъюнкт (например, в первой <tex>(x \wedge y \wedge z) \vee (x \wedge y \wedge \neg z)=(x \wedge y) \vee (z \wedge \neg z))</tex>. Т.к. <tex>z \wedge \neg z = 0</tex>, то такой конъюнкт не влияет на значение выражения, и его можно опустить. Получим в итоге формулу <tex>(x \wedge y) \vee (y \wedge z) \vee (x \wedge z)</tex>.<br><br>
+
<tex>(x \wedge y \wedge z) \vee (x \wedge y \wedge \neg z) \vee (x \wedge \neg y \wedge z) \vee (\neg x \wedge y \wedge z)</tex>.
 +
Известно, что это выражение равносильно следующему:
 +
<tex>((x \wedge y \wedge z) \vee (x \wedge y \wedge \neg z)) \vee ((x \wedge \neg y \wedge z) \vee (x \wedge y \wedge z)) \vee ((\neg x \wedge y \wedge z) \vee (x \wedge y \wedge z))</tex>.
 +
Вынесем в каждой скобке общий конъюнкт (например, в первой <tex>(x \wedge y \wedge z) \vee (x \wedge y \wedge \neg z)=(x \wedge y) \vee (z \wedge \neg z))</tex>. Т.к. <tex>z \wedge \neg z = 0</tex>, то такой конъюнкт не влияет на значение выражения, и его можно опустить.
 +
Получим в итоге формулу <tex>(x \wedge y) \vee (y \wedge z) \vee (x \wedge z)</tex>.<br><br>
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Строка 9: Строка 13:
 
Функцию можно записать с помощью сокращенной ДНФ не единственным способом.
 
Функцию можно записать с помощью сокращенной ДНФ не единственным способом.
 
}}
 
}}
 +
 
== Минимальная ДНФ ==
 
== Минимальная ДНФ ==
 
{{Определение
 
{{Определение

Версия 08:51, 21 ноября 2010

Сокращенная ДНФ

Запишем известную функцию <x,y,z> (медиана) в СДНФ: [math](x \wedge y \wedge z) \vee (x \wedge y \wedge \neg z) \vee (x \wedge \neg y \wedge z) \vee (\neg x \wedge y \wedge z)[/math]. Известно, что это выражение равносильно следующему: [math]((x \wedge y \wedge z) \vee (x \wedge y \wedge \neg z)) \vee ((x \wedge \neg y \wedge z) \vee (x \wedge y \wedge z)) \vee ((\neg x \wedge y \wedge z) \vee (x \wedge y \wedge z))[/math]. Вынесем в каждой скобке общий конъюнкт (например, в первой [math](x \wedge y \wedge z) \vee (x \wedge y \wedge \neg z)=(x \wedge y) \vee (z \wedge \neg z))[/math]. Т.к. [math]z \wedge \neg z = 0[/math], то такой конъюнкт не влияет на значение выражения, и его можно опустить. Получим в итоге формулу [math](x \wedge y) \vee (y \wedge z) \vee (x \wedge z)[/math].

Определение:
Сокращенная ДНФ: форма записи функции, обладающая следующими свойствами:

1. Никакие два слагаемых нельзя объединить по рассмотренному выше правилу.
2. Ни один из конъюнктов не является подмножеством другого (например, [math](x \wedge y)[/math] - подмножество [math](x \wedge y \wedge z)[/math]).

Функцию можно записать с помощью сокращенной ДНФ не единственным способом.


Минимальная ДНФ

Определение:
Минимальная ДНФ - та сокращенная ДНФ, в которой содержится минимальное количество вхождений переменных.

Каждая минимальная ДНФ является сокращенной, но не каждая сокращенная - минимальна. Например, запись [math](x \wedge y) \vee (y \wedge z) \vee (x \wedge z)[/math] является минимальной ДНФ для медианы (она же сокращенная, как видно в примере выше); а запись [math](x \wedge y \wedge \neg z) \vee (\neg x \wedge y \wedge z) \vee (x \wedge z)[/math] - не минимальная, но сокращенная ДНФ.
Минимальная ДНФ представляет функцию в наиболее удобно для работы с ней виде.

См. также

Минимизация ДНФ с помощью покрытий гиперкуба и карт Карно