Funktionale Vollständigkeit < Technische Inform. < Praktische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Zeigen Sie: { [mm] \to [/mm] ; 0} ist funktional vollständig.
wobei [mm] \overline{x} \cup [/mm] y = x [mm] \to [/mm] y ist. |
Hallo Leute,
es geht hier um den Beweis für die Boolsche Algebra.
Nand und Nor hab ich bereits beweisen können, allerdings stellt sich mir bei dieser Aufgabe die Frage, wie ich denn die Null verwenden darf und vorallem warum!?
Also mein 1. Ansatz:
[mm] \overline{x} [/mm] = [mm] \overline{x} [/mm] + 0 = [mm] \overline{x} \to [/mm] y.
Wobei 0 ja nicht zwangsweise y ist [mm] \Rightarrow [/mm] falsch
Aus "x nicht" kann ich ja laut der Gesetze der Boolschen Algebra "x nicht" + "x nicht" gemacht werden allerdings müsste ich dann die 2te negation beim 2ten x irgendwie umformen, aber wie?
Gruss
math
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:11 Mo 01.03.2010 | | Autor: | cycore |
hi..
nimms mir bitte nich übel, aber ich werde definitiv junktoren verwenden^^ also [mm] \perp [/mm] ist deine 0
wenn du das schon für [mm] \{\vee, \neg\} [/mm] gezeigt hast bist du schon fast fertig...
aber ich sehe da ein problem: du sagst [mm] {a\to b} [/mm] sei äquivalent zu [mm] {\neg a \oplus b} [/mm] aber das stimmt i.A. nicht! [mm] {(a\to b)\equiv (\neg a\vee b)}
[/mm]
aber so krigst du dann ganz einfach äquivalenz zwischen [mm] a\to\perp [/mm] und [mm] {(\neg a \vee\perp)\equiv\neg a}. [/mm] Also ist [mm] \neg [/mm] schonmal fertig.
Ich denke ab hier kommst du alleine weiter, denn wie bekommst du [mm] \vee [/mm] aus [mm] \to [/mm] und [mm] \neg [/mm] ?
;)
Korrektur: selbst wenn du [mm] {a\to b} [/mm] so definierst wie du es geschrieben hast funktioniert es, denn auch hier erhälst du [mm] {(\neg a\oplus\perp)\equiv\neg a} [/mm] ..da wird der nächste schritt zwar ein wenig komlplizierter, aber auch das ist machbar
gruß cycore
|
|
|
| |
|
Hallo Leute,
ich bin bei meiner Suche auf diese Antwort gestossen.
Ich habe ebenfalls Probleme mit dem Beweis der Funktionalen Vollstaendigkeit.
NAND und NOR sind FV, das konnte ich noch nachvollziehen.
Aber fuer diesen Beweis { [mm] \rightarrow [/mm] , 0 } fehlt mir das Verstandnis.
Ausgehend vom NAND: [mm]x \uparrow y = \overline{xy}[/mm]
1. [mm]\overline{x} = \overline{x} + \overline{x} = \overline{ \overline{ \overline{x} + \overline{x}}} = \overline{xx} = x \uparrow x[/mm]
2. [mm]x + y = \neg (x + y) = \neg ( \neg x \neg y )= \overline{ x } \uparrow \overline{ y } = ( x \uparrow x ) \uparrow ( y \uparrow y )[/mm]
3. [mm]xy = \neg (\neg (xy)) = \neg (x \uparrow y) = (x \uparrow y) \uparrow (x \uparrow y)[/mm]
Habe ich mir folgenden Ansatz fuer [mm] (\rightarrow, [/mm] 0); x [mm] \rightarrow [/mm] y = [mm] \overline{x} [/mm] + y ueberlegt:
1. [mm]\overline{x} = \overline{x} + 0 = x \to 0[/mm] hier fehlt jedoch das y
2. [mm]x + y = \overline{ \overline{x + y}} = \neg( \negx \negy )[/mm][mm]x + y = \overline{ \overline{x + y}} = \neg(\neg x \neg y) = \overline{(x \rightarrow 0)(y \rightarrow 0)} = [(x \rightarrow 0)(y \rightarrow 0)] \rightarrow 0[/mm]
(hier gehe ich von der Wahrheit der ersten Aussage aus)
3. [mm]xy = \overline{ \overline{xy}} = \overline{x} + \overline{y} = [(x \rightarrow 0) + (y \rightarrow 0)] \rightarrow 0[/mm] (hier ebenfalls)
Ich habe das ungute Gefuehl, das das alles so nicht stimmt.
1. Frage: Stimmt mein Beweis :)?
2. Frage: Wie gehe ich vor wenn nicht?
Gruss
adrenaline
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:42 Di 13.03.2012 | | Autor: | cycore |
Hallo adrenaline,
das funktioniert soweit.
> [...]
>
> Habe ich mir folgenden Ansatz fuer [mm](\rightarrow,[/mm] 0); x
> [mm]\rightarrow[/mm] y = [mm]\overline{x}[/mm] + y ueberlegt:
>
> 1. [mm]\overline{x} = \overline{x} + 0 = x \to 0[/mm] hier fehlt
> jedoch das y
und das ist gar kein problem, was sollte die Negation auch mit y zu tun haben?
>
> 2. [mm]x + y = \overline{ \overline{x + y}} = \neg( \negx \negy )[/mm][mm]x + y = \overline{ \overline{x + y}} = \overline{\overline{x}\overline{y}} = \overline{(x \rightarrow 0)(y \rightarrow 0)} = [(x \rightarrow 0)(y \rightarrow 0)] \rightarrow 0[/mm]
> (hier gehe ich von der Wahrheit der ersten Aussage aus)
Du siehst, dass der zweite Schritt überflüssig ist — gehe ich richtig in der Annahme, dass du [mm]x+y = \overline{ \overline{x + y}} = \overline{\overline{x}\;\overline{y}} \dots[/mm] meintest?
> 3. [mm]xy = \overline{ \overline{xy}} = \overline{x} + \overline{y} = [(x \rightarrow 0) + (y \rightarrow 0)] \rightarrow 0[/mm]
> (hier ebenfalls)
Abgesehen davon, dass hier wirklich ein Strich über [mm]\overline{x}+\overline{y}[/mm] fehlt. Demnach:
>
> [...]
>
> 1. Frage: Stimmt mein Beweis :)?
Vgl. Korrektur.
> 2. Frage: Wie gehe ich vor wenn nicht?
Hiermit hinfällig ;)
Gruß cycore
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:48 Mo 19.03.2012 | | Autor: | adrenaline |
Hallo cycore, danke fuer die Rueckmeldung.
Du siehst, dass der zweite Schritt überflüssig ist — gehe ich richtig in der Annahme, dass du $ x+y = [mm] \overline{ \overline{x + y}} [/mm] = [mm] \overline{\overline{x}\;\overline{y}} \dots [/mm] $ meintest?
Du hast recht der eine Schritt ist ueberfluessig, ich hatte Probleme mit dem Formeleditor.
Gruss
adrenaline
|
|
|
|
