Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Prolog
Перезагрузить страницу Перевод из ДНФ в КНФ
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
VANISH-fcsm
Guest
 
Сообщений: n/a
По умолчанию 03.05.2009, 18:05

Нужно решить задачу: Дана формула исчисления высказываний в дизъюнктивной нормальной форме. Преобразовать ее в конъюнктивную нормальную форму.

Вопросы:
1) По какому алгоритму переводится ДНФ в КНФ
2) Как это реализовывается

P.S.

Есть уже решенная задача: Разработать синтаксический анализатор формулы исчисления высказываний.
Вот её код:
Код:
domains
   strings=symbol*        
predicates
       formula(strings,strings)
       simple_formula(strings,strings)
       atom(strings,strings)
       term(strings,strings)
       predicate(strings,strings)
       predName(string,integer)
       funcName(string,integer)
       expression(symbol)
       scaner(symbol,strings)
       C(strings,symbol,strings)
       termList(strings,strings,integer)
       var(symbol)
       analize(string)
goal
clearwindow,
analize("#X(@X(P3(f2(X,Y),Y,a))|(#X(~(P2(X,Y)))))"),
nl,
analize("#X(@X(P2(f2(X,Y),Y))|(#X(~(P2(X,Y)))))"),
nl,
analize("@X(#Y(#P2(f2(X,Y),X))&(#Y(P2(X,Y))))").

clauses
analize(E):-write(E),
nl,expression(E),
write("ok");write("bad").


expression(E):-scaner(E,L),formula(L,[]).
scaner(S,[C|L]):- 
    fronttoken(S,C,S1),!, 
    scaner(S1,L). 
  scaner(_,[]). 

formula(L,Remain):-simple_formula(L,Remain).
formula(L,Remain):-simple_formula(L,L1),C(L1,"&",L2),formula(L2,Remain).
formula(L,Remain):-simple_formula(L,L1),C(L1,"|",L2),formula(L2,Remain).
formula(L,Remain):-simple_formula(L,L1),C(L1,">",L2),formula(L2,Remain).

simple_formula(["("|L],Remain):-formula(L,L1),C(L1,")",Remain).
simple_formula(L,Remain):-atom(L,Remain).
simple_formula(["~"|L],Remain):-formula(L,Remain).
simple_formula(["#",D,"("|L],Remain):-var(D),formula(L,L1),C(L1,")",Remain).
simple_formula(["@",D,"("|L],Remain):-var(D),formula(L,L1),C(L1,")",Remain).
C([X|L], X, L).

atom([D|Remain],Remain):-var(D).
atom(L,Remain):-predicate(L,Remain).
predicate([D,"("|L],Remain):-predName(D,Len),termList(L,L1,Len),C(L1,")",Remain).
term([D|Remain],Remain):-var(D).
term([D,"("|L],Remain):-funcName(D,Len),termList(L,L1,Len),C(L1,")",Remain).
term([D|Remain],Remain):-D>="a",D<="z".
var(D):-D>="A",D<="Z".
termList(L,Remain,Len):-term(L,Remain),Len=1.
termList(L,Remain,Len):-term(L,L1),C(L1,",",L2),Len1=Len-1,termList(L2,Remain,Len1).
predName(D,Len):-substring(D,1,1,P),P="P",substring(D,2,1,L),str_int(L,Len).
funcName(D,Len):-substring(D,1,1,P),P="f",substring(D,2,1,L),str_int(L,Len).
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

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

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Перевод с Delphi на C# Ardni Delphi 0 19.12.2011 17:18
перевод времени win 7 игарокby Любые вопросы от новичков 8 07.11.2011 23:58
Перевод из C++ в Delphi fredwriter Delphi 1 08.10.2010 12:34
Перевод из Pascal в С++ Garg С/С++ 1 05.05.2010 11:55
Перевод переменной CString в int winamp Visual C++ 17 18.08.2009 00:02
Перевод строки в 0 и 1 *Юльчик* Delphi 5 26.05.2009 09:11
Перевод Hex в Int как это осуществить Makavely C++ Builder 14 19.12.2007 14:27
Перевод чисел. ПОИОГИТЕ! meteliti Pascal 1 11.12.2007 06:24
Перевод моделей в 3D _kT Программирование графики 1 09.11.2007 15:17
Перевод из 3d в 2d координаты dralexthk Программирование графики 4 11.04.2007 12:34
Перевод данных из HEX MG Delphi 0 29.02.2004 12:29



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов