СДНФ и СКНФ

@efremovxp · Регистрация: 10.06.2013

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

Я уже пытался решить путем построения таблицы истинности, но преподаватель сказала что надо другим методом решать. "Что ты будешь делать, если функция будет очень длинной?".
Прошу вашей помощи.

Помогите

@Divinesites · 04.07.2013, 13:41

Для начала просто упростите это выражение, используя Закон Порецкого: $https://www.cyberforum.ru/cgi-bin/latex.cgi?A\bigcup \bar{A}B\$ = $https://www.cyberforum.ru/cgi-bin/latex.cgi?A\bigcup B$

@efremovxp · 04.07.2013, 23:51 **[ТС]**

Упростить проблем нет, надо вот СДНФ и СКНФ...

Добавлено через 36 минут
Методом эквивалентных преобразований что ли...

Добавлено через 9 часов 8 минут
Ну пожалуйста, помогите...

@кот Бегемот · 05.07.2013, 01:31

После упрощений остаётся только первое слагаемое

@Mikl___ · 05.07.2013, 04:11

$https://www.cyberforum.ru/cgi-bin/latex.cgi?y = \bar{x_{1}x_{2}} + \bar{x_{1}+x_{2}}x_{3}=\bar{x_1}+\bar{x_2}+\bar{x_1}\bar{x_2}x_3 =$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?= \bar{x_2}+\bar{x_1}(1+\bar{x_2}x_3)=\bar{x_2}+\bar{x_1} = \bar{x_{1}x_{2}}$

@XpoHoc · 05.07.2013, 07:21

А зачем упрощать формулу если необходимо получить СДНФ и СКНФ?
Думаю, что нужно избавится от инверсий чтобы получить ДНФ и домножить x1' и x2' на недостоющие конституенты так найдем СДНФ, далее выпишим недостоющие конституенты СДНФ и выразиим СКНФ через их инверсию.

Добавлено через 29 минут
$https://www.cyberforum.ru/cgi-bin/latex.cgi?y=\bar{x1\cdot x2}+\bar{x1+x2}\cdot x3\equiv \bar{x1}+\bar{x2}+\bar{x1}\cdot \bar{x2}\cdot x3\equiv \bar{x1}\cdot (x2+\bar{x2})\cdot (x3+\bar{x3})+\bar{x2}\cdot (x1+\bar{x1})\cdot (x3+\bar{x3})+\bar{x1}\cdot \bar{x2}\cdot x3 \equiv$

$https://www.cyberforum.ru/cgi-bin/latex.cgi?\equiv \bar{x1}\cdot (x2\cdot x3+x2\cdot \bar{x3}+\bar{x2}\cdot x3+\bar{x2}\cdot \bar{x3})+\bar{x2}\cdot (x1\cdot x3+x1\cdot \bar{x3}+\bar{x1}\cdot x3+\bar{x1}\cdot \bar{x3})+\bar{x1}\cdot \bar{x2}\cdot x3 \equiv$

$https://www.cyberforum.ru/cgi-bin/latex.cgi?\equiv \bar{x1}\cdot x2\cdot x3+\bar{x1}\cdot x2\cdot \bar{x3}+\bar{x1}\cdot \bar{x2}\cdot x3+\bar{x1}\cdot \bar{x2}\cdot \bar{x3}+x1\cdot \bar{x2}\cdot x3+x1\cdot \bar{x2}\cdot \bar{x3}+\bar{x1}\cdot \bar{x2}\cdot x3+\bar{x1}\cdot \bar{x2}\cdot \bar{x3}+\bar{x1}\cdot \bar{x2}\cdot x3 \equiv$

$https://www.cyberforum.ru/cgi-bin/latex.cgi?\equiv \bar{x1}\cdot x2\cdot x3+\bar{x1}\cdot x2\cdot \bar{x3}+\bar{x1}\cdot \bar{x2}\cdot x3+\bar{x1}\cdot \bar{x2}\cdot \bar{x3}+x1\cdot \bar{x2}\cdot x3+x1\cdot \bar{x2}\cdot \bar{x3}$ -СДНФ

$https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{y}=x1\cdot x2\cdot x3+x1\cdot x2\cdot \bar{x3}$

$https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{\bar{y}}=(\bar{x1\cdot x2\cdot x3+x1\cdot x2\cdot \bar{x3}})\equiv (\bar{x1\cdot x2\cdot x3})\cdot (\bar{x1\cdot x2\cdot \bar{x3}})\equiv (\bar{x1}+ \bar{x2}+ \bar{x3})\cdot (\bar{x1}+ \bar{x2}+ x3)$ - СКНФ

@efremovxp · 05.07.2013, 13:05 **[ТС]**

XpoHoc, преподаватель не понимает каким обоазом я получил отрицание у.

@XpoHoc · 05.07.2013, 14:30

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

преподаватель не понимает каким обоазом я получил отрицание у.

Странный преподаватель

Элементарные конъюнкции, входящие в функции СДНФ называются конституентами единицы (или минтермами).
Выписываем все конституенты единицы не входящие в функцию Y, другими словами выписываем отрицания исходной функции.
Затем выполняем отрицание выписанных конституент не входящие в функцию и преобразоваем их по закону Де Моргана.

Добавлено через 5 минут
Переход от СКНФ к СДНФ и обратно.

Посмотрите подобные примеры решения.
Еще встречается немного в учебнике Аляева "Дискретная математика и мат. логика"

Новые блоги и статьи Все статьи Все блоги /
Вопросы на собеседованиях по микросервисам ArchitectMsa 27.03.2025 Работодатели ищут не просто разработчиков, знающих базовые концепции, а специалистов, разбирающихся в тонкостях масштабирования, отказоустойчивости и производительности. Сейчас на первый план выходят. . .	Взаимодействие Python с REST API py-thonny 27.03.2025 REST API - это архитектурный стиль взаимодействия компонентов распределённого приложения в сети. Python располагает функциональным набором инструментов для работы с REST API и основная библиотека для. . .	sshd restrictions, ssh access limitations jigi33 26.03.2025 sshd restrictions \| ssh access limitations рестрикции доступа на сервер sshd статья: https:/ / www. golinuxcloud. com/ restrict-allow-ssh-certain-users-groups-rhel	Компиляция C++ с Clang API NullReferenced 24.03.2025 Компиляторы обычно воспринимаются как черные ящики, которые превращают исходный код в исполняемые файлы. Мы запускаем компилятор командой в терминале, и вуаля — получаем бинарник. Но что если нужно. . .	Многопоточное программирование в C#: Класс Thread UnmanagedCoder 24.03.2025 Когда запускается приложение на компьютере, операционная система создаёт для него процесс - виртуальное адресное пространство. В C# этот процесс изначально получает один поток выполнения — главный. . .
SwiftUI Data Flow: Передача данных между представлениями mobDevWorks 23.03.2025 При первом знакомстве со SwiftUI кажется, что фреймворк предлагает избыточное количество механизмов для передачи данных: @State, @Binding, @StateObject, @ObservedObject, @EnvironmentObject и другие. . . .	Моки в Java: Сравниваем Mockito, EasyMock, JMockit Javaican 23.03.2025 Как протестировать класс, который зависит от других сложных компонентов, таких как базы данных, веб-сервисы или другие классы, с которыми и так непросто работать в тестовом окружении? Для этого и. . .	Архитектурные паттерны микросервисов: ТОП-10 шаблонов ArchitectMsa 22.03.2025 Популярность микросервисной архитектуры объясняется множеством важных преимуществ. К примеру, она позволяет командам разработчиков работать независимо друг от друга, используя различные технологии и. . .	Оптимизация рендеринга в Unity: Сортировка миллиона спрайтов GameUnited 22.03.2025 Помните, когда наличие сотни спрайтов в игре приводило к существенному падению производительности? Время таких ограничений уходит в прошлое. Сегодня геймдев сталкивается с задачами совершенно иного. . .	Образование и практика Igor3D 21.03.2025 Добрый день А вот каково качество/ эффективность ВУЗовского образования? Аналитическая геометрия изучается в первом семестре и считается довольно легким курсом, что вполне справедливо. Ну хорошо,. . .

@efremovxp 0 / 0 / 0 Регистрация: 10.06.2013 Сообщений: 19

	СДНФ и СКНФ 04.07.2013, 09:10. Показов 2262. Ответов 7 Метки нет (Все метки) Я уже пытался решить путем построения таблицы истинности, но преподаватель сказала что надо другим методом решать. "Что ты будешь делать, если функция будет очень длинной?". Прошу вашей помощи. Помогите 0

@Divinesites 107 / 102 / 9 Регистрация: 29.06.2013 Сообщений: 369
	04.07.2013, 13:41
	Для начала просто упростите это выражение, используя Закон Порецкого: $https://www.cyberforum.ru/cgi-bin/latex.cgi?A\bigcup \bar{A}B\$ = $https://www.cyberforum.ru/cgi-bin/latex.cgi?A\bigcup B$ 1

@efremovxp 0 / 0 / 0 Регистрация: 10.06.2013 Сообщений: 19
	04.07.2013, 23:51 [ТС]
	Упростить проблем нет, надо вот СДНФ и СКНФ... Добавлено через 36 минут Методом эквивалентных преобразований что ли... Добавлено через 9 часов 8 минут Ну пожалуйста, помогите... 0

@кот Бегемот Платежеспособный зверь 8959 / 4384 / 1652 Регистрация: 28.10.2009 Сообщений: 11,629
	05.07.2013, 01:31
	После упрощений остаётся только первое слагаемое 1

@Mikl___ Ушел с форума 16355 / 7671 / 1078 Регистрация: 11.11.2010 Сообщений: 13,730
	05.07.2013, 04:11
	$https://www.cyberforum.ru/cgi-bin/latex.cgi?y = \bar{x_{1}x_{2}} + \bar{x_{1}+x_{2}}x_{3}=\bar{x_1}+\bar{x_2}+\bar{x_1}\bar{x_2}x_3 =$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?= \bar{x_2}+\bar{x_1}(1+\bar{x_2}x_3)=\bar{x_2}+\bar{x_1} = \bar{x_{1}x_{2}}$ 1

@XpoHoc 41 / 20 / 3 Регистрация: 10.04.2011 Сообщений: 75
	05.07.2013, 07:21
	А зачем упрощать формулу если необходимо получить СДНФ и СКНФ? Думаю, что нужно избавится от инверсий чтобы получить ДНФ и домножить x1' и x2' на недостоющие конституенты так найдем СДНФ, далее выпишим недостоющие конституенты СДНФ и выразиим СКНФ через их инверсию. Добавлено через 29 минут $https://www.cyberforum.ru/cgi-bin/latex.cgi?y=\bar{x1\cdot x2}+\bar{x1+x2}\cdot x3\equiv \bar{x1}+\bar{x2}+\bar{x1}\cdot \bar{x2}\cdot x3\equiv \bar{x1}\cdot (x2+\bar{x2})\cdot (x3+\bar{x3})+\bar{x2}\cdot (x1+\bar{x1})\cdot (x3+\bar{x3})+\bar{x1}\cdot \bar{x2}\cdot x3 \equiv$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?\equiv \bar{x1}\cdot (x2\cdot x3+x2\cdot \bar{x3}+\bar{x2}\cdot x3+\bar{x2}\cdot \bar{x3})+\bar{x2}\cdot (x1\cdot x3+x1\cdot \bar{x3}+\bar{x1}\cdot x3+\bar{x1}\cdot \bar{x3})+\bar{x1}\cdot \bar{x2}\cdot x3 \equiv$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?\equiv \bar{x1}\cdot x2\cdot x3+\bar{x1}\cdot x2\cdot \bar{x3}+\bar{x1}\cdot \bar{x2}\cdot x3+\bar{x1}\cdot \bar{x2}\cdot \bar{x3}+x1\cdot \bar{x2}\cdot x3+x1\cdot \bar{x2}\cdot \bar{x3}+\bar{x1}\cdot \bar{x2}\cdot x3+\bar{x1}\cdot \bar{x2}\cdot \bar{x3}+\bar{x1}\cdot \bar{x2}\cdot x3 \equiv$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?\equiv \bar{x1}\cdot x2\cdot x3+\bar{x1}\cdot x2\cdot \bar{x3}+\bar{x1}\cdot \bar{x2}\cdot x3+\bar{x1}\cdot \bar{x2}\cdot \bar{x3}+x1\cdot \bar{x2}\cdot x3+x1\cdot \bar{x2}\cdot \bar{x3}$ -СДНФ $https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{y}=x1\cdot x2\cdot x3+x1\cdot x2\cdot \bar{x3}$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{\bar{y}}=(\bar{x1\cdot x2\cdot x3+x1\cdot x2\cdot \bar{x3}})\equiv (\bar{x1\cdot x2\cdot x3})\cdot (\bar{x1\cdot x2\cdot \bar{x3}})\equiv (\bar{x1}+ \bar{x2}+ \bar{x3})\cdot (\bar{x1}+ \bar{x2}+ x3)$ - СКНФ 2

@efremovxp 0 / 0 / 0 Регистрация: 10.06.2013 Сообщений: 19
	05.07.2013, 13:05 [ТС]
	XpoHoc, преподаватель не понимает каким обоазом я получил отрицание у. 0

@XpoHoc 41 / 20 / 3 Регистрация: 10.04.2011 Сообщений: 75
	05.07.2013, 14:30
	Сообщение от efremovxp преподаватель не понимает каким обоазом я получил отрицание у. Странный преподаватель Элементарные конъюнкции, входящие в функции СДНФ называются конституентами единицы (или минтермами). Выписываем все конституенты единицы не входящие в функцию Y, другими словами выписываем отрицания исходной функции. Затем выполняем отрицание выписанных конституент не входящие в функцию и преобразоваем их по закону Де Моргана. Добавлено через 5 минут Переход от СКНФ к СДНФ и обратно. Посмотрите подобные примеры решения. Еще встречается немного в учебнике Аляева "Дискретная математика и мат. логика" 0

Опции темы