Chapter 2: Elementary Mathematical logic

Introduction
The purpose of this chapter is to reiterate our investigation into those notions from a rigorous,
abstract, and indeed mathematical perspective. The idea of this chapter is thus to formalize part of
chapter 1 (no quantifiers). To do so we will delve into the basics of classical Boolean/propositional
logic. It is going to deepen three aspects:
1. propositional syntax/formal language (key “sentences”, whose goal is to produce an
algorithm to test for “mathematical statements”. In this formal language there can be no
ambiguity. Look at Theorem 3
2. formal semantics/Boolean semantics, whose goal is to come up with an algorithm to
compute the truth value of arbitrarily complex mathematical statements from the truth
value of the components. Look at Lemma 2
3. A definition of what it means for a mathematical statement to follow logically from other
sentences.

2.1 Propositional Syntax

Language
We start with a language L which is a non-empty finite set of propositional variables
L= { p 1, p 2 , … pn }
The elements inside are called propositional variables and are the “smallest” units for which it
makes sense to ask whether they are true or false.

They are called propositional variables because what really matters about p is what happens when
it takes one of the two values in { 0 , 1 } and because they can represent any statement that we
want. Our goal is to use those building blocks to form increasingly more complex sentences in such
a way as to be able to investigate unambiguously their logical structure. This is obtained by
applying four propositional connectives

Sentences
Connectives can be used to combine the (finite) set of propositional variables in L to give rise to
the (infinite) set of sentences of L, denoted by S L.

The set S L is defined recursively as follows:

- base S L1=L

- recursive step

We suppose that we have combined several sentences to give rise to a more complicated
ones and have done so n times. The condition says how we may be able to get from n to
n+1 (the successor)

- closure

Finally, we add a condition that says that we can iterate this recursive construction (also
called structural recursion) for as long as we please, and by doing so we get an infinite set
out of the combination of a finite number of building block (S L1) and four connectives.
In other words:

- if θ, φ are sentences, then so are ¬(θ), (θ ∧ φ), (θ ∨ φ),(θ → φ);

- all propositional variables are sentences.

- nothing else is a sentence.

Alphabet
The problem of deciding sentences is solvable algorithmically. Set A, the alphabet, is the set of the
symbols needed to create sentences that belong to S L .

Examples:
σ =ρ ∧q check if it belongs to S L
1. Does σ belong to L? (Which means is σ a propositional variable?) σ is not a propositional
variable since propositional variables can only be one letter whereas here I have 3 symbols
(too many symbols).
2. Does ρ ∧q belong to S L? By the recursive step a sentence must start with one of the
connectives but there must be parentheses. So, the answer is no.

Remark: brackets are important since otherwise I won’t be able to distinguish, for instance
( ρ ∧q ) ∨ r ¿ from p ∧(q ∨r ).
Parsing trees
The fact that S L is defined recursively allows us to visualize sentences as trees, or more precisely
their parsing trees, which are themselves defined recursively as follows

Theorem 3
It’s a theorem that says there is no ambiguity in syntax
The theorem says that each element of S L is free of ambiguities, i.e., it is written in an objectively
clear way. This follows from the fact that the definition of S L allows us to combine in a finite (very
small) number of distinct ways the elements which recursively build the set up. This is why the
result is established by induction on the length of θ.

Conventions for omitting parentheses

The following is a small set of conventions that may be used to cut down
significantly the number of parentheses in our sentences.

1. Omit parentheses when introducing negations of single sentences, i.e., write ¬θ and ¬¬θ
instead of ¬(θ) and ¬(¬(θ)) etc.
2. Remove the outmost parentheses. i.e., instead of writing (¬p → ¬q), we shall write ¬p → ¬q
etc.

associating to the left. Instead that is of writing ((θ ∧ φ) ∧ ψ) we write θ ∧ φ ∧ ψ.)

3. If a sentence contains only one binary connective, remove all the parentheses by

4. Priorities connectives as follows:

connective priority

∧
¬ 1

∨
2
3
→ 4

In practice convention 1 and convention 2 are always used; convention 3. is used sometimes, and
convention 4. is often used for just one or two connectives. It is in fact much easier to use
parentheses than to work out the priority of connectives.

¬θ ∨ φ
So, we write

(¬(θ) ∨ φ),
instead of

¬θ → (ψ ∨ φ)
just as we write

(¬(θ) → ((ψ ∨ φ)))

instead of

Note that that is what you are used to from elementary number theory, where you don’t feel
confused in reading x+y·z, since you know that it is a shorthand for x + (y · z).
Remark
With recursive sets we use
 2.2 Boolean Valuation and Boolean Matrices
The alphabet and the sentences of a language L belong to a part of logic called syntax. As we just
learn, it has to do with defining the rules which allow us to decide unambiguously, objectively, and
indeed mechanically, whether a certain expression belong to the set of sentences of our language.
However, an interpretation or meaning can be attached to logical languages. This is the part of
logic usually referred to as (formal) semantics.

Semantics: part of logic that discusses the relationship between linguistic objects (such as
sentences) and what is expressed by these objects).

Propositional valuation: it’s a function mapping L into the set {0, 1} which we call the set of truth-
values. Note that it is one distinctive feature of classical logic to have the binary set {0, 1} as the
codomain of propositional. And it is often the case that we refer to those values with “false” and
“true”, respectively. The formal definition is:

The set V corresponds to the (proper) rows of a Boolean matrix.

How to construct Boolean matrices

Consider the sentence
λ=(q ∧ ( p → q ) )→ p
if you ask what its logical meaning is, the answer will not be a binary digit (a o or a 1) but 4 of
them. Too see way, start by noting that in λ there are just two propositional variables, so it is
sufficient to ground our analysis in L= { p , q } .This gives rise to V = { v 1 , v 2 , v 3 , v 4 } . V contains all and
only the row of the Boolean matrix for L.

This table shows the correspondence between the set of all the valuations on L and the rows of
the Boolean matrix for L.

correspond to the values each valuation attach to it. It is conveniente to refer ⟨0, 0, 1, 1⟩ as the
Note that underneath each propositional variable is a column of binary digits, which clearly

truth-vector of p denoted ⃗v(p), and similarly for q, so ⃗v(q) = ⟨0, 1, 0, 1⟩. We will now show how
Boolean matrices give us an algorithm to compute the truth-vector of λ from the truth-vectors of
p and q. So, the sentence λ can be evaluated by suitable expanding the table above. These are the
steps to follow:

1. copy down all the possible truth-value

distributions
 2. then we work out the truth-value of the
innermost connective according to the Boolean
matrix for → .

3. we move on computing the truth-value of the

second-innermost connective, according to the
Boolean matrix for ∧.

4. Finally, we can use this latter computation to

calculate the sentence’s truth-vector by focusing on
the only remaining connective. To make it more

truth-vector of ((q ∧ (p → q)) → p) we enclose this

visible and to signal that this coincides with the

column within a triple vertical line.

This argument shows that Boolean matrices allow us to analyze the sentence of interest in a
completely formal way. The method just described is not limited to the particular λ we have just

for some sentences θ, ⃗v(θ) contains only 1’s, whereas for some other sentence φ it will contain
used but applies to all the sentences in S L. When you apply it across the board you will find that,

only 0’s. If this happens, it is customary to call θ a tautology and φ a contradiction, respectively. A
sentence which is neither a tautology nor a contradiction is called contingent. In short φ is
- a contingent if { 0 , 1 } ∈ v(φ)
- a tautology if 0 ∈ v(φ)
- a contradiction if 1∈ v(φ)

Definition of logically equivalent

θ, φ ∈ L are logically equivalent if v (θ) = v (φ). (if they have the same truth-values)

How to find a sentence given a truth vector

We can also do the opposite procedure, i.e., we can construct a sentence in S L from a given

such that v(θ) = ⟨0, 1, 1, 0⟩. Here is the

Boolean matrix. Let’s consider the following table. A sentence which fits the table, i.e., a θ ∈ S L
method for arriving at the conclusion.

1. start by removing the lines in which v ( θ )=0, which leaves us with the following table
 behave exactly as prescribed by the valuation itself, i.e. write ¬p ∧ q for v2 and p ∧ ¬q for
2. then read the remaining valuation as a requirement for all propositional variables to

v3. Since a disjunction is evaluated to 1 when at least one of the disjuncts is evaluated to 1,

valuations v2 and v3, that is to say θ = (p ∧ ¬q) ∨ (¬p ∧ q).

the required θ is the disjunction of the two sentences which uniquely identify the
 2.3 Using Boolean matrices in practice
The task of logic is to draw logical conclusions from the supposition that elements of L are
evaluated in a certain way (for this reason we say truth-values). If the question is: is
(q ⋀ ( p→ q ))→ p true?
The answer is “it depends”. The thing it depends on is which valuation correctly describes the
“true state of the world” which is modelled by L. In other words, it depends on how we distribute
truth values on the language { p , q } even if we a real statement associated to p and q, the truth-
value does not depend on the intuitive meaning/interpretation associated to p and q. Boolean
tables in fact, allow us to analyze the sentence of interest in. a completely formal way, free that is,
of any particular intuitions we may or may not associate to natural language interpretation of L.

Deciding which valuation is the correct description of the world is an empirical rather than logical
question: logic serves to analyze all the possibilities and doesn’t tell you what the right thing to do
is. More precisely, to give a concrete meaning to the information displayed on a Boolean matrix
one needs to interpret propositional variables. The combination of a valuation and an
interpretation is sometimes referred to as a propositional model.

Propositional model
In the propositional model, when a sentence gets value 1, you infer that it is true in-the-model.
Let’s consider 3 examples of interpretations:

Let L= { p , q } and consider ( p → q)⋀ (q → p). The truth vector is ⟨1, 0, 0, 1⟩. Now suppose we
example 1

interpret L in the context of Sars-CoV-2 diagnostic as follows:

- p: antigen test is positive
- q: the patient is infected
Now suppose we perform a PCR test (which we take to define whether the patient is infected or
not) and we get that they are, i.e., v(q)= 1. Then we perform an antigen test, and we have two
possible outcomes for it. If v(p) = 0, then we know we are in the real-world situation which in
statistical terms is referred to as the “False negative”. Conversely, if v(p) = 1, then we know we are
in the real-world situation which in statistical terms is referred to as the “True negative”.

Now, in the same propositional model, take λ = (q ∧ (p

→ q)) → p) as a candidate policy to deal with infected
patients. Note that v(λ) = 0 is evaluated to 0 (say, “it is
not applied as a containment measure”) we are in the
“False negative” case. It is however evaluated to 1 if the
antigen test results in a positive, whether or not the
patient is infected. Hence, λ can be seen, through the
analysis carried out in this (admittedly contrived) propositional model, as a potentially very
harmful policy, letting go many infected people and indeed trusting too blindly a fallible test. As it
turns out, the best practical contribution a logical model can give you is this.

Suppose θ with language {p, q} was the result of an epidemiological think-tank aimed at producing
actionable policies. If under the above interpretation −→v (θ) resulted in constant 0, then we
would obtain that if the propositional model is adequate, then you should never put θ into
practice, for it is guaranteed to not to yield any result, in the face of, say, considerable effort and
financial costs.
Interpreting the language effectively means using experimental or otherwise factual knowledge.
So, in the diagnostic scenario of the Covid example, you know the truth-values of p and q after a
reasonable amount of time since testing this factual information can be used to remove some, or
even all possibilities, i.e. reducing a truth-vector to a single truth-value. As noted above, if v(p) = 1,
then no matter what value will be taken by q then v(λ) = 1. If our diagnostics is restricted to the
two parameters p and q, logic’s contribution stops here, signaling as noted, that λ is not a
diagnostic policy anyone should really follow.

example 2
- p: test is positive
- q: pregnant
p and q are logically independent since, for example, it can happen that you are positive to the
test but non necessarily pregnant (false positive test). So ideally the perfect tests, as in the
previous examples, would be either v 1 or v4 (since they are reliable, look at the table). Of course,
people want to make v2 and v3 the least probable error and want to maximize v1 and v4.

example 3
Another interpretation can be the following, which regard airport security:
- p: alarm off
- q. explosive

Remark 8:
compatibility with the Boolean matrices is a necessary but not sufficient condition to do the
interpretation correct.

2.4 Compositionality (aka Truth-functionality)

The idea of this paragraph is that syntax + semantics allow us to compute the Boolean vector of
arbitrarily “complex” sentences. Suppose I have φ ⋀ ψ . Formally you can’t do the Boolean
matrices on this. In fact, the set of valuation says:
v={ v ∥ v : L → {0 ,1 } }

whereas to have the set of valuations I should have specified

v={ v ∥ v : S L→ {0 , 1 } } since L is different from S L.

As you can see from the example, Boolean matrices can only be applied to propositional variables.
However, this restriction is not meaningful as shown by the next Lemma which leads to a rather
general consideration, and indeed helps us identifying an extremely important property of
Boolean logic. this property is referred to as compositionality or as truth-functionality and had
been made clear by Alfred Tarski in 1933. (This is why we refer to semantics as Tarskian
semantics).
The lemma says that no matter how complicate a sentence is, you can just treat  and  as they
were just propositional variables p and q, since you already know the truth value of the sentences
and you can use what are now called extended Boolean tables. It guarantees that the method of
Boolean tables can be extended to those cases in which the distribution of truth values on L is not
known. Thus, the method of extended Boolean tables gives you an algorithm in order to verify
whether  belongs to L .

The proof of this Lemma is by induction:

 φ2 ∈ S L.
In the above,
clearly, φ1,
The induction
hypothesis
guarantees that the previous stipulations are well-defined, and this concludes the proof.

Remark 9:
The above discussion
(together with Theorem 3)
guarantees that the method of
Boolean matrices can be
illustrate. Let θ, φ ψ ∈ SL. No further knowledge of L is available. Consider now the sentence
extended to those cases in which the distribution of truth-values on L is not known, as we now

χ = (θ ∧ φ) → ψ

Extended Boolean matrices provide an algorithm to decide for each θ ∈ S L whether θ is

Remark 10:

1. a tautology
2. a contradiction
3. a contingent

All tautologies and contradictions will have always the same truth vector (only.1 or 0) and they are
the contradiction of one another. You will never get from a tautology or a contradiction to a
contingent sentence with normal connectives.

Principle of compositionality
Let us go back to the Tarskian conditions featuring in Lemma 2 to note that what they effectively
amount to is the fact that the truth-value of any sentence in SL is a fixed function of the truth-
values of its components. To make this explicit we will spell out the argument for the connective
of conjunction. The other cases are similar and are left as exercise.
Exercise 26: define suitable truth-functions for negation and for disjunction

Exercise 27: are any of the following individually sufficient to determine

- v(θ)?v(θ∧φ) = 0 and v(φ) = 0

- v(θ∨ φ) = 1 and
v(φ) = 1

2.5 Satisfiability
The general idea of this this paragraph is a formalization of rationality (coherence). Recall that a
valuation v : L → {0 , 1 }is a complete description of a logical of affairs which means that is a full

description of a row in a Boolean matrix and therefore the set of all valuations on L can be
thought of as a complete distribution of truth-values on L .

So, a “model” is a valuation that sends all the element of the set to 1. Let’s consider the following
examples:
N.B. the notion of satisfiability and the associated notion of logical model can be seen as a
formalization of the intuitive notion of coherence. For if a set is unsatisfiable, there is no way to
which its elements can be all true, that is to say they do not cohere. Let us put this observation to
work in the problem from lecture 1.
Recall the situation where 3 experts are asked to put forward their opinion on recommending a
new vaccine to a certain population segment. The situation led to the following puzzling situation:
where the law captures the basic idea that a vaccine should be recommended (r) if and only if it is
effective (p) and it is safe (q). All the three experts agree on this but disagree on the remaining two
parameters. As we discussed above, the key problem arises here because the three experts submit
individually coherent judgments which are turned collectively incoherent by majority rule. We
have now covered all the logical background needed to be more precise about the meaning of
coherence in this setting: each expert judges in accord with the Tarskian conditions listed in
Lemma 2, whereas the simple-majority aggregation of their judgments does not. Indeed, the
majority’s judgment is not satisfiable. If consistency is identified with rationality (and at this level
of abstraction, this seems entirely plausible), the discursive dilemma is a situation in which
individual rationality leads, via simple majority aggregation, to collective irrationality.
 2.6Logical Consequence (“what follows from what”)

Definition 11: We say that θ is a logical consequence of Γ, written Γ |= θ if and only if ∀v ∈ V, if

v(Γ) = 1 then v(θ) = 1.

we write as follows: Γ |= θ if and only if MΓ ⊆ Mθ.

This means that θ is a logical consequence of Γ if and only if every model of Γ is a model of θ, which

In order to check whether θ is a logical consequence of Γ it suffices to check whether all the rows
assigning 1 to all the sentences in Γ also evaluate θ to 1. Let’s
consider some examples

example 1: Let Γ ={ p , p → q } and let θ=q . Is this the case

that Γ |= θ? By definition we can answer YES only if the models of Γ are
included in the models of θ, or equivalently, we must answer NO if we
can find a model of Γ which is not a model of θ. So let us visualize what
the models of Γ and θ are.

By inspecting the lines of the above table, it is apparent that Mod ( Γ )= { v 4 } ⊆ Mod ( q )= { v 2 , v 4 } .
Therefore the answer must be YES.

example 2: Let Γ ={ p , p ⋁ q } and let θ=q. It is the case that Γ |= θ? Let us reason as in the
previous example. As we can see from the table, v 3 is a model of Γ but is not in Mod(q), so the
answer this time is NO.

Recall that sentences come in three kinds: tautologies, contradictions and contingencies. The
notion of logical consequence allows us to provide an alternative definition of the first two. We
say that a sentence θ is a tautology, and write |= θ, if and only if every valuation satisfies θ
(alternatively: θ is true under all the 2L valuations on L, alternatively: if it is mapped to 1 in each
row of a suitable Boolean matrix). A tautology is therefore true “in virtue of its logical structure”,
and therefore we don’t need to mention its models. This explains the notation. A contradiction is
defined similarly, i.e., as a sentence which has no models. So, contradictions are unsatisfiable.
Key properties of |=
The following proposition captures a number of central properties of classical consequence.

Proof of property 1

Remark 11
in Proposition 3 allows us to make a very
precise than rather obvious semantic analogy
between the propositional connective “”
and the consequence relation |=. in the special case when Γ = 0 (empy set) then φ |= θ if and only
if |= φ → θ.

Note also that this extends immediately to the analysis of arguments which combine several
consequence relations.

2.7Logical equivalence (it tells you when syntactic difference is irrelevant)

1. syntax: the key element of syntax is S L

- S L defined recursively proof by induction
- lack of ambiguity uniqueness of the parsing tree, i.e., φϵS L→ T (φ)
2. semantics: the key element of semantics is v : L → {1 , 2 }
- lemma 2 says that valuations extend uniquely to S L .
- the consequence of this is that lemma 2 allows me to use Boolean Matrices to compute
any truth vector v(φ ¿

Definition 12(Logical equivalence): θ, φ ∈ S L are logically equivalent, written θ ≡ φ, if ∀v ∈ V,

v(θ) = v(φ). (they mean the same, but the are not the same!)

The inverse Boolean Matrices is not unique:

p q Φ1 Φ2
0 0 0 0
0 1 1 1
1 0 1 1
1 1 0 0