Talk:Logical graph
Notes & Queries
- Jon Awbrey 20:20, 1 February 2008 (PST)
Place for Discussion
\(\ldots\)
Logical Equivalence Problem
Problem
Solution
Date: 30 Nov 2008, 2:00 AM
Author: Jon Awbrey
Subject: Re: logical equivalence problem
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
required to show: ~(p <=> q) is equivalent to (~q) <=> p
in logical graphs, the required equivalence looks like this:
q o o p q o
| | |
p o o q o o p
\ / | |
o p o o--o q
| \ /
@ = @
we have a theorem that says:
y o xy o
| |
x @ = x @
see: http://www.mywikibiz.com/Logical_graph#C2.__Generation_theorem
applying this twice to the left hand side of the required equation:
q o o p pq o o pq
| | | |
p o o q p o o q
\ / \ /
o o
| |
@ = @
by collection, the reverse of distribution, we get:
p q
o o
pq \ /
o o
\ /
@
but this is the same result that we get from one application of
double negation to the right hand side of the required equation.
QED
Jon Awbrey
PS. I will copy this to the Inquiry List:
http://stderr.org/pipermail/inquiry/
since I know it preserves the trees.
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
Discussion
o12:30, 2 December 2008 (PST)Jon Awbrey 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)Jon Awbrey 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)Jon Awbrey 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)Jon Awbrey 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)Jon Awbrey 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)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)Jon Awbrey 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)Jon Awbrey 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)Jon Awbrey 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)Jon Awbrey 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)Jon Awbrey 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)Jon Awbrey 12:30, 2 December 2008 (PST)o
