Построение СДНФ и СКНФ методом эквивалентных преобразований

[c0d3r]

Здравствуйте.
У меня имеется 2 задания, в одном из них требуется построить СДНФ 2мя способами: через таблицу истинности и путем эквивалентных преобразований формулы, во втором нужно сделать то же самое, только для СКНФ.
Вроде бы как понимаю в общем что это такое и понимаю теорию, наизусть тоже помню большинство свойств\тождеств булевой алгебры и статьи (к примеру в википедии) по составлению СДНФ, СКНФ прочел и понял, однако возникают проблемы...
Первым способом (через таблицу истинности) у меня получилось составить и СДНФ и СКНФ и сложностей особо не вызвало...
Но вот построить то же самое через эквивалентные преобразования, к сожалению, не получается.
Я сидел над этим несколько часов, читал теорию по Андресону ("Дискретная математика и комбинаторика") и Новикову("Дискретная математика для программистов"), в принципе я и другой литературы по дискретной математике читал, но там, где именно об этом больше вычитывал, то да.. Также посмотрел пару лекций на ИНТУИТе и прочел соотв. статьи из википедии, ну и, конечно же, прочёл те лекции, что у меня в конспекте записаны.
Но когда я составляю СДНФ и СКНФ через эквивалентные преобразования, то в результате они, мягко говоря, не везде сходятся.

Подозреваю, что, возможно, я не там где нужно и\или не так как нужно применяю свойство дистрибутивности. Может быть есть какие-то "правила\советы" насчёт того как и над чем и каким образом их применять где-либо?

Прилагаю мои попытки решения:


P.S.: Прошу прощения за то, что, возможно, не очень понятный почерк.. Просто я это переписывал по несколько раз и боялся, что ничего не успею, поэтому приходилось писать быстро.
Помогите, пожалуйста, разобраться, если можно[offtop], т.к. науки и вообще учеба и т.п. - это достаточно важные вещи в моей жизни и они играют одно из ключевых значений, которые, к тому же, определяют моё настроение и т.д., собственно говоря мне хочется хорошо понимать все эти темы, разбираться в них и т.п., в общем ладно, не важно.[/offtop].

[Chifu]

Дважды проинвертируйте и примените закон де Моргана.

[c0d3r]

Цитата:

Дважды проинвертируйте и примените закон де Моргана.

Спасибо за совет, однако, наверное, это вы так пошутили?)

Т.к. вроде как двойное отрицание, к примеру, А это и есть само А. Собственно инволютивность отрицания.

Ошибки мне уже помогли найти, так что в принципе проблема решена. Тему можно закрывать.

[Joker_vD]

Вообще, есть такой трюк: преобразованиями СДНФ построить довольно легко, а вот СКНФ — не очень, мешают психологические причины... так вот, трюк такой: пишется формула, двойственная к исходной, ищется ее СДНФ, а потом выписивывается двойственная ней — это и будет СКНФ исходной формулы.

[Chifu]

c0d3r в сообщении #492216 писал(а):

Спасибо за совет, однако, наверное, это вы так пошутили?)

Нет, это что-то вроде определения СКНФ, можно сразу СКНФ искать, а можно и СДНФ инверсной функции, а далее она с помощью второй инверсии и закона де Моргана преобразуется в СКНФ.

Цитата:

Т.к. вроде как двойное отрицание, к примеру, А это и есть само А. Собственно инволютивность отрицания.

А вы в результате тождественных преобразовений что-то не тождественное хотели получить? Между отрицаниями можно ведь другие законы применить.

[Joker_vD]

Chifu в сообщении #492331 писал(а):

можно сразу СКНФ искать, а можно и СДНФ инверсной функции

Только надо не инверсной, а двойственной.

[Chifu]

Joker_vD в сообщении #492384 писал(а):

Только надо не инверсной, а двойственной.

Тогда объясните чем двойственная функция отличается от инверсной в данном примере.

[Joker_vD]

Chifu
Может, мы просто разные названия используем? Двойственная функция $f^*(x_1,\ldots,x_n)$ определяется как $f^*(x_1,\ldots,x_n)\equiv\overline{f(\bar x_1,\ldots,\bar x_n)}$. Ясно, что $(f^*)^*\equiv f$, и понятно, что $\text{СКНФ}(f)\equiv(\text{СДНФ}(f^*))^*$

[c0d3r]

Господа.
Спасибо, конечно, за столь интересные обсуждения уже когда я всё решил и сдал. Просто в то время мне действительно нужно была эта помощь и т.п., но, однако, я ведь уже всё сделал.

В любом случае спасибо за различные советы, размышления.

[Chifu]

Joker_vD в сообщении #492225 писал(а):

... трюк такой: пишется формула, двойственная к исходной, ...

Что мы хотим получить с помощью такого трюка? И что такое формула? :) С помощью инверсии функции мы переходим от набора "1", к набору "0". Сколько "1" в таблице истинности, столько термов в СДНФ, сколько "0" в таблице истинности (исходной функции), столько термов в СКНФ. С помощью тождественных преобразований надо от набора термов СДНФ перейти к набору термов СКНФ.

Joker_vD в сообщении #492418 писал(а):

Может, мы просто разные названия используем?

Нет, мы используем разные понятия для преобразования от СДНФ к СКНФ, но понятие двойственности и инверсии различны. Например в вашем определении двойственных функций используется понятие инверсной функции. В вашем определении пишется, что двойственная функция, это такая функция, что выполняется тождество ... Закон де Моргана (закон инверсии) говорит, что функции "И" и "ИЛИ" удовлетворяют такому тождеству, т.е. это двойственные функции.

[Joker_vD]

Chifu в сообщении #492706 писал(а):

Что мы хотим получить с помощью такого трюка?

Мы получим двойственную, выпишем ее СДНФ — сделаем еще раз "двойствоение", и СДНФ двойственной превратится в СКНФ исходной. Ваш трюк с инверсией — тоже самое, только вы используете отрицание, вместо двойственности. Наверное, это даже проще, хотя в том курсе, который мне читали, двойственными формулами пользовались повсюду.

[Chifu]

Joker_vD в сообщении #492870 писал(а):

... двойственными формулами пользовались повсюду.

Какими двойственными формулами (в данном случае)? Напомню, по вашему определению, если используем двойственные функции, то получаем функцию инверсную исходной.

[Joker_vD]

Не-е-ет. Есть функция $f(x_1,\ldots,x_n)$. Двойственной к ней называется функция $f^*(x_1,\ldots,x_n)=\overline{f(\bar x_1,\ldots,\bar x_n)}$. Инверсной к $f$ называется функция $\bar f(x_1,\ldots,x_n)=\overline{f(x_1,\ldots,x_n)}$.

[Chifu]

Joker_vD в сообщении #492931 писал(а):

Не-е-ет. Есть функция $f(x_1,\ldots,x_n)$. Двойственной к ней называется функция $f^*(x_1,\ldots,x_n)=\overline{f(\bar x_1,\ldots,\bar x_n)}$.

Я вам уже привёл двойственные функции, а теперь приведите пример двойственного преобразования. Если применяем двойственные функции и не инвертируем полученную функцию, то получаем инверсию исходной функции, а если ещё и инвертируем, то получаем тождество.
Пусть $f(x_1, x_2)=x_1\cdot x_2$, тогда $f^*(\bar x_1, \bar x_2)=\bar x_1 + \bar x_2=\overline{f(x_1, x_2)}=\overline{x_1\cdot x_2}$ или $f^*(x_1, x_2)=\overline{f(\bar x_1, \bar x_2)}$. :)

[Joker_vD]

Что вы от меня хотите?

$f(x_1,x_2)=x_1\wedge x_2$

$f^*(x_1,x_2)=\overline{\bar x_1\wedge \bar x_2}=x_1\vee x_2$