Talk:Logical graph

Notes & Queries

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

Place for Discussion

\(\ldots\)

Logical Equivalence Problem

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

• Solution posted by Jon Awbrey, working by way 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