12,080
edits
Changes
MyWikiBiz, Author Your Legacy — Monday March 17, 2025
Jump to navigationJump to searchUndo revision 73910 by Jon Awbrey (Talk)
Line 10:
Line 10:
===Problem===
===Solution===+
−</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
==Logical Equivalence Problem==
==Logical Equivalence 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].
−* [http://mathforum.org/kb/plaintext.jspa?messageID=6514666 Solution posted by Jon Awbrey, working in the medium of logical graphs].
<pre>
<pre>
Line 77:
Line 73:
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
−</pre>
</pre>
