СДНФ и СКНФ достоинства и недостатки

@EchoesArina · Регистрация: 27.10.2017

Студворк — интернет-сервис помощи студентам

Добрый день! Объясните пожалуйста, в чем проявляются достоинства и недостатки СКНФ И СДНФ, а так же взаимосвязь этих двух форм.

@3D Homer · 22.06.2018, 20:30

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

@EchoesArina · 22.06.2018, 20:46 **[ТС]**

3D Homer, мы ведь из СДНФ получаем СКНФ с помощью двойственности ? Или есть какой-то другой способ ?

@3D Homer · 22.06.2018, 21:27

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

@EchoesArina · 22.06.2018, 21:37 **[ТС]**

3D Homer, у меня вопрос взаимосвязь СДНФ и СКНФ, ответ что из одного можно получить другое не подойдет. Будет вопрос каким образом выражать одно через другое. Есть выражение (ДНФ f*)*=КНФ f, оно ведь верно и для совершенных форм ?

@3D Homer · 22.06.2018, 23:56

Сообщение от EchoesArina

Есть выражение (ДНФ f*)*=КНФ f, оно ведь верно и для совершенных форм ?

Да.

Можно также действовать через таблицу истинности: вычеркнуть строчки, соответствующие элементарным конъюнкциям в имеющейся СДНФ (например, 101 соответствует $https://www.cyberforum.ru/cgi-bin/latex.cgi?x\bar{y}z$ ) и выписать элементарные дизъюнкции для оставшийся строчек (например, 110 соответствует $https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{x}\vee\bar{y}\vee z$ ). Альтернативно можно последовательно применять дистрибутивность $https://www.cyberforum.ru/cgi-bin/latex.cgi?x\vee yz=(x\vee y)(x\vee z)$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?xy\vee z=(x\vee z)(y\vee z)$ к СДНФ, пока все внешние связки (которые выполняются последними) не станут конъюнкциями. Также нужно убрать дизъюнкции, где есть противоположные литералы $https://www.cyberforum.ru/cgi-bin/latex.cgi?x$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{x}$ , и склеить одинаковые литералы. В результате получится СКНФ.

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .

@EchoesArina 1 / 1 / 0 Регистрация: 27.10.2017 Сообщений: 123

	СДНФ и СКНФ достоинства и недостатки 22.06.2018, 19:47. Показов 4322. Ответов 5 Метки нет (Все метки) Добрый день! Объясните пожалуйста, в чем проявляются достоинства и недостатки СКНФ И СДНФ, а так же взаимосвязь этих двух форм. 0

@3D Homer $Эксперт по математике/физике$ 5016 / 3628 / 1164 Регистрация: 01.09.2014 Сообщений: 9,790
	22.06.2018, 20:30
	Достоинства: любую функцию можно представить в одной и только одной СДНФ (СКНФ). Поэтому из различия СДНФ вытекает различие функций. Из СДНФ можно легко получить СКНФ и наоборот, то выход может быть экспоненциально длиннее входа. СДНФ и СКНФ не являются самыми компактными представлениями функций. 1

@EchoesArina 1 / 1 / 0 Регистрация: 27.10.2017 Сообщений: 123
	22.06.2018, 20:46 [ТС]
	3D Homer, мы ведь из СДНФ получаем СКНФ с помощью двойственности ? Или есть какой-то другой способ ? 0

@3D Homer $Эксперт по математике/физике$ 5016 / 3628 / 1164 Регистрация: 01.09.2014 Сообщений: 9,790
	22.06.2018, 21:27
	Для любой вычислимой функции (в том числе функции, которая преобразует СДНФ в СКНФ), есть бесконечно много алгоритмов. Поэтому да, есть и другие способы. Что именно вы имеете в виду под "с помощью двойственности"? 1

@EchoesArina 1 / 1 / 0 Регистрация: 27.10.2017 Сообщений: 123
	22.06.2018, 21:37 [ТС]
	3D Homer, у меня вопрос взаимосвязь СДНФ и СКНФ, ответ что из одного можно получить другое не подойдет. Будет вопрос каким образом выражать одно через другое. Есть выражение (ДНФ f)=КНФ f, оно ведь верно и для совершенных форм ? 0

СДНФ и СКНФ достоинства и недостатки

Решение