Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Приведение к КНФ, булевая алгебра 
:(
    Опции темы
Lonley
Дата 30.7.2004, 00:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 597
Регистрация: 7.10.2003
Где: северные ворота М урманск

Репутация: нет
Всего: 4



Привет!!!
Вот блин не получается точне получается ДНФ , а КНФ нет

(a > b)V((c > d) & p)
после преобразов получ ДНФ
~a V b V ~cp V dp а как получить КНФ ни как не могу получить sad.gif
---------
если кто может объясните как


--------------------
Земную жизнь пройдя до половины,
Я очутился в сумрачном лесу,
Утратив правый путь во тьме долины.
Каков он был, о, как произнесу,
Тот дикий лес, дремучий и грозящий,
PM MAIL ICQ   Вверх
e-moe
Дата 3.8.2004, 23:03 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 88
Регистрация: 3.8.2004
Где: Украина, Донецк

Репутация: нет
Всего: 4



как я понял '\/' это '+'
'&' это 'И'

А что такое '>' и '~' ?

PM MAIL WWW ICQ   Вверх
p0s0l
Дата 3.8.2004, 23:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Г-н Посол
****


Профиль
Группа: Экс. модератор
Сообщений: 3668
Регистрация: 13.7.2003
Где: 58°38' с.ш. 4 9°41' в.д.

Репутация: нет
Всего: 112



~ - отрицание
> - следование (из a следует b)



--------------------
С уважением, г-н Посол.
PM   Вверх
p0s0l
Дата 4.8.2004, 00:23 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Г-н Посол
****


Профиль
Группа: Экс. модератор
Сообщений: 3668
Регистрация: 13.7.2003
Где: 58°38' с.ш. 4 9°41' в.д.

Репутация: нет
Всего: 112



Построим таблицу истинности:
Код
abcdp  F
0****  1
11***  1
10**0  0 <- идёт в КНФ
100*1  1
10101  0 <- идёт в КНФ
10111  1


Из неё следует КНФ такая:
(~a V b V p)(~a V b V ~c V d V ~p)

хотя давно это было... может и попутался...

Это сообщение отредактировал(а) p0s0l - 4.8.2004, 00:25


--------------------
С уважением, г-н Посол.
PM   Вверх
e-moe
Дата 4.8.2004, 21:13 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 88
Регистрация: 3.8.2004
Где: Украина, Донецк

Репутация: нет
Всего: 4



Цитата(p0s0l @ 3.8.2004, 22:18)
> - следование (из a следует b)

Следование? А это как?
Когда я учил ПТЦА(Прикладн. Теор. Цифров. Автоматов), у нас такого небыло.... Или это название какой-то логич. операции?
PM MAIL WWW ICQ   Вверх
p0s0l
Дата 4.8.2004, 21:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Г-н Посол
****


Профиль
Группа: Экс. модератор
Сообщений: 3668
Регистрация: 13.7.2003
Где: 58°38' с.ш. 4 9°41' в.д.

Репутация: нет
Всего: 112



Следование - это вроде называется "импликация" (в голове это слово всплывает, но может это вообще не из той области smile.gif...)
Но суть такова: из истины не может следовать ложь...
Т.е. a > b = 0 в случае, если a=1, b=0, в других случах результат = 1...
И если приглядишься к приведенному в первом посте приводу к ДНФ, заметишь, что:
(a > b) = (~a V b) = ~(a & ~b)



--------------------
С уважением, г-н Посол.
PM   Вверх
e-moe
Дата 4.8.2004, 22:03 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 88
Регистрация: 3.8.2004
Где: Украина, Донецк

Репутация: нет
Всего: 4



Ясн...
Спасибо!
PM MAIL WWW ICQ   Вверх
KuzZzya
Дата 11.12.2007, 17:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 3
Регистрация: 11.12.2007

Репутация: нет
Всего: нет



а может есть у кого-нить реализованный КНФ? всё-равно на каком языке, но хотелось бы html файлик, очень надо
PM MAIL   Вверх
nworm
Дата 16.12.2007, 03:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 502
Регистрация: 22.10.2005

Репутация: 4
Всего: 8



Не совсем понятно, что конкретно надо

тут есть exe-шник строящий совершенную КНФ по функции

PM MAIL WWW   Вверх
KuzZzya
Дата 25.12.2007, 14:09 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 3
Регистрация: 11.12.2007

Репутация: нет
Всего: нет



Необходимо реализовать алгоритм преобразования формулы в КНФ. Примерно как описано и показано на рисунках тут: http://blaga.ru/Javascriptbook/book/gl20/gl20.html#24
PM MAIL   Вверх
KuzZzya
Дата 25.12.2007, 15:16 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 3
Регистрация: 11.12.2007

Репутация: нет
Всего: нет



Т.е. В текстовое поле вводится формула, после щелчка по кнопке, формируется эквивалентная формула, находящаяся в КНФ. 
PM MAIL   Вверх
Smskaaa
  Дата 7.10.2009, 21:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 2
Регистрация: 7.10.2009

Репутация: нет
Всего: нет



((( помогите пожалуйста к КНФ привести пример:
((R->P)->(|(QvR)->P))
-> это импликация
| это отрицание
v это дизъюнкция
срочно нужно очень
PM MAIL   Вверх
dengalf
Дата 8.10.2009, 05:06 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 48
Регистрация: 10.4.2009

Репутация: нет
Всего: нет



((R->P)->(|(QvR)->P))
если память не изменяет будет примерно так:
((|RvP)->(QvRvP))=R|PvQvRvP=(RvP)(|PvP)vQvR=RvPvQvR=PvQvRесли таблицей - то также получится
Или Вам это программно для общего случая реализовать надо?

А насчет основной темы  - если ДНФ получается, то, помниться, она как-то элементарно в КНФ переводиться. То ли ее сначала надо до СДНФ дополнить, а уже потом в КНФ, точнее СКНФ(чего-то там с отрицаниями поколдовать)
PM MAIL   Вверх
nworm
Дата 8.10.2009, 14:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 502
Регистрация: 22.10.2005

Репутация: 4
Всего: 8



СДНФ -> СКНФ
за два хода напрашивается вариант
1) строим по СДНФ таблицу
2) строим по таблице СКНФ.
PM MAIL WWW   Вверх
dengalf
Дата 8.10.2009, 14:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 48
Регистрация: 10.4.2009

Репутация: нет
Всего: нет



Чего-то там помнится хитрее было, а вот чего - хоть убей не помню smile . Хотя вариант по таблице наверное действительно будет самый "незамороченный" и легко реализуемый
PM MAIL   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.0834 ]   [ Использовано запросов: 20 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.