Funkt. Vollständigkeit < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Sind die Operatoren Implikation und Negation zusammen eine funktional vollständige Signatur ? ( Boolesche Terme ) |
Hallo,
ich wollte noch ein wenig Logik üben und funktionale Vollständigkeiten sind für mich die größte Hürde.
Wie zeigt man sowas ? Wie geht man da vor ?
|
|
| |
|
Hallo,
> Sind die Operatoren Implikation und Negation zusammen eine
> funktional vollständige Signatur ? ( Boolesche Terme )
> Hallo,
>
> ich wollte noch ein wenig Logik üben und funktionale
> Vollständigkeiten sind für mich die größte Hürde.
>
> Wie zeigt man sowas ? Wie geht man da vor ?
Du kennst sicher ein funktional vollst. System, etwa [mm] $\{\neg,\wedge\}$
[/mm]
Wenn du [mm] $\neg$ [/mm] und [mm] $\wedge$ [/mm] durch [mm] $\neg$ [/mm] und [mm] $\Rightarrow$ [/mm] ausdrücken kannst, hast du gewonnen ...
Wobei für [mm] $\neg$ [/mm] nichts zu tun ist.
Versuche [mm] $p\wedge [/mm] q$ als Verknüpfung von Negation(en) und Implikation(en) darzustellen ..
Gruß
schachuzipus
|
|
|
| |
|
Hallo,
habs versucht:
p [mm] \wedge [/mm] q [mm] \equiv \neg( \neg [/mm] p [mm] \vee \neg [/mm] q) [mm] \equiv \neg [/mm] ( [mm] \neg [/mm] p -> [mm] \neg \neg [/mm] q)
Ist das richtig ?
Hab folgenden Trick benutzt:
p -> q [mm] \equiv \neg [/mm] q [mm] \vee [/mm] p...
|
|
|
| |
|
Hallo nochmal,
das sieht richtig aus, wenn m.E. auch etwas umständlich ...
Gruß
schachuzipus
|
|
|
| |
|
Hallo,
danke für die Antwort.
Damit habe ich jetzt bewiesen , dass Negation und Implikation funktional vollständig ist , oder ?
|
|
|
| |
|
Hallo nochmal,
ja, wenn du schon weißt, dass [mm] $\{\wedge,\neg\}$ [/mm] f.v. ist ...
Alles, was du mit [mm] $\wedge,\neg$ [/mm] darstellen kannst, kannst du auch mit [mm] $\Rightarrow,\neg$ [/mm] darstellen.
Du hast ja gezeigt, dass man das [mm] $\wedge$ [/mm] geeeignet ersetzen kann.
Gruß
schachuzipus
|
|
|
| |
|
> Hallo nochmal,
>
> ja, wenn du schon weißt, dass [mm]\{\wedge,\neg\}[/mm] f.v. ist
> .
>
> Alles, was du mit [mm]\wedge,\neg[/mm] darstellen kannst, kannst du
> auch mit [mm]\Rightarrow,\neg[/mm] darstellen.
>
> Du hast ja gezeigt, dass man das [mm]\wedge[/mm] geeeignet ersetzen
> kann.
>
> Gruß
>
>
> schachuzipus
Hallo,
aber [mm] \{\wedge,\neg\} [/mm] ist als Ganzes f.v , nicht z.B. [mm] \wedge [/mm] allein , oder ?
Ich muss also noch die Negation mit Implikation & Negation ausdrücken, erst dann wäre ich doch fertig , oder ?
|
|
|
| |
|
Hallo nochmal,
> > Hallo nochmal,
> >
> > ja, wenn du schon weißt, dass [mm]\{\wedge,\neg\}[/mm] f.v. ist
> > .
> >
> > Alles, was du mit [mm]\wedge,\neg[/mm] darstellen kannst, kannst du
> > auch mit [mm]\Rightarrow,\neg[/mm] darstellen.
> >
> > Du hast ja gezeigt, dass man das [mm]\wedge[/mm] geeeignet ersetzen
> > kann.
> >
> > Gruß
> >
> >
> > schachuzipus
> Hallo,
>
> aber [mm]\{\wedge,\neg\}[/mm] ist als Ganzes f.v , nicht z.B. [mm]\wedge[/mm]
> allein , oder ?
Jo
Nur "und" reicht nicht ...
> Ich muss also noch die Negation mit Implikation & Negation
> ausdrücken,
Du hast doch in beiden Systemen die Negation, da brauchst du nichts zu zeigen, allein die Ersetzung der Konjunktion durch Implikation/Negation war zu zeigen
> erst dann wäre ich doch fertig , oder ?
Nee, bist du schon 
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:06 Fr 03.01.2014 | | Autor: | pc_doctor |
Alles klar, vielen Dank für deine Hilfe.
|
|
|
|
