Prüfungsbeispiel

[owaye]

gegeben ist folgender ausddruck (wobei /\ = "und"; -atom = "nicht atom"):

(eq?(rest(x),nil) /\ (-atom?(x) /\ atom?(rest(x))))

Ist dieser Ausdruck:
(_) Tautologie?
(_) gültig?
(_) erfüllbar?
(_) unerfüllbar?

auch mehrere antworten möglich.

HILFEEE!!! wie berechne ich denn sowas?? kannn mir bitte jemand erklären wie das geht? meine fragen: ich krieg da glaub nur 1 ergebnis raus, woher soll ich da wissen ob das eine tautolgie ist? was ist der unterschied zwischen gültig und tautolgie? und wie berechnet man rest(x) ? da "x" kein atom ist (sonst währs ja unterwellt)??

wenn ihr eine lösung schreibt, bitte gut kommentieren und ausführlich für die nicht-so-versierten gehirne in theoinf
:( greez

[Septic.exe]

(eq?(rest(x),nil) /\ (-atom?(x) /\ atom?(rest(x))))


"atom?(rest(x))": Der Teil ergibt immer "false", da "rest(x) = ()" und das ist kein Atom, so wie ich das sehe.

Damit ist der "(-atom?(x) /\ atom?(rest(x)))"-Teil auch immer "false". => Der ganze Term kann nie "true" werden ... deswegen "ungültig".

Ich hoff', ich verzapf' da keinen kompletten Blödsinn. Auf alle Fälle kommt man mit dieser "Vorgangsweise" (also ohne viel herumzurechnen mit Wahrheitstabellen und so) bei diesen Beispielen recht schnell auf ein Ergebnis.

[owaye]

jo laut lösung kommt raus: "unerfüllbar". :shinner:

ich bin nur verwirrt weil:

rest(x) => ergibt normal ()
rest(x) => ergibt was? weil kann "x" nicht alles sein? eine zahl 12345 oder so?

wenn das x nicht unterstrichen (oder unterwellt) ist, ist es doch kein atom oder?

[templar]

Achtung: x ist nur eine Variable, kann also jede mögliche Listenbelegung sein, z.B. nil, A, true,...

Unerfüllbar ist es deswegen, weil rest(x) nicht gleichzeitig ein Atom sein kann UND =nil

[owaye]

meinst du jetzt dass eq?(rest(x),nil) nicht geht? aber angenommen x wäre nil , dann hätt ich ja eq?(() ,nil) und das wär ja true, oder? :confused:

weil ja
() und nil gleichbedeutend sind

[Murmel]

meinst du jetzt dass eq?(rest(x),nil) nicht geht? aber angenommen x wäre nil , dann hätt ich ja (nil,nil) und das wär ja true, oder? :confused:er meint, dass wenn rest(x) gleich Nil ist (und damit obiger Ausdruck true) auf keinen Fall atom?(rest(x)) true sein kann, was es ja auch sein muss, damit der ganze Ausdruck true wird -> unerfüllbar

lG,
Murmel

[owaye]

weil nil kein atom ist oder?

[Murmel]

weil nil kein atom ist oder?jo stimmt genau, Nil ist die leere Liste, also kein Atom

[owaye]

oke, ich hab das glaub jetzt halbwegs begriffen.
ich hätt sonst noch 1 beispiel: impl = impliziert

((ist1?(x) impl istleer?(pop(x))) impl ist1?(pop(x)))

ist1?(x) => t/f (es kann ja sein dass ne "1" an vorderster stelle ist, oder?)
istleer?(pop(x)) => t/f (angenommen das x wäre 1001. "pop" ich da dann den gesamten ausdruck "1001" weg, oder nur die "1"?)
ist1?(pop(x)) => t/f

t/f impl t/f impl t/f => erfüllbar, oder?

[Murmel]

gelöscht weil falsch (nicht, dass sich noch jemand was falsches anlernt)

[owaye]

oke letzte verständnisfrage:
du hast geschrieben dass: ist1?(x) den gesamten ausdruck überpüft und nur dann "true" ist wenn das gesamte x=1 ist;

gilt aber nicht folgendes: wenn ich jetzt habe x=1001
=> ist1?(1001) => true, da wird doch nur überprüft ob die erste stelle die beim stack kommt, eine "1" ist, oder nicht?

oder gilt: dass 1 sein muss. d.h. wenn ich habe
ist1?(0000001) wäre true, weil 00001 die binäre darstellung der zahl "1" ist?


ist nicht bei 6.3.b) am schluss ist0?(01) => true? bitte korrigieren ich befürchte ich hab mir das was falsches angelernt :shinner:

[Murmel]

Sorry, nicht du hast dir was Falsches angelernt, sondern ich, du hast Recht, so wies scheint überprüfen ist0? und ist1? nur die erste Stelle, hatte das falsch in Erinnerung...

[owaye]

oke passt; ich glaub jetzt versteh ichs. allgemein muss man, wenn man x gegeben hat, immer höllisch aufpassen, weil x verschiedene belegungen haben kann. und dementsprechend muss man das ganze auswerten und kriegt auf diese weise meist mehrer lösungen und nicht genau eine. daraus kann man nachher bewerten ob das ganze erfüllbar, tautologie etc. ist. (nur zur wiederholung so gesagt) :)