VPF::определить является ли формула тавтологией

Chuchka

Дата 25.11.2010, 08:59 (ссылка)

(нет голосов)

Загрузка ...

Новичок

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

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

Требуется определить, является ли введенная формула тавтологией, алгебра булева, т.е из всех операций есть только конъюнкция, дизъюнкция и отрицание. Максимальное число переменных - три штуки. Очень нужна помощь. Я уже пыталась сама написать эту программу, но получается полная белеберда=(

Код


domains
formula = formula(symbol,formula,formula); nil
el = symbol
spisok = el*
 
predicates
 
nondeterm true_f(formula)
nondeterm false_f(formula)
nondeterm tautology(formula, spisok)
 
clauses
 
true_f(formula(true, nil,nil)). %проверка на выполнимость формулы (работает)
true_f(formula("^", X,Y)):- true_f(X), true_f(Y).
true_f(formula("|",X,_)):- true_f(X).
true_f(formula("|",_,Y)):- true_f(Y).
true_f(formula("~",X,nil)):-false_f(X).
true_f(formula("~",nil,X)):-false_f(X).
 
false_f(formula(false, nil,nil)). %проверка на опровержимость формулы(работает)
false_f(formula("|",X,Y)):- false_f(X), false_f(Y).
false_f(formula("^",X,_)):- false_f(X).
false_f(formula("^",_,Y)):- false_f(Y).
false_f(formula("~",X,nil)):-true_f(X).
false_f(formula("~",nil,X)):-true_f(X).
 
tautology(formula("|", formula(X,nil,nil),formula("~",formula(X,nil,nil),nil)),[X,_,_]). %тут должна быть
tautology(formula("|", formula(X,nil,nil),formula("~",formula(X,nil,nil),nil)),[_,X,_]). %проверка на
tautology(formula("|", formula(X,nil,nil),formula("~",formula(X,nil,nil),nil)),[_,_,X]). %тавтологию=)
 
formula("X",nil,nil).
 
tautology(formula("^",X,Y),[X,Y,Z]):-tautology(X,[X,Y,Z]), tautology(Y,[X,Y,Z]).
tautology(formula("|",X,Y),[X,Y,Z]):-true_f(X),true_f(Y); true_f(X),false_f(Y); false_f(X),true_f(Y).
tautology(formula("~",X,nil),[X,Y,Z]):-false_f(X).
 
tautology(formula(X,nil,nil),[X1,Y1,Z1]) :- X = "X", X1; X="Y", Y1; X="Z", Z1.
 
goal
 
tautology(formula("|", formula("X",nil,nil),formula("~",formula("X",nil,nil),nil)),["X"]).

Я совершенно не знаю как можно сделать полный перебор всех значений true и false для этих переменных и как сделать чтобы переменные с одинаковых веток дерева с одним названием пролог видел именно как одни и те же переменные=( так что вся надежда на вас=)

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