# Implication

*By Robert Laing*

Of classical logic’s four binary operators, one whose truth table
I initially found incomprehensible, was *implication*. In contemporary textbooks implication
tends to be written using the arrow operator p ⇒ q. Older texbooks use p ⊃ q,
making it even more confusing by misleading one
to think p is a superset of q. It turns out it’s actually the other way round.

Gottlob Frege’s Begriffsschrift uses a kind of branching wiring diagram for implication.

A convention I’ve addopted (which I haven’t seen elsewhere) is to use p ≤ q instead of p ⇒ q.
As the truth table shows, it gives the expected results for 1 and 0.
Writing p ≤ q has a further advantage of again being a *spiky* version
of its set *rounded* counterpart P ⊆ Q.

Equivalence is *reciprocal* implication. In logic and regular algebra,
if p ≤ q and q ≤ p, then we know p = q.

Similarly for sets, if P ⊆ Q and Q ⊆ P, then P = Q.

p | q | p ≤ q | p + q |
---|---|---|---|

1 | 1 | 1 | 1 |

1 | 0 | 0 | 0 |

0 | 1 | 1 | 1 |

0 | 0 | 1 | 1 |

In conjunctive normal form (CNF), implication is written ¬p ∨ q, which in product-of-sums notation is p + q.

One of the reasons I find implication’s arrow notation p ⇒ q confusing is because the arrow
operator is also commonly used to mark the final *then* answer of a series of
steps. Sometimes implication as in logic’s p ≤ q is called *material* implication to differentiate
it from *if … then …* usage.

The meaning of the implication operator ⇒ may appear unintuitive, since we must get used to the notion that “falsehood implies everything.” We should not confuse ⇒ with causation. That is, p ⇒ q may be true, yet p does not “cause” q in any sense. For example, let p be “it is raining,” and q be “Sue takes her umbrella.” We might assert that p ⇒ q is true. It might even appear that the rain is what caused Sue to take her umbrella. However, it could also be true that Sue is the sort of person who doesn’t believe weather forecasts and prefers to carry an umbrella at all times.— Propositional Logic, Al Aho and Jeff Ullman

In difference I included the following Prolog example:

```
apply(SID, _, 'EE', _),
\+ apply(SID, _, 'CS', _).
```

Which returns *false* since EE ⊆ CS, ie EE implies CS. Substituting p for `apply(SID, _, 'EE', _)`

and q for `apply(SID, _, 'CS', _)`

, the above Prolog code translates into
p ∧ ¬q. When p ∧ ¬q is *false*, it’s *true* that p ⇒ q, so lets toggle it by writing it like so
¬(p ∧ ¬q). Apply De Morgan’s Law to that, and voila, we get
¬p ∨ q.

De Morgan’s law tells us ¬(¬p ∨ q) is equivalent to p ∧ ¬q. Due to Prolog’s negation as failure convention, we need to add a statement to look up SID before using it in ¬(¬p ∨ q):

```
apply(SID, _, _, _),
\+ ( \+ apply(SID, _, 'EE', _) ; apply(SID, _, 'CS', _) ).
```

In equivalence I’ll show that (¬p ∨ q) ∧ (¬q ∨ p) is the same as (p ∧ q) ∨ (¬p ∧ ¬q).

As usual, lets use the SQL college examples,

## How to find all the subsets in the college data?

The example database contains a lot of subsets:

‘bioengineering’ ⊂ ‘EE’ ⊂ ‘CS’

‘marine biology’ ⊂ ‘CS’

‘marine biology’ ⊂ ‘biology’

‘psychology’ ⊂ ‘history’

Just as < in normal algebra, ⊂ is a *transitive* relation, so
‘bioengineering’ is a subset of both ‘CS’ and ‘EE’.

‘bioengineering’ ⊂ ‘CS’

‘bioengineering’ ⊂ ‘EE’

‘EE’ ⊂ ‘CS’

‘marine biology’ ⊂ ‘CS’

‘marine biology’ ⊂ ‘biology’

‘psychology’ ⊂ ‘history’

Implication means P is a subset of or equal to Q.
Though the default college example doesn’t happen to have any equal sets
(which means when we get to the next
section equivalence we need to modify the data),
it means all sets *imply* themselves. So our query needs to return the following
pairs:

‘bioengineering’ ⊆ ‘bioengineering’

‘bioengineering’ ⊆ ‘CS’

‘bioengineering’ ⊆ ‘EE’

‘biology’ ⊆ ‘biology’

‘CS’ ⊆ ‘CS’

‘EE’ ⊆ ‘CS’

‘EE’ ⊆ ‘EE’

‘history’ ⊆ ‘history’

‘marine biology’ ⊆ ‘biology’

‘marine biology’ ⊆ ‘CS’

‘marine biology’ ⊆ ‘marine biology’

‘psychology’ ⊆ ‘history’

‘psychology’ ⊆ ‘psychology’

## Venn’s 5 relations

To find P ⊆ Q pairs, we need a rule that satisfies diagrams 1 and 2, and fails for the last three:

One simple test is that P - Q = ∅.

### SQL

In SQL, we can find all those Ps and Qs like so:

```
SELECT DISTINCT a1.major AS subset, a2.major AS superset
FROM Apply as a1, Apply as a2
WHERE NOT EXISTS (
SELECT sid FROM Apply WHERE major = a1.major
EXCEPT
SELECT sid FROM Apply WHERE major = a2.major
)
ORDER BY a1.major, a2.major;
```

Which gives us the expected table:

```
subset | superset
----------------+----------------
bioengineering | bioengineering
bioengineering | CS
bioengineering | EE
biology | biology
CS | CS
EE | CS
EE | EE
history | history
marine biology | biology
marine biology | CS
marine biology | marine biology
psychology | history
psychology | psychology
(13 rows)
```

### Prolog

My Prolog rule, which I’ll elaborate on below, looks as follows:

```
implies_(P, Q) :-
apply(_, _, P, _),
apply(_, _, Q, _),
\+ ( apply(SID, _, P, _),
\+apply(SID, _, Q, _)
).
implies(P, Q) :-
distinct([P, Q], implies_(P, Q)).
```

Everything implies itself (ie P ⊆ P always holds), so to strip these out, we run the following query with a P == Q filter to omit listing every set.

```
implies(P, Q), P \== Q.
```

### Laws Involving Implication

- ((p → q) AND (q → p)) ≡ (p ≡ q) Reciprocal implication is equivalence
- (p ≡ q) → (p → q)
- Transitivity of implication ((p → q) AND (q → r)) → (p → r) ‘bioengineering’ ⊂ ‘EE’ ⊂ ‘CS’
- (p → q) ≡ ( ̄p + q)

Implication appears in relational database theory as Armstrong’s axioms.