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