Bonusklausur 2022, Aufgabe zu BDD

Question

Hallo,

ich verstehe nicht richtig warum das eine davon richtig und das andere falsch ist:

Kann mir das jemand bitte kurz erklären?

Also warum ist f(x,y,z) beim zweiten gleich x?

Comments

Und eine kleine zusätzliche Frage zu der BDD Aufgabe:
Gibt es irgendein "Trick", wie ich schnell bei den Formel (die nicht auf dem Screenshot zu sehen sind) darauf komme, ob es zum BDD gehört oder nicht?
Ich hab nämlich in der BK das BDD erstellt und daraus die Formel abgeleitet und versucht umzuformen, das war aber sehr langsam.

Answer 1

Die Formel war glaube ich x or (y xor z)' (verbessere mich gerne, wenn ich falsch liege, ich habe die Bonusklausur leider nicht vor mir).

Die obere Formel ist falsch, da nicht für alle Kombinationen y und z das x egal ist. Z.B. y=1,z=0. Dann gilt mit x=1: f(x,y,z)=1 und f(x',y,z)=0. Das ist ein Widerspruch zu der Aussage.

Bei der unteren: mit x=1 gilt (unabhängig davon, was y und z sind) f(x,..,..)=1. Da hier nur der Existenzquantor ist, stimmt die gesamte Aussage (es muss für x=0 nicht gelten und gilt hier auch nicht).

Schlimmstenfalls musst du (wenn du es nicht durch hinsehen siehst oder ausprobieren) eine Wahrheitstafel daraus machen und die Aussagen dann Stück für Stück überprüfen.

Einen richtigen 'Trick' gibt es da nicht, Übung macht den Meister...

Und auch mit den anderen Formeln: Es ist definitiv sinnvoll, die gängigen Zeichen (und, oder, xor, not,...) zu kennen (inklusive deren Negation). Mir hat es geholfen, die Wahrheitstafeln im Kopf zu haben. Auch hier hilft vor allem üben, dann erkennt man die Dinge schneller. Und auch hier können Wahrheitstafeln helfen.

Falls noch etwas unklar ist, kannst du gerne noch einmal nachfragen oder in der Fragestunde fragen.

Viele Grüße
Anne (Tutorin)

Comments

Hi Anne, danke für deine Antwort.
Die Formel war x AND (y xor z)'.

Ich verstehe leider immer noch nicht so ganz bei den zwei Bedingungen, was das "Ziel" ist, also was zu überprüfen ist. Die Bedingungen mit Allquantor und Existenzquantor verstehe ich.
Ich hab irgendwie Probleme, das nach dem ":" zu verstehen.
Warum ist z.B. beim unteren f(x,y,z)=x gemeint? Also warum NUR das x?

---

Dann hatte ich es fast richtig im Kopf. Mit dieser Formel ist die untere Aussage wahr mit x=0  f(x,y,z)=0 für alle.
f(.,.,.) ist einfach eine Formel. Was kommt raus mit welcher Belegung, ist die Aussage mit dieser Belegung wahr (1) oder falsch (0).
f(x,y,z) = x AND (y xor z)' ist eine Formel, (xyz)oder(xy'z') ist die gleiche Formel nur anders geschrieben.
Mit dem speziellen x(=0) ist die Formel immer 0 (wegen x AND ()) und kann durch nur x verkürzt werden und sie sagt das gleiche aus wie die längere.

---

Alles klar, ich verstehe es jetzt.
Im Endeffekt schauen wir uns bei der unteren Formel ein spezielles x an, was in dem Fall den Wert 0 trägt. Also haben wir f(0,y,z)=x=0. Für den Fall 1 wäre das aber nicht gegeben, aber wegen dem Existenzquantor reicht ja eine Belegung.

---

Ganz genauso