KNF / Booleschen Funktionen: 4-Tupel Z(a3, a2, a1, a0) = ∑³i=0 ai • 2i (Bitfolge und Bittupel)

Question

Wie Sie wissen, kann man jede Bitfolge und damit jedes Bittupel als natürliche Zahl interpretieren. Wir wollen das in dieser Aufgabe für 4-Tupel wie üblich festlegen:
Z(a_3, a_2, a_1, a₀) = ∑_³i=0 a_i • 2ⁱ

Finden Sie für die folgenden Booleschen Funktionen möglichst einfache Darstellungen als KNF. Denken Sie immer zuerst darüber nach, ob Sie wirklich die kanonische KNF konstruieren müssen, oder ob Sie durch andere Überlegungen schneller und eleganter zum Ziel kommen (welche Tupel aus f^-1 (0) kann man zusammenfassen).

                         1 falls Z(x, y, z, u) durch 4 teilbar ist

f (x, y, z, u) =

                          0 sonst

 

                         1 falls Z(x, y, z, u) ≤ 5

g(x, y, z, u) =

                         0 sonst

 

                          1 falls (Z(x, y, z, u) mod 8) ≠ 3

h(x, y, z, u) =

                          0 sonst

Comments

Welche Art von Zahlen sind denn bei den a_i erlaubt? Nur 0 und 1, alle Natürlichen Zahlen, oder gar alle reellen?

---

Ich habe aus 2_i ein 2ⁱ gemacht und vermute, dass a_i nur 0 und 1 sein dürfen.

---

n-Tuppel kenne ich auf Deutsch mit zwei 'p'.

Answer 1

Ich nehme mal an, dass a_i 0 oder 1 sind.  Und mache ein paar Bemerkungen zu den einzelnen Funktionen.

                           1 falls Z(x, y, z, u) durch 4 teilbar ist

f (x, y, z, u) =

                          0 sonst

Für den Wert 1 müssen im binären Zahlensystem z und u 0 sein. D. h. es muss gelten ⌉z ∧ ⌉u . Das ist dasselbe wie f…=     ⌉(z ∨ u)

Für x und y ist nichts vorgeschrieben.

 

                         1 falls Z(x, y, z, u) ≤ 5

g(x, y, z, u) =

                         0 sonst

(x und y sind 0 ) oder (x und z sind 0)

g… =(nicht (x oder y) ) oder (nicht (x oder z))

                          1 falls (Z(x, y, z, u) mod 8) ≠ 3

h(x, y, z, u) =

                          0 sonst

h…= nicht (z und u)

h…=(nicht z) oder (nicht u)