Hilfe bei Aufstellen der Wahrheitstabelle-Brauche Hilfe

Wissenschaft Informatik
#1

ich habe die Wahrheitstabelle gemacht und die KNF und die DNF bereits von dieser abgeleitet, bin mir aber nicht sicher, ob die Wahrheitstabelle richtig ist:

Aufgabe: Stellen Sie eine Wahrheitstabelle auf, die für eine dreistellige Binärzahl berechnet, ob Anzahl der Einsen gerade( Ergebnis = 0) oder nicht (Ergebnis = 1).
x1 x2 x3 y
0. 0. 0. 0 (kommt hier eine 0 oder 1 raus, weil es ja hier keine Einsen gibt, für alle anderen ist das ja klar.

Und zur Resolutionsregel , die kann nicht angewandt werden, wenn es zwei Disjunktionen gibt, die sich in mehr als einer komplementären Variable unterscheiden, oder ?

#2

Und wie sieht die aus?
(Überlege dir, wie die Definition von „gerade Zahl“ lautet. )

#3

Wie lautet die, in deinen eigenen Worten?

#4

Die Tabelle sieht wie folgt aus

wie ich schon angeführt habe, haben wir drei Eingänge oder drei Bits und einen Ausgang y.

x1 x2 x3 y
0 0. 0. 0 ( nehmen wir an 0 Einsen und 0 ist gerade, daher 0)
0. 0. 1. 1
0. 1. 0. 1
0. 1. 1. 0
1 0. 0. 1
1 0. 1. 0
1.1. 0. 0
1 1. 1. 1.

Zur Resolutionregel: Ein Ausdruck wie (x1x2-x3)V(x1x2x3) wird zu x1x2, weil sich nur nicht x3 und x3 unterscheiden. Auf der linken Seite ist nicht x3 und auf der rechten Seite x3 alle anderen Eingänge sind auf beiden Seite und so kann man den Ausdruck vereinfachen weil es bei diesem Ausdruck sich die Variable x3 auf beiden Seiten unterscheidet. Und wenn wir bei diesem Ausdruck zwei Ausdrücke auf beiden Seiten hätten, die sich unterscheiden, könnte man ja die Regel nicht anwenden. Bitte korrigiere mich, falls ich was falsch verstanden habe.

#5

Wenn du dir anschaust, wie „gerade/ungerade Zahl“ definiert ist, dann musst du nicht annehmen, dass 0 gerade ist. Dann weißt du, dass es so ist.

Achtung! Die Resolutionsregel wird auf konjunktive Normalformen angewendet.

Sie basiert auf der Implikation
(Ausdruck1 ∨ A) ∧ (Ausdruck2 ∨ ¬A) → (Ausdruck1 ∨ Ausdruck2)

Entscheidend ist, dass in zwei Klauseln ein Literal jeweils einmal negiert und einmal nicht negiert auftritt. Die anderen Literale sind wurscht, denn sie wandern ja jeweils en bloc in die Resolvente.
Aus Wikipedia kopiert:

image

#6

Also ist die Tabelle richtig?

#7

Und die resolutionsregel kann angewandt werden, weil ja es nur nur eine literale sein muss die nicht negiert und negiert ist, das heißt, die werden ersetzt und die anderen einfach übernommen.

#8

Nehmen wir also an ich habe folgende DNF : (x1x2-x3)V(x1-x2x3)V(x1-x2x3)V(x1x2-x3)wäre dann die Resolution x1Vx1?

#9

Also nochmal zur Verdeutlichung (Das erste Beispiel von mir war irgendwie nicht verständlich genug): Gegeben sei z.B die DNF: (D ∧ A ∧ B) ∨ (¬B ∧ C) ∨ (D ∧ C) lautet die Resolutionsregel so: (D ∧ A ∧ B ∧ C) ∨ (D ∧ C)? Was mache ich, wenn ich folgende DNF habe:

(D ∧ A ∧ B) ∨ (¬D ∧ ¬B ∧ C) ∨ (D ∧ C), dann würde die doch so lauten: (A∧C)∨(D∧C).

#10

Die Resolutionsregel wird auf die konjunktive Normalform angewendet, nicht auf die DNF.

#11

Ja, die Tabelle ist richtig.