Changes

31 bytes removed ,  22:29, 2 December 2008
Line 13: Line 13:  
===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===
 
===Solution===
Line 75: Line 75:     
===Discussion===
 
===Discussion===
  −
<pre>
  −
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
      
Back to the initial problem:
 
Back to the initial problem:
   −
* Show that ~(p <=> q) is equivalent to (~q) <=> p
+
* Show that ~(p <=> q) is equivalent to (~q) <=> p.
   −
We can translate this into logical graphs by supposing that we
+
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 &mdash; that is, "(x)" for "not x" &mdash; and simple concatenation for conjunction &mdash; "xyz" or "x y z" for "x and y and z".
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
+
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 "existential interpretation" of logical graphs, we have
  −
the following expressions for basic logical operations:
      
The disjunction "x or y" is written "((x)(y))".
 
The disjunction "x or y" is written "((x)(y))".
Line 97: Line 88:  
This corresponds to the logical graph:
 
This corresponds to the logical graph:
    +
<pre>
 
         x  y
 
         x  y
 
         o  o
 
         o  o
Line 103: Line 95:  
           |
 
           |
 
           O
 
           O
 +
</pre>
    
The disjunction "x or y or z" is written "((x)(y)(z))".
 
The disjunction "x or y or z" is written "((x)(y)(z))".
Line 108: Line 101:  
This corresponds to the logical graph:
 
This corresponds to the logical graph:
    +
<pre>
 
         x y z
 
         x y z
 
         o o o
 
         o o o
Line 114: Line 108:  
           |
 
           |
 
           O
 
           O
 +
</pre>
    
Etc.
 
Etc.
   −
The implication "x => y" is written "(x (y)),
+
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.
which can be read "not x without y" if that
  −
helps to remember the form of expression.
      
This corresponds to the logical graph:
 
This corresponds to the logical graph:
    +
<pre>
 
         y o
 
         y o
 
           |
 
           |
Line 128: Line 122:  
           |
 
           |
 
           O
 
           O
 +
</pre>
   −
Thus, the equivalence "x <=> y" has to be written somewhat
+
Thus, the equivalence "x <=> y" has to be written somewhat inefficiently as a conjunction of to and fro implications: "(x (y))(y (x))".
inefficiently as a conjunction of to and fro implications:
  −
"(x (y))(y (x))".
      
This corresponds to the logical graph:
 
This corresponds to the logical graph:
    +
<pre>
 
       y o  o x
 
       y o  o x
 
         |  |
 
         |  |
Line 140: Line 134:  
         \ /
 
         \ /
 
           O
 
           O
 +
</pre>
   −
Putting all the pieces together, the problem given
+
Putting all the pieces together, the problem given amounts to proving the following equation, expressed in the forms of logical graphs and parenthetical parse strings, respectively:
amounts to proving the following equation, expressed
  −
in parse string and logical graph forms, respectively:
     −
* Show that ~(p <=> q) is equivalent to (~q) <=> p
+
* Show that ~(p <=> q) is equivalent to (~q) <=> p.
    +
<pre>
 
       q o  o p          q o
 
       q o  o p          q o
 
         |  |              |
 
         |  |              |
Line 156: Line 150:     
( (p (q)) (q (p)) ) = (p ( (q) )) ((p)(q))
 
( (p (q)) (q (p)) ) = (p ( (q) )) ((p)(q))
 +
</pre>
   −
No kidding ...
+
No kidding &hellip;
 
  −
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
  −
</pre>
 
12,080

edits