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

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

Версия 07:28, 17 января 2011

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

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

Определение:
Сокращенная ДНФ: форма записи функции, обладающая следующими свойствами:
  1. Никакие два слагаемых нельзя объединить по рассмотренному выше правилу.
  2. Ни один из конъюнктов не является подмножеством другого. Например, [math](x \land y)[/math] — подмножество [math](x \land y \land z)[/math].
Функцию можно записать с помощью сокращенной ДНФ не единственным способом.


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

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

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

См. также

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