12,080
edits
Changes
MyWikiBiz, Author Your Legacy — Monday March 17, 2025
Jump to navigationJump to searchlogical equivalence problem from the drexel math forum
Line 5:
Line 5:
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
==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>
