| 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]. |
| | | | |
| − | ===Solution===
| + | * [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>
| |
| − |
| |
| − | ===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> |