The language of propositions

Why logic for computer science

A program spends its time deciding: if (x > 0 && !fini), a query WHERE age >= 18 OR parent, a firewall rule, a specification stating what a function must guarantee. Each time, a condition is built from simpler conditions, with “and”, “or”, “not”, “if… then”.

Logic studies these constructions for their own sake. It answers questions a computer scientist asks every day: do two conditions say the same thing? Can this condition be true? Is it always true, and therefore useless? Does this property follow from the ones I already know?

This chapter fixes the language: what we are allowed to write, and how we read it. The next chapter will say what it means.

Propositions and connectives

Propositional variables

A proposition is a statement that is true or false: “it is raining”, “$x$ is even”, “the file exists”. We are not interested in its content, only in its truth value. So we represent it by a letter, a propositional variable: $p$, $q$, $r$, $p_1$, $p_2$…

We add two constants: $\top$ (always true) and $\bot$ (always false).

The connectives

Propositions are combined with connectives:

Negation is unary: it applies to a single formula. The others are binary: they connect two formulas. The “or” of logic is inclusive; the exclusive “or” of everyday language (“cheese or dessert”) is written $\oplus$.

Syntax

Formulas, defined by induction

Not every sequence of symbols may be written. Formulas are defined by three rules:

1. a propositional variable, $\top$ and $\bot$ are formulas;
2. if $A$ is a formula, $(\lnot A)$ is a formula;
3. if $A$ and $B$ are formulas, $(A \land B)$, $(A \lor B)$, $(A \to B)$ and $(A \leftrightarrow B)$ are formulas.

Nothing else is a formula. Thus $((\lnot p) \to (q \lor r))$ is a formula: $p$, $q$ and $r$ are formulas (rule 1), hence so are $(\lnot p)$ and $(q \lor r)$ (rules 2 and 3), hence so is the whole (rule 3). On the other hand, $p \lor \land q$ is not one: no rule produces it.

The letters $A$, $B$, $C$ are not propositional variables: they stand for any formula. We use them to state general rules.

The syntax tree

A formula has a tree structure. Its root is the main connective, the last one applied by the rules; its leaves are the variables.

flowchart TD
  A["→"] --> B["¬"]
  A --> C["∨"]
  B --> D["p"]
  C --> E["q"]
  C --> F["r"]

This is the tree of $((\lnot p) \to (q \lor r))$. Its main connective is $\to$. Each node of the tree is the root of a subformula: here $((\lnot p) \to (q \lor r))$, $(\lnot p)$, $(q \lor r)$, $p$, $q$ and $r$.

It is the tree that gives the formula its meaning. Two ways of writing it that have the same tree say the same thing; two ways of writing it that have different trees do not.

Writing fewer parentheses

Precedence

The parentheses of the definition make every formula readable without ambiguity, but heavy. We remove some by fixing precedences, as in arithmetic where $2 + 3 \times 4$ reads $2 + (3 \times 4)$:

The connective with the highest precedence applies first: $\lnot p \land q$ reads $((\lnot p) \land q)$, and $p \lor q \to r$ reads $((p \lor q) \to r)$.

Associativity

When the same connective is repeated:

• $\land$ and $\lor$: we write $p \land q \land r$ without parentheses. Both groupings give the same result (we will show it in the next chapter).
• $\to$: to the right. $p \to q \to r$ reads $(p \to (q \to r))$. This is not the same formula as $((p \to q) \to r)$: the parentheses are then compulsory.

Removing parentheses without changing the meaning

A pair of parentheses is removed when precedence and associativity restore it on their own. Method: draw the tree, then for each node, ask whether the child's connective has higher precedence than the parent's.

Language and metalanguage

Two kinds of symbols will coexist in this course, and they must not be confused.

• The connectives $\lnot, \land, \lor, \to, \leftrightarrow$ belong to the language: they are used to write formulas. $p \to q$ is a formula.
• The symbols $\vDash$ (“has as a consequence”) and $\equiv$ (“is equivalent to”) belong to the metalanguage: they are used to say something about formulas. $p \vDash p \lor q$ is not a formula, it is a statement about two formulas, true or false.

So we cannot ask whether “$p \equiv q$” is satisfiable: it is not a formula. We can ask it of $p \leftrightarrow q$. The next chapter makes the link between the two precise.