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