12,080
edits
Changes
→Logical Equivalence Problem
==Logical Equivalence Problem==
==Logical Equivalence Problem==
===Problem===
* [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].
* [http://mathforum.org/kb/plaintext.jspa?messageID=6514666 Solution posted by Jon Awbrey, working by way of logical graphs].
===Solution===
* [http://mathforum.org/kb/plaintext.jspa?messageID=6514666 Solution posted by Jon Awbrey, working in the medium of logical graphs].
<pre>
<pre>
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
</pre>
===Discussion===
o12:30, 2 December 2008 (PST)[[User:Jon Awbrey|Jon Awbrey]] 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)[[User:Jon Awbrey|Jon Awbrey]] 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)[[User:Jon Awbrey|Jon Awbrey]] 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)[[User:Jon Awbrey|Jon Awbrey]] 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)[[User:Jon Awbrey|Jon Awbrey]] 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)[[User:Jon Awbrey|Jon Awbrey]] 12:30, 2 December 2008 (PST)o
Back to the initial problem:
* Show that ~(p <=> q) is equivalent to (~q) <=> p
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".
In this form of representation, for historical reasons called
the "existential interpretation" of logical graphs, we have
the following expressions for basic logical operations:
The disjunction "x or y" is written "((x)(y))".
This corresponds to the logical graph:
x y
o o
\ /
o
|
O
The disjunction "x or y or z" is written "((x)(y)(z))".
This corresponds to the logical graph:
x y z
o o o
\|/
o
|
O
Etc.
The implication "x => y" is written "(x (y)),
which can be read "not x without y" if that
helps to remember the form of expression.
This corresponds to the logical graph:
y o
|
x o
|
O
Thus, the equivalence "x <=> y" has to be written somewhat
inefficiently as a conjunction of to and fro implications:
"(x (y))(y (x))".
This corresponds to the logical graph:
y o o x
| |
x o o y
\ /
O
Putting all the pieces together, the problem given
amounts to proving the following equation, expressed
in parse string and logical graph forms, respectively:
* Show that ~(p <=> q) is equivalent to (~q) <=> p
q o o p q o
| | |
p o o q o o p
\ / | |
o p o o--o q
| \ /
O = O
( (p (q)) (q (p)) ) = (p ( (q) )) ((p)(q))
No kidding ...
o12:30, 2 December 2008 (PST)[[User:Jon Awbrey|Jon Awbrey]] 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)[[User:Jon Awbrey|Jon Awbrey]] 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)[[User:Jon Awbrey|Jon Awbrey]] 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)[[User:Jon Awbrey|Jon Awbrey]] 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)[[User:Jon Awbrey|Jon Awbrey]] 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)[[User:Jon Awbrey|Jon Awbrey]] 12:30, 2 December 2008 (PST)o
</pre>
</pre>