Сокращённая и минимальная ДНФ — различия между версиями
| Строка 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> |
{{Определение | {{Определение | ||
|definition = | |definition = | ||
Сокращенная ДНФ: форма записи функции, обладающая следующими свойствами:<br> | Сокращенная ДНФ: форма записи функции, обладающая следующими свойствами:<br> | ||
1. Никакие два слагаемых нельзя объединить по рассмотренному выше правилу.<br> | 1. Никакие два слагаемых нельзя объединить по рассмотренному выше правилу.<br> | ||
| − | 2. Ни один из конъюнктов не является подмножеством другого (например, < | + | 2. Ни один из конъюнктов не является подмножеством другого (например, <tex>(x \wedge y)</tex> - подмножество <tex>(x \wedge y \wedge z)</tex>).<br> |
Функцию можно записать с помощью сокращенной ДНФ не единственным способом. | Функцию можно записать с помощью сокращенной ДНФ не единственным способом. | ||
}} | }} | ||
== Минимальная ДНФ == | == Минимальная ДНФ == | ||
| + | {{Определение | ||
| + | |definition = | ||
Минимальная ДНФ - та сокращенная ДНФ, в которой содержится минимальное количество переменных. | Минимальная ДНФ - та сокращенная ДНФ, в которой содержится минимальное количество переменных. | ||
| + | }} | ||
Каждая минимальная ДНФ является сокращенной, но не каждая сокращенная - минимальна.<br> | Каждая минимальная ДНФ является сокращенной, но не каждая сокращенная - минимальна.<br> | ||
Минимальная ДНФ представляет функцию в наиболее удобно для работы с ней виде. | Минимальная ДНФ представляет функцию в наиболее удобно для работы с ней виде. | ||
Версия 03:36, 12 октября 2010
Сокращенная ДНФ
Запишем известную функцию <x,y,z> (медиана) в СДНФ:
. Известно, что это выражение равносильно следующему: . Вынесем в каждой скобке общий конъюнкт (например, в первой . Т.к. , то такой конъюнкт не влияет на значение выражения, и его можно опустить. Получим в итоге формулу .
| Определение: |
| Сокращенная ДНФ: форма записи функции, обладающая следующими свойствами: 1. Никакие два слагаемых нельзя объединить по рассмотренному выше правилу. |
Минимальная ДНФ
| Определение: |
| Минимальная ДНФ - та сокращенная ДНФ, в которой содержится минимальное количество переменных. |
Каждая минимальная ДНФ является сокращенной, но не каждая сокращенная - минимальна.
Минимальная ДНФ представляет функцию в наиболее удобно для работы с ней виде.
