Logische Verknüpfungen auf funktionale Vollständigkeit prüfen

02.10.2013, 14:43

un1x

Auf diesen Beitrag antworten »

Logische Verknüpfungen auf funktionale Vollständigkeit prüfen

Hi

Es gilt

Zitat:

Eine Menge logischer Verknüpfungen heisst funktional vollständig, wenn man alle
Junktoren ( $\begin{eqnarray*} \wedge ,\lor ,\rightarrow ,\lnot \end{eqnarray*}$ ) durch Kombinationen dieser Verknüpfungen äquivalent ausdrücken
kann.

Zeigen Sie, dass folgende Mengen von Verknüpfungen funktional vollständig sind:

Die erste aufgabe waere

$\begin{eqnarray*} \{\lnot ,\lor\} \end{eqnarray*}$

Meine Antwort:

$\begin{eqnarray*} A \wedge B \equiv \lnot(\lnot A \lor \lnot B) \end{eqnarray*}$
$\begin{eqnarray*} A \rightarrow B \equiv \lnot A \lor B \end{eqnarray*}$

Somit waere bewiesen, dass diese funktional vollstaendig sind, sofern ich die Aufgabe richtig verstanden habe.

Jetzt stehe ich aber bei einer Aufgabe fest:

$\begin{eqnarray*} \{|\}, wobei A | B := \lnot(A \wedge B) (NAND-Operator) \end{eqnarray*}$

Muss ich jetzt dies beweisen, indem ich $\begin{eqnarray*} \{\lor ,\rightarrow \} \end{eqnarray*}$ benutze?

Ich habe mir ueberlegt, wie ich $\begin{eqnarray*} \lnot (A \wedge B) \end{eqnarray*}$ nur mit $\begin{eqnarray*} \{\lor ,\rightarrow \} \end{eqnarray*}$ darstellen kann. Aber ich kriege das nicht wirklich hin. Oder bin ich da auf dem falschen Weg?

02.10.2013, 14:51

un1x

Auf diesen Beitrag antworten »

Mein Ansatz:

$\begin{eqnarray*} \lnot(A \wedge B) \equiv \lnot A \lor \lnot B \equiv A \rightarrow \lnot B \end{eqnarray*}$

02.10.2013, 15:01

jimmyt

Auf diesen Beitrag antworten »

Zitat:

Original von un1x
Mein Ansatz:

$\begin{eqnarray*} \lnot(A \wedge B) \equiv \lnot A \lor \lnot B \equiv A \rightarrow \lnot B \end{eqnarray*}$

Ich sag mal: das stimmt alles.
Damit hast du ja alle 4 Junktoren der Aufgabenstellung benutzt. Augenzwinkern

Augenzwinkern

02.10.2013, 15:03

un1x

Auf diesen Beitrag antworten »

Zitat:

Original von jimmyt
Ich sag mal: das stimmt alles.
Damit hast du ja alle 4 Junktoren der Aufgabenstellung benutzt. Augenzwinkern

Augenzwinkern

Und das ist wirklich so einfach? Tanzen

Tanzen

02.10.2013, 15:19

jimmyt

Auf diesen Beitrag antworten »

Naja, Voraussetzung dass die Aufgabe so gemeint ist. Aber wenn sie so gemeint ist und ich sie richtig verstanden habe, dann sage ich mal ja. Augenzwinkern

Augenzwinkern

Du hast das logische UND durch das logische ODER erklärt (De Morgan), dann das logische ODER durch die Implikation erklärt.
Die Negation hast du auch benutzt ... hmm, vielleicht kannst du die Negation $\begin{eqnarray*} \neg \end{eqnarray*}$ noch erklären.
Aber ansonsten ist es, meiner bescheidenen Meinung nach, ok.

edit von sulo: Doppeltes Vollzitat entfernt.

02.10.2013, 15:23

Huggy

Auf diesen Beitrag antworten »

So einfach ist das natürlich nicht. Du musst 4 Äquivalenzen aufschreiben

$\begin{eqnarray*} \neg A \equiv ... \end{eqnarray*}$

$\begin{eqnarray*} A \land B \equiv ... \end{eqnarray*}$

$\begin{eqnarray*} A \lor B \equiv ... \end{eqnarray*}$

$\begin{eqnarray*} A \to B \equiv ... \end{eqnarray*}$

Dabei darf auf der rechten Seite neben den Aussagevariablen A und B nur die |-Verknüpfung auftreten.

Anzeige

02.10.2013, 15:37

Guppi12

Auf diesen Beitrag antworten »

Kleiner Zusatz:

Damit das ganze etwas übersichtlicher wird, kannst du, wenn du beispielsweise $\begin{eqnarray*} \neg A \end{eqnarray*}$ bereits mit der |-Verknüpfung ausgedrückt hast, auch das $\begin{eqnarray*} \neg \end{eqnarray*}$ bereits verwenden um die restlichen zu zeigen. Gleiches gilt für die anderen.

02.10.2013, 15:57

un1x

Auf diesen Beitrag antworten »

Zitat:

Original von Huggy
So einfach ist das natürlich nicht. Du musst 4 Äquivalenzen aufschreiben

$\begin{eqnarray*} \neg A \equiv ... \end{eqnarray*}$

$\begin{eqnarray*} A \land B \equiv ... \end{eqnarray*}$

$\begin{eqnarray*} A \lor B \equiv ... \end{eqnarray*}$

$\begin{eqnarray*} A \to B \equiv ... \end{eqnarray*}$

Dabei darf auf der rechten Seite neben den Aussagevariablen A und B nur die |-Verknüpfung auftreten.

Dachte ich mir, dass hier noch ein Haken steckt..

D.h auf der rechten Seite darf keines der Zeichen $\begin{eqnarray*} \wedge ,\lnot ,\lor ,\rightarrow \end{eqnarray*}$ stehen? Und das geht? Big Laugh

Big Laugh

02.10.2013, 16:00

Guppi12

Auf diesen Beitrag antworten »

Zitat:

D.h auf der rechten Seite darf keines der Zeichen $\begin{eqnarray*} \wedge ,\lnot ,\lor ,\rightarrow \end{eqnarray*}$ stehen? Und das geht?

Falls die Frage ernst gemeint war: Ja, das geht.

02.10.2013, 16:04

un1x

Auf diesen Beitrag antworten »

OK. Mal ein Versuch

$\begin{eqnarray*} \neg A \equiv A | A \end{eqnarray*}$

$\begin{eqnarray*} \neg B \equiv B | B \end{eqnarray*}$

$\begin{eqnarray*} A \land B \equiv (A|B)|(A|B) \end{eqnarray*}$

$\begin{eqnarray*} A \lor B \equiv \lnot A|\lnot B \end{eqnarray*}$

$\begin{eqnarray*} A \to B \equiv A|\lnot B \end{eqnarray*}$

02.10.2013, 16:12

Math1986

Auf diesen Beitrag antworten »

Zitat:

Original von Huggy
So einfach ist das natürlich nicht. Du musst 4 Äquivalenzen aufschreiben

$\begin{eqnarray*} \neg A \equiv ... \end{eqnarray*}$

$\begin{eqnarray*} A \land B \equiv ... \end{eqnarray*}$

$\begin{eqnarray*} A \lor B \equiv ... \end{eqnarray*}$

$\begin{eqnarray*} A \to B \equiv ... \end{eqnarray*}$

Dabei darf auf der rechten Seite neben den Aussagevariablen A und B nur die |-Verknüpfung auftreten.

Wobei es ausreicht, die Äquivalenzen
$\begin{eqnarray*} \lnot A \equiv ... \end{eqnarray*}$
$\begin{eqnarray*} A \lor B \equiv ... \end{eqnarray*}$
zu zeigen, dass das funktional vollständig ist folgt schon aus seiner ersten Aufgabe.

02.10.2013, 16:18

un1x

Auf diesen Beitrag antworten »

Zitat:

Original von un1x
OK. Mal ein Versuch

$\begin{eqnarray*} \neg A \equiv A | A \end{eqnarray*}$

$\begin{eqnarray*} \neg B \equiv B | B \end{eqnarray*}$

$\begin{eqnarray*} A \land B \equiv (A|B)|(A|B) \end{eqnarray*}$

$\begin{eqnarray*} A \lor B \equiv \lnot A|\lnot B \end{eqnarray*}$

$\begin{eqnarray*} A \to B \equiv A|\lnot B \end{eqnarray*}$

Ist wohl bei den letzten 2 posts untergekommen.. Habe eine Formel gefunden wo besagt

$\begin{eqnarray*} (A \wedge A) \equiv A \end{eqnarray*}$ ist. Somit war es dann relativ einfach. (Sofern die Loesung stimmt)

02.10.2013, 16:24

Math1986

Auf diesen Beitrag antworten »

Zitat:

Original von un1x
$\begin{eqnarray*} \neg A \equiv A | A \end{eqnarray*}$

Richtig.
$\begin{eqnarray*} \neg A \equiv A | A \equiv\lnot\left(A\land A\right) \equiv\lnot A \end{eqnarray*}$

Zitat:

Original von un1x
$\begin{eqnarray*} \neg B \equiv B | B \end{eqnarray*}$

Richtig. Ist das selbe wie oben, nur mit A=B. Es ist also unnötig, dies zweimal zu zeigen.

Zitat:

Original von un1x
$\begin{eqnarray*} A \land B \equiv (A|B)|(A|B) \end{eqnarray*}$

Richtig. Da du im vorherigen schon gezeigt hast, dass du $\begin{eqnarray*} \lnot \end{eqnarray*}$ darstellen kannst, darfst du dies hier auch verwenden, und kannst dies darstellen als
$\begin{eqnarray*} A \land B \equiv\lnot (A|B)\equiv\lnot\lnot\left(A\land B\right)=A\land B \end{eqnarray*}$

Zitat:

Original von un1x
$\begin{eqnarray*} A \lor B \equiv \lnot A|\lnot B \end{eqnarray*}$

Richtig. Folgt eigendlich direkt aus de Morgan.

Zitat:

Original von un1x
$\begin{eqnarray*} A \to B \equiv A|\lnot B \end{eqnarray*}$

Richtig.

------------------------------------------------

Es genügt also zu zeigen, dass
$\begin{eqnarray*} \neg A \equiv A | A \equiv\lnot\left(A\land A\right) \equiv\lnot A \end{eqnarray*}$
$\begin{eqnarray*} A \lor B \equiv \lnot A|\lnot B \end{eqnarray*}$
und sich dann auf die erste Aufgabe zu beziehen.

02.10.2013, 16:24

Math1986

Auf diesen Beitrag antworten »

Zitat:

Original von un1x
Habe eine Formel gefunden wo besagt

$\begin{eqnarray*} (A \wedge A) \equiv A \end{eqnarray*}$ ist.

Richtig (Idempotenz)

02.10.2013, 16:50

un1x

Auf diesen Beitrag antworten »

Cool. Danke

Und $\begin{eqnarray*} A \otimes B := A \rightarrow \lnot B \end{eqnarray*}$

Muss ich bei dem auch wieder folgendes beweisen?

$\begin{eqnarray*} <br /> \lnot B \equiv (B \otimes B) \equiv B \rightarrow \lnot B \equiv \lnot B \lor \lnot B \equiv \lnot(B \wedge B) \end{eqnarray*}$

$\begin{eqnarray*} <br /> A \wedge B \equiv \lnot(A \otimes B) \equiv \lnot (\lnot A \lor \lnot B) \equiv \lnot \lnot (A \wedge B)<br /> \end{eqnarray*}$

$\begin{eqnarray*} <br /> A \lor B \equiv (\lnot A \otimes \lnot B) \equiv \lnot A \rightarrow B \equiv A \lor B<br /> \end{eqnarray*}$

02.10.2013, 17:06

Math1986

Auf diesen Beitrag antworten »

Alles richtig (hätte nach Aufgabe 1 auch gereicht, nur "nicht" und "oder" zu zeigen)

Interessanter ist hier die Umformung:
$\begin{eqnarray*} A\otimes B\equiv A\rightarrow\lnot B \equiv\lnot A\lor\lnot B\equiv\lnot\left(A\land B\right)\equiv A| B \end{eqnarray*}$
Das ist genau der selbe Ausdruck wie in Aufgabe 2. Genügt also, das so umzuformen und sich darauf zu beziehen.

02.10.2013, 17:07

un1x

Auf diesen Beitrag antworten »

Habe ich auch gesehen. Ich habe es trotzdem mal alles ausgeschrieben, da ich nicht weiss ob ich auf andere Aufgaben verweisen darf smile

smile

Danke euch.

02.10.2013, 17:08

Math1986

Auf diesen Beitrag antworten »

Zitat:

Original von un1x
Habe ich auch gesehen. Ich habe es trotzdem mal alles ausgeschrieben, da ich nicht weiss ob ich auf andere Aufgaben verweisen darf smile

smile

Darfst du.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »