12,122
edits
Changes
logical equivalence problem from the drexel math forum
==Place for Discussion==
==Place for Discussion==
<math>\ldots\!</math>
<br><math>\ldots</math><br>
==Logical Equivalence Problem==
* [http://mathforum.org/kb/message.jspa?messageID=6513648&tstart=0 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].
<pre>
Date: 30 Nov 2008, 2:00 AM
Author: Jon Awbrey
Subject: Re: logical equivalence problem
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
required to show: ~(p <=> q) is equivalent to (~q) <=> p
in logical graphs, the required equivalence looks like this:
q o o p q o
| | |
p o o q o o p
\ / | |
o p o o--o q
| \ /
@ = @
we have a theorem that says:
y o xy o
| |
x @ = x @
see: http://www.mywikibiz.com/Logical_graph#C2.__Generation_theorem
applying this twice to the left hand side of the required equation:
q o o p pq o o pq
| | | |
p o o q p o o q
\ / \ /
o o
| |
@ = @
by collection, the reverse of distribution, we get:
p q
o o
pq \ /
o o
\ /
@
but this is the same result that we get from one application of
double negation to the right hand side of the required equation.
QED
Jon Awbrey
PS. I will copy this to the Inquiry List:
http://stderr.org/pipermail/inquiry/
since I know it preserves the trees.
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
</pre>