Lecture Notes on Mathematical Logic
Vladimir Lifschitz
January 16, 2009
These notes provide an elementary, but mathematically solid, introduc-
tion to propositional and first-order logic. They contain many exercises.
Logic is the study of reasoning. The British mathematician and philoso-
pher George Boole (1815–1864) is the man who made logic mathematical.
His book The Mathematical Analysis of Logic was published in 1847.
Logic can be used in programming, and it can be applied to the analysis
and automation of reasoning about software and hardware. This is why
it is sometimes considered a part of theoretical computer science. Since
reasoning plays an important role in intelligent behavior, logic is closely
related to artificial intelligence.
The short book by the German philosopher Gottlob Frege (1848–1925)
with the long title Ideography, a Formula Language, Modeled upon that of
Arithmetic, for Pure Thought (1879), introduced notation that is somewhat
similar to what is now called first-order formulas. Frege wrote:
I believe that I can best make the relation of my ideography to
ordinary language clear if I compare it to that which the micro-
scope has to the eye. Because of the range of its possible uses
and the versatility with which it can adapt to the most diverse
circumstances, the eye is far superior to the microscope. . . But,
as soon as scientific goals demand great sharpness of resolution,
the eye proves to be insufficient.
. . . I am confident that my ideography can be successfully used
wherever special value must be placed on the validity of proofs, as
for example when the foundations of the differential and integral
calculus are established.
In logic and in linguistics, we distinguish between two languages: the
one that is the object of study and the one that we use to talk about that
1
,object. The former is called the object language; the latter is the metalan-
guage. In Sections 1 and 2 below, the object language is the formal language
of propositional formulas; in Section 3, we turn to first-order formulas. The
metalanguage is the usual informal language of mathematics and theoretical
computer science, which is a mixture of the English language and mathemat-
ical notation. The importance of distinguishing between the object language
and the metalanguage was emphasized by the mathematician and logician
Alfred Tarski (1902–1983), who taught logic at Berkeley since 1942.
1 Syntax and Semantics of Propositional Formulas
Propositional Formulas
A propositional signature is a set of symbols called atoms. (In examples, we
will assume that p, q, r are atoms.) The symbols
∧ ∨ → ↔ ¬ ⊥ ⊤
are called propositional connectives. Among them, the symbols ∧ (con-
junction), ∨ (disjunction), → (implication) and ↔ (equivalence) are called
2-place, or binary connectives; ¬ (negation) is a 1-place, or unary connective;
⊥ (false) and ⊤ (true) are 0-place.
Take a propositional signature σ which contains neither the proposi-
tional connectives nor the parentheses (, ). The alphabet of propositional
logic consists of the atoms from σ, the propositional connectives, and the
parentheses. By a string we understand a finite string of symbols in this
alphabet. We define when a string is a (propositional) formula recursively,
as follows:
• every atom is a formula,
• both 0-place connectives are formulas,
• if F is a formula then ¬F is a formula,
• for any binary connective ⊙, if F and G are formulas then (F ⊙ G) is
a formula.
For instance,
¬(p → q)
and
(¬p → q) (1)
2
, are formulas; the string
¬p → q (2)
is not a formula. But very soon (see next page) we are going to introduce a
convention according to which (2) can be used as an abbreviation for (1).
Properties of formulas can be often proved by induction. One useful
method is strong induction on length (number of symbols). In such a proof,
the induction hypothesis is that every formula which is shorter than F has
the property P that we want to prove. From this assumption we need to
derive that F has property P also. Then it follows that all formulas have
property P .
In another useful form of induction, we check that all atoms and 0-place
connectives have property P , and that the property is preserved when a new
formula is formed using a unary or binary connective. More precisely, we
show that
• every atom has property P ,
• both 0-place connectives have property P ,
• if a formula F has property P then so does ¬F ,
• for any binary connective ⊙, if formulas F and G have property P
then so does (F ⊙ G).
Then we can conclude that property P holds for all formulas. This is called
“structural induction.”
For instance, it is not difficult to prove, using either form of induction,
that the number of left parentheses in any formula is equal to the number
of right parentheses. (Do it!)
Problem 1.1 In any prefix of a formula, the number of left parentheses
is greater than or equal to the number of right parentheses. (A prefix of a
string a1 · · · an is any string of the form a1 · · · am where 0 ≤ m ≤ n.)
Problem 1.2 Every prefix of a formula F
• is a string of negations (possibly empty), or
• has more left than right parentheses, or
• equals F .
3
Vladimir Lifschitz
January 16, 2009
These notes provide an elementary, but mathematically solid, introduc-
tion to propositional and first-order logic. They contain many exercises.
Logic is the study of reasoning. The British mathematician and philoso-
pher George Boole (1815–1864) is the man who made logic mathematical.
His book The Mathematical Analysis of Logic was published in 1847.
Logic can be used in programming, and it can be applied to the analysis
and automation of reasoning about software and hardware. This is why
it is sometimes considered a part of theoretical computer science. Since
reasoning plays an important role in intelligent behavior, logic is closely
related to artificial intelligence.
The short book by the German philosopher Gottlob Frege (1848–1925)
with the long title Ideography, a Formula Language, Modeled upon that of
Arithmetic, for Pure Thought (1879), introduced notation that is somewhat
similar to what is now called first-order formulas. Frege wrote:
I believe that I can best make the relation of my ideography to
ordinary language clear if I compare it to that which the micro-
scope has to the eye. Because of the range of its possible uses
and the versatility with which it can adapt to the most diverse
circumstances, the eye is far superior to the microscope. . . But,
as soon as scientific goals demand great sharpness of resolution,
the eye proves to be insufficient.
. . . I am confident that my ideography can be successfully used
wherever special value must be placed on the validity of proofs, as
for example when the foundations of the differential and integral
calculus are established.
In logic and in linguistics, we distinguish between two languages: the
one that is the object of study and the one that we use to talk about that
1
,object. The former is called the object language; the latter is the metalan-
guage. In Sections 1 and 2 below, the object language is the formal language
of propositional formulas; in Section 3, we turn to first-order formulas. The
metalanguage is the usual informal language of mathematics and theoretical
computer science, which is a mixture of the English language and mathemat-
ical notation. The importance of distinguishing between the object language
and the metalanguage was emphasized by the mathematician and logician
Alfred Tarski (1902–1983), who taught logic at Berkeley since 1942.
1 Syntax and Semantics of Propositional Formulas
Propositional Formulas
A propositional signature is a set of symbols called atoms. (In examples, we
will assume that p, q, r are atoms.) The symbols
∧ ∨ → ↔ ¬ ⊥ ⊤
are called propositional connectives. Among them, the symbols ∧ (con-
junction), ∨ (disjunction), → (implication) and ↔ (equivalence) are called
2-place, or binary connectives; ¬ (negation) is a 1-place, or unary connective;
⊥ (false) and ⊤ (true) are 0-place.
Take a propositional signature σ which contains neither the proposi-
tional connectives nor the parentheses (, ). The alphabet of propositional
logic consists of the atoms from σ, the propositional connectives, and the
parentheses. By a string we understand a finite string of symbols in this
alphabet. We define when a string is a (propositional) formula recursively,
as follows:
• every atom is a formula,
• both 0-place connectives are formulas,
• if F is a formula then ¬F is a formula,
• for any binary connective ⊙, if F and G are formulas then (F ⊙ G) is
a formula.
For instance,
¬(p → q)
and
(¬p → q) (1)
2
, are formulas; the string
¬p → q (2)
is not a formula. But very soon (see next page) we are going to introduce a
convention according to which (2) can be used as an abbreviation for (1).
Properties of formulas can be often proved by induction. One useful
method is strong induction on length (number of symbols). In such a proof,
the induction hypothesis is that every formula which is shorter than F has
the property P that we want to prove. From this assumption we need to
derive that F has property P also. Then it follows that all formulas have
property P .
In another useful form of induction, we check that all atoms and 0-place
connectives have property P , and that the property is preserved when a new
formula is formed using a unary or binary connective. More precisely, we
show that
• every atom has property P ,
• both 0-place connectives have property P ,
• if a formula F has property P then so does ¬F ,
• for any binary connective ⊙, if formulas F and G have property P
then so does (F ⊙ G).
Then we can conclude that property P holds for all formulas. This is called
“structural induction.”
For instance, it is not difficult to prove, using either form of induction,
that the number of left parentheses in any formula is equal to the number
of right parentheses. (Do it!)
Problem 1.1 In any prefix of a formula, the number of left parentheses
is greater than or equal to the number of right parentheses. (A prefix of a
string a1 · · · an is any string of the form a1 · · · am where 0 ≤ m ≤ n.)
Problem 1.2 Every prefix of a formula F
• is a string of negations (possibly empty), or
• has more left than right parentheses, or
• equals F .
3
