Prolog: Überprüfen ob eine boolsche Funktion monton ist oder nicht

Beginner

Thursday, January 7th 2010, 7:07pm

Prolog: Überprüfen ob eine boolsche Funktion monton ist oder nicht

Hallo!
Ich versuche seit einigen Tagen ein vermutlich einfaches Prolog Programm hinzubekommen. Ich möchte eine Prädikat definieren welches mir überprüft ob eine gegebene boolsche Funktion monoton ist oder nicht. Ich habe mir gedacht ich probiere das damit, dass ich zwei Listen erstelle die Werte einsetze und damit überpüfe ob die boolsche Funktion monoton ist oder nicht. Ist das der richtige Weg oder gibt es da einen anderen. Ich komme da einfach nicht weiter, ist das überhaupt so richtig?

Ich bin für jede Hilfe dankbar!!!!
Florian

SeBa

Master

Posts: 1,134

Thursday, January 7th 2010, 8:55pm

Hilf mir bitte auf die Sprünge. Was bedeutet monoton in diesem Zusammenhang Die mir geläufigen Defintionen von Monotonie scheinen hier nicht zu passen. Wann ist eine boolsche Funktion monoton?

eolith421

Beginner

Posts: 3

Saturday, January 9th 2010, 6:04pm

Hallo!
Darüber rätsle ich jetzt auch noch, bin derweil einmal zum zweiten Teil gegangen und möchte den fertig bekommen, ehe ich mich mit dem ersten Problem beschäftige. Allerdings habe ich da auch Fragen damit icvh weiterkomme. Tut mir leid.

Ziel ist es ein Prädikat self_dual/1 zu schreiben welches eine boolsche Funktion die ich per Paramter übergebe überpürft ob sie self_dual ist, d.h. f(not(x1)....,not(xn)) = not(f(x1,...,xn)).

Ich habe es bisher geschafft ein Prädikat check zu erstellen welches mir das richtige Ergebnis ausgibt, nur sollte das dynamisch gehen, das heißt das Prädikat soll zuerst die Anzahl der Argumente vermutlich mithilfe von arity herausfinden, dann damit die richtige Listen erzeugen und überpürfen. Mein derzeitiger Code schaut so aus:

Source code

% das ist eine gegeben funktion mit 2 Paramtern %
f(A,B,0) :- 0 is A xor B.
arity(f,2).

% statische überprüfung auf self_dual von Funktion %

or(A,B) :- A; B.
check(A,B) :- or(not(A),B),or(A,not(B)).

numberOfArgument(Funktion,Counter) :-
	arity(Funktion,Counter).
	
self_dual(ZZ) :-
	check(f(1,1,0),f(0,0,0)),
	check(f(1,0,0),f(0,1,0)),
	check(f(0,1,0),f(1,0,0)),
	check(f(0,0,0),f(1,1,0)).

Wie bekomme ich die Funktion self_dual dynamisch hin?

Florian

SeBa

Master

Posts: 1,134

Saturday, January 9th 2010, 11:03pm

Ich verstehe leider wieder nicht was du genau machen möchtest. In Prolog gibt es keine boolschen Variablen und auch keine boolsche Funktionen. Es gibt Fakten, die stehen in der Wissensbasis und es gibt Prädikate. Alles was man mit Prolog letzendlich macht, ist gucken ob man eine Anfrage so "hinbiegen" kann, dass sie mit dem was in der Wissenbasis steht übereinstimmt. Gelinkt Prolog das, ist die Aussage wahr, andernfalls nicht. Ein Kerninstrument welches man bei Prolog dafür benutzt ist die Unifikation.

eolith421

Beginner

Posts: 3

Sunday, January 10th 2010, 11:09am

Danke, dass dur dir so viel Mühe gibst mir zu helfen. Die Sache ist wirklich verzwickt. Das ganze ist eine Aufgabe für die UNI. Ich zermatere mir deswegen schon seit Mittoch den Kopf.

Es ist so:
Die Aufgabe besteht aus drei Teilen.

1. Hier sollen wir ein Prädikat monoton/1 erstellen die überpürft ob die boolean Funktion die als Argument übergeben wird monoton ist oder nicht. orginal: Define a predicat monton/1 which checks where (eigentlich if, wie es auf Nachfrage herauskam) the boolean function given as argument is montone. Dieses Problem habe ich jetzt einmal geskipped.

2. Es soll ein Prädikat self_dual/1 definiert werden welches überpürft ob die boolean function die als Argument übergeben wird self_dual ist. Unter self dual verstehen wir folgendes: f(not(a1),not(a2),...) = not(f(a1,a2,...)).

3. Es soll ein Prädikat adequate/1 bestimmt werden das überprüft ob die boolche Funktion die als Argument übergeben wird adequate ist.

Ich konzentriere mich im Moment auf 2.

Unter boolsche Funktionen verstehen wir hier folgendes:

	Source code
1 2	f(A,B,O) :- O is A xor B arity(f,2).

So das ist die Ausgangslage. Das bedeutet ich muss ein Prädikat was ja hier die boolsche Funktion repäsentiert als Argument an mein Prädikat self_dual übergeben (bei mit ZZ). Dann muss ich die Anzahl der Argumente herausfinden, das geht mit arity(f,X), f ist hier das Prädikat bzw. die Funktion. Z.B.: für die oben gegebene Funktion müsste ich also eine Liste erzeugen die etwa so ausschaut [[1,1],[1,0],[0,1],[0,0]]. Dann erzeuge ich eine Schleife die folgendes tut:

sie nimmt den ersten Teil der Liste [1,1] und setzt hier den head und Tail ein also f(1,1,O). Dann mach die Schleife das Selbe mit not also f(not(1), not(1), O). Dies wird an die Funktion check übergeben und liefert in diesem Fall true zurück. Dann macht die Schelife das selbe mit dem zweiten Element der Liste also [1,0] usw. Wenn dann am Ende bei allen Ergebnissen von check true rauskommt ist das Prädikat self dual.

Hier die vorgeschlagene Prädikate die auf montone und self_dual hin überprüft werden sollen:

	Source code
1 2 3 4 5 6	f(A,B,0) :- 0 is A xor B. arity(f,2). g(A,0) :- 0 is 1-A. arity(g,1). h(A,B,0) :- 0 is min(A,B). arity(h,2).

Hier nochmals mein Code:

Source code

% Statische Überprüfung auf self_dual von Funktion %
or(A,B) :- A; B.
check(A,B) :- or(not(A),B),or(A,not(B)).

% Dieses Prädikat setzt alle Kombinationen der Funktionswerte der Funktion in check ein,
% wenn alle Überprüfungen true ergeben, dann ist das übergebene Prädikat self_dual.
self_dual(ZZ) :-
	arity(ZZ,X).
	check(f(1,1,0),f(0,0,0)),
	check(f(1,0,0),f(0,1,0)),
	check(f(0,1,0),f(1,0,0)),
	check(f(0,0,0),f(1,1,0)).

Hier mein überarbeiteter Code bei dem ich schon versuche mit einer Liste zu arbeiten, aber was leider noch nicht geht:

Source code

% Statische Überprüfung auf self_dual von Funktion %
or(A,B) :- A; B.
check(A,B) :- or(not(A),B),or(A,not(B)).

% Dieses Prädikat setzt alle Kombinationen der Funktionswerte der Funktion in check ein,
% wenn alle Überprüfungen true ergeben, dann ist das übergebene Prädikat self_dual.

list([]).
listensplit([H|T], H, T).
self_dual(ZZ) :-
	%arity(ZZ,X),
	list([[1,1],[1,0],[0,1],[0,0]]),
	
	listensplit([[1,1],[1,0],[0,1],[0,0]],Head,Rest),
	listensplit(Head,First,Second),
	check(f(First,Second,0),f(not(First),not(Second),0)),
	
	
	listensplit(Rest,Head,Rest),
	listensplit(Head,First,Second),
	check(f(First,Second,0),f(not(First),not(Second),0)),
	
	listensplit(Rest,Head,Rest),
	listensplit(Head,First,Second),
	check(f(First,Second,0),f(not(First),not(Second),0)),
	
	listensplit(Rest,Head,Rest),
	listensplit(Head,First,Second),
	check(f(First,Second,0),f(not(First),not(Second),0)).

Im Prinzip sollte am Ende die Bedienung ähnlich ausschauen wie bei arity.