Difference between revisions of "Talk:Logical graph"

MyWikiBiz, Author Your Legacy — Sunday October 26, 2025
Jump to navigationJump to search
Line 10: Line 10:
  
 
==Logical Equivalence Problem==
 
==Logical Equivalence Problem==
 +
 +
===Problem===
  
 
* [http://mathforum.org/kb/message.jspa?messageID=6513648 Problem posted by Mike1234 on the Discrete Math List at the Math Forum].
 
* [http://mathforum.org/kb/message.jspa?messageID=6513648 Problem posted by Mike1234 on the Discrete Math List at the Math Forum].
  
−
* [http://mathforum.org/kb/plaintext.jspa?messageID=6514666 Solution posted by Jon Awbrey, working by way of logical graphs].
+
===Solution===
 +
 
 +
* [http://mathforum.org/kb/plaintext.jspa?messageID=6514666 Solution posted by Jon Awbrey, working in the medium of logical graphs].
  
 
<pre>
 
<pre>
Line 73: Line 77:
  
 
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
 
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
 +
</pre>
 +
 +
===Discussion===
 +
 +
o12:30, 2 December 2008 (PST)[[User:Jon Awbrey|Jon Awbrey]] 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)[[User:Jon Awbrey|Jon Awbrey]] 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)[[User:Jon Awbrey|Jon Awbrey]] 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)[[User:Jon Awbrey|Jon Awbrey]] 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)[[User:Jon Awbrey|Jon Awbrey]] 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)[[User:Jon Awbrey|Jon Awbrey]] 12:30, 2 December 2008 (PST)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 ...
 +
 +
o12:30, 2 December 2008 (PST)[[User:Jon Awbrey|Jon Awbrey]] 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)[[User:Jon Awbrey|Jon Awbrey]] 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)[[User:Jon Awbrey|Jon Awbrey]] 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)[[User:Jon Awbrey|Jon Awbrey]] 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)[[User:Jon Awbrey|Jon Awbrey]] 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)[[User:Jon Awbrey|Jon Awbrey]] 12:30, 2 December 2008 (PST)o
 
</pre>
 
</pre>

Revision as of 20:30, 2 December 2008

Notes & Queries

Place for Discussion


\(\ldots\)

Logical Equivalence Problem

Problem

Solution

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

o12:30, 2 December 2008 (PST)Jon Awbrey 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)Jon Awbrey 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)Jon Awbrey 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)Jon Awbrey 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)Jon Awbrey 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)Jon Awbrey 12:30, 2 December 2008 (PST)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 ...

o12:30, 2 December 2008 (PST)Jon Awbrey 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)Jon Awbrey 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)Jon Awbrey 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)Jon Awbrey 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)Jon Awbrey 12:30, 2 December 2008 (PST)o12:30, 2 December 2008 (PST)Jon Awbrey 12:30, 2 December 2008 (PST)o

Retrieved from "https://mywikibiz.com/index.php?title=Talk:Logical_graph&oldid=73910"