12,080
edits
Changes
MyWikiBiz, Author Your Legacy — Monday March 17, 2025
Jump to navigationJump to search→Logical Equivalence Problem: + discussion
Line 10:
Line 10:
+
==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>
Line 73:
Line 77:
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
+</pre>
+
+===Discussion===
+
+<pre>
+o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~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 ...
+
+o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
</pre>
</pre>
