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.

• Required to show that \(\lnot (p \Leftrightarrow q)\) is equivalent to \((\lnot q) \Leftrightarrow p.\)

Solution

Solution posted by Jon Awbrey, proceeding by way of logical graphs.

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 : C₂. 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

Discussion

Back to the initial problem:

• Show that \(\lnot (p \Leftrightarrow q)\) is equivalent to \((\lnot q) \Leftrightarrow 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 and simple concatenation for conjunction, thus:

The negation \(\lnot x\) is written \((x).\!\)

This corresponds to the logical graph:

          x
          o
          |
          O

The conjunction \(x \land y\) is written \(x y.\!\)

This corresponds to the logical graph:

         x y
          O

The conjunction \(x \land y \land z\) is written \(x y z.\!\)

This corresponds to the logical graph:

        x y z
          O

And so on.

In this form of representation — for historical reasons called the "existential interpretation" of logical graphs — we have the following expressions of basic logical operations:

The disjunction \(x \lor y\) is written \(((x)(y)).\!\)

This corresponds to the logical graph:

        x   y
        o   o
         \ /
          o
          |
          O

The disjunction \(x \lor y \lor z\) is written \(((x)(y)(z)).\!\)

This corresponds to the logical graph:

        x y z
        o o o
         \|/
          o
          |
          O

And so on.

The implication \(x \Rightarrow 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 \Leftrightarrow 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 the forms of logical graphs and parenthetical parse strings, respectively:

• Show that \(\lnot (p \Leftrightarrow q)\) is equivalent to \((\lnot q) \Leftrightarrow 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))