80
правок
Изменения
Новая страница: «== Сокращенная ДНФ == Запишем известную функцию ''<x,y,z>'' (медиана) в СДНФ: <math>(x \and y \and z) \or (x \and y …»
== Сокращенная ДНФ ==
Запишем известную функцию ''<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>
Сокращенная ДНФ: форма записи функции, обладающая следующими свойствами:<br>
1. Никакие два слагаемых нельзя объединить по рассмотренному выше правилу.<br>
2. Ни один из конъюнктов не является подмножеством другого (например, <math>(x \and y)</math> - подмножество <math>(x \and y \and z)</math>).<br>
Функцию можно записать с помощью сокращенной ДНФ не единственным способом.
== Минимальная ДНФ ==
Минимальная ДНФ - та сокращенная ДНФ, в которой содержится минимальное количество переменных.
Каждая минимальная ДНФ является сокращенной, но не каждая сокращенная - минимальна.<br>
Минимальная ДНФ представляет функцию в наиболее удобно для работы с ней виде.
Запишем известную функцию ''<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>
Сокращенная ДНФ: форма записи функции, обладающая следующими свойствами:<br>
1. Никакие два слагаемых нельзя объединить по рассмотренному выше правилу.<br>
2. Ни один из конъюнктов не является подмножеством другого (например, <math>(x \and y)</math> - подмножество <math>(x \and y \and z)</math>).<br>
Функцию можно записать с помощью сокращенной ДНФ не единственным способом.
== Минимальная ДНФ ==
Минимальная ДНФ - та сокращенная ДНФ, в которой содержится минимальное количество переменных.
Каждая минимальная ДНФ является сокращенной, но не каждая сокращенная - минимальна.<br>
Минимальная ДНФ представляет функцию в наиболее удобно для работы с ней виде.
