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.

Proofs

The contrapositive law

(p ⇒ q) ⇔ (¬q ⇒ ¬p)

Proof by Contradiction

(¬p ⇒ 0) ⇔ p

Equivalence to Truth

(p ≡ 1) ≡ p

Deduction

(E₁ AND E₂ AND · · · AND E_k) ⇒ E

Modus ponens

(p AND (p ⇒ q)) ⇒ q

Resolution

((p + q)(¬p + r)) → (q + r)