Informatiker Board | Druckvorschau: Rausfinden ob Aussagen equivalent sind

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
---- Logik (http://www.informatikerboard.de/board/board.php?boardid=16)
----- Rausfinden ob Aussagen equivalent sind (http://www.informatikerboard.de/board/thread.php?threadid=2504)

Geschrieben von Shizmo am 25.10.2015 um 18:55:

Rausfinden ob Aussagen equivalent sind

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

Geschrieben von eulerscheZahl am 25.10.2015 um 19:05:

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

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

Geschrieben von Shizmo am 25.10.2015 um 19:25:

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!

Geschrieben von eulerscheZahl am 26.10.2015 um 05:56:

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]$

Geschrieben von Shizmo am 26.10.2015 um 19:13:

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

Geschrieben von eulerscheZahl am 26.10.2015 um 20:01:

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.

Geschrieben von Shizmo am 26.10.2015 um 22:29:

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

Geschrieben von eulerscheZahl am 27.10.2015 um 05:19:

$[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]$