Informatiker Board | Logik | Rausfinden ob Aussagen equivalent sind

Informatiker Board » Themengebiete » Theoretische Informatik » Logik » Rausfinden ob Aussagen equivalent sind

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Rausfinden ob Aussagen equivalent sind

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

Rausfinden ob Aussagen equivalent sind

Zitatantwort auf diesen Beitrag erstellen

Hallo, ich muss eine Aufgabe lösen, wo ich mit einer calculation (also mit umformen mit den Standard-Equivalenzen, wie Commutativity, Associativity, Idempotence, Double Negation, Inversion, T/F-Elimination, Negation, Contradiction, Excluded-Middle, Distributivitz, De Morgan, Implication, Contraposition, Bi-implication, Self-equivalence) rausfinden muss, ob die Aussagen equivalent sind.

Z.B die Aufgabe:

a ^ b AND (¬a v b) <=> a

Mit einer Wahrheitstabelle ist schnell klar, dass beide Aussagen equivalent sind, aber was muss bei der Umformung rauskommen, damit ich sehe, dass es equivalent ist.

Bei a ^ b kann ich eh nicht viel machen,
bei dem Zweiten allerdings schon, hab mal umgeformt und komme dann auf:

(a ^ ¬b v a) ^ (¬a v b)

Aber was kann ich damit anfangen?

LG

25.10.2015 18:55

Nehmen Sie Shizmo in Ihre Freundesliste auf

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

Ich kann deine Gedanken nicht nachvollziehen, was tust du da?

a * b*(¬a+b) = a*b*¬a + a*b*b = a*b.

__________________
Syntax Highlighting fürs Board (Link)

25.10.2015 19:05

Nehmen Sie eulerscheZahl in Ihre Freundesliste auf

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

Naja das AND soll bedeuten, dass es zwei verschiedene sind und ich die miteinander vergleichen soll. Dann kann ich sie ja nicht einfach mit einem und verknüpfen oder schon?

Hab auch eine zweite, wo ich rausgefunden habe, dass sie equivalent sind, dank einer Wahrheitstabelle, aber wieder nicht weiß, wie ich umformen soll, damit ich rausfinde dass sie equivalent sind.

((a => b) => ¬a) AND (¬b v ¬a) ^ (¬b v b)

//edit: oder ich versteh einfach nicht, wie/was du jetzt da gemacht hast.

//edit2: Im Anhang noch die originale Angabe!

Shizmo hat dieses Bild (verkleinerte Version) angehängt:

Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von Shizmo: 25.10.2015 21:13.

25.10.2015 19:25

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

Nochmal die Angabe zur b):
$[latex]a \wedge b \wedge (\overline{a}\vee b)[/latex]$ . Statt des $[latex]\wedge[/latex]$ kann man auch ein Mal schreiben, statt des $[latex]\vee[/latex]$ ein Plus.
$[latex]a \cdot b \cdot (\overline{a}+b)[/latex]$ . Das kann man auch in der boolschen Algebra ausmultiplizieren.
$[latex]a\cdot b\cdot\overline{a}+a\cdot b\cdot b[/latex]$ .
$[latex]a\cdot\overline{a} = 0[/latex]$ , womit der erste Teil wegfällt. $[latex]b\cdot b = b[/latex]$ , also bleibt $[latex]a\cdot b[/latex]$

__________________
Syntax Highlighting fürs Board (Link)

26.10.2015 05:56

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

Hallo danke fuer deine Antwort.

Also ich versteh schon, dass man es auch anders schreiben kann.

Aber ich soll mit (¬a v b) <=> a zeigen, dass es das gleich ist wie a ^ b

Da kann ich ja nicht alles zusammenfassen und dann zeigen, dass es mit a äquivalent ist, denn das ist ja ein Teil der zweiten Angabe.
Kannst ja mal Aufgabe a) zeigen, vielleicht wirds dann klarer fuer mich.

Außerdem sollen wir glaub ich nichts ausmultiplizieren, sondern Schritt fuer Schritt zeigen, wie wir vom ersten auf den zweiten Teil kommen, indem wir auch immer dazuschreiben, zB:
Aufgabe a) erster Teil:

((a => b) => ¬a) {implication, leibniz}
(¬a v b) => ¬a {implication, substitution}
¬(¬a v b) v ¬a {de Morgan, leibniz}
a v ¬b v ¬a

So weiter komm ich da nicht, bei Teil 2 schon:

(¬b v ¬a) ^ (¬b v b) {excluded middle, leibnix}
(¬b v ¬a) ^ (T) {True/False-elimination, substituion}
(¬b v ¬a) {De Morgan, substitution}
¬(b ^ a)

So und wie zeige ich jetzt das beides äquivalent ist?
Wenn ich ein <=> zwischen Teil 1 und 2 stelle und dann weiter so verfahr komm ich auf:

(¬a v b ^ a v ¬b v a) ^ (b ^ a) v (a ^ ¬b v ¬a)

So, das sollte jetzt True ergeben, dann wärs äquivalent großes Grinsen

Darf man irgendwas kürzen???

Also zumindest kannst du dir jetzt wahrscheinlich vorstellen, wie ich versuche die Aufgabe zu lösen und erkennst eventuell den Fehler Augenzwinkern

26.10.2015 19:13

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

Ich glaube, ich habe die Aussage falsch verstanden: das "and" ist keine logische Verknüpfung, sondern soll die Aussagen trennen, oder?

Sehen wir uns mal deine Umformungen an:
Du kommst von ¬(¬a v b) auf a v ¬b. Nach de Morgan muss aber das ODER zum UND werden.
Wir haben also:
$[latex]a \cdot \overline{b} + \overline{a}[/latex]$ . Das $[latex]\overline{a}[/latex]$ kann man erweitern:
$[latex]a\overline{b} + \overline{a}b+\overline{a}\overline{b}[/latex]$ . Man kann einen Teil des Terms auch einfach doppelt schreiben:
$[latex](a\overline{b}+\overline{a}\overline{b}) + (\overline{a}b+\overline{a}\overline{b})[/latex]$ . Die beiden Klammern haben jeweils eine Variable gemeinsam, die andere kommt einmal negiert und einmal nicht negiert vor, fällt also weg.
$[latex]\overline{a}+\overline{b}[/latex]$
Ein letztes mal de Morgan und du bist am Ziel.

__________________
Syntax Highlighting fürs Board (Link)

26.10.2015 20:01

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

Vielen Dank fuer deinen Beitrag.

Zitat:

Original von eulerscheZahl
Ich glaube, ich habe die Aussage falsch verstanden: das "and" ist keine logische Verknüpfung, sondern soll die Aussagen trennen, oder?

Ja genau

Zitat:

Sehen wir uns mal deine Umformungen an:
Du kommst von ¬(¬a v b) auf a v ¬b. Nach de Morgan muss aber das ODER zum UND werden.

Ups, ja genau.

Zitat:

Wir haben also:
$[latex]a \cdot \overline{b} + \overline{a}[/latex]$ . Das $[latex]\overline{a}[/latex]$ kann man erweitern:
[...]

Wieso darf man denn ein ¬a zu einem ¬a ^ b v ¬a ^ ¬b erweitern?

Hmm ich glaub mir fehlen da wohl noch ein paar Regeln, ich wusste nicht das man da einfach was erweitern kann oder Glieder darin verschieben oder etwas streichen verwirrt

26.10.2015 22:29

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

$[latex]xy+x\overline{y} = x(y+\overline{y}) = x\cdot 1 = x[/latex]$ . Ist das klar?
Die Umformung geht auch in die andere Richtung, genau das habe ich gemacht.

Bei einem UND bzw. ODER kannst du auch tauschen:
$[latex]x \vee y = y \vee x[/latex]$ , sollte sich von selbst erklären.

Und du kannst einen Term auch doppelt hinschreiben
$[latex]x = x \vee x[/latex]$

__________________
Syntax Highlighting fürs Board (Link)

27.10.2015 05:19

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

Ja ich habs, hey vielen vielen Dank fuer die Hilfe und vor allem Geduld Daumen hoch

28.10.2015 21:27

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Logik » Rausfinden ob Aussagen equivalent sind