Logical literacy

[article index] [] [@mattmight] [rss]

Logical literacy is essential to mathematical fluency.

Logical literacy is an awareness and understanding of the metalanguage in which propositions, conjectures, lemmas and theorems are written.

Learning how to read this metalanguage is not hard; and once it's learned, it becomes possible to tease out and translate (perhaps slowly at first) the main ideas in a technical paper.

Logical fluency is a working knowledge of a second metalanguage: the language in which proofs are written.

Every field has its own proof language, constructed by convention. In theory, every proof in these languages can be reduced to a formal and rigorous proof given sufficient time and appetite for tedium.

Unfortunately, each proof language takes a couple years of immersion--usually in graduate school--to master.

As such, the spirit of this post is not "how to write a proof."

The spirit is "how to read a theorem."

Read on for my short capsule on logical literacy.

The roles and meaning of logic

Logic is the calculus of truth.

As both the metalanguage of mathematics and an object of study within mathematics, it is important to be able to distinguish the two roles of logic and their respective notations.

When used as a metalanguage for mathematics, logic takes the form of crisp, standardized English. When logical statements are being studied as mathematical objects in their own right, symbolic forms of quantifiers, relations and connectives are appropriate.

Being able to translate between the forms is a critical part of logical literacy:

  • $ p \land q$ means ``$ p$ and $ q$ .''
  • $ p \lor q$ means ``$ p$ or $ q$ .''
  • $ \lnot p$ means ``it is not the case that $ p$ .''
  • $ p \implies q$ means ``$ p$ implies $ q$ .''
  • $ p \iff q$ means ``$ p$ if and only if $ q$ .''
  • $ \forall x : p$ means ``for each object $ x$ , it is the case that $ p$ .''
  • $ \exists x : p$ means ``there exists an object $ x$ such that $ p$ .''
In symbolic logic, the variables $ p$ and $ q$ are expressions that evaluate to true or false; in the metalanguage of mathematics, the variables $ p$ and $ q$ are statements.

Statements

Logic forms complex statements from simpler ones.

In mathematics, equations are the most common simple statements. But, any relation (e.g., less than, greather than or equal, subset-inclusion) can form a mathematical statement.

More generally, any set can form the basis of a relation. When a set $ R$ is used as a relation, the notation $ R(x)$ is the same as $ x \in R$ .

The following are all simple statements:

  • The sum of three and four is seven.
  • $ 3 + 4 = 7$ .
  • $ x$ is less than $ y$ .
  • $ x < y$ .
  • Bob is an accountant.
  • $ \mathit{Accountants}(\mathtt{Bob})$ .

Confusing the two roles of logic

In mathematical prose, it is jarring to see the symbolic forms in lieu of their English counterparts.

Consider the following two formulations of the same theorem:

Theorem $ \forall n : n > 1 \implies \exists p : \exists q : p \neq q \land n = p \times q$ .

Theorem For every integer $ n$ greater than 1, there exist two distinct integers $ p$ and $ q$ such that the product of $ p$ and $ q$ is $ n$ .

Which formulation reads more clearly?

[Niggling detail In the first formulation, how do we know that the numbers involved are integers? How do we even know they're numbers?

We don't, unless the ``universe of discourse'' is specified.

The universe of discourse determines what kinds of values variables and expressions may take.

In this case, the universe of discourse is implicitly assumed to be integers. In some texts, it's explicitly specified; in others, it must be inferred from context. To be clear and context-insensitive, one could specify the range of every variable each time, as in this third formulation:

Theorem $ \forall n \in \mathbb{N} : n > 1 \implies \exists p \in \mathbb{N} : \exists q \in \mathbb{N} : p \neq q \land n = p \times q$ .

Whether one specifies the universe of discourse, leaves it to be inferred, or specifies the range of each variable must be made in light of the tradeoffs between clarity and precision for the reader.]

Going in the other direction, however, it isn't as awkward (even if it is uncommon). One could use English connectives in place of symbolic connectives--especially when the connectives are bold-faced, e.g., and, or.

The meaning of and, or and not

For the statement ``$ p$ and $ q$ '' to be true, both $ p$ and $ q$ must be true.

There are two ors in logic, and the default or is inclusive: ``$ p$ or $ q$ '' is true when $ p$ is true, when $ q$ is true and when $ p$ and $ q$ are both true. In other words, ``$ p$ or $ q$ '' is false only when both $ p$ and $ q$ are false.

The other or is exclusive-or (or xor); ``$ p$ xor $ q$ '' is true only when $ p$ is true and $ q$ is false, or when $ p$ is false but $ q$ is true. Exclusive-or is typically written ``either $ p$ or $ q$ .'' In some texts, the symbol $ \oplus$ denotes exclusive or, but this notation is not universal.

Logical negation (prefixing a statement with the symbol $ \lnot$ or ``it is not the case that'') flips the truth value of a statement from true to false or false to true.

In most logics, double negation self-eliminates:

$\displaystyle \lnot\lnot p = p$$\displaystyle \text.$    

DeMorgan's laws express the relationship between and, or and not:

  • $ \lnot(p \lor q) = \lnot p \land \lnot q$ ;
  • $ \lnot(p \land q) = \lnot p \lor \lnot q$ .

And and or also distribute across each other:

  • $ r \lor (p \land q) = (r \lor p) \land (r \lor q)$ ;
  • $ r \land (p \lor q) = (r \land p) \lor (r \land q)$ .

Truth tables for and and or

A truth table enumerates all possible values of a logical expression based on the value of its operands. A truth table gives a precise, formal meaning to a logical connective. For example, the truth table for the or-connective $ (\lor)$ is:

$ p$ $ q$ $ p \lor q$
false false false
false true true
true false true
true true true

Likewise, the truth table for the and-connective $ (\land)$ is:

$ p$ $ q$ $ p \land q$
false false false
false true false
true false false
true true true

The truth table for the xor-connective $ (\oplus)$ is:

$ p$ $ q$ $ p \oplus q$
false false false
false true true
true false true
true true false

The meaning of implication

Many understand implication intuitively, yet find its symbolic formulation puzzling. The statement ``$ p$ implies $ q$ '' has several equivalent interpretations:

  • if $ p$ , then $ q$ ;
  • $ q$ follows $ p$ ;
  • $ p$ entails $ q$ ;
  • $ p$ is sufficient for $ q$ .
Symbolically, implication can be phrased in terms of or and not:

$\displaystyle p \implies q = \lnot p \lor q$$\displaystyle \text.$    

Bidirectional implication, or logical equivalence, also has equivalent formulations. The statement ``$ p$ if and only if $ q$ '' is the same as:

  • $ p$ iff $ q$ ;
  • $ p$ is necessary and sufficient for $ q$ .
Bidirectional implication is the conjuction of two implications:

$\displaystyle p \iff q = (p \implies q) \land (q \implies p)$$\displaystyle \text.$    

Alternate notations for implication

Expressing implications in inference-rule notation is also popular:

$\displaystyle {\renewcommand {\arraystretch}{1.4}\begin{array}{c}P_1 \;\;\;\;\;... ...;\;\;\;\;\;P_n \hline Q\text{,}\end{array}\renewcommand {\arraystretch}{1.0}}$    

means ``if $ P_1$ and $ P_2$ and ...$ P_n$ , then $ Q$ .'' Or, in the case of equivalences:

$\displaystyle {\renewcommand {\arraystretch}{1.4}\begin{array}{c}P_1 \;\;\;\;\;... ...;\;\;\;P_n \hline\hline Q\text,\end{array}\renewcommand {\arraystretch}{1.0}}$    

means ``$ P_1$ and $ P_2$ and ...and $ P_n$ if and only if $ Q$ .''

The contrapositive

It's easy to prove that $ p \implies q$ is true if and only if $ \lnot q \implies \lnot p$ is true:

$\displaystyle p \implies q$ $\displaystyle = \lnot p \lor q$    
  $\displaystyle = q \lor \lnot p$    
  $\displaystyle = \lnot\lnot q \lor \lnot p$    
  $\displaystyle = \lnot q \implies \lnot p$$\displaystyle \text.$    

$ \lnot q \implies \lnot p$ is the contrapositive of $ p \implies q$ .

Truth tables for implication

The truth table for implication $ (\implies)$ is:

$ p$ $ q$ $ p \implies q$
false false true
false true true
true false false
true true true

The truth table for bidirectional implication $ (\iff)$ is:

$ p$ $ q$ $ p \iff q$
false false true
false true false
true false false
true true true

Quantifiers

The symbols $ \forall$ and $ \exists$ are quantifiers. The symbol $ \forall$ is the universal quantifier because it claims something for every element in the universe; while the symbol $ \exists$ is the existential quantifier because it claims the existence of an object that satisfies a claim.

DeMorgan's laws generalize to quantifiers:

  • $ \lnot \forall x : p = \exists x : \lnot p$ ;
  • $ \lnot \exists x : p = \forall x : \lnot p$ .

There are subtle notational variations on quantifier forms in symbolic logic:

  • $ \forall x \in X: p$ means ``for each $ x$ in the set $ X$ , it is the case that $ p$ .''
  • $ \exists x \in X: p$ means ``there exists an $ x$ in the set $ X$ such that $ p$ .''
Symbolically, the set-restricted forms of quantifiers desugar differently:
  • $ \forall x \in X : p = \forall x : x \in X \implies p$ ;
  • $ \exists x \in X : p = \exists x : x \in X \land p$ .

In some texts, the colon $ :$ is left off quantifiers.

Implicit universal quantification

Consider the following statements:

  • $ f$ is the function that squares its argument and adds two.
  • $ \forall x : f(x) = x^2 + 2$ .
  • $ a$ is prime and $ b$ is prime implies that $ ab$ is composite.
  • $ \forall a : \forall b : \mathit{prime}(a) \land \mathit{prime}(b) \implies \mathit{composite}(ab)$ .
The symbolic forms look awkward. They are more commonly written:
  • $ f(x) = x^2 + 2$ .
  • $ \mathit{prime}(a) \land \mathit{prime}(b) \implies \mathit{composite}(ab)$ .
When a statement in logic contains an undefined variable, that variable is implicitly universally quantified. This is a widely used convention.

Rules of inference

In logic, rules of inference allow true statements to be transformed into new true statements. The application of a sequence of rules of inference is what constitutes a formal proof. Being aware of rules of inference, and the most common rules, acts as nice supplement to logical literacy.

Rules of inference may be expressed in the following form:

\begin{displaymath} % latex2html id marker 3841 \begin{array}{ll} & p_1 & \vd... ...erefore & p_n \hline \multicolumn{2}{c}{q\text,} \end{array}\end{displaymath}    

or as:

$\displaystyle {\renewcommand {\arraystretch}{1.4}\begin{array}{c} p_1\; \cdots\; p_n \hline q\text, \end{array}\renewcommand {\arraystretch}{1.0}}$    

and such a rule means, ``if $ p_1$ , $ p_2$ , ..., $ p_n$ are true, then $ q$ must also be true.''

The most frequently applied rule of inference is modus ponens:

$\displaystyle {\renewcommand {\arraystretch}{1.4}\begin{array}{c} p \;\;\;\;\;\;\;p \implies q \hline q\text. \end{array}\renewcommand {\arraystretch}{1.0}}$    

In short, modus ponens says that if we know $ p$ and we know that $ p$ implies $ q$ , then we also know $ q$ .

Modus tollens, for instance, works in reverse:

$\displaystyle {\renewcommand {\arraystretch}{1.4}\begin{array}{c} \lnot q \;\;\... ...plies q \hline \lnot p \text. \end{array}\renewcommand {\arraystretch}{1.0}}$    

If we know that $ p$ implies $ q$ , but $ q$ is false, then $ p$ must be false.

Wikipedia provides a good summary of the rules of inference.

Sound rules of inference

For a rule of inference:

$\displaystyle {\renewcommand {\arraystretch}{1.4}\begin{array}{c} p_1\; \cdots\; p_n \hline q \end{array}\renewcommand {\arraystretch}{1.0}}$    

to be sound, $ (p_1 \land \cdots \land p_n) \implies q$ must be equivalent to true. Consider modus ponens:

$\displaystyle (p \land (p \implies q)) \implies q$ $\displaystyle = \lnot (p \land (p \implies q)) \lor q$    
  $\displaystyle = (\lnot p \lor \lnot (p \implies q)) \lor q$    
  $\displaystyle = (\lnot p \lor \lnot (\lnot p \lor q)) \lor q$    
  $\displaystyle = (\lnot p \lor (p \land \lnot q)) \lor q$    
  $\displaystyle = ((\lnot p \lor p) \land (\lnot p \lor \lnot q)) \lor q$    
  $\displaystyle = (\mathit{true} \land (\lnot p \lor \lnot q)) \lor q$    
  $\displaystyle = (\lnot p \lor \lnot q) \lor q$    
  $\displaystyle = \lnot p \lor (\lnot q \lor q)$    
  $\displaystyle = \lnot p \lor \mathit{true}$    
  $\displaystyle = \mathit{true}$    

Logical fallacies

A logical fallacy is a would-be rule of inference which is not always true. A common fallacy is affirming the consequent; that is, assuming:

$\displaystyle {\renewcommand {\arraystretch}{1.4}\begin{array}{c} q \;\;\;\;\;\;\;p \implies q \hline p\text. \end{array}\renewcommand {\arraystretch}{1.0}}$    

It's a good exercise to prove that this rule is a fallacy by showing it does not always reduce to true.


What's next?

With respect to logic's role as a metalanguage in mathematical prose, this post covers the essential vocabulary for technical reading.

I glossed over the nitty gritty that should be common sense, like the idempotent laws (e.g., p or p is just p), the commutative laws and the identity laws. Any textbook on logic will cover these.

For most, the next step is to learn how to read and write proofs.

If you're interested in getting deeper into symbolic logic, the first rabbit hole starts with relations and formulae, continues through entailment, satisfication, derivation, validity, consistency, soundness and completeness, and ends with models, theories and incompleteness.

More resources

  • My recommended reading for grad students.
  • Harry Gensler's Introduction to Logic is the best introduction to logic and proofs that I know of. This is probably because it was written for philosophers instead of mathematicians.
  • Mathematical Logic, on the other hand, is a punishing read for non-mathematicians. That said, it is a complete, unified development of all of the foundational concepts in symbolic logic (including Gödel's incompleteness theorems). As a reference for the working formal mathematician, it is an indispensible resource.
  • Gödel's Theorem: An Incomplete Guide to Its Use and Abuse is the best lay reader's overview of Gödel's incompleteness theorems that I know of.