12,123
edits
Changes
→Logical Equivalence Problem: TXT → TeX
[http://mathforum.org/kb/message.jspa?messageID=6513648 Problem posted by Mike1234 on the Discrete Math List at the Math Forum].
[http://mathforum.org/kb/message.jspa?messageID=6513648 Problem posted by Mike1234 on the Discrete Math List at the Math Forum].
* Required to show that <math>\lnot (p \Leftrightarrow q)</math> is equivalent to <math>(\lnot q) \Leftrightarrow p.</math>
===Solution===
===Solution===
[http://mathforum.org/kb/plaintext.jspa?messageID=6514666 Solution posted by Jon Awbrey, working in the medium of logical graphs].
[http://mathforum.org/kb/plaintext.jspa?messageID=6514666 Solution posted by Jon Awbrey, working in the medium of logical graphs].
In logical graphs, the required equivalence looks like this:
In logical graphs, the required equivalence looks like this:
Back to the initial problem:
Back to the initial problem:
* Show that ~(p <=> q) is equivalent to (~q) <=> p.
* Show that <math>\lnot (p \Leftrightarrow q)</math> is equivalent to <math>(\lnot q) \Leftrightarrow p.</math>
We can translate this into logical graphs by supposing that we have to express everything in terms of negation and conjunction, using parentheses for negation — that is, "(x)" for "not x" — and simple concatenation for conjunction — "xyz" or "x y z" for "x and y and z".
We can translate this into logical graphs by supposing that we have to express everything in terms of negation and conjunction, using parentheses for negation — that is, "(x)" for "not x" — and simple concatenation for conjunction — "xyz" or "x y z" for "x and y and z".
Putting all the pieces together, the problem given amounts to proving the following equation, expressed in the forms of logical graphs and parenthetical parse strings, respectively:
Putting all the pieces together, the problem given amounts to proving the following equation, expressed in the forms of logical graphs and parenthetical parse strings, respectively:
* Show that ~(p <=> q) is equivalent to (~q) <=> p.
* Show that <math>\lnot (p \Leftrightarrow q)</math> is equivalent to <math>(\lnot q) \Leftrightarrow p.</math>
<pre>
<pre>