Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 11 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Переход из ДНФ в КНФ
СообщениеДобавлено: 12 ноя 2017, 13:05 
Не в сети
Начинающий
Зарегистрирован:
22 окт 2017, 18:24
Сообщений: 38
Cпасибо сказано: 10
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Есть ДНФ и СДНФ. Как из какой-нибудь формулы перейти к КНФ, ну или сразу к СКНФ?

ДНФ: [math]F =y \lor x \lor \overline{y}z[/math]
СДНФ: [math]F =xyz \lor \overline{x}yz \lor xy\overline{z} \lor \overline{x}y\overline{z} \lor x\overline{y}z \lor x\overline{y}\overline{z} \lor \overline{x}\overline{y}\overline{z}[/math]

Пробовал двойное отрицание:
[math]\overline{\overline{y \lor x \lor \overline{y}z}} = \overline{(\overline{y})(\overline{x})(y \lor \overline{z})}= y \lor x \lor \overline{y}z[/math]

но как видите результат не радует. Может что-то упустил тут? или неправильно делаю? или другой способ есть?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Переход из ДНФ в КНФ
СообщениеДобавлено: 12 ноя 2017, 14:32 
Не в сети
Light & Truth
Зарегистрирован:
23 авг 2010, 22:28
Сообщений: 4430
Cпасибо сказано: 565
Спасибо получено:
1075 раз в 952 сообщениях
Очков репутации: 315

Добавить очки репутацииУменьшить очки репутации
huffy писал(а):
двойное отрицание


Двойное отрицание приведёт к той же самой формуле, согласно закону двойного отрицания.

Используйте ДНФ и дистрибутивность дизъюнкции относительно конъюнкции. Почти сразу же получите КНФ (она же в данном случае и СКНФ).

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Ellipsoid "Спасибо" сказали:
huffy
 Заголовок сообщения: Re: Переход из ДНФ в КНФ
СообщениеДобавлено: 12 ноя 2017, 14:58 
Не в сети
Light & Truth
Зарегистрирован:
23 авг 2010, 22:28
Сообщений: 4430
Cпасибо сказано: 565
Спасибо получено:
1075 раз в 952 сообщениях
Очков репутации: 315

Добавить очки репутацииУменьшить очки репутации
Ellipsoid писал(а):
дистрибутивность дизъюнкции относительно конъюнкции


А перед этим - коммутативность дизъюнкции.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Ellipsoid "Спасибо" сказали:
huffy
 Заголовок сообщения: Re: Переход из ДНФ в КНФ
СообщениеДобавлено: 12 ноя 2017, 15:29 
Не в сети
Начинающий
Зарегистрирован:
22 окт 2017, 18:24
Сообщений: 38
Cпасибо сказано: 10
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Всё, разобрался, спасибо!

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Переход из ДНФ в КНФ
СообщениеДобавлено: 12 ноя 2017, 15:31 
Не в сети
Light & Truth
Зарегистрирован:
23 авг 2010, 22:28
Сообщений: 4430
Cпасибо сказано: 565
Спасибо получено:
1075 раз в 952 сообщениях
Очков репутации: 315

Добавить очки репутацииУменьшить очки репутации
Пожалуйста.
А что получилось, если не секрет?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Переход из ДНФ в КНФ
СообщениеДобавлено: 12 ноя 2017, 16:10 
Не в сети
Начинающий
Зарегистрирован:
22 окт 2017, 18:24
Сообщений: 38
Cпасибо сказано: 10
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
У меня ошибка была при эквивалентных преобразованиях. Заново всё сделал и оказалось, что и ничего не нужно искать.

А если вы хотите узнать, как бы я сделал то, что вы мне посоветовали, то вот так бы я сделал:

[math]y \lor x \lor z\overline{y} = (y \lor x \lor z )(y \lor x \lor \overline{y}) = (y \lor x \lor z )(y \lor x) = (y \lor x \lor z )(y \lor x \lor \overline{z})(y \lor x \lor z ) = (y \lor x \lor \overline{z})[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Переход из ДНФ в КНФ
СообщениеДобавлено: 12 ноя 2017, 16:20 
Не в сети
Light & Truth
Зарегистрирован:
23 авг 2010, 22:28
Сообщений: 4430
Cпасибо сказано: 565
Спасибо получено:
1075 раз в 952 сообщениях
Очков репутации: 315

Добавить очки репутацииУменьшить очки репутации
Ерунда какая-то. И ответ неверный. Первый шаг правильный. А вот дальше...
И я немного про другое говорил.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Переход из ДНФ в КНФ
СообщениеДобавлено: 12 ноя 2017, 16:23 
Не в сети
Light & Truth
Зарегистрирован:
23 авг 2010, 22:28
Сообщений: 4430
Cпасибо сказано: 565
Спасибо получено:
1075 раз в 952 сообщениях
Очков репутации: 315

Добавить очки репутацииУменьшить очки репутации
Если уж вы сразу использовали дистрибутивность, не переставляя члены дизъюнкции местами, то следующим шагом должно быть использование коммутативности дизъюнкции во второй скобке, а потом - закона исключённого третьего.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Переход из ДНФ в КНФ
СообщениеДобавлено: 12 ноя 2017, 17:44 
Не в сети
Начинающий
Зарегистрирован:
22 окт 2017, 18:24
Сообщений: 38
Cпасибо сказано: 10
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Так, если вы сказали, что первый шаг правильный, то во второй скобке я могу использовать закон инверсии: [math]y \lor \overline{y} = 1[/math]
и если в скобке осталось [math]1 \lor x[/math], то это равно 1

[math]y \lor x \lor z\overline{y} = (y \lor x \lor z )(y \lor x \lor \overline{y}) = (y \lor x \lor z )(1 \lor x) = (y \lor x \lor z )1 = (y \lor x \lor z )[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Переход из ДНФ в КНФ
СообщениеДобавлено: 12 ноя 2017, 18:30 
Не в сети
Light & Truth
Зарегистрирован:
23 авг 2010, 22:28
Сообщений: 4430
Cпасибо сказано: 565
Спасибо получено:
1075 раз в 952 сообщениях
Очков репутации: 315

Добавить очки репутацииУменьшить очки репутации
huffy писал(а):
закон инверсии


Я его знаю под именем закона исключённого третьего.

Теперь правильно. Но можно ещё и так:

[math]y \vee x \vee zy'=y \vee y'z \vee x=(y \vee y')(y \vee z) \vee x=(1 \cdot (y \vee z)) \vee x = x \vee y \vee z[/math].

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Ellipsoid "Спасибо" сказали:
huffy
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему    На страницу 1, 2  След.  Страница 1 из 2 [ Сообщений: 11 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Переход в СЦМ

в форуме Механика

MuCTeP_TTP0

6

141

09 сен 2023, 18:33

Переход

в форуме Алгебра

Bonaqua

1

296

03 дек 2014, 23:28

Переход

в форуме Тригонометрия

Bonaqua

5

481

16 янв 2015, 09:13

Переход ß/a = ß/(ln(1+ß) * ∂ * (ln(1+a))/a

в форуме Пределы числовых последовательностей и функций, Исследования функций

afraumar

2

290

17 фев 2015, 13:42

Переход

в форуме Дифференциальное исчисление

Vkus_quavasa

2

142

18 сен 2020, 08:23

Объясните переход

в форуме Алгебра

Andreww

4

388

28 фев 2018, 18:51

Индукционный переход

в форуме Дискретная математика, Теория множеств и Логика

dserp18

3

139

25 апр 2020, 09:13

Как тут сделали переход?

в форуме Пределы числовых последовательностей и функций, Исследования функций

felil723

1

151

26 янв 2022, 13:24

Объясните переход

в форуме Алгебра

Bonaqua

3

411

18 дек 2014, 17:52

Не понятен переход

в форуме Алгебра

Andreww

1

205

27 фев 2018, 03:02


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 15


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved