Aussagelogische Formel < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 18:48 So 15.04.2007 | | Autor: | RalU |
| Aufgabe | Gegeben sei eine aussagelogische Formel:
[mm] \psi= [/mm] a [mm] \wedge [/mm] b [mm] \vee \neg [/mm] c
a) Ist [mm] \psi [/mm] efüllbar bzw. allgemeingültig?
b) Stellen Sie [mm] \psi [/mm] ausschließlich mit der Sheffer-Funktion(NAND) dar.
c) Stellen Sie [mm] \psi [/mm] ausschließlich mit der Peirce-Funktion(NOR) dar.
d) Stellen Sie [mm] \psi [/mm] ausschließlich mit dem "if-then-else"-Operator (Konditional) dar. |
Ich weiß, das eine aussagelogische Formel erfüllbar heißt, wenn es mindestens eine Interpretation der in ihr vorkommenden Atome (Satzbuchstaben) gibt, unter der die Formel wahr ist.
Allerdings weiß ich nicht, wie man sowas nachprüfen kann...
Wie geht man denn grundsätzlich an solch eine Aufgabe heran?
Kann mir jemand auch gute Literatur nennen?
|
|
| |
|
Hallo RalU!
> Gegeben sei eine aussagelogische Formel:
>
> [mm]\psi=[/mm] a [mm]\wedge[/mm] b [mm]\vee \neg[/mm] c
>
> a) Ist [mm]\psi[/mm] efüllbar bzw. allgemeingültig?
>
> b) Stellen Sie [mm]\psi[/mm] ausschließlich mit der
> Sheffer-Funktion(NAND) dar.
>
> c) Stellen Sie [mm]\psi[/mm] ausschließlich mit der
> Peirce-Funktion(NOR) dar.
>
> d) Stellen Sie [mm]\psi[/mm] ausschließlich mit dem
> "if-then-else"-Operator (Konditional) dar.
> Ich weiß, das eine aussagelogische Formel erfüllbar heißt,
> wenn es mindestens eine Interpretation der in ihr
> vorkommenden Atome (Satzbuchstaben) gibt, unter der die
> Formel wahr ist.
Naja, das ist die formale Definition. Intuitiv reicht es, wenn du einfach für a, b und c Nullen und Einsen so einsetzt, dass die Formel erfüllbar ist. das sollte hier nicht wirklich schwierig sein.
Um zu zeigen, dass eine Formel nicht erfüllbar ist, musst du sie zu einem Widerspruch führen, wenn du also z. B. durch Umformungen erhältst [mm] $a\wedge \neg [/mm] a$. Denn so etwas kann ja nie erfüllt sein - das ist ein Widerspruch.
Um die Teile b)-d) zu lösen, würde ich einfach die Verknüpfungen [mm] \wedge, \vee [/mm] und [mm] \neg [/mm] mit der angegebenen Verknüpfung darstellen. Also z. B. gilt ja:
$a NAND [mm] b=\neg(a\wedge [/mm] b)$
Dann ist [mm] $\neg a=\neg(a\wedge [/mm] a)=a NAND b$ und [mm] $a\wedge b=\neg[\neg(a\wedge b)]=\neg[\neg(a\wedge b)\wedge\neg(a\wedge b)]=\neg(a [/mm] NAND b [mm] \wedge [/mm] a NAND b)=(a NAND b) NAND (a NAND b)$ und zuletzt noch: [mm] $a\vee b=\neg(\neg a\wedge\neg b)=\neg [/mm] a NAND [mm] \neg [/mm] b$, und wenn du hier jedes [mm] \neg [/mm] noch durch die erste "Formel" ersetzt, hast du auch das Oder nur durch NAND dargestellt. Nicht erschrecken, das wird meistens recht unhandlich und länglich...
Naja, und wenn du diese drei hast, kannst du auch die obige Formel nur mit NANDs darstellen - einfach jedes einzelne Zeichen ersetzen. Auch das wird sehr unhandlich...
Probier's doch mal.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 10:39 Di 17.04.2007 | | Autor: | RalU |
| Aufgabe | Gegeben sei eine aussagelogische Formel:
$ [mm] \psi= [/mm] $ a $ [mm] \wedge [/mm] $ b $ [mm] \vee \neg [/mm] $ c
a) Ist $ [mm] \psi [/mm] $ efüllbar bzw. allgemeingültig?
b) Stellen Sie $ [mm] \psi [/mm] $ ausschließlich mit der Sheffer-Funktion(NAND) dar.
c) Stellen Sie $ [mm] \psi [/mm] $ ausschließlich mit der Peirce-Funktion(NOR) dar.
d) Stellen Sie $ [mm] \psi [/mm] $ ausschließlich mit dem "if-then-else"-Operator (Konditional) dar. |
Also hier mal meine Lösungen:
zu a) [mm] \psi [/mm] ist erfüllbar, aber nicht allgemein gültig, da nicht für alle möglichen Ausgaben erfüllbar. (Das ergab meine Wertetabelle).
zu b) [mm] \neg(a \wedge [/mm] b) - NAND
also folgt:
a [mm] \wedge [/mm] b [mm] \vee \neg [/mm] c [mm] \equiv
[/mm]
[mm] \neg \neg(a \wedge [/mm] b) [mm] \vee \neg [/mm] c [mm] \equiv [/mm] (de Morgan)
[mm] \equiv \neg [/mm] ( [mm] \neg(a \wedge [/mm] b) [mm] \wedge [/mm] c) (nochmal mit de Morgan)
c) [mm] \neg [/mm] (a [mm] \vee [/mm] b) - NOR
a [mm] \wedge [/mm] b [mm] \vee \neg [/mm] c [mm] \equiv
[/mm]
[mm] \equiv [/mm] (a [mm] \wedge [/mm] b) [mm] \vee \neg [/mm] c [mm] \equiv
[/mm]
[mm] \equiv \neg (\neg [/mm] (a [mm] \wedge [/mm] b)) [mm] \vee \neg [/mm] c [mm] \equiv
[/mm]
[mm] \equiv \neg (\neg [/mm] a [mm] \vee \neg [/mm] b) [mm] \vee (\neg [/mm] c [mm] \wedge \neg [/mm] c) [mm] \equiv
[/mm]
[mm] \equiv \neg (\neg [/mm] a [mm] \vee \neg [/mm] b) [mm] \vee (\neg [/mm] ( c [mm] \vee [/mm] c)
Allerdings komm ich jetzt nich weiter. Oder entspricht
[mm] \neg (\neg [/mm] a [mm] \vee \neg [/mm] b) auch einem NOR? Dann wär ich doch fertig...
zu d) "if - then - else": if a then b else c
[mm] \psi [/mm] = a [mm] \wedge [/mm] b [mm] \vee \neg [/mm] c
daraus zunächt mal (a [mm] \wedge [/mm] b):
if a then b else 0
und [mm] \neg [/mm] c:
if c then 0 else 1
zusammenführen:
if (a then b else 0) [mm] \vee [/mm] if (c then 0 else 1)
insgesamt also:
if(if(a then b else 0) then 1 else if(c then 0 else 1))
Ist das so alles korrekt?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:20 Do 19.04.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
