Boolesche Algebra - Vereinfachung

24.10.2016, 13:50

Fang222

Boolesche Algebra - Vereinfachung

Meine Frage:
Hallo zusammen, ich soll folgenden Ausdruck in die konjunktive Normalform bringen:

$\begin{eqnarray*} x_{1}\cap x_{3} (\neg x_{0}\cup \neg x_{2}) \end{eqnarray*}$

Meine Ideen:
Mir fehlt hier etwas der Ansatz. Die einzige Idee die ich hatte war DeMorgan auf die Konjunktion anzuwenden:

$\begin{eqnarray*} \neg(\neg(x_{1}) \cup \neg(x_{3})) (\neg x_{0}\cup \neg x_{2}) \end{eqnarray*}$

Wie's aber von da aus weitergehen soll, erschließt sich mir nicht.

24.10.2016, 14:38

Dopap

Auf diesen Beitrag antworten »

RE: Boolesche Algebra - Vereinfachung

Zitat:

Original von Fang222
Meine Frage:
Hallo zusammen, ich soll folgenden Ausdruck in die konjunktive Normalform bringen:

$\begin{eqnarray*} x_{1}\cap x_{3} (\neg x_{0}\cup \neg x_{2}) \end{eqnarray*}$

was ist das ? meinst du

$\begin{eqnarray*} x_{1}\land x_{3} (\neg x_{0}\lor \neg x_{2}) \end{eqnarray*}$ und was steht zwischen x3 und der Klammer verwirrt

24.10.2016, 15:03

Fang222

Auf diesen Beitrag antworten »

Ich bitte um Entschulding:

Uns wurde erklärt, dass man das Symbol für Konjunktionen weglassen kann. Der korrigierte, voll ausgeschriebene Term lautet:

$\begin{eqnarray*} x_{1}\land x_{3} \land (\neg x_{0}\lor \neg x_{2}) \end{eqnarray*}$

Mir war ehrlich gesagt nicht bewusst, dass es zwischen den logischen Operatoren und den Mengenoperatoren Unterschiede in der Betrachtungsweise gibt. Danke für den Hinweis.

24.10.2016, 16:27

Dopap

Auf diesen Beitrag antworten »

ja ja, so kocht jeder sein Süppchen. Wenn schon, dann schreibt man das "oder" mit dem Pluszeichen.

Die Xi sind logische Variable, das Ganze ist eine vierstellige Funktion $\begin{eqnarray*} \{0,1\}^4 \to \{0,1\} \end{eqnarray*}$

hier noch ne' Schreibfigurenmöglichkeit: Big Laugh

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:

  X0X1X2X3 |  (X1& X3) & (~X2 v ~X0)
  ----------+-------------------------
  1 1 1 1  |      1    *0  0   0 0   
  1 1 1 0  |      0    *0  0   0 0   
  1 1 0 1  |      1    *1  1   1 0   
  1 1 0 0  |      0    *0  1   1 0   
  1 0 1 1  |      0    *0  0   0 0   
  1 0 1 0  |      0    *0  0   0 0   
  1 0 0 1  |      0    *0  1   1 0   
  1 0 0 0  |      0    *0  1   1 0   
  0 1 1 1  |      1    *1  0   1 1   
  0 1 1 0  |      0    *0  0   1 1   
  0 1 0 1  |      1    *1  1   1 1   
  0 1 0 0  |      0    *0  1   1 1   
  0 0 1 1  |      0    *0  0   1 1   
  0 0 1 0  |      0    *0  0   1 1   
  0 0 0 1  |      0    *0  1   1 1   
  0 0 0 0  |      0    *0  1   1 1

Die KNF dürfte jetzt kein Problem mehr sein. Augenzwinkern

Und es ist nicht vielleicht die DNF gefordert ?

24.10.2016, 21:05

Fang222

Auf diesen Beitrag antworten »

Hallo,

ich suchte die konjunktive Normalform. Fairerweise habe ich mir die Aufgabe selber rausgesucht.

So wie ich das sehe, müsste ich alle Zeilen der Wahrheitstafel, bei denen das Endergebnis 0 ist (bei dir mit Stern markiert) mit Disjunktionen verbinden (negieren, wo der Wert eine 1 ergibt) und das Ganze dann mit einer Konjunktion verbinden?

Also z.B.

$\begin{eqnarray*} (\neg x_{0} \vee \neg x_{1} \vee \neg x_{2} \vee x_{3} )\wedge .... \end{eqnarray*}$

Sind ja ein paar Terme.... unglücklich

24.10.2016, 21:59

Dopap

Auf diesen Beitrag antworten »

ist dir schon aufgefallen, dass das Original schon eine KNF ist geschockt

Viel Spass beim Nachrechnen.

Das Vorgehen ist wie folgt:

Für jede Zeile, die als Resultat eine 0 liefert,
wird eine Klausel gebildet, die alle Variablen der Funktion
disjunktiv mit der invertierten Belegung verknüpft.
Die entstehenden Terme sind Maxterme.
Deren konjunktive Verknüpfung liefert die kanonische konjunktive Normalform.

Obige minimale Originalform liefert das aber nicht. unglücklich

----------------------------------------------------------------------
übrigens ist die DNF :

$\begin{eqnarray*} (\lnot X_2 \land X_1 \land X_3) \lor (\lnot X_0 \land \lnot X_1 \land \lnot X_3) \end{eqnarray*}$

Neue Frage »

Antworten »

Boolesche Algebra - Vereinfachung

Verwandte Themen