Talk:Logical graph

Notes & Queries

• Jon Awbrey 20:20, 1 February 2008 (PST)

Place for Discussion

\(\ldots\)

Logical Equivalence Problem

Problem

• Problem posted by Mike1234 on the Discrete Math List at the Math Forum.

Solution

• Solution posted by Jon Awbrey, working in the medium of logical graphs.

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

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