Difference between revisions of "Talk:Logical graph"
MyWikiBiz, Author Your Legacy — Saturday November 30, 2024
Jump to navigationJump to searchJon Awbrey (talk | contribs) (→Logical Equivalence Problem: + discussion) |
Jon Awbrey (talk | contribs) (→Solution: format) |
||
Line 19: | Line 19: | ||
* [http://mathforum.org/kb/plaintext.jspa?messageID=6514666 Solution posted by Jon Awbrey, working in the medium of logical graphs]. | * [http://mathforum.org/kb/plaintext.jspa?messageID=6514666 Solution posted by Jon Awbrey, working in the medium of logical graphs]. | ||
− | |||
− | |||
− | |||
− | |||
− | + | Required to show: ~(p <=> q) is equivalent to (~q) <=> p. | |
− | + | In logical graphs, the required equivalence looks like this: | |
− | |||
− | |||
+ | <pre> | ||
q o o p q o | q o o p q o | ||
| | | | | | | | ||
Line 37: | Line 32: | ||
| \ / | | \ / | ||
@ = @ | @ = @ | ||
+ | </pre> | ||
− | + | We have a theorem that says: | |
+ | <pre> | ||
y o xy o | y o xy o | ||
| | | | | | ||
x @ = x @ | x @ = x @ | ||
+ | </pre> | ||
− | + | See [http://www.mywikibiz.com/Logical_graph#C2.__Generation_theorem Logical Graph : C<sub>2</sub>. Generation Theorem]. | |
− | + | Applying this twice to the left hand side of the required equation, we get: | |
+ | <pre> | ||
q o o p pq o o pq | q o o p pq o o pq | ||
| | | | | | | | | | ||
Line 55: | Line 54: | ||
| | | | | | ||
@ = @ | @ = @ | ||
+ | </pre> | ||
− | + | By collection, the reverse of distribution, we get: | |
+ | <pre> | ||
p q | p q | ||
o o | o o | ||
Line 64: | Line 65: | ||
\ / | \ / | ||
@ | @ | ||
+ | </pre> | ||
− | + | But this is the same result that we get from one application of double negation to the right hand side of the required equation. | |
− | double negation to the right hand side of the required equation. | ||
QED | QED | ||
Line 72: | Line 73: | ||
Jon Awbrey | Jon Awbrey | ||
− | PS. I will copy this to the | + | PS. I will copy this to the [http://stderr.org/pipermail/inquiry/ Inquiry List], since I know it preserves the trees. |
− | |||
− | |||
− | |||
− | |||
− | |||
===Discussion=== | ===Discussion=== |
Revision as of 22:20, 2 December 2008
Notes & Queries
- Jon Awbrey 20:20, 1 February 2008 (PST)
Place for Discussion
\(\ldots\)
Logical Equivalence Problem
Problem
Solution
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 Logical Graph : C2. Generation Theorem.
Applying this twice to the left hand side of the required equation, we get:
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, since I know it preserves the trees.
Discussion
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~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 ... o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o