Difference between revisions of "Talk:Logical graph"

MyWikiBiz, Author Your Legacy — Saturday November 30, 2024
Jump to navigationJump to search
(→‎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].
  
<pre>
 
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.
  
required to show:  ~(p <=> q) is equivalent to (~q) <=> p
+
In logical graphs, the required equivalence looks like this:
 
 
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:
+
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
+
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:
+
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:
+
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
+
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 Inquiry List:
+
PS.  I will copy this to the [http://stderr.org/pipermail/inquiry/ Inquiry List], since I know it preserves the trees.
    http://stderr.org/pipermail/inquiry/
 
    since I know it preserves the trees.
 
 
 
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
 
</pre>
 
  
 
===Discussion===
 
===Discussion===

Revision as of 22:20, 2 December 2008

Notes & Queries

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