12,080
edits
Changes
→Logical Equivalence Problem: format
===Problem===
===Problem===
[http://mathforum.org/kb/message.jspa?messageID=6513648 Problem posted by Mike1234 on the Discrete Math List at the Math Forum].
===Solution===
===Solution===
===Discussion===
===Discussion===
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 — that is, "(x)" for "not x" — and simple concatenation for conjunction — "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))".
This corresponds to the logical graph:
This corresponds to the logical graph:
<pre>
x y
x y
o o
o o
|
|
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))".
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
|
|
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
|
|
|
|
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
| |
| |
\ /
\ /
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
| | |
| | |
( (p (q)) (q (p)) ) = (p ( (q) )) ((p)(q))
( (p (q)) (q (p)) ) = (p ( (q) )) ((p)(q))
</pre>
No kidding ...
No kidding …