Introduction to Formal Logic

(Fall 2022)

Dr. Teppei Hayashi

Department of Philosophy
University of Calgary

Email: thayashi@ucalgary.ca
Contents

1 Language L1 6
1.1 Syntax of L1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.1 The Vocabulary of L1 . . . . . . . . . . . . . . . . . . . 7
1.1.2 The Formation Rules of L1 -Sentences . . . . . . . . . . 7
1.1.3 The Main Connective . . . . . . . . . . . . . . . . . . . 8
1.1.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 Semantics of L1 . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.1 Interpretations of a Sentence Letter of L1 . . . . . . . . 9
1.2.1.1 Interpretations of a Denial . . . . . . . . . . . 10
1.2.2 Interpretations of a Conjunction . . . . . . . . . . . . . 10
1.2.3 Interpretations of a Disjunction . . . . . . . . . . . . . 10
1.2.4 Interpretations of a Conditional . . . . . . . . . . . . . 11
1.2.5 Interpretations of a Bi-Conditional . . . . . . . . . . . 11
1.2.6 Examples . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3 Semantical Properties of (a Set of) L1 -Sentences . . . . . . . . 13
1.3.1 Satisfiability . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3.2 Unsatisfiability . . . . . . . . . . . . . . . . . . . . . . 14
1.3.3 Validity . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3.4 Invalidity . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3.5 Interrelations among the Properties . . . . . . . . . . . 15
1.3.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.4 Logical Implication and Logical Equivalence . . . . . . . . . . 16
1.4.1 Logical Implication . . . . . . . . . . . . . . . . . . . . 16
1.4.1.1 Problems . . . . . . . . . . . . . . . . . . . . 18
1.4.2 Logical Equivalence . . . . . . . . . . . . . . . . . . . . 19
1.4.2.1 Problems . . . . . . . . . . . . . . . . . . . . 20

1
 1.5 Argument . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.5.1 Problems . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.6 Some Words on Implication/Argument . . . . . . . . . . . . . 24
1.6.1 The Difference between the Validities of a Sentence and
of an Argument . . . . . . . . . . . . . . . . . . . . . . 25
1.6.2 The Condition in Which an Implication and an Argu-
ment Hold . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.7 Complete Disjunctive Normal Form . . . . . . . . . . . . . . . 26
1.7.1 Truth-Functional Connectives . . . . . . . . . . . . . . 26
1.7.2 Complete Disjunctive Normal Form . . . . . . . . . . . 27
1.7.2.1 Problems . . . . . . . . . . . . . . . . . . . . 30
1.8 Expressive Completeness . . . . . . . . . . . . . . . . . . . . . 30
1.8.1 Problems . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.9 Truth-Tree Method for L1 . . . . . . . . . . . . . . . . . . . . 33
1.9.1 10 Rules of the Truth-Tree Method . . . . . . . . . . . 33
1.9.1.1 Problem . . . . . . . . . . . . . . . . . . . . . 35
1.9.2 Testing the Satisfiability of sentences . . . . . . . . . . 35
1.9.2.1 Problem . . . . . . . . . . . . . . . . . . . . . 39
1.9.3 Testing the Validity of a Sentence . . . . . . . . . . . . 41
1.9.3.1 Problems . . . . . . . . . . . . . . . . . . . . 43
1.9.4 Testing the Validity of an Argument . . . . . . . . . . 43
1.9.4.1 Problems . . . . . . . . . . . . . . . . . . . . 45
1.9.5 Testing the Implication . . . . . . . . . . . . . . . . . . 45
1.9.5.1 Problems . . . . . . . . . . . . . . . . . . . . 47
1.9.6 Testing the Equivalence . . . . . . . . . . . . . . . . . 47
1.9.6.1 Problems . . . . . . . . . . . . . . . . . . . . 49

2 Language L2 50
2.1 Syntax of L2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.1.1 The Vocabulary of L2 . . . . . . . . . . . . . . . . . . . 51
2.1.1.1 Names . . . . . . . . . . . . . . . . . . . . . . 52
2.1.1.2 Predicates . . . . . . . . . . . . . . . . . . . . 52
2.1.1.3 Quantifiers . . . . . . . . . . . . . . . . . . . 53
2.1.2 The Formation Rules of L2 -Sentences . . . . . . . . . . 54
2.1.2.1 Examples of L2 -Sentences . . . . . . . . . . . 55
2.1.2.2 Examples of Non-Sentences . . . . . . . . . . 55
2.2 Translation from/into L2 -Sentences . . . . . . . . . . . . . . . 55
2.2.1 Translating L2 -sentences with one predicate . . . . . . 56

2
 2.2.2 Translating L2 -sentences with two predicates . . . . . . 57
2.2.2.1 Many faces of ∃ . . . . . . . . . . . . . . . . . 57
2.2.3 Translating Noun Phrases . . . . . . . . . . . . . . . . 58
2.2.3.1 Problems . . . . . . . . . . . . . . . . . . . . 59
2.2.4 Some Translation Practices . . . . . . . . . . . . . . . 59
2.2.4.1 Problem . . . . . . . . . . . . . . . . . . . . . 60
2.2.5 Some Translation Tips . . . . . . . . . . . . . . . . . . 60
2.2.5.1 If . . . , then . . . . . . . . . . . . . . . . . . . . . 60
2.2.5.2 Only . . . . . . . . . . . . . . . . . . . . . . . 61
2.2.5.3 Unless . . . . . . . . . . . . . . . . . . . . . . 61
2.2.5.4 Any . . . . . . . . . . . . . . . . . . . . . . . 62
2.2.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . 63
2.3 Semantics of L2 . . . . . . . . . . . . . . . . . . . . . . . . . . 64
2.3.1 Assignment of an Object to a Name . . . . . . . . . . . 64
2.3.2 Assignment of Truth Values to a Predicate . . . . . . . 65
2.3.2.1 Assignment of Truth Values to a One-Place
Predicate . . . . . . . . . . . . . . . . . . . . 65
2.3.2.2 Assignment of Truth Values to a Two-Place
Predicate . . . . . . . . . . . . . . . . . . . . 66
2.3.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . 67
2.3.3.1 Determining the Truth Values of Sentences
under a Given Interpretation . . . . . . . . . 67
2.3.3.2 Constructing an Interpretation under Which
a Given Sentences Are True (or False) . . . . 71
2.4 Truth-Tree Method for L2 . . . . . . . . . . . . . . . . . . . . 74
2.4.1 Testing the satisfiability of a sentence . . . . . . . . . . 75
2.4.2 Testing the Validity of a Sentence . . . . . . . . . . . . 76
2.4.3 Testing the Validity of an Argument . . . . . . . . . . 76
2.4.4 Construct an Interpretation from an Open Path . . . . 79
2.4.5 Testing the Equivalence . . . . . . . . . . . . . . . . . 81
2.4.6 Some Metalogical Considerations . . . . . . . . . . . . 83
2.4.6.1 Decidability . . . . . . . . . . . . . . . . . . . 84
2.4.6.2 Soundness . . . . . . . . . . . . . . . . . . . . 84
2.4.6.3 Completeness . . . . . . . . . . . . . . . . . . 85
2.4.6.4 Problem . . . . . . . . . . . . . . . . . . . . . 85

3
3 Language L3 86
3.1 Translation from/into L3 -sentences . . . . . . . . . . . . . . . 87
3.1.1 Translating L3 -Sentences . . . . . . . . . . . . . . . . . 87
3.1.1.1 By Way of a Quasi-English Sentence . . . . . 87
3.1.1.2 Translating an L3 -Sentence Step by Step . . . 89
3.1.2 Translating English sentences into L3 -Sentences . . . . 90
3.1.2.1 Trial and Error . . . . . . . . . . . . . . . . . 90
3.1.2.2 Utilizing What We Have at Our Disposal . . 92
3.1.2.3 Translating Step by Step . . . . . . . . . . . . 92
3.1.2.4 Introducing the Templates . . . . . . . . . . . 93
3.1.3 Problems . . . . . . . . . . . . . . . . . . . . . . . . . 95
3.2 Interpretation of L3 -Sentences . . . . . . . . . . . . . . . . . . 96
3.2.1 Deciding a Truth Value of a Sentence under a Given
Interpretation . . . . . . . . . . . . . . . . . . . . . . . 96
3.2.2 Providing an Interpretation Which Makes a Given Sen-
tence True or False . . . . . . . . . . . . . . . . . . . . 98
3.2.3 Providing One Interpretation for Two Sentences . . . . 99
3.2.4 Problems . . . . . . . . . . . . . . . . . . . . . . . . . 100
3.3 Truth Trees for L3 . . . . . . . . . . . . . . . . . . . . . . . . 101
3.3.1 Testing the satisfiability of a sentence . . . . . . . . . . 102
3.3.2 Testing the Validity of a Sentence . . . . . . . . . . . . 103
3.3.3 Testing the Satisfiability, Again . . . . . . . . . . . . . 103
3.3.4 Testing the Validity of an Argument . . . . . . . . . . 106
3.3.5 Testing the Equivalence between Sentences . . . . . . . 106

4 Further Extension of L3 108

4.1 Identity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
4.1.1 Problems . . . . . . . . . . . . . . . . . . . . . . . . . 113
4.2 Numerical Expressions . . . . . . . . . . . . . . . . . . . . . . 113
4.2.1 At Least . . . . . . . . . . . . . . . . . . . . . . . . . . 113
4.2.2 At Most . . . . . . . . . . . . . . . . . . . . . . . . . . 115
4.2.3 Exactly . . . . . . . . . . . . . . . . . . . . . . . . . . 116
4.2.3.1 Problem . . . . . . . . . . . . . . . . . . . . . 117
4.2.4 Definite Description . . . . . . . . . . . . . . . . . . . . 118
4.2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 119
4.2.6 Examples . . . . . . . . . . . . . . . . . . . . . . . . . 119
4.2.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . 121
4.3 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

4
 4.3.1 Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
4.3.2 Translating with Functions . . . . . . . . . . . . . . . . 122
4.3.3 Truth-Tree Method for Functions . . . . . . . . . . . . 123

Solutions 127
Solutions for Problems 1.1.4 . . . . . . . . . . . . . . . . . . . . . . 127
Solutions for Problems 1.2.7 . . . . . . . . . . . . . . . . . . . . . . 127
Solutions for Problems 1.3.6 . . . . . . . . . . . . . . . . . . . . . . 128
Solutions for Problems 1.4.1.1 . . . . . . . . . . . . . . . . . . . . . 129
Solutions for Problems 1.4.2.1 . . . . . . . . . . . . . . . . . . . . . 130
Solutions for Problems 1.5.1 . . . . . . . . . . . . . . . . . . . . . . 130
Solutions for Problems 1.7.2.1 . . . . . . . . . . . . . . . . . . . . . 131
Solutions for Problems 1.8.1 . . . . . . . . . . . . . . . . . . . . . . 131
Solutions for Problems 1.9.3.1 . . . . . . . . . . . . . . . . . . . . . 132
Solutions for Problems 1.9.4.1 . . . . . . . . . . . . . . . . . . . . . 136
Solutions for Problems 1.9.5.1 . . . . . . . . . . . . . . . . . . . . . 139
Solutions for Problems 1.9.6.1 . . . . . . . . . . . . . . . . . . . . . 141
Solutions for Problems 2.2.3.1 . . . . . . . . . . . . . . . . . . . . . 144
Solutions for Problems 2.2.4.1 . . . . . . . . . . . . . . . . . . . . . 145
Solutions for Problems 2.2.6 . . . . . . . . . . . . . . . . . . . . . . 146
Solutions for Problems 2.4.6.4 . . . . . . . . . . . . . . . . . . . . . 146
Solutions for Problems 3.1.3 . . . . . . . . . . . . . . . . . . . . . . 147
Solutions for Problems 3.2.4 . . . . . . . . . . . . . . . . . . . . . . 148
Solutions for Problems 4.1.1 . . . . . . . . . . . . . . . . . . . . . . 153
Solutions for Problems 4.2.3.1 . . . . . . . . . . . . . . . . . . . . . 157
Solutions for Problems 4.2.7 . . . . . . . . . . . . . . . . . . . . . . 160

5
Chapter 1

Language L1

We are dealing with a language called L1 . So let’s start with very basic
aspects of this language.
L1 can be seen from two different angles: syntax and semantics. In
short, the syntax and semantics of L1 tell us:

Syntax: What kind of expression is considered as a sentence of L1 (vo-

cabulary and formation rules of a sentence of L1 ).

Semantics: How to assign the truth values {true, false}1 to a sentence

of L1 (truth table).

Let’s take a bit closer look at these two aspects.

1.1 Syntax of L1
As we’ve seen in the above, the syntactical aspect of L1 tells us what kind
of expression is considered as a sentence of L1 . As in ordinary languages,
the syntax of L1 comprises of the vocabulary and formation rules (namely,
grammar) of L1 -sentences. Let’s start with the vocabulary of L1 .
1
True and false are sometimes abbreviated as: T and F, t and f, T and ⊥ (upside-down
T), or 1 and 0 respectively. I’m going to use the first abbreviation (namely, T and F)
throughout this study guide

6
1.1.1 The Vocabulary of L1
The vocabulary of L1 comprises of

Logical Symbols: (, ), −, ∧, ∨, →, ↔

Non-Logical Symbols: Sentence letters A, B, C, . . . with or without

subscript (e.g., A1 , B2 , Z1028 ).

Auxiliary Symbols: Sentence variables α, β, γ, . . . (the lower Greek

letters) with or without subscript.

Sentence letters are sometimes called atomic sentences; if a sentence

is not a sentence letter, it’s called a compound sentence.
The logical symbols −, ∧, ∨, →, ↔ are called logical connectives, and
called “denial” (or “negation”), “conjunction”, “disjunction”, “conditional”,
and “bi-conditional” respectively. A sentence variable is used for referring
to an arbitrary sentence of L1 . So, the sentence variable α may refer to a
sentence letter like A, or a rather complicated sentence like −(A ∧ (B ↔
(C ∨ D))).

1.1.2 The Formation Rules of L1 -Sentences

The formation rules of L1 -sentences are as follows.

1. Every sentence letter is a sentence of L1 .

2. If α and β are sentences of L1 , so are −α, (α ∧ β), (α ∨ β), (α →

β), (α ↔ β).2

3. Nothing else is a sentence of L1 .

Thus, −(A ∧ (B ↔ C)) is a sentence of L1 but ((→ A is not.

2
Officially, the formation rules for a conjunction and a disjunction are as follows:
1. If α1 , α2 , . . . , αn are sentences of L1 , so is (α1 ∧ α2 ∧ . . . ∧ αn ).
2. If α1 , α2 , . . . , αn are sentences of L1 , so is (α1 ∨ α2 ∨ . . . ∨ αn ).
However, for several reasons (especially in writing truth tables or truth trees), it would be
better to adopt the above non-official way.

7
 The components of a conjunction (α and β in the above case) are
called conjuncts; the components of a disjunction are called disjuncts; and the
first component of a conditional (α in the above case) is called anantecedent
while the second component (β in the above case) is called a consequent.3
Some authors call sentence letters and their denials literals; so A,
−B, C256 etc. are all literals.

1.1.3 The Main Connective

In writing truth tables or truth trees,4 first you need to be able to answer
the following question: “What kind of a sentence is this?” In the case of a
denial sentence, it’s easy to answer because every denial sentence has a form
“−(. . .)”. In the case of a simple sentences like (A ∧ B) or (A → B), it’s easy
as well; the former is a conjunctive sentence, the latter conditional. However,
in the case of a more complicated sentence, figuring out what sentence we’re
thinking of can be a substantial task. Let’s take (((B ∨ C) → A) ↔ ((B →
A) ∧ (−A → −C))) as an example.
First, note that a sentence of L1 is built in a bottom-up way; in
other words, a bigger sentence should be built from smaller ones. For ex-
ample, in order to build ((A ∧ B) → −C), we need to build (A ∧ B) and
−C first, and then, connect them by → (and of course enclose it with brack-
ets). In the case of our example, we need to build −A and −C first, and
then (B ∨ C), (B → A) and (−A → −C), and then ((B ∨ C) → A) and
((B → A) ∧ (−A → −C)), and lastly connect them by ↔. This building
process can be shown graphically as follows.

(((B ∨ C) → A) ↔ ((B → A) ∧ ( −A → −C )))

| {z } | {z } |{z} |{z}
(2) (2) (1) (1)
| {z } | {z }
(3) (2)
| {z }
(3)
| {z }
(4)

In the stage 4 of the above building process, we connect the two

sentences built in the stage 3 by ↔; in other words, the last connective we
3
There’s no special way to call the components of a bi-conditional; we simply call them
“the left-hand (right-hand) side of a bi-conditional”.
4
We’re gonna learn what truth tables and truth trees are later in the course.

8
add in building the sentence is ↔. We call this last connective the main
connective, and say, “the sentence is a bi-conditional”.

1.1.4 Problems
Determine the main connectives of the following sentences.
1. ((− − A ∧ B) → (−A ↔ B))
2. (−D ∧ (−H ∨ (D ∧ E)))
3. (−(D ↔ (−A ∧ B)) ∨ (−D ∨ −B))
4. ((J ∧ ((E ∨ F ) ∧ (−E ∧ −F ))) → −J)
5. −(−A ↔ −(B ↔ −(A ↔ (B ∧ C))))

1.2 Semantics of L1
The semantics of L1 tells us how to assign the truth values {T,F} to a
sentence of L1 . Such assignments of the truth values to a sentence are called
interpretations or truth-value assignments. Let’s start with the simplest one.

1.2.1 Interpretations of a Sentence Letter of L1

A sentence letter α is going to be true in an interpretation I if and only if5
I assigns true to α; otherwise, α is going to be false. The truth table for the
interpretations of α is

α
T
F

Each row in the above truth table represents an interpretation; thus,

there are two interpretations for each sentence letter.
5
In the course, we use “just in case” (abbreviated as “jic”) instead of “if and only if”
(abbreviated as “iff”). Since “if and only if” is more popular (especially in mathematics),
I adopt “if and only if” (iff) in this study guide.

9
1.2.1.1 Interpretations of a Denial
A denial −α is going to be true in I if and only if I assigns false to α;
otherwise, −α is going to be false. Thus, the truth table for a denial −α is

α −α
T F
F T

1.2.2 Interpretations of a Conjunction

A conjunction (α ∧ β) is going to be true in I if and only if I assign true
to both conjuncts; in other words, if I assigns false to at least one of its
conjuncts, (α ∧ β) is going to be false in I.

α β (α ∧ β)
T T T
T F F
F T F
F F F

Again, each row represents an interpretation. If a sentence in con-

sideration contains two components, there should be four rows (interpreta-
tions).

1.2.3 Interpretations of a Disjunction

A disjunction (α ∨ β) is going to be true in I if and only if I assigns true to
at least one of the sentence’s disjuncts; in other words, if I assigns false to
both of its disjuncts, (α ∨ β) is going to be false in I.

α β (α ∨ β)
T T T
T F T
F T T
F F F

Note that our disjunction is going to be true when I assigns true to

both disjuncts; namely, our disjunction is not exclusive.

10
1.2.4 Interpretations of a Conditional
A conditional (α → β) is going to be true in I if and only if I assigns false to
the antecedent (α in this case) or true to the consequent (β in this case); in
other words, if I assigns true to the antecedent and false to the consequent,
(α → β) is going to be false in I.

α β (α → β)
T T T
T F F
F T T
F F T

1.2.5 Interpretations of a Bi-Conditional

A bi-conditional (α ↔ β) is going to be true in I if and only if I assigns
the same truth value to both components; in other words, if I assigns the
different truth value to the components, (α ↔ β) is going to be false in I.

α β (α ↔ β)
T T T
T F F
F T F
F F T

1.2.6 Examples
Let’s construct the truth table for (((B ∨ C) → A) ↔ ((B → A) ∧ (−A →
−C))). In constructing it, you need to proceed from smaller sentences to
bigger ones. So, you need to fill out the truth values for −A and −C first.
(If you’re not so sure why you need to do so, read Section 1.1.3 again.)

11
 A B C (((B ∨ C) → A) ↔ ((B → A) ∧ ( − A → − C)))
T T T F F
T T F F T
T F T F F
T F F F T
F T T T F
F T F T T
F F T T F
F F F T T

And then, (B ∨ C), (B → A), and (−A → −C).

A B C (((B ∨ C) → A) ↔ ((B → A) ∧ ( − A → − C)))

T T T T T F T F
T T F T T F T T
T F T T T F T F
T F F F T F T T
F T T T F T F F
F T F T F T T T
F F T T T T F F
F F F F T T T T

And then, ((B ∨ C) → A) and ((B → A) ∧ (−A → −C)).

A B C (((B ∨ C) → A) ↔ ((B → A) ∧ ( − A → − C)))

T T T T T T T F T F
T T F T T T T F T T
T F T T T T T F T F
T F F F T T T F T T
F T T T F F F T F F
F T F T F F F T T T
F F T T F T F T F F
F F F F T T T T T T

And finally, based on what you’ve got in the above, you’re gonna fill out the
truth values for the entire sentence.

12
 A B C (((B ∨ C) → A) ↔ ((B → A) ∧ ( − A → − C)))
T T T T T T T T F T F
T T F T T T T T F T T
T F T T T T T T F T F
T F F F T T T T F T T
F T T T F T F F T F F
F T F T F T F F T T T
F F T T F T T F T F F
F F F F T T T T T T T

As you see, it turned out that (((B∨C) → A) ↔ ((B → A)∧(−A →

−C))) is a valid sentence. (For what is a valid sentence, see Section 1.3.3.)

1.2.7 Problems
Construct truth tables for the sentences in Problems 1.1.4.

1.3 Semantical Properties of (a Set of ) L1-

Sentences
There are some properties of L1 -sentences which concern a semantical aspect
of sentences. In short, those properties tell us how to classify a sentence
according to what kind of truth-value assignments the sentence has. Let’s
take a look at them one by one.

1.3.1 Satisfiability
A sentence (or a set of sentences) is called satisfiable if there is at least
one interpretation where the sentence (or the set of sentences) is going
to be true.

Here, some clarification as to when a set of sentences is considered

as true (or false) would be in order.

13
 A set of sentences is going to be true if and only if an interpretation I
assigns true to all sentences in the set; otherwise, it’s going to be false.
In other words, the truth value for a set of sentences can be identified
with that of the conjunction of the sentences in the set.

For example, the set of L1 -sentences {(A → B), A}6 is satisfiable

because, in the following truth table,

A B (A → B)
T T T ⇐
T F F
F T T
F F T

you find an interpretation (which is the line 1) where (A → B) and A are

both true.
Note that any sentence letter is satisfiable. (See Section 1.2.1 for
the truth table.)
Sometimes a satisfiable sentence (resp. a satisfiable set of sentences)
is called a consistent sentence (resp. a consistent set of sentences).

1.3.2 Unsatisfiability
A sentence (or a set of sentences) is called unsatisfiable if there is no
interpretation where the sentence (or the set of sentences) is going to
be true. In other words, an unsatisfiable sentence (or an unsatisfiable
set of sentences) is always false no matter what truth value we assign to
sentence letters.

A paradigmatic example of unsatisfiable sentences would be (A ∧

−A).

( A ∧ − A)
T F F
F F T
6
We use the curly brackets {} for constructing a set.

14
What we find in the truth value assignments for (A ∧ −A) is nothing but F.
Sometimes an unsatisfiable sentence (resp. an unsatisfiable set of
sentences) is called an inconsistent sentence (resp. an inconsistent set of
sentences).

1.3.3 Validity
Validity is the exact opposite of unsatisfiability.

A sentence (or set of sentences) is called valid if and only if there’s no

interpretation where the sentence is going to be false; in other words, a
valid sentence (or a valid set of sentences) is always true in all interpre-
tation.

A paradigmatic example of valid sentences would be (A ∨ −A).

( A ∨ − A)
T T F
F T T

What we find in the truth value assignments for (A ∨ −A) is nothing but T.
Sometimes a valid sentence is called a tautology.

1.3.4 Invalidity
Invalidity is a kind of relatives of satisfiability.

A sentence (or a set of sentences) is called invalid if there is at least one

interpretation where the sentence (or the set of sentences) is going to be
false.

For example, the set of L1 -sentences {(A → B), A} is invalid be-

cause, in its truth table (see Section 1.3.1), we find Fs in the lines 2–4.

1.3.5 Interrelations among the Properties

As you may notice from the wordings of their definitions, there are some
interrelations among satisfiability/unsatisfiability/validity/invalidity as fol-
lows.

15
 subclass
Satisfiability Validity

not compatible

not compatible
ite co
p os mp
op at
t ibl
ac e
e ex
th

Unsatisfiability Invalidity
subclass

Note that the directions of the arrows matter. For example, there
is a single-headed arrow from “Validity” to “Satisfiability”; this means that,
together with the description “subclass” at the above of the arrow, valid-
ity is a subclass of satisfiability (meaning, every valid sentence is satisfiable
but not every satisfiable sentence is valid). On the other hand, there is a
double-headed arrow between “Satisfiability” and “Invalidity”; this means
that, together with the description “compatible”, a sentence can be both
satisfiable and invalid at the same time.

1.3.6 Problems
Classify the following sentences into satisfiable/unsatisfiable/valid/invalid.
(Note that a sentence can be classified into more than one category.)
1. (J → (K → J))
2. ((E ↔ H) → (−E → −H))
3. ((((C → D) ∧ (D → E)) ∧ C) ∧ −E)
4. −(((A ∨ B) ∧ (B ∨ B)) ∧ (−A ∧ −B))
5. (−B → ((B ∨ D) → D))

1.4 Logical Implication and Logical Equiva-

lence
1.4.1 Logical Implication

16
 α logically implies β if and only if there’s no interpretation where α is
true but β is false. In other words, α implies β if and only if a conditional
α → β is valid.

We usually omit “logically” and simply say “α implies β”. In the

below, we’ll use the notation “|=” for denoting logical implication.
The left-hand side of an implication can be a set of sentences; in
such cases, we write {α, β, . . . , γ} |= δ or Γ |= δ (we use the upper Greek
letters to denote a set of sentences). Obviously, here, you need to be able to
assign truth values to a set of sentences.7
In order to figure out whether α implies β or not, you can use
the truth table method. For example, you can figure out whether or not
−(A → B) implies A just by taking a look at the following truth table.

A B (A → B) −(A → B)
T T T F
T F F T
F T T F
F F T F

In the above table, there’s no interpretation where −(A → B) is true but A

is false; thus, you conclude that −(A → B) implies A.
Although the truth-table method comes in handy, writing a truth
table can be quite tedious. If there’s a handier way to figure out whether
α |= β or not, we want to use it. Is there any such method? Actually there
is.
Let’s think about ((B → C) → (A → B)) |= (A → B) and try
to show that ((B → C) → (A → B)) doesn’t imply (A → B). For the
implication to fail, (A → B) must be false; and for (A → B) to be false, A
must be true and B must be false. Thus, we get the following truth-value
assignment.

((B → C) → (A → B )) |= (A → B )
F T F T F
| {z } | {z }
F F

On the other hand, we want the left-hand side of the implication to be true;
thus, since (A → B) has been already assigned the truth value F, (B → C)
7
If you’re not so sure how to assign truth values to a set of sentences, see Section 1.3.1.

17
must be false in order for ((B → C) → (A → B)) to be true. However, we’ve
already assigned F to B; consequently, it’s impossible to make (B → C)
false no matter what truth value we assign to C because a conditional with
a false antecedent never be false. Therefore, it’s impossible to assign T to
the left-hand side of the implication and F to the right side; in other words,
it’s impossible to make the implication fail; ((B → C) → (A → B)) actually
implies (A → B).
How about (A ∨ −(B ∧ C)) |= ((A ↔ C) ∨ B)? Let’s see if we can
make this implication fail. For the implication to fail, the right-hand side
((A ↔ C) ∨ B) must be false; and for ((A ↔ C) ∨ B) to be false, both of its
conjuncts, namely (A ↔ C) and B, must be false.

(A ∨ −(B ∧ C)) |= ((A ↔ C ) ∨B )

F ? ? F
| {z }
F

In the above, for (A ↔ C) to be false, there are two options; A is

true and C is false, or A is false and C is true. If we choose the first option,
we instantly know that the left-hand side of the disjunction is going to be
true. Therefore, in this case, the implication fails and the counterexample is
given by the truth values TFF for A, B, and C.

(A ∨ −(B ∧ C )) |= ((A ↔ C ) ∨B )
T F F T F F
| {z } | {z }
T F

On the other hand, if we choose the second option (A is false, C is true),

the truth value of the disjunction on the left-hand side is determined by
−(B ∧ C).

(A ∨ − (B ∧ C )) |= ((A ↔ C ) ∨B )
F F T F T F
| {z } | {z }
F F
| {z }
T
| {z }
T

In either way, the implication fails.

1.4.1.1 Problems
1. Prove:

18
 1. α |= α
2. If Γ |= α, then Γ, β |= α (Here, “Γ, β” on the left-hand side of the
second implication means {γ1 , γ2 , . . . , γn , β} with Γ = {γ1 , γ2 , . . . , γn }.
3. If Γ |= α and α, ∆ |= β, then Γ, ∆ |= β
4. Γ, α |= β if and only if Γ |= (α → β)
5. If α |= β and β |= γ, then α |= γ

2. Determine whether the following implications hold. If the implication

fails, provide a counterexample.
1. {A, (B ∧ C)} |= B
2. {A, (B ∨ C)} |= B
3. {(K ∨ J), −(K ∨ J)} |= K
4. {(W ∨ J), ((W → Z) ∨ (J → Z)), −Z} |= −(W ∧ J)

1.4.2 Logical Equivalence

α logically equivalent to β if and only if α |= β and β |= α; in other
words, α is equivalent to β if and only if α ↔ β is valid.

We usually omit “logically” and simply say “α is equivalent to β”.

In the below, I use the notation “≡” for denoting logical equivalence. (Note
that this is my notation; if you want to use this notation in the exam, please
explicitly state that ≡ denotes logical equivalence.)
As an example, let’s prove that, if S1 |= S2 , S1 is equivalent to
(S1 ∧ S2 ) and S2 is equivalent to (S1 ∨ S2 ). In order to prove this, we have
to consider the following four implications.

1. S1 |= (S1 ∧ S2 )
2. (S1 ∧ S2 ) |= S1
3. S2 |= (S1 ∨ S2 )
4. (S1 ∨ S2 ) |= S2

In order for the first implication to fail, (S1 ∧ S2 ) must be false; and
in order for the conjunction to be false, at least one of its conjuncts (namely,
either S1 or S2 ) must be false. However, if S1 is false, the implication is going
to hold because, in order for the implication to fail, S1 on the left-hand side
must be true. On the other hand, if S2 is false, S1 cannot be true because

19
we’re assuming the truth of S1 |= S2 . In either case, there’s no interpretation
where the left-hand side is true but the right-hand side is false.
In a similar fashion, you can make sure that there’s no interpretation
where the left-hand sides of the items 2–4 are true but the right-hand sides
of the items are false. Therefore, S1 is equivalent to (S1 ∧ S2 ) and S2 is
equivalent to (S1 ∨ S2 ).
In this particular case, the truth-table method might be easier.

S1 S2 (S1 ∧ S2 ) (S1 ∨ S2 )
T T T T
T F F T
F T F T
F F F F

Note that the situation depicted in the line 2 never happens because
S1 |= S2 (there’s no interpretation where S1 is true but S2 is false). Thus,
we can safely ignore the line 2. Obviously, the turth-value assignments of S1
(resp. S2 ) match up with those of (S1 ∧ S2 ) (resp. (S1 ∨ S2 )). Therefore, S1
(resp. S2 ) is equivalent to (S1 ∧ S2 ) (resp. (S1 ∨ S2 )).
Let’s do one more example by constructing a truth table. This time
we’re gonna check whether (A → B) and (−A ∨ B) are logically equivalent
or not.

A B (A → B) (−A ∨ B) ((A → B) ↔ (−A ∨ B))

T T T T T
T F F F T
F T T T T
F F T T T

The truth-value assignments for ((A → B) ↔ (−A ∨ B)) are all

true; namely, ((A → B) ↔ (−A ∨ B)) is valid. This shows that (A → B)
and (−A ∨ B) are logically equivalent.

1.4.2.1 Problems
1. Prove:
1. −−α ≡ α (Remember: “≡” is read as “is equivalent to”.)
2. α ≡ −β if and only if −α ≡ β

20
 3. −(α ∧ β) ≡ (−α ∨ −β)
4. −(α ∨ β) ≡ (−α ∧ −β)
5. (α → β) ≡ (−α ∨ β)
6. (α → β) ≡ (−β → −α)
7. (α ↔ −β) ≡ (−α ↔ β)
(The above equivalences are all useful. I recommend you to memorize them.)

2. Determine whether or not the following equivalences are correct.

1. (A → (B → A)) ≡ ((C ∧ −C) ∨ (A → A))
2. (C ∧ (B ∨ A)) ≡ ((C ∧ B) ∨ A)
3. (−(D ∨ B) → (C → B)) ≡ (C → (D ∧ B))
4. (A → (B → (A → B))) ≡ (B → (A → (B → A)))
5. (F ∨ −(G ∨ −H)) ≡ ((H ↔ −F ) ∨ G)

1.5 Argument
An argument is comprised of two parts: a set of premises and one con-
clusion. An argument is called valid if there’s no interpretation where
a set of premises is true8 but the conclusion is false. If there’s such an
interpretation, an argument is called invalid and the interpretation is
called a counterexample.

We express an argument in the following form.

Premise 1
Premise 2
..
.
Premise n
Conclusion

As is easily seen, the definitions of (valid) arguments and implica-

tions are almost identical; so, we sometimes write an argument in the form
of {Premise 1, Premise 2, . . . , Premise n} |= Conclusion.
Let’s think of the following simple argument.
8
If you’re not sure when a set of sentences (which are premises of an argument) is going
to be true, see Section 1.3.1.

21
 (A → B)
A
B
You can show its validity (or invalidity) either by the truth-table
method or by the one explained above (let’s call this method the try-to-refute
method).

Truth-Table Method:
A B (A → B)
T T T
T F F
F T T
F F T
As you see, there’s no interpretation where B (your conclusion) is false but
both A and (A → B) (your premises) are true; therefore, this argument is
valid.

Try-to-Refute Method:
{(A → B ), A} |= B
F F F F
| {z }
T
| {z }
F
In order for the above argument to be invalid, B must be false; and in order
for (A → B) to be true with the truth value F of B, A must be false. However,
such a truth-value assignment makes the set of premises false (why?); and
consequently, the argument is going to be valid. In this way, we know that
there’s no way to assign T to the premises and F to the conclusion, which
means the argument is valid.9
Let’s do another example: {(A → B), B} |= A.

Truth-Table Method:
A B (A → B)
T T T
T F F
F T T ⇐
F F T
9
An argument with the form {(α → β), α} |= β is called modus ponens.

22
Try-to-Refute Method:

{(A → B ), B } |= A
F T T F
| {z }
T
| {z }
T

In both ways, we find the interpretation which assigns T to the

premises and F to the conclusion. Further, we know that it happens when A
is false and B is true; that truth-value assignment would be your counterex-
ample to the argument.
Here’s a more complicated example: {(A ↔ (−B ∨ C)), (C ↔
−A)} |= −A.

Truth-Table Method:
A B C −A −B (−B ∨ C) (A ↔ (−B ∨ C)) (C ↔ −A)
T T T F F T T F
T T F F F F F T
T F T F T T T F
T F F F T T T T ⇐
F T T T F T F T
F T F T F F T F
F F T T T T F F
F F F T T T F T

In the line 4, we find a counterexample (A: T, B: F, C: F) which makes all

the premises true but the conclusion false.

Try-to-Refute Method:

{(A ↔ ( −B ∨C )), (C ↔ −A )} |= −A
T F F F |{z} T
|{z} F |{z}
T | {z } F
| {z } T
T
| {z }
T

In order for the argument to be invalid, −A must be false; thus, A

must be true. On the other hand, all the premises must be true. In order
for the premises to be all true, both (A ↔ (B ∨ C)) and (C ↔ −A) must be

23
true. In order for (C ↔ −A) to be true, the truth value of C must match up
with that of −A; thus, C must be false. In order for (A ↔ (B ∨ C)) to be
true, the truth values of the both sides of ↔ must match up; and since the
one side of the bi-conditional, namely A, is true, (−B ∨ C) must be true as
well. Since C is false, in order for (−B ∨ C) to be true, −B must be true;
thus, B must be false. In this truth-value assignment (A: T, B: F, C: F),
we successfully assigned T to the premises and F to the conclusion, which
means the argument is invalid.

1.5.1 Problems
1. Prove:
1. {(α ∨ β), −α} |= β
2. {(α → β), −β} |= −α
3. {(α → γ), (β → γ), (α ∨ β)} |= γ
(The above forms of arguments are called disjunctive syllogism, modus tol-
lens, and constructive dillema respectively.)

2. Determine whether or not the following arguments are valid.

1. {(B ∨ (A ∧ −C)), ((C → A) ↔ B), (−B ∨ A)} |= −(A ∨ C)
2. {−(Y ↔ A), −Y, −A} |= (W ∧ −W )
3. {(B ∨ B), ((−B → (−D ∨ −C)) ∧ ((−D ∨ C) ∨ (B ∨ C)))} |= C
4. {(((J ∧ T ) ∧ Y ) ∨ (−J → −Y )), (J → T ), (T → Y )} |= (Y ↔ T )
5. {((A ∧ (B ∨ C)) ↔ (A ∨ B)), (B → −B)} |= (C ∨ A)

1.6 Some Words on Implication/Argument

Some students may find the following aspects troubling.
1. The difference between the validities of a sentence and of an argument.
2. The condition in which an implication (resp. argument) holds.
In this section, I like to arouse such students’ attention.

24
1.6.1 The Difference between the Validities of a Sen-
tence and of an Argument
Let’s replicate the definitions where the same word “valid” appears.

A sentence (or set of sentences) is called valid if and only if there’s no

interpretation where the sentence is going to be false; in other words, a
valid sentence is always true in all interpretation.

An argument is called valid if there’s no interpretation where a set of

premises is true but the conclusion is false.

Some students seem to confuse the definition of the validity of a

sentence with that of the validity of an argument and think that an argument
is going to be valid if and only if both the premises and the conclusion are
true in all interpretations. Surely, if its premises and conclusion are always
true, an argument is going to be valid; however, this is not the only case
where the argument is going to be valid. Let’s see when an argument is
going to be valid in the next section.

1.6.2 The Condition in Which an Implication and an

Argument Hold
First, let’s take a look again at the definitions of implication and argument.

α logically implies β if and only if there’s no interpretation where α is

true but β is false.

An argument is called valid if there’s no interpretation where a set of

premises is true but the conclusion is false.

Note that they don’t explicitly tell us when an implication or an

argument holds. However, they implicitly tell us when an implication or
an argument is going to be valid; as long as there’s no interpretation where
α (resp. a set of premises) is true but β (resp. the conclusion) is false,
an implication (resp. argument) holds. More explicitly, α implies β if the
configuration of the truth values for α and β take one of the following forms.

25
 T |= T, F |= T, F |= F

Likewise, an argument is going to be valid if the configuration of the truth

values for a set of premises and the conclusion take one of the following forms.

T F F
T T F

When you think about the situations where α implies β or the

situations where an argument is valid, please don’t forget the cases F |= T,
F |= F, TF , and FF .

1.7 Complete Disjunctive Normal Form

1.7.1 Truth-Functional Connectives
As we know perfectly well by now, there are four combinations of the truth
values for a pair of sentence letters α, β: (T, T), (T, F), (F, T), and (F, F).
Those combinations of the truth values give us different truth-value assign-
ments according to which connective we’re thinking of. For example, if we’re
thinking of ∧, the truth-value combination (T, F) gives us the truth value F;
and if we’re thinking of ∨, it gives us T.
From the above consideration, we notice that we can think of a
connective in terms of a mathematical function. A mathematical function
receive some inputs and returns an output. For example, the conjunction
∧ can be thought of as a function which receive two inputs and return an
output: f∧ (α, β). This function gives us T when we input T to both α and
β; in other cases, it gives us F.
Is there any mechanical (i.e. algorithmic) way to express an ar-
bitrary function in our language L1 ? In other words, if we’re given some
sentence letters and truth-value assignments to each combination of those
letters, can we find an L1 -sentence which meet those specifications? In sim-
ple cases, we may be able to find such a sentence by trial and error. For
example, for the following truth table, we can manage to figure out that it
can be expressed as (A ∨ −(A ∨ B)) (or in a simpler form, (B → A)).

26
 A B γ
T T T
T F T
F T F
F F T

But what if we’re given the following truth table and asked to con-
struct an L1 -sentence which has the truth-value assignments given in the
table?

A B C δ
T T T T
T T F F
T F T F
T F F T
F T T F
F T F T
F F T F
F F F T

We’re at a loss.

1.7.2 Complete Disjunctive Normal Form

Luckily, we have a mechanical method for finding an L1 -sentence which meets
a given specification. In order to explain what that method is (and how it
works), let’s go back to the above example.
The sentence δ defined in the above truth table is going to be true
if all the sentence letters in it are true. Thus, this situation can be expressed
as (A ∧ B ∧ C) because this sentence is going to be true only when we assign
T to all A, B, C. From the line 4, we also notice that the sentence δ is going
to be true when (A ∧ −B ∧ −C) is true (why?). In this way, we know that
δ is going to be true if at least one of the following L1 -sentences is true:
(A ∧ B ∧ C), (A ∧ −B ∧ −C), (−A ∧ B ∧ −C), (−A ∧ −B ∧ −C). Thus, we can
express δ as ((A∧B ∧C)∨(A∧−B ∧−C)∨(−A∧B ∧−C)∨(−A∧−B ∧−C)).
This is exactly what is called a complete disjunctive normal form.

27
 A complete disjunctive normal form of a sentence is
1. a disjunction
2. whose disjuncts are conjunctions
3. whose conjuncts are comprised of all the sentence letters (possibly
with the denial) of the target sentence
4. each of which appears once and only once in each conjunction.

Let’s compare what we’ve got in the above with this definition.
((A∧B∧C)∨(A∧−B∧−C)∨(−A∧B∧−C)∨(−A∧−B∧−C)) is obviously a
disjunction; also, its disjuncts are all conjunctions; and these conjunctions are
comprised of the sentence letters and/or their denials of the target sentence
δ; therefore, ((A∧B ∧C)∨(A∧−B ∧−C)∨(−A∧B ∧−C)∨(−A∧−B ∧−C))
has a complete disjunctive normal form.
In fact, given any sentence (except one special case. We’re gonna
look at such a special case below), we can transform it into a complete
disjunctive normal form in a mechanical way. Let’s take ((A ∧ B) ∨ −A) as
an example. First, you need to construct its truth table.

A B −A (A ∧ B) ((A ∧ B) ∨ −A)
T T F T T
T F F F F
F T T F T
F F T F T

And then, look at the interpretations where the sentence ((A ∧ B) ∨ −A) is
going to be true. In our case, the sentence is going to be true in the lines 1,
3, and 4. In the line 1, the sentence letters A, B take the truth value T; and
this situation can be expressed by (A ∧ B). Similarly, the situations depicted
in the lines 3–4, namely where the sentence letters A, B take the truth value
(F, T) and (F, F) respectively, can be expressed as (−A ∧ B) and (−A ∧ −B)
respectively ((−A ∧ B) is going to be true if and only if A is false and B is
true, and (−A ∧ −B) is going to be true if and only if both A and B are
false). Since ((A ∧ B) ∨ −A) is going to be true in one of those situations,
the sentence can be expressed as ((A ∧ B) ∨ (−A ∧ B) ∨ (−A ∧ −B)) which
is a complete disjunctive normal form.
To recap:

28
 If you’re asked to transform a sentence α into its complete disjunctive
normal form,
1. Construct a truth table for the target sentence α.
2. Find rows where the target sentence is true.
3. In each row where the target sentence is true, look at the truth-
value assignments for the sentence letters, and create a conjunction
based on those truth-value assignments as follows.
α. If the truth-value assignment for the sentence letter is true,
the sentence letter itself is one of your conjuncts.
β. If the truth-value assignment for the sentence letter is false,
the denial of the sentence letter is one of your conjuncts.
γ. Connect what you’ve got above with ∧ (and of course enclose
it with brackets).
4. Connect the conjunctions you’ve got above with ∨ (and don’t forget
brackets).

Now, let’s consider the following truth table for (A ∧ −A) and con-
struct a complete disjunctive normal form out of it.

A B (A ∧ −A)
T T F
T F F
F T F
F F F

As is easily seen, there’s no row where (A ∧ −A) is going to be

true; (A ∧ −A) is an unsatisfiable sentence. However, according to the above
instruction, we have to take a look at the rows where the target sentence
(in this case, (A ∧ −A)) is going to be true; obviously, there’s no row to
look at. In fact, there’s no complete disjunctive normal form corresponding
to any unsatisfiable sentence. What should we do? Well, if you’re asked to
construct a complete disjunctive normal form of an unsatisfiable sentence,
simply reply, “There’s no complete disjunctive normal form of it”.10
10
However, there are disjunctive normal forms of an unsatisfiable sentence. First, note
that we dropped the qualification “complete” here; your conjunctions (which will be part
of your disjunction) can have the same sentence letter more than once, and can lack

29
1.7.2.1 Problems
Find complete disjunctive normal forms for the following sentences.
1. (−(A → B) ∨ (−A ∧ C))
2. ((A ∨ B) ∧ (−B ∨ C))
3. ((A ∧ −B) ∨ (A ∧ C))
4. (−A ∨ (B → −C))
5. ((A ∨ B) ↔ −C)

1.8 Expressive Completeness

Now we know that any sentence can be expressed in a (complete) disjunctive
normal form. From this, we can conclude that the connectives −, ∧, ∨ would
suffice to express any sentences. We call such a set of connectives expressively
complete.

A set of connectives is called expressively complete if you can express any

sentence (i.e. any possible truth-value assignments) with the connectives
in the set.

From Problems 1.4.2.1, we know that ∧ can be defined in terms of

− and ∨. This means that − and ∨ are sufficient for expressing any sentence;
the set {−, ∨} is expressively complete.

Given an expressively complete set Γ of connectives; if you can express

each connective in Γ in terms of connectives in another set ∆ of connec-
tives, ∆ is also expressively complete.

Is {−, ∨} the smallest expressively complete set? There are actu-

ally two expressively complete sets each of which is comprised of just one
connective: | (the Sheffer stroke, or NAND) and ↓ (the Peirce arrow, or
NOR).
one or more sentence letters. For example, with a target sentence with three sentence
letter A, B, C, all the following are legitimate candidates for conjunctions for a disjunctive
normal form: (A ∧ A), (B ∧ −C), (A, B, C). Now, let’s go back to our main business;
find a disjunctive normal form of an unsatisfiable sentence. Let’s cut to the chase; the
target sentence (A ∧ −A) itself would do the job. “Wait. This is a conjunction, not a
disjunction. Why is this considered as a disjunctive normal form?”, you may ask. Answer:
it’s a disjunction of (A ∧ −A) and the empty sentence.

30
 α β (α | β) α β (α ↓ β)
T T F T T F
T F T T F F
F T T F T F
F F T F F T

Let’s focus on the Peirce arrow. As you may notice, the truth-value
assignments for (α ↓ β) are exactly the opposite of those of (α ∨ β) (that’s
why it’s sometimes called “NOR”!).11 With this, we know that (α ∨ β) can
be expressed as −(α ↓ β). Thus, if we figure out how to express “−” (denial)
with the Peirce arrow alone, we can express “∨” with the arrow alone as well.
So let’s figure it out.
From the above truth table, we know that (α ↓ β) is going to be
true if α and β are both false and it’s gonna be false if α and β are both true.
Now let’s replace β in the above table with α and see what’s gonna happen.

α (α ↓ α)
T F
F T

(α ↓ α) is going to be false if α is true, true if α is false. This is exactly what

we want for the denial. Thus, we can define −α as (α ↓ α).
Since we now know how to express “−” with the Peirce arrow alone,
we also know how to express “∨” with the arrow alone; (α ↓ β) being defined
as −(α ∨ β), its denial should give you (α ∨ β).

α β ((α ↓ β)|(α ↓ β)) (≡ (α ∨ β))

T T T
T T F
F T F
F F F

And we now know how to express “∧” with {−, ∨} (recall that
(α ∧ β) ≡ −(−α ∨ −β) and (α ∨ β) ≡ −(α ↓ β)), we also know how to
express “∧” with the Peirce arrow alone.
11
And the truth-value assignments for the Sheffer stroke | are exactly the opposite of
those of ∧; that’s why it’s called “NAND”.

31
 In a similar fashion, you can show that the Sheffer arrow | is ex-
pressively complete.
Now let f be a zero-place connective (that is, a connective which
connects nothing). You can think of this as a shorthand for (A ∧ −A) (or any
other unsatisfiable sentences). Then, the set {f, →} is expressively complete
(that is, you can express any sentences in which other connectives −, ∧, ∨, ↔
might appear). Let’s show this.
In order to show that {f, →} is expressively complete, we have to
show that some other expressively complete set can be expressed in terms of
{f, →}. Let’s take {−, ∧} as an expressively complete set. Our first task is
to express − only with {f, →}.
Now take a look at the following truth table for →.

α β (α → β)
T T T
T F F
F T T
F F T

We notice that, when the consequent (β) is false, the true antecedent gives
us false, the false antecedent true; namely, when the consequent is false,
(α → β) gives us the truth value for the denial of the antecedent. So, with
f and →, we can express − as follows.

α (α → f ) (≡ −α)
T F
F T

Next, we have to express ∧ with {f, →}. Note that (α → β) can be

expressed as (sometimes even defined by) (−α ∨ β) and (α ∧ β) can be ex-
pressed as −(−α ∨ −β) (de Morgan’s law). Therefore, α ∧ β can be expressed
as ((α → (β → f )) → f ). Since we’ve just shown how to express {−, ∧} in
terms of {f, →}, we’ve also shown that {f, →} is expressively complete.

1.8.1 Problems
1. Express ∨, →, ↓ in terms of |.
2. Express −, ∧, ∨, →, | in terms of ↓.
3. Express ∨, →, |, ↓ in terms of {−, ∧}.

32
 4. Express ∧, →, |, ↓ in terms of {−, ∨}.
5. Express ∧, ∨, |, ↓ in terms of {−, →}.

1.9 Truth-Tree Method for L1

To figure out the satisfiability/unsatisfiability/validity/invalidity of a sen-
tence, the validity of an argument, or the truth of a logical implication (resp.
a logical equivalence), the truth-table method comes in handy. However, as
the number of sentence letters in a sentence increases, constructing a truth
table becomes a substantial task. It would be nice if there’s a handier way to
figure out the above properties of a sentence or an argument. The truth-tree
method provides such a handier way.
To construct a truth tree is, basically, to decompose sentences into
literals. (Remember: literals refer to sentence letters and their denials. See
1.1.2.) In constructing it, your tree grows, maybe branching into paths, and
eventually stops growing when every sentences in a set are decomposed into
literals.
By decomposing sentences into literals, it enables us to easily find
whether a set of sentences is satisfiable (consistent) or unsatisfiable (inconsis-
tent). If you find at least one contradiction (a contradictory pair of sentences
like A and −A; namely, a pair of a sentence letter and its own denial) in each
path of your tree, your set of sentences is unsatisfiable. On the other hand,
after finish constructing your tree, if there’s at least one path immune from
contradiction, your set of sentences is satisfiable. The truth-tree method tells
us how to decompose a sentence into its components for that purpose.

1.9.1 10 Rules of the Truth-Tree Method

There are 10 rules you need to memorize. Each rule is comprised of two
parts: the premise and the conclusions.

2 Rules for Denial

1. α
−α
× 2. X − −α
α

2 Rules for Conjunction

33
 3. X (α ∧ β) 4. X − (α ∧ β)
α
β −α −β

2 Rules for Disjunction

5. X (α ∨ β) 6. X − (α ∨ β)
−α
α β −β

2 Rules for Conditional

7. X (α → β) 8. X − (α → β)
α
−α β −β

2 Rules for Bi-Conditional

9. X (α ↔ β) 10. X − (α ↔ β)

α −α α −α
β −β −β β

Memorizing these 10 rules may not sound quite lovely; however, if

you have a good understanding of the truth conditions of the logical connec-
tives (−, ∧, ∨, →, ↔), memorizing them is not so hard.
Let’s take the rules for ∧ as an example. The result of decomposing
(α ∧ β) is, according to Rule 3, vertically-aligned α and β (in this case, the
premise of the rule is (α ∧ β), and the conclusions are α and β); and when
two sentences are vertically aligned, it means that, if there’s an interpretation
which assigns T to those two sentence, that interpretation also assigns T to a
sentence from which the two sentences come. Thus, in the case of vertically-
aligned α and β, it means that, if there’s an interpretation which assigns T
to α and β, that interpretation also assigns T to (α ∧ β); this is nothing
but the truth condition of (α ∧ β). On the other hand, Rule 5 tells us that
we have two branches after decomposing (α ∨ β); and this means that, if
there’s an interpretation which assigns T to either α or β (maybe both), that
interpretation also assigns T to (α ∨ β); again, this is nothing but the truth
condition of (α ∨ β).

34
 In the above, we described the relation between a rule and the
truth condition of its premise with starting from the truth of conclusions
(the existence of an interpretation which makes both, or at least one, of
conclusions). We can of course describe the relation the other way around;
namely, from the assumption of the truth of the premise, we can conclude
the truth of conclusions. When this relation is seen from the first point of
view (from the truth of the conclusions to that of the premise), it’s called
the completeness of the rules; on the other hand, when the relation is seen
from the second point of view (from the truth of the premise to that of the
conclusions), it’s called the soundness of the rules.

1.9.1.1 Problem
Convince yourself that the rules are closely connected to the truth conditions
of the logical connectives; namely, verify that each rule is sound and complete.

In doing the above problem, you may have noticed that two of the
rules don’t seem to be connected to the truth conditions of the connectives in
a straightforward way: those for the denial. (Still, there are some connections
between the rules and the truth condition of the denial of course).
The plain version of the rule for the denial (Rule 1) tells you that
you can close a path if you find a contradictory pair of sentences. (The
meaning of “closing a path” will become clear eventually.) Its negated ver-
sion (Rule 2) tells you that you can take the double negation (−−) away.

Now it’s time to see how these rules work.

1.9.2 Testing the Satisfiability of sentences

To test the satisfiability of a set of sentences, start constructing a tree
with the sentences themselves. If all paths of the tree are closed, the
set is unsatisfiable; if there’s at least one open path in the finished tree
(namely, the tree which stops growing), the set is satisfiable; and such
an open path tells you an interpretation which makes the set true.

Let’s start with a simple example: {(A ∧ −B), C, (−A ∨ −B)}.

You start constructing your tree by listing your sentences up verti-
cally. We call this list of sentences an initial list.

35
 1. (A ∧ −B)
2. C
3. (−A ∨ −B)

And then, apply one of the rules to one of the sentences. Here, we have two
options: apply the rule 3 to the line 1, or apply the rule 5 to the line 3. In
general, if you can apply a non-branching rule (like the rules 3, 6, 8), apply
it.

Rule of Thumb 1: Apply a non-branching rule when you can.

Let’s apply the non-branching rule 3 to the line 1. (In the below I wrote down
which rule is applied to which line. This is purely for pedagogical purpose.
You don’t have to do it in the exam or in the assignments.)

1. X (A ∧ −B)
2. C
3. (−A ∨ −C)
4. A Rule 3 to Line 1
5. −B Rule 3 to Line 1

After applying a rule to a sentence, you should put a check mark to the
left or right of the sentence in order to avoid applying a rule again to it.

Then, there’s only one option left: apply the rule 5 to the line 3.

1. X (A ∧ −B)
2. C
3. X (−A ∨ −C)
4. A Rule 3 to Line 1
5. −B Rule 3 to Line 1

6. −A −C Rule 5 to Line 3

At this point, we have two paths; one with sentences (A∧−B), C, (−A∨
−C), A, −B, −A, the other with (A ∧ −B), C, (−A ∨ −C), A, −B, −C.

36
 All sentences except literals are check-marked; there’s no sentence
left to which our rules can be apply. We finish drawing the tree. The next
task is to find a contradiction (a sentence and its own denial) in the paths.
In this example, it’s obvious; we can easily find two contradictions: A in the
line 4 and −A in the line 6, and C in the line 2 and −C in the line 6. And
the following is what to do if you come across such a path.

If you find a contradiction, you put × under the path where you find it.
When you do this, we say that you close the path. And if all the paths
are closed, we say that the tree is closed.

1. X (A ∧ −B)
2. C
3. X (−A ∨ −C)
4. A Rule 3 to Line 1
5. −B Rule 3 to Line 1

6. −A −C Rule 5 to Line 3
× ×
4,6 2,6

(In the above I wrote down which line and which line are contradictory.
Again, this is just for pedagogical purpose. You don’t have to do it in the
exam or in the assignments.)
All the paths in the above tree are closed. What does this mean?
Well, let’s look at the left path and make a list from the sentences in the
path: {(A ∧ −B), C, (−A ∨ −C), A, −B, −A}. Recall that the results of the
decomposition are the truth conditions for sentences in our initial list. If
there are some contradictory sentences (A and −A in this case), some of
the truth conditions for sentences are conflicting; in other words, there’s no
interpretation which assigns T to all the sentences in the list at the same
time. And if there are conflicting truth conditions in all the paths, there’s
no way to assign T to the sentences in the initial list at the same time; in
short, a set of the sentences in the initial list is unsatisfiable.

Let’s do another example: the satisfiability check for {(A → B), (B →

A), −A}. As before, we start drawing our tree by listing up the sentences
vertically.

37
 1. (A → B)
2. (B → A)
3. −A

This time, unfortunately, there’s no non-branching rule we can ap-

ply. Thus, it seems it doesn’t matter which rule we apply first. However, if
we apply the rule 7 to the line 2, we immediately come across a contradiction;
and we can close the path.

Rule of Thumb 2: Apply the rule which leads to a contradiction.

1. (A → B)
2. X (B → A)
3. −A

4. −B A Rule 7 to Line 2
×
3,4

There’s one more sentence to decompose in the tree.

1. X (A → B)
2. X (B → A)
3. −A

4. −B A Rule 7 to Line 2
×
3,4
5. −A B Rule 7 to Line 1
×
4,5

We decomposed all the sentences except literals; we finish construct-

ing the tree. We call this tree finished, and because the left-most path remains
open, we also call the tree open. And if there’s at least one open path in
your finished tree, the set of sentences in the initial list is satisfiable.12
12
In order to know whether or not the set of sentences in the initial list of a tree is
satisfiable, you don’t necessarily have to finish your entire tree. We’ll be back to this point
later.

38
1.9.2.1 Problem
Explain why the existence of at least one open path means the satisfiability
of the set of sentences in the initial list.

Now we know that the set of sentences (A → B), (B → A), −A

is satisfiable; and we want to know under what truth-value assignments it’s
going to be true. To figure this out, we need to go back the path to its root,
and assign T to each sentence letter which appear as a line itself. From −A
to (A → B), we find no sentence letter which appears as a line itself; in
this case, we’re gonna assign F to A, B (which still appear as a part of other
compound sentences).

Yet another example: {(A → (B ↔ C)), −(C → A)}. Since the

rules for −(C → A) is non-branching, so we apply the rule 8 first.

1. X (A → (B ↔ C))
2. X − (C → A)
3. C Rule 8 to Line 2
4. −A Rule 8 to Line 2

5. −A (B ↔ C) Rule 7 to Line 1

At this point, we notice that there’s nothing to do for the left path
because we decomposed all the compound sentences which are in the “root”
positions as to the left path. It remains open no matter what happens on the
right path. We call such an path (in which there’s no contradiction and no
compound sentence left) a finished open path. (Note that (B ↔ C) belongs
to the different path; we can’t decompose it under −A on the left path.)
Thus, we can stop here (unless you’re required to find all the open paths).

Rule of Thumb 3: You can stop decomposing the tree once you find
an open path (unless you’re required to find all the open paths).

As in the previous example, we assign T to sentence letters which

appear as a line itself on the open path (in this case, C) and assign F to those
which don’t appear as a line itself but as a component of other sentences (in

39
this case, A and B); thus, on this open path, we have truth-value assignments
A : F, B : F, C : T which make all the sentences in the initial list true.
According to Rule of Thumb 3 above, we can stop decomposing the
tree here because we already know the set of sentences is satisfiable. Even
so, let’s keep decomposing (yet again, for pedagogical purpose).

1. X (A → (B ↔ C))
2. X − (C → A)
3. C Rule 8 to Line 2
4. −A Rule 8 to Line 2

5. −A (B ↔ C) Rule 7 to Line 1

6. B −B
7. C −C
×
3,7

It turns out that the tree has one more open path and it tells us
that the set is going to be true when A is false, B is true, and C is true.

Last example: {(A → (B ∧ C)), (−(A → B) ∧ −(A → C))}.

1. X (A → (B ∧ C))
2. (−(A → B) ∨ −(A → C))

3. −A (B ∧ C) Rule 7 to Line 1

Here, we have two options: decompose (−(A → B) ∨ −(A → C))

which is at the root position to both branches, or decompose (B ∧ C) which
is in a branch. Which one should we decompose first? The following is a rule
of thumb.

Rule of Thumb 4:
1. If a sentence in a branch is decomposed by a non-branching rule,
decompose it first.

40
 2. If a sentence in a branch is decomposed by a branching rule, de-
compose a sentence at the root position.

In this case, the sentence in the right branch is decomposed by a

non-branching rule; so decompose it first.

1. X (A → (B ∧ C))
2. (−(A → B) ∨ −(A → C))

3. −A X (B ∧ C) Rule 7 to Line 1
4. B Rule 3 to Line 3
5. C Rule 3 to Line 3

Now the only decomposable sentence is (−(A → B) ∨ −(A → C)).

Since it is at the root position of two branches, make sure that you decompose
it in both branches.

1. X (A → (B ∧ C))
2. X (−(A → B) ∨ −(A → C))

3. −A X (B ∧ C) Rule 7 to Line 1

4. X − (A → B) −(A → C) Rule 5 to Line 2

5. B Rule 3 to Line 3
6. C Rule 3 to Line 3
7.
8. −(A → B) −(A → C) Rule 5 to Line 2
9. A A A A Rule 8 to Lines 4, 8
10. −B −C −B −C Rule 8 to Lines 4, 8
× × × ×

All paths are closed; thus, the set of the sentences are unsatisfiable.

1.9.3 Testing the Validity of a Sentence

41
 To test the validity of a sentence, test the satisfiability of the denial of
the sentence. If the tree is closed, the sentence is valid; if not, it’s not.
In the latter case, an open path gives you an interpretation in which the
sentence is going to be false.

Example: Check the validity of ((C → R) → (−R → −(C ∧ J))).

According to the above instruction, we should start our tree with
the denial of the sentence.

1. X − ((C → R) → (−R → −(C ∧ J)))

2. X (C → R) Rule 8 to Line 1
3. X − (−R → −(C ∧ J)) Rule 8 to Line 1
4. −R Rule 8 to Line 3
5. X − −(C ∧ J) Rule 8 to Line 3
6. X (C ∧ J) Rule 2 to Line 6
7. C Rule 3 to Line 6
8. J Rule 3 to Line 6

9. −C R Rule 7 to Line 2
× ×
7,9 4,9

All the paths are closed; ((C → R) → (−R → −(C ∧ J))) is valid.

Now, let’s think about why you need to start with the denial of your
sentence whose validity you’re gonna check. First, recall the case of satisfia-
bility. In checking the satisfiability of sentence(s), you start with sentence(s)
itself (themselves). If your tree has at least one finished open path, your
sentence is satisfiable; if not, it’s not (namely, unsatisfiable). And if a tree
for the denial of a sentence is closed, the denial of a sentence is unsatisfiable;
and because the denial of any valid sentence is unsatisfiable, a sentence itself
has to be valid. On the other hand, if a tree for the denial of a sentence has
at least one finished open path, the denial of a sentence is satisfiable; namely,
there’s at least one interpretation which assigns F to a sentence. In such a
case, a sentence cannot be valid of course.

One more example: Check the validity of ((L ∨ (J ∨ −K)) ∧ (K ∧

((J ∨ L) → −K))).

42
1. X − ((L ∨ (J ∨ −K)) ∧ (K ∧ ((J ∨ L) → −K)))

2. X − (L ∨ (J ∨ −K)) −(K ∧ ((J ∨ L) → −K)) Rule 4 to Line 1

3. −L Rule 6 to Line 2
4. X − (J ∨ −K) Rule 6 to Line 2
5. −J Rule 6 to Line 4
6. X − −K Rule 6 to Line 4
7. K Rule 2 to Line 6

At this point, we notice that there’s nothing to do for the left path
because we decomposed all the sentences which are in the “root” positions
as to the left path. The left path remains open no matter what happens to
the rest. ((L ∨ (J ∨ −K)) ∧ (K ∧ ((J ∨ L) → −K))) is going to be false when
J is false, K is true, and L is false because the only sentence letter which
appears as a line itself on this open path is K.

1.9.3.1 Problems
Do Problems 1.3.6 by the truth-tree method.

1.9.4 Testing the Validity of an Argument

To test the validity of an argument, test the satisfiability of the premises
and the denial of the conclusion. If the tree is closed, the argument
is valid; if not, it’s not. In the latter case, an open path gives you a
counterexample to the argument.

Example: Check the validity of the argument {((−B ∨ −H) →

M ), (K ∧ −M )} |= B.

43
 1. X ((−B ∨ −H) → M )
2. X (K ∧ −M )
3. −B
4. K Rule 3 to Line 2
5. −M Rule 3 to Line 2

6. X − (−B ∨ −H) M Rule 7 to Line 2

7. −−B × Rule 6 to Line 6
8. −−H 5,6 Rule 6 to Line 6
×
3,7

It’s closed; the argument is valid.

Let’s think about why this works (especially why your initial list
should have the denial of the conclusion of the argument) as its member.
First, suppose your argument is {P1 , . . . , Pn } |= C; in this case, your tree
starts with the initial list {P1 , . . . , Pn , −C}. If all the paths in your tree
are closed, the initial list {P1 , . . . , Pn , −C} is unsatisfiable; in other words,
there’s no interpretation which assigns T to all the sentences in the list. Be-
cause the impossibility of assigning T to the denial of a sentence is the same
as the impossibility of assigning F to a sentence itself, the above conclusion
amounts to saying that there’s no interpretation which assigns T to all the
premises and F to the conclusion; this is exactly what an argument needs in
order to be valid.

Another example: Check the validity of {(−W ∧−L), ((J → −W ) ↔

−L), H} |= (J ∧ H)

44
 1. X (−W ∧ −L)
2. X ((J → −W ) ↔ −L)
3. H
4. X − (J ∧ H)
5. −W Rule 3 to Line 1
6. −L Rule 3 to Line 1

7. X (J → −W ) −(J → −W ) Rule 9 to Line 2

8. −L −−L Rule 9 to Line 2
×
5,7
9. −J −H Rule 4 to Line 4
×
3,9
10. −J −W

We have two open paths according to both of which the arguments

is invalid when H is true and J, L, W are false; and we say these truth-value
assignments (H: T, J.L.K: F) is (or provides) a counter-example to the
argument.
This works because the satisfiability of the sentences in the list
means there’s at least one interpretation which assigns T to the premises
and F to the conclusion; this is exactly what we need for confirming the
argument is invalid.

1.9.4.1 Problems
Do Problems 1.5.1 (2) by the truth-tree method.

1.9.5 Testing the Implication

Recall that an implication α |= β holds if and only if α → β is valid (see
Section 1.4.1). Thus, checking the truth of the implication α |= β amounts
to that of the validity of α → β.

To test the truth of an implication α |= β, test the validity of α → β.

If the tree is closed, the implication holds; if not, it’s not. In the latter
case, an open path gives us an instance where the implication fails.

45
 Example: Check the truth of the implication {(−J ∨ S), (S →
E)} |= (J → E). (Remember: the truth of a set of sentences amounts
to that of the conjunction of the sentences.)

1. X − (((−J ∨ S) ∧ (S → E)) → (J → E))

2. X ((−J ∨ S) ∧ (S → E)) Rule 8 to Line 1
3. X − (J → E) Rule 8 to Line 1
4. X (−J ∨ S) Rule 3 to Line 2
5. X (S → E) Rule 3 to Line 2
6. J Rule 8 to Line 3
7. −E Rule 8 to Line 3

8. −J S Rule 5 to Line 4
×
6,8
9. −S E Rule 7 to Line 5
× ×
8,9 7,9

The tree is close; the implication {(−J ∨ S), (S → E)} |= (J → E)

actually holds.
Another example: {(B ∧ K), (N → −K), (K ∨ −K)} |= (B → N )
(This time I start the tree by vertically aligning the sentences of the left side
and the denial of the sentence of the right side. You might not want to adopt
this way in the exam unless you can justify this based on the definitions of
implication and argument.)

46
 1. X (B ∧ K)
2. X (N → −K)
3. X (K ∨ −K)
4. X − (B → N )
5. B Rule 3 to Line 1
6. K Rule 3 to Line 1
7. B Rule 8 to Line 4
8. −N Rule 8 to Line 4

9. −N −K Rule 7 to Line 2
×
6,9
10. K −K Rule 5 to Line 3
×
6,10

We have an open path according to which the implication fails when

B, K are true and N is false.

1.9.5.1 Problems
Do Problems 1.4.1.1 (2) by the truth-tree method.

1.9.6 Testing the Equivalence

Recall that an equivalence α ≡ β holds if and only if α ↔ β is valid (see
Section 1.4.2). Thus, checking the truth of the equivalence α ≡ β amounts
to that of the validity of α ↔ β.

To test the truth of an equivalence α ≡ β, test the validity of α ↔ β.

If the tree is closed, the equivalence holds; if not, it’s not. In the latter
case, an open path gives us an instance where the equivalence fails.

Example: Check the truth of ((W ∧ Y ) → H) ≡ (W → (Y → H)).

47
1. X − (((W ∧ Y ) → H) ↔ (W → (Y → H)))

2. X ((W ∧ Y ) → H) X − ((W ∧ Y ) → H) Rule 10 to Line 1

3. X − (W → (Y → H)) X (W → (Y → H)) Rule 10 to Line 1
4. W Rule 8 to Line 3
5. X − (Y → H) Rule 8 to Line 3
6. Y Rule 8 to Line 5
7. −H Rule 8 to Line 5

8. X − (W ∧ Y ) H Rule 7 to Line 2
×
9. −W −Y Rule 6 to Line 8
10. × × X (W ∧ Y ) Rule 8 to Line 2
11. −H Rule 8 to Line 2
12. W Rule 3 to Line 10
13. Y Rule 3 to Line 10

14. −W X (Y → H) Rule 7 to Line 3

15. ×
16. −Y H Rule 7 to Line 14
17. × ×

All paths are closed; the implication holds.

Another (and last) example: {(E ∨ H) ≡ ((H ∨ J) ∨ E)}. This time
I omit the justifications and other annotations.

48
 X − ((E ∨ H) ↔ ((H ∨ J) ∨ E))

X (E ∨ H) X − (E ∨ H)
X − ((H ∨ J) ∨ E) X ((H ∨ J) ∨ E)
X − (H ∨ J) −E
−E −H
−H
−J X (H ∨ J) E
×
E H H J
× × ×

One path remains open; the equivalence doesn’t hold when E, H

are false, and J is true.

1.9.6.1 Problems
Do Problems 1.4.2.1 (2) by the truth-tree method.

49
Chapter 2

Language L2

We’ve studied the language L1 which has as its vocabulary some logical
connectives (−, ∧, ∨, →, ↔), sentence letters (the upper case alphabets
with or without subscripts), and some auxiliary symbols (brackets ( and
), sentence variables α, β, γ . . . (the lower Greek letters) with or without
subscripts). Although it’s powerful enough to capture (or formalize) a variety
of situations, it’s quite powerless to formalize an argument like the following.

All humans are mortal.

Socrates is a human.
Socrates is mortal.

Of course, we can still formalize the above argument in L1 by in-

troducing some sentence letters each of which refers to each statement in
the argument (e.g. H means all humans are mortal, S means Socrates is a
human, etc.). However, in order to judge whether an argument is valid or
not, we have to capture the internal structures of sentences of the argument
in our formal language and relate these structures to show the validity of an
argument. If we simply formalized the above argument with sentence letters,
there would be no way to make connection between them.
Then, the questions is this: How to capture the internal structures
of sentences? First, you immediately notice that these sentences above share
some vocabulary: human, mortal, and Socrates. Thus, if we have some ways
to express these in our formal language, we’d be able to express the relation
between sentences. Second, more importantly, there’s an occurrence of a
determiner “all” in the first premise. The first premise is not talking about

50
this or that human; it’s talking about humans in general. Thus, if we have
some way to express this kind of generality in our formal language, we’d be
able to express a general situation, not this or that situation. In order to
implement these in our formal language, we’re gonna introduce the following
new vocabulary: names, predicates, variables, and quantifiers.

2.1 Syntax of L2
2.1.1 The Vocabulary of L2
Our new language L2 is an extension of our familiar language L1 . In L2 ,
we have all we have in L1 . We’re just gonna add a small number of new
vocabulary to L1 . However, this addition will make a huge difference.

Logical Symbols

Brackets: (, ).

Connectives: −, ∧, ∨, →, ↔.

Quantifiers: ∀ (universal quantifier), ∃ (existential quantifier).

Variable: x with or without subscripts.

Non-Logical Symbols

Sentence Letters: A, B, C, . . . with or without subscript. E.g.,

A1 , B2 , Z1028 .

Names: a, b, c, . . . , w with or without subscripts.

Predicate Letters: A, B, C, . . . with or without super- and sub-

scripts.

Auxiliary Symbols

Sentence variables α, β, γ, . . . (the lower Greek letters) with or

without subscript.

Let’s take a look at the new elements one by one.

51
2.1.1.1 Names
A Name is used for referring to an object, it must refer to one and only
one object; but different names may refer to the same object.

In real life, one name can refer to many different objects; the name
“David” can refer to millions of Davids. In this sense, the reference of a name
in real life is vague. In order to avoid this kind of vagueness, we stipulate
that in L2 a name must refer to one and only one object; a cannot refer
to the natural number 1 and Socrates at the same time. Moreover, a name
must refer to something; an empty name (a name without reference) is not
allowed. On the other hand, different names can refer to the same object.
Different names a and b may refer to the same object, say, Socrates. (You
may have a nickname besides your real name.)

2.1.1.2 Predicates
A predicate is used for expressing a property of an object or a relation be-
tween objects. An n-place predicate followed by n names (not variables!)
forms a sentence.
Sometimes a predicate has a superscript, like H 1 or L2 , for
making clear how many names are required to form a sentence. Thus, for
example, L2 ab counts as a legitimate L2 -sentence whereas L2 a doesn’t.

Let s be a name for Socrates, H 1 be a predicate expressing a prop-

erty of being a human. Thus, Hs means “Socrates is a human”. If a predicate
is followed by one name or variable, it’s called a one-place predicate.
We can think of n-place predicates in general for some natural num-
ber n. For example, a two-place predicate L2 may mean, with names a and
b, “a loves b” (strictly speaking, the names a and b in “a loves b” should
be written as “an object referred to by a” and “an object referred to by b”
respectively, but I take the liberty of using this kind of omissions), and a
three-place predicate B 3 may mean, with names a, b, c, “a is between b and
c”.
What if we take 0 for n? In this case, in order for a 0-place predicate
to be a sentence, 0 names must follow the predicate letter. What does this
mean? Yes, a 0-place predicate itself is a sentence; in other words, a 0-place

52
predicate is nothing but a sentence letter.

n-place predicates followed by n names are called atomic sentences.

Together with their denials, they are called literals. E.g. A, −B, F a, −Lbc
are all literals.

2.1.1.3 Quantifiers
Here comes our main dish in this section: the quantifiers ∀ and ∃.
Conceptually, these are not hard to understand; ∀ means “’all’, ∃
means “some”. That’s it. However, some words of caution are in order,
especially for ∃. Let’s take a look at these with some examples.
First, a general remark on both quantifiers; the quantifiers are al-
ways used with variables, and in general, followed by predicates with those
variables. For example, with some predicate H 1 , we write ∀xH 1 x or ∃xH 1 x.
Now, let H 1 in the above be a predicate which means “. . . is a
human”; then, ∀xHx means “all are humans”, ∃xHx means “some are hu-
mans”.
Here, in our language L2 , “some” doesn’t necessarily means/refers
to plural objects; it can just refer to one object. However, as in the case of
names, it has to refer to at least one object. Thus, the stricter translation of
∃x . . . x . . . would be “there is at least one object which is . . . ”.

To recap:

∀x . . . x . . .: All objects are . . . .

∃x . . . x . . .: There is at least object which is . . . .1

Lastly, considering that “all are . . . ” can be paraphrased as “there’s

nothing which is not . . . ”, and “some are . . . ” as “not all are not . . . ”, we
have the following equivalences.

∀x can be written as −∃x−.

∃x can be written as −∀x−.
1
Of course, there are more than one way to express (or translate) ∀ and ∃ in our
ordinary language (in this case, in English). We’ll take a look at a few more ways to
express or translate ∀ and ∃ in English in Section 2.2.

53
2.1.2 The Formation Rules of L2 -Sentences
As was mentioned earlier, the language L2 is an extension of the language
L1 . Thus, all we have to do here is to add a few rules to the formation rules
of L1 .

1. Every sentence letter is a sentence of L2 .2

2. If P n is an n-place predicate, and a1 , . . . , an are names, then

P n a1 . . . an is a sentence of L2 .

3. If α and β are sentences of L2 , so are −α, (α ∧ β), (α ∨ β), (α →

β), (α ↔ β). Sentences of these forms are called compound sen-
tences.

4. If S is an L2 -sentence with a name n in it, and a variable x doesn’t

appear in it, the result of replacing n with x and prefixing ∃x or
∀x is a sentence of L2 .

5. Nothing else is a sentence of L2 .

In forming quantified sentences (namely, sentences with the quan-

tifier(s)), a special care must be taken in some cases. In the cases of simple
sentences like F a or Lab, the formation of the quantified sentences from them
would cause no trouble; just replace a name with a variable and put one of
the quantifiers in front of it. For example, by replacing a in F a (or in Lab)
with x and putting ∀x in front of it, we get ∀xF x (or ∀xLxb). However,
if we want to make a quantified sentence from a compound sentence like
(F a → Lab), there are several options as follows.

1. ∀x(F x → Lab)
2. ∀x(F x → Lxb)
3. (∃xF x → Lab)
4. (∃xF x → ∃xLxb)34

2
Note that sentence letters can be thought of as 0-place predicates. Thus, we can do
without sentence letters at all. However, as a convention, we keep using the term “sentence
letter(s)”.
3
This list is not meant to be exhaustive; there are lot more options.
4
The formation processes of the sentences are as follows. In the sentence 1, by replacing

54
 In all the cases above, the variable x is said to be bound (or gov-
erned ) by the quantifiers ∀x or ∃x. And it’s said that the scope of the
quantifier ∀x in the sentences 1 and 2 is the whole sentence (F x → Lab) or
(F x → Lxb) whereas the scope of ∃x in the sentence 3 is just F x. Thus, it’s
okay to use the same variable x in the sentence 4 because the scopes of the
two existential quantifiers don’t overlap. (The first ∃x just binds F x whereas
the second binds Lxb.)
What if we omit the second ∃x in the sentence 4? In that case, x
in Lxb stops being bound (remember, the first ∃x just binds F x), and said
to be free. And then, (∃xF x → Lxb) stops being a sentence.

2.1.2.1 Examples of L2 -Sentences

F 1 a, L2 ab, −F a, (F a∧Lab), ∃xF x (from F a), ∃xF x∧Lab, ∀Lax (from Lab),
∀xLxx (from ∀xLax), ∃xLxx (from Laa), ∃xLxa (from Laa), ∃x(F x ∧ Lxb).

2.1.2.2 Examples of Non-Sentences

F 1 ab (F 1 is a one-place predicate so it has to be followed by one names),
L2 a (L2 is a two-place predicate so it has to be followed by two names), F 1 x
(in terms of the number of names following the predicate letter, there’s no
problem; however, the variable x is not bound hence this is not a sentence),
(∃xF x ∧ Lxb) (x in Lxb is not bound hence (∃xF x ∧ Lxb) is not a sentence).

2.2 Translation from/into L2-Sentences

Before moving on to the semantics (i.e. interpretations) of L2 -sentences, let’s
see how L2 -sentences are translated into English and how English sentences
are translated into L2 -sentences.
Let’s start with simple examples: sentences with a quantifier and a
predicate.
a in F a with x and putting ∀x in front of the whole sentence, we get the quantified sentence.
On the other hand, in the sentence 2, by replacing both a’s in F a and Lab with x and
putting ∀x in front of the whole sentence, we get the quantified sentence as well. In the
sentence 3, by replacing a in F a with x and putting ∃x in front of F x, we get the quantified
sentence (and this is not equivalent to ∃x(F x → Lab)!). Finally, by replacing a in both F a
and Lab and putting ∃x in front of each atomic sentences, we get the quantified sentence.

55
2.2.1 Translating L2 -sentences with one predicate
As was mentioned in footnote 1, the same quantified sentence can be trans-
lated into various English sentences. For example, with a one-place predicate
N which means “. . . is a number”, ∀xN x can be translated as

• All are numbers.

• Everything is a number.
• Anything whatsoever is a number.

Similarly, ∃xN x can be translated as

• There is at least one number.

• There are numbers.
• Some are numbers.
• Something is a number.
• Numbers exist.

If we replace N x with −N x, the English translations would be

∀x−N x: Everything is not a number.

∃x−N x: Some are not numbers.

Moreover, the above translations can be paraphrased as “there’s

no number” and “not everything is a number” respectively. And because
“there’s no number” and “not everything is a number” are just the nega-
tions of “there are numbers” and “everything is a number”, these are also
expressed as −∃xN x and −∀xN x respectively.

To recap:
For some one-place predicate P ,
∀xP x: All are P .
∃xP x: Some are P .
∀x−P x; −∃xP x: Everything is not P ; there’s no P .
∃x−P x; −∀xP x: Some are not P ; not everything is P .5

5
From the above, we also notice that ∀x− ≡ −∃x and ∃x− ≡ −∀x; this is the direct

56
2.2.2 Translating L2 -sentences with two predicates
So far, we’ve been dealing with L2 -sentences in which just one predicate
appears. However, in many cases, we need more than one predicate to express
what we want to express. For example, in order to express “all humans are
mortal”, we need two predicates one of which is “. . . is a human” and the
other of which is “. . . is mortal”. And then, we somehow “bind” them with
the universal quantifier.
To translate the “all . . . are . . . ”-type of sentences into L2 , the fol-
lowing four forms (or templates) come in handy.

For some one-place predicates P and Q,

1. All P are Q: ∀x(P x → Qx).
2. No P are Q: ∀x(P x → −Qx); −∃x(P x ∧ Qx).
3. Some P are Q: ∃x(P x ∧ Qx).
4. Some P are not Q: ∃x(P x ∧ −Qx); −∀x(P x → Qx).

For example, with one-place predicates A and D which mean “. . . is

an apple” and “. . . is delicious” respectively, “all apples are delicious”, “no
apples are delicious”, “some apples are delicious”, and “some apples are not
delicious” are translated as ∀x(Ax → Dx), ∀x(Ax → −Dx) (or −∃x(Ax ∧
Dx)), ∃x(Ax ∧ Dx), and ∃x(Ax ∧ −Dx) (or −∀x(Ax → Dx)) respectively.
Note that in the above the universal quantifier ∀ is always accom-
panied by →, and the existential quantifier ∃ with ∧. The moral here is

If your translation has the forms ∀x(. . . ∧ . . .) or ∃x(. . . → . . .), there

may be something wrong with it.

For example, if you translate “All apples are delicious” as ∀x(Ax ∧

Dx), your translation actually means that everything in this world is a deli-
cious apple, which is quite a wild statement.

2.2.2.1 Many faces of ∃

As we’ve seen a number of times in the above, the same L2 -sentence can be
translated into English in many ways. For example, let’s take a look at the
results of the other equivalences ∃x ≡ −∀x− and ∀x ≡ −∃x−. See Section 2.1.1.3.

57
following sentences.

• There is a delicious apple.

• There is at least one delicious apple.
• Some apples are delicious.
• At least one apple is delicious.

As you instantly notice, these sentences are translated as the same

L2 -sentence, ∃x(Ax ∧ Dx), and the sentences are so simple that you may
think that you’re not gonna have any trouble in translating such English
sentences. However, in more complicated cases, you may become unsure
whether you should use ∀ or ∃ in translating some English sentences. The
following would give you some guide.

English expressions “there exist(s)/is/are”, “some”, “at least one” and

“a/an” are translated with the existential quantifier ∃.6

And as a general translation tip,

When you’re asked to translate an English sentence to an L2 -sentence,

first try to translate your English sentence into another English sentence
which is close to one of the four templates above.

2.2.3 Translating Noun Phrases

Let’s think about translating the following sentence: All red apples are deli-
cious. Here, unlike the previous examples, we need two predicates in order to
express a noun phrase “red apple”. In such cases, all we need is just combine
two predicates with ∧.

When you need more than one predicate to express a noun phrase, just
combine those predicates with ∧.

Thus, by introducing yet another one-place predicate R which means

“. . . is red”, “all red apples are delicious” are translated as ∀x((Rx ∧ Ax) →
Dx).
6
However, a special attention must be paid to the cases where “a/an” is used for
expressing something general. See Section 2.2.5.1.

58
2.2.3.1 Problems
Translate the following into L2 -sentences.

1. There’s no delicious red apple.

2. At least one red apple is delicious.
3. Not all red apples are delicious.

2.2.4 Some Translation Practices

Let’s translate the following English sentence into L2 . Here, we’re given the
following predicates: N (“. . . is a number”), P (“. . . is prime”), and O (“. . . is
odd”).

Every prime number is odd.

As we’ve seen in the previous section, the noun phrase “prime num-
ber” can be expressed with the predicates P and N . And using one of the
four template, it’s translated as

∀x((P x ∧ N x) → Ox).

Obviously, the above statement is false because there’s a prime num-

ber which is not odd, namely 2. How can we amend the statement? On way
is to add an extra predicate “other than 2” to the noun phrase.

Every prime number other than 2 is odd.

The above can be paraphrased as “Every object which is a number,

prime, and not 2, is odd”. Thus, by introducing a new predicate T which
means “. . . is 2”, the above sentence is translated as

∀x((P x ∧ N x ∧ −T x) → Ox).

However, the above is not the only amendment to the false state-
ment. We can amend the statement by rewriting it as “Every prime number
is odd or 2”. In this case, we need to use compound phrases in the subject

59
and complement.

∀x((P x ∧ N x) → (Ox ∨ T x)).

Although these L2 -sentences look different, they capture the very

same situation. And actually, they are logically equivalent.

2.2.4.1 Problem
Show that ∀x((P x ∧ N x ∧ −T x) → Ox) and ∀x((P x ∧ N x) → (Ox ∨ T x))
are logically equivalent by transforming the one into the other using (α →
β) ≡ (−α ∨ β), −(α ∧ β) ≡ (−α ∨ −β), and −(α ∨ β) ≡ (−α ∧ −β).

2.2.5 Some Translation Tips

In this section, we’re gonna take a look at how we translate some English
words/phrases into L2 -sentences.

2.2.5.1 If . . . , then . . . .
Basically, if you come across a sentence which has the if-then structure, you
simply translate it as a conditional. For example, the sentence “if Alma is
hungry, she eats something” is translated as (Ha → ∃xEax) (here, the name
a refers to Alma, and the two predicate Hx and Exy mean “x is hungry”
and “x eats y” respectively). However, in some cases, special care should be
taken. Let’s think about the following sentence.

If an apple is red, it is delicious.

In the above, “it” in the consequent of the conditional refers back to

“an apple” in the antecedent. Thus, we need to make the connection between
“it” and “an apple” explicit. But how? We use one of the quantifiers.
The quantifiers can make such connections explicit. For example,
“an apple is red” can be expressed as ∃x(Ax ∧ Rx). This sentence literally
means that there exists at least one object which is an apple and red. Then,
on first sight, it seems that the sentence is translated as ∃x((Ax∧Rx) → Dx).
However, this doesn’t capture the meaning of the sentence properly. the sen-
tence doesn’t merely talk about this or that red apple’s deliciousness; rather,

60
it talks about a red apple in general is delicious. Thus, the proper translation
is

∀x((Rx ∧ Ax) → Dx).

2.2.5.2 Only
There’s a handy template for translating sentences in which the word “only”
appears.

Only P are Q: ∀x(Qx → P x).

Thus, with this template, “only red apples are delicious” is trans-
lated as

∀x(Dx → (Rx ∧ Ax)).7

2.2.5.3 Unless
The words “unless” is simply interpreted as “if not”. Thus, “Q unless P ” is
interpreted as “if not P , then Q”. For example, “An apple is not delicious
unless it’s red” is interpreted as “if it’s not red, an apple is not delicious”,
and then translated as ∀x(−Rx → −(Ax ∧ Dx)). And this suggests that
if an apple is delicious, it should be red; thus, we have another translation:
∀x((Ax ∧ Dx) → Rx).8
7
Why can’t we translate this as ∀x((Rx∧Ax) → Dx)? In order to answer this question,
first let’s think about a quantified conditional.
In general, in a quantified conditional ∀x(P x → Qx), the cases (or things) which is said
to be P are among the cases (or things) which are said to be Q; but the reverse doesn’t
generally hold. For example, in the conditional ∀x(Rx ∧ Ax) → Dx, red apples are among
things which are said to be delicious. However, what is delicious is not necessarily a red
apple. The conditional ∀x(Rx ∧ Ax) → Dx implies that there might be some other things
than red apples which are delicious.
On the other hand, the statement “only red apples are delicious” means that what are
delicious are red apples, and nothing else is delicious; what are delicious are among red
apples (however, there might be some red apples which are not delicious). Thus, the
statement is translated as ∀x(Dx → (Rx ∧ Ax)), not ∀x((Rx ∧ Ax) → Dx).
8
From this, you may notice that (P → Q) is equivalent to (−Q → −P ); the latter
(resp. the former) is called the contrapositive of the former (resp. the latter).

61
 Furthermore, “unless” can be interpreted as “or”. The reason is as
follows. From the above remark, “Q unless P ” is translated as (−P → Q).
This conditional can be written as (−−P ∨ Q) (using (α → β) ≡ (−α ∨ β)).
Therefore, “Q unless P ” ≡ (−P → Q) ≡ (P ∨ Q) ≡ “P or Q”.

2.2.5.4 Any
The word “any” is perhaps the most troubling one to translate because it
sometimes means “some”, sometimes means “every”.
Unfortunately, there’s no etched-in-stone way to figure out in which
sense “any” is used. However, there are some rules of thumb.

If any . . . : If there’s at least one . . . , then . . . ⇒ ∃x(. . . x . . .) → . . .

Ex. If anyone can do it, then Alma can do it.
⇒ If there’s at least one who can do it, then Alma can do it.
⇒ (∃xDx → Da).

Not any . . . : There’s no . . . ⇒ −∃x(. . . x . . .).

Ex. Not any can do it.
⇒ There’s no one who can do it.
⇒ −∃xDx.

Any . . . : Every . . . ⇒ ∀x(. . . x . . .).

Ex. Anything Alma eats is . . .
⇒ Everything Alma eats is . . .
⇒ ∀x(Eax → . . .).

Unfortunately again, none of the above rules of thumb doesn’t seem

to be readily applied to a sentence like “if Alma eats anything, then she eats
an apple”. In this case, you need to interpret your sentence in both ways
and decide which interpretation is more natural.
First, let’s interpret “any” as “every”; then, we have “If Alma eats
everything, then Alma eats an apple”, which sounds a little bit too wild.
On the other hand, if we interpret “any” as “some”, we have “If Alma eats
something, then Alma eats an apple”, which sounds more natural.
(You may also wonder how you should translate “Alma eats an
apple”. Here, remember that in many cases “a/an” is interpreted as “at

62
least one” in L2 . Thus, “Alma eats an apple” is interpreted as “There’s at
least one apple which Alma eats”, and then translated as ∃x(Dax ∧ Ax).)

2.2.6 Problems
1. Translate the following sentences. In translating them, use the following
names and predicate: h: Holmes; m: Moriarty; Cxy: x can catch y.

1. Holmes can catch anyone who can catch Moriarty.

2. Holmes can catch anyone whom Moriarty can catch.
3. Holmes can catch anyone who can be caught by Moriarty.
4. If anyone can catch Moriarty, then Holmes can.
5. If everyone can catch Moriarty, then Holmes can.
6. Anyone who can catch Holmes can catch Moriarty.
7. No one can catch Holmes unless he can catch Moriarty.

2. Formalize the following argument. In formalizing it, use the following

predicates: Ax: I avoid x; Bx: x is carnivorous; Cx: x is a cat; Dx: I detest
x; Ex: x is in this house; Hx: x is a kangaroo; Kx: x kills mice; Lx: x
loves to gaze at the moon; M x: x prowls at night; N x: x is suitable for pets;
Rx: x takes to me. Furthermore, in the argument, we are talking only about
animals. (Thus, we can formalize the argument without a predicate which
means “. . . is an animal”.)

The only animals in this house are cats.

Every animal is suitable for pets if it loves to gaze at the moon.
When I detest an animal, I avoid it.
No animals are carnivorous unless they prowl at night.
No cat fails to kill mice.
No animals ever take to me except what are in this house.
Kangaroos are not suitable for pets.
None but carnivora kill mice.
I detest animals that do not take to me.
Animals that prowl at night always love to gaze at the moon.
I avoid kangaroos.

(The above argument is taken from a book by Charles Lutwidge

63
Dodgson, aka Lewis Carroll, who is needless to say the author of Alice in
Wonderland, and incidentally taught logic at Oxford.)

2.3 Semantics of L2
In Section 1.2, we learned how to assign truth values to an L1 -sentence; the
truth values of an L1 -sentence is determined by those of sentence letters in
it. The truth-value assignments to an L2 -sentence is carried out in a similar
fashion as in the cases of L1 -sentences; the truth values of an L2 -sentence
is determined by its components. However, in the cases of L2 -sentences, we
have more components besides sentence letters as “building blocks” or “truth
makers” of L2 -sentences; predicates. And recall that a predicate is nothing
but a sentence; it has its own truth value which is determined by objects the
names in the predicate (remember: in general, an n-place predicate should
have n names) refer to. Schematically, this procedure is depicted as follows.

Truth values of an L2 -sentence

are determined by
−−−−−−−−−−→ Truth values of predicates in the sentence
are determined by
−−−−−−−−−−→ References of names in the predicate.

Thus, in order to assign truth values to an L2 -sentence, we need to

start with assigning objects to names.

2.3.1 Assignment of an Object to a Name

In order to assign an object to a name, first we need to decide what kind of
objects we’re talking about. This collection of objects we’re talking about
is called the domain. The domain can be any collection but it cannot be
empty; it has to have at least one objects in it. Other than that, there’s no
restriction as to how we set up our domain or the universe of discourse. The
domain may be a collection of numbers, of people, of numbers and people,
or of anything ever imaginable.
Now, let’s suppose that our domain is comprised of three numbers
1, 2, 3; we write this as {1, 2, 3}. Once we set up the domain, we can assign
an object of the domain to a name. For example, if we have a name a, we
assign one and only one member of the domain; the same name cannot refer
to two different objects in the domain although it may be the case that two

64
different names refer to the same object in the domain (see Section 2.1.1.1
for a bit more details). And a name has to refer to something in the domain;
namely, an empty name is not allowed (i.e., a name without reference). The
object assigned to a name is called an extension or valuation of that name
and denoted as Ext(a) or v(a); and we say “the name refers to the assigned
object”. Thus, the extensions (or valuations) for the names a, b, c may be

a : 1; b : 2; c : 3
(in this set-up, we say “a refers to 1, b to 2, and c to 3 respectively”)

or

a : 1; b : 1; c : 3
(a and b refer to the same object, namely 1)

or

a:1
(there’s no names for 2 and 3; yes, an object in the domain doesn’t
have to be named).

2.3.2 Assignment of Truth Values to a Predicate

Once we assigned objects to names in a predicate, we’re ready to assign
truth values to the predicate. And how we assign truth values to a predicate
depends on how many names the predicate in question has. Let’s start with
the simplest case: a one-place predicate.

2.3.2.1 Assignment of Truth Values to a One-Place Predicate

Recall that a one-place predicate is that which takes one name, and this is
sometimes indicated by the superscript (for more detail, see Section 2.1.1.2);
for example, the superscript 1 in F 1 indicates that this predicate takes one
name, and with some name a, F 1 a means that an object referred to by a has
the property F ; or more simply, F 1 a means that a is F . Thus, intuitively, if
an object referred to by the name a actually has the property F (or simply,
if a is actually F ), the sentence F 1 a is true.

65
 A sub-collection (which is usually called a subset) of the domain
the members of which have the property F is called the extension of F . For
example, if our domain is {1, 2, 3}, its subsets ∅ (or Λ; both are read as
“the empty set”), {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}, and {1, 2, 3} (namely,
the domain itself) are all candidates for the extension of F and denoted as
Ext(F 1 ). (Note that in a set (or subset), the order doesn’t matter; {1, 2} is
the same as {2, 1}, {1, 2, 3} is the same as {2, 1, 3}, {3, 2, 1}, etc.)
For example, if the extension of F is {1, 3}, F a (here, we omit the
superscript 1) is going to be true when a refers to 1 or 3; otherwise (in this
case, when a refers to 2), it’s going to be false.
Note that the extension of a one-place predicate can be empty; for
example, if our domain is the set of people, and if the one-place predicate Rx
means “x is a reptile”, obviously there’s nothing in the extension of R. In
this case, we write the extension of R as ∅ and say “nothing in the domain
is a reptile”.9

2.3.2.2 Assignment of Truth Values to a Two-Place Predicate

A two-place predicate is that which takes two names and this is sometimes
indicated by the superscript 2; for example, the superscript 2 in L2 indicates
that this predicate takes two names, and with some names a and b, L2 ab
means that an object referred to by a has the relation L to an object referred
to by b; or more simply, L2 ab means that a has the relation L to b. Thus,
intuitively, if an object referred to by the name a actually has the relation
L to an object referred to by b (or simply, if a actually has the relation L to
b), the sentence L2 ab is true.
The rough description above is almost the same as that for a one-
place predicate. However, the form of the extensions for a two-place predicate
is significantly different from that of a one-place predicate; the extension of
a two-place predicate is a set comprised of ordered pairs of the members of
the domain, not just a subset of the members of the domain.
An ordered pair is just two members of the domain enclosed with
the angle brackets h and i. For example, h1, 2i, h2, 3i, and h3, 1i are all
ordered pairs. Note that, for some members x, y of the domain, hx, yi is not
the same as hy, xi unless x, y are the same.
9
You cannot write this empty extension as {∅}; {∅} does have a member, namely ∅,
and consequently, {∅} is not empty.

66
 The reason why the extension of a two-place predicate has to be a
set of ordered pairs, not just a subset of the domain, comes from the following
observation.
Let Lab (we omit the superscript 2 here) mean “a loves b”. if a and b
referred to 1 and 2 respectively, and if the extension of L were just comprised
of a subset {1, 2} of the domain, Lba as well as Lab would be true with this
extension because {1, 2} is the same {2, 1}. However, the sentence “a loves
b” (which is meant by Lab) is not the same “b loves a” (Lba). Therefore, we
have to differentiate these two sentences. For this reason, we need to use a
set of ordered pairs for the extension of a two-place predicate.
Now, let’s take a look at a simple example. If the extension of L
is {h1, 2i, h2, 1i}, Lab is going to be true when a refers to 1 and b to 2, or a
to 2 and 1; otherwise (for example, a refers to 1 but b to 3), it’s going to be
false. In either case, if Lab is true, a and b love with each other.
As in the case of a one-place predicate, the extension of a two-
predicate can be empty; for example, if the extension of L is empty, no one
loves anyone under such an interpretation.

2.3.3 Examples
Problems concerning the interpretation of L2 -sentences roughly fall into the
following two types.

1. Given an interpretation, determine whether some sentences are true or

not under that interpretation.
2. Given a sentence, construct an interpretation under which the given
sentences are true (or false).

In this section, we’re gonna take a look at some examples of these

two types of problems.

2.3.3.1 Determining the Truth Values of Sentences under a Given

Interpretation
Suppose that we’re given the following two interpretations I1 and I2 .

67
 I1 I2
Domain: {1, 2, 3} {1, 2, 3}
Extension of F 1 : {1} ∅
Extension of G1 : {2} {2}
Extension of L2 : {h1, 1i, h1, 2i} ∅
Extension of a: 1 1
Extension of b: 2 2

Let’s determine whether the following sentences are true or not

under these interpretations.

1. Fa 5. Laa 9. ∃x−F x 13. ∀x(F x → Gx)

2. (F a ∧ Gb) 6. (Lba → Laa) 10. ∃x(F x ∧ Gx) 14. ∀x(F x ↔ Gx)
3. −F b 7. (Laa → Lba) 11. (∃xF x ∧ ∃xGx)
4. (F b → Gb) 8. ∃xF x 12. ∀xF x

1. F a
This sentence is true under I1 because the reference of a, namely 1, is
in the extension of F . On the other hand, the sentence is false under
I2 because there’s nothing which is F in I2 .

2. (F a ∧ Gb)
The sentence is a conjunction. Therefore, in order for it to be true,
both conjuncts have to be true. Under I1 , the references of a and b
are 1 and 2 respectively, and 1 is in the extension of F and 2 in the
extension of G. Thus, since both conjuncts are actually true under I1 ,
the sentence is true under I1 . On the other hand, as we know from the
case of F a, nothing is F in I2 , and consequently, F a is false under I2 .
Thus, the sentence is false under I2 .

3. −F b
The sentence is a negation. Thus, in order for it to be true, F b has
to be false, which means that the reference of b shouldn’t be in the
extension of F . In I1 and I2 , the reference of b, namely 2, is not in the
extension of F . Therefore, the sentence is true under both I1 and I2 .

4. (F b → Gb)
The sentence is a conditional. Thus, in order for it to be true, at least
one of the following has to be the case: F b is false or Gb is true. In

68
 I1 and I2 , F b is false (the reference of b is not in the extension of F ).
Therefore, the sentence is true under both interpretations.

5. Laa
The sentence is a two-place predicate. Thus, in order for it to be true,
the ordered pair which is comprised of the reference of a, namely h1, 1i
in both interpretations, has to be in the extension of L. That ordered
pair is in the extension of L under I1 but not in that of L under I2
(because the extension of L is empty in L2 ). Therefore, the sentence is
true under I1 whereas it’s false under I2

6. (Lba → Laa)
The sentence is a conditional with two two-place predicates. Thus,
in order for it to be true, at least one of the following has to be the
case: the ordered pair which is comprised of the references of b and a,
namely h2, 1im is not in the extension of L, or the ordered pair which is
comprised of the reference of a, namely h1, 1i, is in the extension of L.
In both interpretations, h2, 1i is not in the extension of L. Therefore,
the sentence is true under both I1 and I2 .

7. (Laa → Lba)
In order for the sentence to be true, at least one of the following has to
be the case: the ordered pair h1, 1i is not in the extension of L or the
ordered pair h2, 1i is in the extension of L. In I2 , h1, 1i is not in the
extension of L. Therefore, the sentence is true under I2 . On the other
hand, in I1 , h1, 1i is in the extension of L and h2, 1i is not. Therefore,
under I1 , the sentence is false.

8. ∃xF x
The sentence is an existential sentence. Thus, in order for it to be
true, there has to be at least one object in the extension of F . In I1 ,
there is one object in the extension of F , namely 1. Therefore, the
sentence is true under I1 . On the other hand, in I2 , there’s nothing in
the extension of F . Therefore, the sentence is false under I2 .

9. ∃x−F x
The sentence tells us that there has to be at least one object which is
not F . Thus, in order for it to be true, there has to be at least one
object which is not in the extension of F . In both interpretations, there

69
 are object which are not in the extension of F (in I1 , they are 2 and 3;
in I2 , they are 1, 2, and 3). Therefore, the sentence is true under both
interpretations.

10. ∃x(F x ∧ Gx)

In order for the sentence to be true, there has to be at least one object
which is in the extensions of F and G. However, in both interpretations,
there’s no shared object in the extensions of F and G. Therefore, the
sentence is false under both interpretations.

11. (∃xF x ∧ ∃xGx)

In order for the sentence to be true, there has to be at least one object
in the extension of F and there has to be at least one object in the
extension of G. In I1 , there is one object in the extensions of F and
G. Therefore, the sentence is true under I1 . On the other hand, in I2 ,
there is no object in the extension of F . Therefore, the sentence is false
under I2 .

12. ∀xF x
In order for the sentence to be true, everything in the domain has to
be in the extension of F . In both interpretations, the extension of F
fails to contain all members of the domain. Therefore, the sentence is
false under both interpretations.

13. ∀x(F x → Gx)

in order for the sentence to be true, each member of the domain, if it’s
in the extension of F , has to be in the extension of G. In our case, only
member of the domain which is in the extension of F is 1. Thus, if the
sentence is true, 1 has to be in the extension of G as well. However,
since the extension of G is empty, there’s no way for 1 to be in the
extension of G. Therefore, the sentence is false.

14. ∀x(F x ↔ Gx)

In order for the sentence to be true, the extension of F has to be the
same as the extension of G. However, they are clearly different; one is
comprised of 1, the other is the empty set. Therefore, the sentence is
false.

70
2.3.3.2 Constructing an Interpretation under Which a Given Sen-
tences Are True (or False)
This type of problems requires much more substantial work. In the previous
type of problems, all you have to do is to check whether a sentence is true
or false under a given interpretation; here, you need to construct your own
interpretation under which a given sentence is true (or false).
Let’s start with a very simple sentence: F a. In constructing an
interpretation, first you need to set up the domain. Here, for the sake of
simplicity, let our domain be {1, 2, 3} throughout this section. Once you
set up the domain, next you need to specify the extensions of predicates;
and as we have seen in the above, if a predicate in question has names,
we need to assign objects to them as well. In our case, there’s a name in
our sentence F a, namely a; thus, we need to first assign an object of the
domain to the name. Let’s assign 1 to the name a. Then, F a is going
to be true if 1 is in the extension of F (the instances of such extensions
are: {1}, {1, 2}, {1, 3}, {1, 2, 3}). On the other hand, if the extension of F
doesn’t contain 1, F a is going to be false (the instances of such extensions
are: ∅, {2}, {3}, {2, 3}).
Next, let’s think about a slightly more complicated example: ∀xF x.
This is, needless to say, a universal sentence which says “everything in the
domain is F ”. Thus, every members of the domain need to be in the extension
of F ; so, the extension should be {1, 2, 3}. On the other hand, the extension
of F doesn’t contain all of the domain, ∀xF x is going to be false.
How about (∀xF x → Lab)? Although there appears a universal
sentence, this is just a conditional. So, the easiest way to make the sentence
true would be to make its antecedent false or the consequent true. For the
antecedent to be false, the extension of F can be anything except the domain
itself. And for the consequent to be true, the extension of L should contain
the ordered pair of the objects which are referred to by the names a and b.
Let a and b refer to 1 and 2 respectively; thus, the extension of L should be
{h1, 2i}. On the other hand, to make the sentence false, we need to make the
antecedent true and the consequent false; thus, the extension of F should be
{1, 2, 3} and that of L shouldn’t contain the objects referred to by a and b.
Note that (∀xF x → Lab) is not equivalent to ∀x(F x → Lab). For
appreciating the difference between them (or more particularly, for finding
an interpretation on which one sentence is true but the other is false), let’s
construct interpretations for ∀x(F x → Lab). The sentence can be trans-

71
lated into the following quasi-English sentence: “For each x in the domain,
(F x → Lab) holds”. Thus, it can be transformed as the following conjunc-
tion: ((F a → Lab) ∧ (F b → Lab) ∧ (F c → Lab)) (here, a, b, c refer to 1, 2, 3
respectively). The easiest way to make all the conjuncts in this conjunc-
tion true would be, once again, to make all the antecedents in the conjuncts
(namely, F a, F b, and F c) false or to make all the consequents (namely, Lab)
true. And we know how to accomplish this; assigning the emptyset (∅) to
the extension of F or assigning {h1, 2i} to the extension of L.
On the other hand, to make ∀x(F x → Lab) false, it would suffice
to make at least one of the conjuncts in ((F a → Lab) ∧ (F b → Lab) ∧
(F c → Lab)) false. So, let’s make the first conjunct (F a → Lab) false. For
(F a → Lab) to be false, its antecedent F a has to be true, the consequent
Lab false; thus, the extension of F should contain 1 and the extension of L
shouldn’t contain the ordered pair h1, 2i. Thus, the assignments {1} for the
extension of F and ∅ for the extension of L make ∀x(F x → Lab) false but
the same assignments make (∀xF x → Lab) true.
There’s another approach to finding interpretations which make
∀x(F x → Lab) false. First, negate the sentence and transform it using
the following equivalences.
(α → β) ≡ (−α ∨ β)
−(α ∧ β) ≡ (−α ∨ −β)
−(α ∨ β) ≡ (−α ∧ −β)
−∀ ≡ ∃−
−∃ ≡ ∀−

With these equivalences, we can transform the negated sentence as

follows.
−∀x(F x → Lab)
≡ ∃x − (F x → Lab)
≡ ∃x − (−F x ∨ Lab)
≡ ∃x(− − F x ∧ −Lab)
≡ ∃x(F x ∧ −Lab)
(You may feel that this procedure of transformation itself is quite
cumbersome; however, with some practices, you’ll be able to do this quite
easily.)

72
 Since there’s no x in −Lab, ∃x(F x∧−Lab) is equivalent to (∃xF x∧
−Lab). Thus, ∃x(F x ∧ −Lab) is going to be true as long as the extension of
F contains at least one object from the domain (for example, setting it up as
{1, 2, 3}, namely the domain itself) and the extension of L doesn’t contain
the ordered pair which is comprised of the objects referred to by a and b (for
example, setting it up as ∅). And then, this makes (∀x(F x → Lab)) false.
To round off this section, let’s construct two interpretations one of
which makes ∃(F x → Lab) true, the other false.
Just like a universal sentence can be thought of as a conjunction,
an existential sentence can be thought of as a disjunction; namely, with the
names a, b, c which refer to 1, 2, 3 respectively, ∃x(F x → Lab) can be written
as ((F a → Lab) ∨ (F b → Lab) ∨ (F c → Lab)). Thus, for ∃x(F x → Lab)
to be true, at least one of the disjuncts ((F a → Lab), (F a → Lab), and
(F a → Lab)) has to be true. To accomplish this, namely, to make one of
the disjuncts true, is easy; just make F a (or F b or F c) false, or make Lab
true. Thus, setting up the extension of F as empty or the extension of L as
{h1, 2i} would do.
On the other hand, to find an interpretation which makes the sen-
tence false is not that straightforward. Here, let’s negate and transform the
sentence first.

−∃x(F x → Lab)
≡ ∀x − (F x → Lab)
≡ ∀x − (−F x ∨ Lab)
≡ ∀x(− − F x ∧ −Lab)
≡ ∀x(F x ∧ −Lab)
Since there’s no x in −Lab, ∀x(F x∧−Lab) is equivalent to (∀xF x∧
−Lab). Thus, ∀x(F x ∧ −Lab) is going to be true as long as the extension of
F contains all the members of the domain (namely, setting it up as {1, 2, 3},
the domain itself) and the extension of L doesn’t contain the ordered pair
which is comprised of the objects referred to by a and b (for example, setting
it up as ∅). And then, this makes (∀x(F x → Lab)) false.
Sometimes it’s much easier to find an interpretation which makes
a sentence false in this way. So, if you’re not so sure about what extensions
would make a sentence false, it might be a good idea to first negate the sen-
tence in question and try to find an interpretation which makes the negated
sentence true.

73
2.4 Truth-Tree Method for L2
Since the language L2 is an extension of L1 , the truth-tree method for L2 is
also an extension of the truth-tree method for L1 ; we add a few new rules to
the ten rules we have studied in 1.9. Those new rules are all concerning the
quantifiers. First, let’s look at two rules called the negated quantifier rules.

Negated Quantifier Rules (NQ)

11. X − ∀x . . . 12. X − ∃x . . .
∃x − . . . ∀x − . . .

The meanings (or functions) of these rules should be clear enough;

if we have a sentence which starts with −∀x (resp. −∃x), we can replace
−∀x with ∃x− (resp. ∀x−). For example, if you have −∀xF x in your tree,
you can write down ∃x − F x.
The next two rules are more important and (unfortunately) it would
take some time to get used to them. These are called the instantiation rules
for the quantifiers.

Instantiation Rules for the Quantifiers

13. Universal Instantiation (UI) 14. Existential Instantiation (EI)

∀x . . . x . . . X ∃x . . . x . . .
. . . name . . . . . . name . . .
In the above, the name with In the above, the name with
which you replace x has to be which you replace x has to be
one which has already appeared new to the path.
in the path unless there’s no
name in the path. Also note
that you must not put the check
mark even after you instanti-
ated a universal sentence be-
cause you may instantiate the
same universal sentence again.

In applying these rules (including ones we’ve studied in 1.9), you

may want to follow the following order of application.

74
Order of Application of the Rules

1. Rules for negation, conjunction, disjunction, conditional, and bi-conditional.

(Rules 2–10; these rules are called the truth-functional rules)
2. Rules for negated quantifiers. (Rules 11–12)
3. EI. (Rule 14)
4. UI. (Rule 13)

You may notice that the rule 1, namely the rule for closure, isn’t
included in the above. This omission means that you should apply the closure
rule whenever you can apply it.
The above order is not mandatory but if you follow this order, your
tree would be going to be shorter in most cases. (But of course there are
exceptions; namely, there are some cases where following the order makes
the tree longer and more complicated. We’ll see one of such instances in the
below.)

2.4.1 Testing the satisfiability of a sentence

Let’s test the satisfiability of (∃xF x ∨ −∃xF x). To test the satisfiability of
a sentence, we write a truth tree for the sentence itself. If there is at least
one finished open path, the sentence is satisfiable.

1. X (∃xF x ∨ −∃xF x)

2. X ∃xF x X − ∃xF x Rule 5 to Line 1

3. Fa ∀x − F x EI with a new name a from Line 2; NQ to Line 2
4. −F a UI with a new name a from Line 3

For the left path of the tree, there’s nothing we can do further; the
left path will remains open no matter what happens to the right path. For
the right path, we can do nothing for closing the path; no matter how many
times we instantiate ∀x − F x, there’s no hope for closing the path. Thus,
both paths are open; the sentence is satisfiable.
How about the satisfiability of (∀xF x ∧ ∃x − F x)?

75
 1. X (∀xF x ∧ ∃x − F x)
2. ∀xF x Rule 3 to Line 1
3. X ∃x − F x Rule 3 to Line 1
4. −F a EI with a new name a from Line 3
5. Fa UI with the name a from Line 2
×

The tree is closed; thus, the sentence is not satisfiable (i.e. it’s
unsatisfiable).

2.4.2 Testing the Validity of a Sentence

Now we know that (∃xF x ∨ −∃xF x) is satisfiable. Is it valid? To test the
validity of a sentence, we need to write a truth tree for the negation of the
sentence. If the tree is closed, the sentence is valid.

1. X − (∃xF x ∨ −∃xF x)
2. −∃xF x Rule 6 to Line 1
3. − − ∃xF x Rule 6 to Line 1
×

The tree is closed; thus, the sentence is valid.

2.4.3 Testing the Validity of an Argument

Let’s recall what motivates the extension of the language L1 . Our motivation
of extending L1 was to capture arguments like the following.
All humans are mortal.
Socrates is a human.
Socrates is mortal.
Now let H and M be predicates which mean “. . . is a human” and
“. . . is mortal” respectively and let s be a name for Socrates. Then, the above
argument can be formalized as follows.
∀x(Hx → M x)
Hs
Ms

76
 Let’s see whether this arguments is valid or not by writing a truth
tree. To test the validity of an argument, we start with writing down its
premise(s) and the negation of its conclusion.

1. ∀x(Hx → M x)
2. Hs
3. −M s
4. X (Hs → M s) UI with the name s from Line 1

5. −Hs Ms Rule 7 to Line 4

× ×

All the paths are closed; thus, the argument is valid.

Next let’s see whether the following argument is valid or not.

∀xF x
(F a → ∃xGx)
(F b → ∃xHx)
(∃xGx ∧ ∃xHx)

Here’s the tree.

1. ∀xF x
2. X (F a → ∃xGx)
3. (F b → ∃xHx)
4. −(∃xGx ∧ ∃xHx)

5. −F a ∃xGx Rule 7 to Line 2

If we follow the recommended order of application, we should de-

compose either Lines 3 or 4 next. However, we also notice that if we instan-
tiate Line 1 with the name a, the left path is going to be closed. So let’s do
it.

77
 1. ∀xF x
2. X (F a → ∃xGx)
3. (F b → ∃xHx)
4. −(∃xGx ∧ ∃xHx)

5. −F a ∃xGx Rule 7 to Line 2

6. Fa Fa UI with the name a from Line 1
×

Next we are back to the recommended order and decompose Line

3.

1. ∀xF x
2. X (F a → ∃xGx)
3. (F b → ∃xHx)
4. −(∃xGx ∧ ∃xHx)

5. −F a ∃xGx Rule 7 to Line 2

6. Fa Fa UI with the name a from Line 1
×
7. −F b ∃xHx Rule 7 to Line 3

We can do the same thing for −F b as we did for −F a and then

decompose Line 4.

78
1. ∀xF x
2. X (F a → ∃xGx)
3. X (F b → ∃xHx)
4. X − (∃xGx ∧ ∃xHx)

5. −F a ∃xGx Rule 7 to Line 2

6. Fa Fa UI with the name a from Line 1
×
7. −F b ∃xHx Rule 7 to Line 3
8. Fb Fb UI with the name b from Line 1
×
9. −∃xGx −∃xHx Rule 4 to Line 4
× ×

All the paths are closed; thus, the argument is valid. (Note that
you don’t even have to instantiate ∃xGx and ∃xHx; these cause immediate
contradiction with the two sentences in Line 9.)

2.4.4 Construct an Interpretation from an Open Path

Let’s write a truth tree for the following argument.

∀x−Gxx
(−∀xHx → ∃xGxa)
∃x(Hx ∧ −Gxx)
The tree is as follows.

79
1. ∀x−Gxx
2. X (−∀xHx → ∃xGxa)
3. X − ∃x(Hx ∧ −Gxx)
4. ∀x−(Hx ∧ −Gxx) NQ to Line 3

5. X − −∀xHx X ∃xGxa Rule 7 to Line 2

6. ∀xHx Gba Rule 2 to Line 5; EI with b from Line 5
7. −Gaa −Gaa UI with a from Line 1
8. X − (Ha ∧ −Gaa) X − (Ha ∧ −Gaa) UI with a from Line 4

9. −Ha −−Gaa −Ha −−Gaa Rule 4 to Line

10. Ha × −Gbb × UI with a from Line 6; UI with b from 1
11. × X − (Hb ∧ −Gbb) UI with b from Line 4

12. −Hb −−Gbb Rule 4 to Line 11

×

The tree remains open; the argument is invalid.

Now let’s construct an interpretation which shows the invalidity of

the argument (namely, a counterexample). The procedure is as follows.

1. Collect atomic sentences which appear as a line by itself in

the open path.
In the above example, Gba is the only atomic sentence which appears
as a line by itself in the open path.

2. List the names which appear in the atomic sentences collected

in the step 1; and assign a numerical object (i.e. 1, 2, 3 etc.)
sequentially to each object. A set of those numerical objects
will be the domain.
In the above, the names which appear in the atomic sentences are a
and b; and we assign 1 and 2 to a and b respectively. The domain is,
therefore, {1, 2}.

3. Set up an extension for each predicate from the atomic sen-

tences collected in the step 1. For predicates which appear

80
 as a component of some sentences but not as a line by itself,
assign ∅ as their extensions.
In the above, the only atomic sentence which appears as a line by itself
in the open path is Gba; and the extension for G is {h2, 1i}. On the
other hand, the predicate H doesn’t appear as a line by itself; thus, the
extension for H is ∅.

2.4.5 Testing the Equivalence

To test the equivalence between sentences α and β, we test the validity of
(α ↔ β); and this amounts to test two implications: α |= β and β |= α
(think why). If both implications hold, α and β are equivalent; if at least
one of the implications fails, α and β are not equivalent.

Let’s see whether ∀x(Ax ∧ Bx) and (∀xAx ∧ ∀xBx) are equivalent
or not. We need to start our tree with −(∀x(Ax ∧ Bx) ↔ (∀xAx ∧ ∀xBx))
of course.

1. X − (∀x(Ax ∧ Bx) ↔ (∀xAx ∧ ∀xBx))

2. ∀x(Ax ∧ Bx) −∀x(Ax ∧ Bx) Rule 10 to Line 1

3. −(∀xAx ∧ ∀xBx) (∀xAx ∧ ∀xBx) Rule 10 to Line 1

Let’s first finish the left branch.

2. ∀x(Ax ∧ Bx) Rule 10 to Line 1

3. X − (∀xAx ∧ ∀xBx) Rule 10 to Line 1

4. X − ∀xAx X − ∀xBx Rule 4 to Line 3

5. X ∃x−Ax X ∃x−Bx NQ to Line 4
6. −Aa −Ba EI with a from Line 5
7. (Aa ∧ Ba) (Aa ∧ Ba) UI with a from Line 2
8. Aa Aa Rule 3 to Line 7
9. Ba Ba Rule 3 to Line 7
× ×

Next, the right branch.

81
 2. X − ∀x(Ax ∧ Bx) Rule 10 to Line 1
3. X (∀xAx ∧ ∀xBx) Rule 10 to Line 1
4. ∀xAx Rule 3 to Line 3
5. ∀xBx Rule 3 to Line 3
6. X ∃x−(Ax ∧ Bx) NQ to Line 2
7. X − (Aa ∧ Ba) EI with a from Line 6

8. −Aa −Ba Rule 4 to Line 8

9. Aa Aa UI with a from Line 4
10. × Ba UI with a from Line 5
×

All paths are closed; ∀x(Ax∧Bx) and (∀xAx∧∀xBx) are equivalent.

Next, let’s see whether ∃x(Ax ∧ Bx) and (∃xAx ∧ ∃xBx) are equiv-
alent or not.

1. −(∃x(Ax ∧ Bx) ↔ (∃xAx ∧ ∃xBx))

2. ∃x(Ax ∧ Bx) −∃x(Ax ∧ Bx) Rule 10 to Line 1

3. −(∃xAx ∧ ∃xBx) (∃xAx ∧ ∃xBx) Rule 10 to Line 1

The left branch:

2. ∃x(Ax ∧ Bx) Rule 10 to Line 1

3. X − (∃xAx ∧ ∃xBx) Rule 10 to Line 1

4. X − ∃xAx X − ∃xBx Rule 4 to Line 3

5. ∀x−Ax ∀x−Bx NQ to Line 4
6. X (Aa ∧ Ba) X (Aa ∧ Ba) EI with a from Line 2
7. Aa Aa Rule 3 to Line 6
8. Ba Ba Rule 3 to Line 6
× ×

The right branch:

82
 2. −∃x(Ax ∧ Bx) Rule 10 to Line 1
3. X (∃xAx ∧ ∃xBx) Rule 10 to Line 1
4. X ∃xAx Rule 3 to Line 3
5. X ∃xBx Rule 3 to Line 3
6. ∀x−(Ax ∧ Bx) NQ to Line 2
7. Aa EI with a from Line 4
8. Bb EI with b from Line 5
9. X − (Aa ∧ Ba) UI with a from Line 6
10. X − (Ab ∧ Bb) UI with b from Line 6

11. −Aa −Ba Rule 4 to Line 9

×
12. −Ab −Bb Rule 4 to Line 10
×

The tree remains open; ∃x(Ax ∧ Bx) and (∃xAx ∧ ∃xBx) are not
equivalent. And from the open path, we can construct an interpretation (a
counterexample) in which one of the sentences is true but the other is false
as follows (see the previous section for how to construct an interpretation
from an open path).

Domain = {1, 2}
Ext(a) = 1
Ext(b) = 2
Ext(A) = {1}
Ext(B) = {2}

2.4.6 Some Metalogical Considerations

So far we’ve been assuming that we can trust the results of the tree method
but not provided any justification for that assumption; now it’s time to
provide it.
The justification for the trustworthiness of the tree method can be
broken down into the justifications for the following three properties of the
tree method for the languages L1 and L2 .
1. A tree always stops; in other words, there’s no tree whose length is
infinite. (Decidability)

83
 2. If the initial list of the tree is satisfiable, there’s at least one open path
in the finished tree. (Soundness)

3. If there’s at least one open path in the finished tree, the initial list of
the tree is satisfiable. (Completeness)

First, let’s verify that a tree always stops.

2.4.6.1 Decidability
Decidability of the tree method is justified by the following properties of the
method.

1. Conclusions of the rules are shorter than the premise.

2. Each rule gives a finite number of conclusions.

3. Each line is decomposed (or instantiated) just once.

4. No rule is applied to literals.

In short, by applying the rules, each sentence in the initial list is

decomposed into a finite number of literals.

(Note that, strictly speaking, the properties 1 and 3 above don’t

hold of the language L2 ; the conclusion of NQ has the same length as the
premise, and a universal sentence can be instantiated more than once. For the
first issue, it can be said that, even though the conclusion of NQ isn’t shorter
than the premise, the conclusion of the conclusion of NQ is always shorter
than the original premise; so, this issue doesn’t affect the overall claim. For
the second issue, first note that there will be only a finite number of names
after decomposing all the sentences except universal ones; and those universal
sentences are instantiated only with a finite number of names. Therefore, the
number of the instantiations of universal sentences is finite as well.)

2.4.6.2 Soundness
This is a direct result of the soundness property of our rules (for the soundness
property of the rules, see 1.9.1); if each sentence in the initial list of the tree is
true in an interpretation, each conclusion of a rule (in the case of a branching

84
rule, at least one of its conclusions) has to be true in that interpretation.
Consequently, there’s at least one path in which all the conclusions are true
in an interpretation. In such a path, there can’t be a contradiction; thus,
such a path remains open.

2.4.6.3 Completeness
This is a direct result of the completeness property of our rules (for the
completeness property of the rules, see 1.9.1); if there’s at least one open path
in the finished tree, there’s an interpretation which makes all the conclusions
in that path true. And by the completeness property of the rules, the truth
of the conclusions guarantees that of each sentence in the initial list.

2.4.6.4 Problem
An interpretation I of a sentence S of L2 is a model of S, if S is true in I. A
model is finite, if its domain is finite. Explain why every satisfiable sentence
of L2 has a finite model.

85
Chapter 3

Language L3

The syntactical and semantical aspects (i.e. its vocabulary, the formation
rules, and how we interpret its sentences) of L3 are just the same as those of
L2 . Only difference between L3 and L2 is that in L3 there are sentences with
multiple quantifiers with overlapping scope.
Here, the determiner “with overlapping scope” is important because
we’ve already encountered with sentences with multiple quantifiers without
overlapping scope. For example, take a look at the following sentence.

(∃xDax → ∃x(Dax ∧ Ax))

In the above, there are multiple occurrence of the quantifiers. How-

ever, the scope of these quantifiers are not overlapping. The first quantifier
∃x governs (or binds) Dax whereas the second governs (Dax ∧ Ax). In each
sentence which is governed by the quantifier, there are no other quantifiers.
However, in the following sentence, the scope of the quantifiers is overlapping.

∀x∀yLxy

The first quantifier ∀x governs ∀yLxy and the second governs Lxy.
Here, there’s another quantifier in the scope of ∀x. In this sense, the scope
of ∀x and ∀y is said to be overlapping.
First, let’s take a look at how we translate (from/into) and interpret
L3 -sentences in the following sections.

86
3.1 Translation from/into L3-sentences
3.1.1 Translating L3 -Sentences
3.1.1.1 By Way of a Quasi-English Sentence
For a starter, let’s take a look at the following sentences with the predicate
Lxy which means “x loves y” with the domain = {people} .

1. ∀x∀yLxy
2. ∀x∃yLxy
3. ∃x∀yLxy
4. ∃x∃yLxy

These four combinations of the quantifiers can be translated into

the following quasi (i.e. not-so-natural) English phrases.

∀x∀y: For each x and for each y . . . .

∀x∃y: For each x there is at least one y such that . . . .

∃x∀y: There is at least one x such that for each y . . . .

∃x∃y: There is at least one x and there is at least one y such that . . . .

With these templates, the above sentences can be translated as

10 . For each person x and for each person y, x loves y.

20 . For each person x there is at least one person y such that x loves y.
30 . There is at least one person x such that for each person y, x loves y.
40 . There is at least one person x and there is at least one person y such
that x loves y.

Of course, these sentences can be translated into more natural En-

glish sentences as follows.

100 . Everyone loves everyone.

200 . Everyone loves someone.
300 . Someone loves everyone.

87
 400 . Someone loves someone.

If you’re dealing with simple sentences like these, it would be easy to

translate the L3 -sentences directly into natural English sentences. However,
in translating a more complicated L3 -sentence, it would be a good idea to
translate it by way of a quasi-English translation; in so doing, you can reduce
the chance of making mistakes.
For example, let’s translate the following L3 -sentence by way of a
quasi-English sentence.

∀x∀y((Ox ∧ Oy) → Oxy)

(Here, the one-place predicate Ox means “x is odd” and the two-
place predicate Oxy means “x times y is odd”. Even though these predicates
are expressed by the same letter O, there’s no danger of confusion because
you can tell them apart by looking at how many names/variables it takes.)

According to the above templates, this L3 -sentence can be trans-

lated as “for each x and for each y, if x is odd and y is odd, then x times y
is odd”. No matter how unnatural this quasi-English translation seems, you
can get a sense of what the L3 -sentence says. Based on this sense, you can
translate the quasi-English sentence into a more natural English sentence as
“the product of two odd numbers is also odd”.
Another example: let’s translate −∃x∃y((P x ∧ P y) ∧ P xy) by way
of a quasi-English sentence. (Here, the one-place predicate P x means “x is
prime” and the two-place predicate P xy means “x times y is prime”.)
Quasi-English Translation: It is not the case that there is at
least one x and there is at least one y such that x is prime, y is prime,
and x times y is prime.
More Natural English Translation: The product of two prime
numbers is never prime.
Yet another example: ∀x∀y(Lxy → Lyx). (Here, Lxy is our now-
familiar predicate “x loves y”.)
Quasi-English Translation: For each x and for each y, if x loves
y, then y loves x.
More Natural English Translation: Love always comes to fruition.

88
3.1.1.2 Translating an L3 -Sentence Step by Step
Let’s translate the following L3 -sentences step by step.

∀x(Lxa → ∀y(Lya → Lxy)) (Here, a refers to Alma.)

First, note that in translating the above L3 -sentence, we can utilize

one of the four templates which we’ve studies in Section 2.2.2: All P are
Q ≡ ∀x(P x → Qx). Then, the L3 -sentence can be translated as

All who love Alma has the property ∀y(Lya → Lxy).

And this property ∀y(Lya → Lxy) is also the “all P are Q”-type, so it can
be translated as

All who love Alma is loved by x |= x loves all who love Alma.

In the above, x is nothing but “all who love Alma”. Thus, the final
translation is

All who love Alma love all who love Alma.

A more complicated example: ∃x((P x∧Ex)∧∀y((P y∧Lyx) → Oy))

(P x: x is prime; E: x is even; Lxy: x is larger than y; Oy: x is odd).

First, this L3 -sentence can be translated as

There is at least one even prime number such that ∀y((P y ∧Lyx) →
Oy).

And ∀y((P y ∧ Lyx) → Oy) can be translated as

All prime numbers larger than x is odd.

In the above, x is nothing but even prime number. Thus, what the
original L3 -sentence tells us is

89
 All prime numbers larger than 2 is odd.

Let’s try another type of step-by-step translation. Our target L3 -

sentence is this: ∃x∀y(Lya → Lxy). This time, we translate two components
Lya and Lxy first. These components are, without any difficulty, translated
as “y loves Alma” and “x loves y” respectively. Here, x in the latter trans-
lation should be translated as “someone” because this x is governed by ∃.
And since y is governed by ∀, the latter translation can be translated as
“someone loves everyone”. However, that “someone” doesn’t love everyone
without condition; here, the former translation comes in. This someone loves
everyone if that “everyone” loves Alma. Thus, using a proper relative pro-
noun, we can translate this sentence as “someone loves everyone who loves
Alma”.

3.1.2 Translating English sentences into L3 -Sentences

3.1.2.1 Trial and Error
Let’s translate “someone loves everyone who loves him- or herself” by trial
and error.
First, note that we can break this sentence down into two parts:
“someone loves everyone” and “everyone loves him- or herself”. Also note
that “someone” is expressed with ∃, “’everyone’ with ∀. Thus, these sentences
can be translated as ∃x∀yLxy and ∀yLyy respectively. (Why use y in ∀yLyy?
Well, that’s because we used y for expressing “everyone” whom someone (who
is expressed by x) loves.)
The next task is to combine what we’ve got above. There seem the
following three possible combinations.

1. ∃x∀y(Lxy ∧ Lyy).
2. ∃x∀y(Lxy → Lyy).
3. ∃x∀y(Lyy → Lxy).

Recall that ∃x∀y can be translated into the following quasi-English

phrase: There is at least one x such that for each y . . . . Let’s put the quasi-
English translations of Lxy and Lyy to “. . . ”. Then, we have

90
 There is at least one x such that for each y, x loves y and y loves y.

On first sight, this (quasi-English) translation seems good. How-

ever, this translation claims not only that someone loves all the self-lovers,
but also that everyone in this world is a self-lover. This is not what the
original sentence says.
How about the second one? Its quasi-English translation is this.

There is at least one x such that for each y, if x loves y, y loves y.

On first sight, this translation also seems good. However, the trans-
lation claims that someone loves only self-lovers. This is not what the original
sentence says either.
Lastly, here comes the third sentence. The following is its quasi-
English translation.

There is at least one x such that for each y, if y loves y, x loves y.

According to the above translation, once a person meets the condi-

tion that s/he is a self-lover, then someone loves all of such persons. This is
exactly what the original sentence says.

Lesson to be learned
In “all/some x love all y who . . . ”, “. . . ” is the condition for y to be
loved by x. Thus, the sentence can be paraphrased as “all/some love all
y if y meets the condition . . . ”; and then, this paraphrase is translated as

∀/∃x(. . . → Lxy).

Of course, you can apply this scheme for other translations by replacing
L with another predicate.

Note that in “all/some x love some y who . . . ”, “. . . ” cannot be

taken as a condition for y to be loved by x; “. . . ” is merely a description
about y. Thus, the translation is ∀/∃x(Lxy ∧ . . .).

91
3.1.2.2 Utilizing What We Have at Our Disposal
A slightly more complicated example: Everyone who loves everyone who
loves Alma loves Alma; let’s translate this by utilizing what we have at our
disposal.
First, note that the above sentence has the same form as “all P are
Q” (here, P is “loving everyone who loves Alma” and Q is “loving Alma”);
thus, we can somehow utilize the ∀x(P x → Qx) (see Section 2.2.2). More-
over, in translating “loves everyone who loves Alma”, we can utilize what we
studied in the previous section (loving Alma is a condition for “everyone” to
be loved). So, the translation is

∀x(∀y(Lya → Lxy) → Lxa).

If what we have is “someone who loves everyone who loves Alma

loves Alma”, we can utilize the “some P are Q” scheme. Thus, the transla-
tion is

∃x(∀y(Lya → Lxy) ∧ Lxa).

3.1.2.3 Translating Step by Step

Last example: Everyone who loves Alma loves someone who loves Alma.
We’re gonna translate this step by step.
First, we translate the above as follows. (Here, we apply the “all P
are Q” scheme.)

∀x(Lxa → x loves someone who loves Alma)

Then we can translate it as

∀x(Lxa → There’s someone who loves Alma and x loves that person)

And finally,

∀x(Lxa → ∃y(Lya ∧ Lxy))

92
3.1.2.4 Introducing the Templates
As we’ve seen in the above, there are several ways to approach translation
problems. In what follows, I’ll give you some templates for L3 translation.
First, note that the above sentences have some additional descrip-
tions for those who love or/and for those who are loved. Let’s call an addi-
tional description for those who love Dx , that for those who are loved Dy .
Then, we have the following templates.

1. ∀x(Dx → ∀y(Dy → Lxy))

2. ∀x(Dx → ∃y(Dy ∧ Lxy))
3. ∃x(Dx ∧ ∀y(Dy → Lxy))
4. ∃x(Dx ∧ ∃y(Dy ∧ Lxy))

Rough (quasi) translations of the above are:

10 . All with the additional description Dx love all with the additional de-
scription Dy .
20 . All with the additional description Dx love some with the additional
description Dy .
30 . Some with the additional description Dx love all with the additional
description Dy .
0
4 . Some with the additional description Dx love some with the additional
description Dy .

And the basic structures of these sentences are:

100 . All love all.

200 . All love some.
300 . Some love all.
400 . Some love some.

In using these templates, first figure out which basic structure your
sentence has, and use the corresponding template. (If your sentence has
the basic structure “Some love all”, you need to use the template ∃x(Dx ∧
∀y(Dy → Lxy)).)

Now, in “all who love Alma love some who don’t love Alma”, Dx is

93
Lxa (with the name a referring Alma) and Dy is −Lya, and the basic struc-
ture of the sentence is “all love some”; thus, the translation of the sentence is:

∀x(Lxa → ∃y(−Lya ∧ Lxy)).

What if our sentence lacks one of additional descriptions? For ex-

ample, let’s think about “all who love Alma love all” and “some love all who
don’t love Alma”. The former lacks an additional description for those who
are loved (namely, in our case, for y), the latter for those who love; moreover,
the basic structure of the former is “all love all”, the latter “some love all”.
Thus, we get the following:

a. ∀x(Lxa → ∀y(Dy → Lxy))

b. ∃x(Dx ∧ ∀y(−Lya → Lxy))

Now we have to remove the place-holders for additional descriptions

for x and y (namely, Dy in the former, Dx for the latter). But simply remov-
ing those wouldn’t do; we also have to remove the logical connectives which
follow those place-holders Dx and Dy . Thus, we get the following:

a0 . ∀x(Lxa → ∀y(Lxy))
b0 . ∃x(∀y(−Lya → Lxy))

They look good but there are unnecessary brackets in ∀y(Lxy) (of
the former sentence) and (∀y(−Lya → Lxy)) (of the latter); so let’s add a
finishing touch by removing them.

a00 . ∀x(Lxa → ∀yLxy)

b00 . ∃x∀y(−Lya → Lxy)

Of course, replacing L with another predicate, we can translate

sentences whose main verb is not “love(s)”. For example, let’s translate “Ev-
eryone who loves Alma knows everyone who doesn’t love Alma”. With the
predicate K which means “. . . know(s) . . . ”, we can translate the sentence as

∀x(Lxa → ∀y(−Lya → Kxy))

Still, those templates look too complicated? Well, first of all, you

94
don’t have to memorize them; you just have to take a look at this document
when you need them. But you may want to memorize them for the exam
situations; if that’s the case, the following is a small tip.

• First, memorize Qx(Dx C1 Qy(Dy C2 P xy)). (Replace P with an

appropriate predicate for your sentence.)
• If Qx is ∀x, C1 is →; if Qx is ∃x, C1 is ∧. (You should be able to mem-
orize this easily because the universal quantifier is usually associated
with →, and the existential usually with ∧.)
• If Qy is ∀y, C2 is →; if Qy is ∃y, C2 is ∧.

3.1.3 Problems
1. Translate the following L3 -sentences into English sentences using the fol-
lowing keys: Ex: x is even; Exy: x times y is even; Ox: x is odd; Oxy: x
times y is odd; Sxy: x plus y is even; P x: x is prime; Lxy: x is larger than y.
1. ∀x(Ex → ∀yExy)
2. ∀x∀y((Ox ∧ Oy) → Oxy)
3. ∀x∀y(Sxy → ((Ex ∧ Ey) ∨ (Ox ∧ Oy)))
4. ∀x((P x ∧ ∃y(P y ∧ Lxy)) → Ox)
5. −∃x(P y ∧ ∀y(P x → Lyx))

2. Translate the following sentences.

1. Alma loves everyone who loves her.
2. Everyone who knows Alma loves her.
3. Someone loves everyone who loves him- or herself.
4. Everyone who loves Alma knows everyone who doesn’t love Alma.
5. Everyone who loves someone loves someone who loves someone.
6. Everyone who loves everyone who loves Alma knows Alma.

3. Translate the following English sentences into L3 -sentences using the fol-
lowing keys: z: 0; Gxy: x > y; Lxy: y > x; Exy: x = y.
1. For every number there is a greater number.
2. Every number other than 0 is greater than some number.
3. 0 is the one and only number having the property that no number is
less than it.

95
4. Using Lxy in the above question, express = and 6=. (Of course, you cannot
use Exy here.)

3.2 Interpretation of L3-Sentences

Basically, you can interpret an L3 -sentence in the way which is described in
Section 2.3. And as in the cases for L2 -interpretations, there are two types of
problems: deciding a truth value of a sentence under a given interpretation
and providing an interpretation which makes a given sentence true or false.
Let’s see these types of problems one by one.

3.2.1 Deciding a Truth Value of a Sentence under a

Given Interpretation
If the sentence you’re dealing with is a simple sentence like ∀x∀yLxy or
∃x∀yLxy, there should be no problem in deciding its truth value under a
given interpretation; so, let’s deal with slightly more complicated examples
in what follows.

∀x∃y−Lxy
Domain = {1, 2, 3}
v(L) = {h1, 1i, h2, 1i, h2, 2i, h3, 3i}

Before you start deciding its truth value, you should try to figure
out what the sentence means. In this case, the meaning of the sentence is
easy to figure out: For each person, there’s at least one person s/he doesn’t
love. According to the above interpretation, the person 1 doesn’t love 2 and
3, 2 doesn’t love 3, and 3 doesn’t love 1 and 2. Thus, in the above interpre-
tation, ∀x∃y−Lxy is going to be true.

What if we have the following interpretation for ∀x∃y−Lxy?

v(L) = {h2, 1i, h2, 2i, h2, 3i, h3, 3i}

According to the above interpretation, the person 2 loves everyone in the

domain; thus, the sentence is going to be false under this interpretation.

96
 ∃x∀y(Lxy → Lyx)
Domain = {1, 2, 3}
v(L) = {h1, 1i, h2, 1i, h3, 1i, h3, 2i}

The meaning of the above sentence is: There’s someone whose love
is always reciprocated. The meaning doesn’t ring a bell? Then, try the
following method.
First, recall that an existential sentence can be thought of as a dis-
junction. Thus, the sentence can be transformed into

(∀y(L 1 y → Ly 1 ) ∨ ∀y(L 2 y → Ly 2 ) ∨ ∀y(L 3 y → Ly 3 ))

The existence of h1, 1i in the extension of L makes the first disjunct

(∀y(L 1 y → Ly 1 )) true; thus, the sentence is going to be true in the above
interpretation.

∃x∀y(Rxy ↔ x = y)
Domain = {1, 2}
v(R) = {h1, 2i}

The meaning of the sentence is unclear. (We don’t even know what
R means!) Still, if you can figure out its truth value without further ado,
that’s terrific; skip to the next section. But if you can’t, first transform it
into a disjunction.

(∀y(R 1 y ↔ 1 = y) ∨ ∀y(R 2 y ↔ 2 = y))

If you’re still not so sure, keep transforming it; turn the universal
sentences into conjunctions.

(((R 1 1 ↔ 1 = 1 ) ∧ (R 1 2 ↔ 1 = 2 ))∨
∀y((R 2 1 ↔ 2 = 1 ) ∧ (R 2 2 ↔ 2 = 2 )))

Then, assign a truth value to each R-sentence; since the only mem-
ber in the extension of R is h1, 2i, all R-sentences except R 1 2 are false.

97
 (((R 1 1 ↔ 1 = 1 ) ∧ (R 1 2 ↔ 1 = 2 ))∨
| {z } | {z }
F T
∀y((R 2 1 ↔ 2 = 1 ) ∧ (R 2 2 ↔ 2 = 2 )))
| {z } | {z }
F F

Next, assign a truth value to each =-sentence.

(((R 1 1 ↔ 1 = 1 ) ∧ (R 1 2 ↔ 1 = 2 ))∨
| {z } | {z } | {z } | {z }
F T T F
∀y((R 2 1 ↔ 2 = 1 ) ∧ (R 2 2 ↔ 2 = 2 )))
| {z } | {z } | {z } | {z }
F F F T

Finally, assign a truth value to each biconditional. (If you’re uncer-

tain about how to assign a truth value to a biconditional, see 1.2.5.)

(((R 1 1 ↔ 1 = 1 ) ∧ (R 1 2 ↔ 1 = 2 ))∨
| {z } | {z } | {z } | {z }
F T T F
| {z } | {z }
F F
∀y((R 2 1 ↔ 2 = 1 ) ∧ (R 2 2 ↔ 2 = 2 )))
| {z } | {z } | {z } | {z }
F F F T
| {z } | {z }
T F

At this point, the truth value of the above sentence should be clear.

3.2.2 Providing an Interpretation Which Makes a Given

Sentence True or False
Let’s consider ∀x∀y∀z((Lxy ∧ Lyz) → Lxz) and provide an interpretation
which makes the sentence true.
Suppose we are given {1, 2} as the domain; and further suppose we
have h1, 2i and h2, 1i in the extension of L; then, when x ranges over 1, y
over 2, and z over 1, the antecedent of the conditional ((Lxy ∧ Lyz)) is going
to be true. Thus, in order to make the sentence true, the extension should
contain h1, 1i as well for making the consequent (Lxz) true.
Is that all? No; when x ranges over 2, y over 1, and z over 2, the
antecedent is going to be true as well. Thus, we also need to include h2, 2i
to the extension. So, one of the extensions which make the sentence true is:
{h1, 2i, h2, 1i, h1, 1i, h2, 2i}, all the possible ordered pairs which are comprised
of the members of the domain.

98
 How about an interpretation which makes the sentence false? Let’s
follow the way described in Section 2.3.3.2.
First, let’s negate the sentence and transform it.

−∀x∀y∀z((Lxy ∧ Lyz) → Lxz) ≡ ∃x∃y∃z−((Lxy ∧ Lyz) → Lxz)

≡ ∃x∃y∃z−(−(Lxy ∧ Lyz) ∨ Lxz)
≡ ∃x∃y∃z(−−(Lxy ∧ Lyz) ∧ −Lxz)
≡ ∃x∃y∃z((Lxy ∧ Lyz) ∧ −Lxz)

Then, if there’s at least one configuration of x, y, z which makes Lxy

and Lyz true but Lxz false, we’re done. From the above consideration, we
know that the ordered pairs h1, 2i and h2, 1i makes both Lxy and Lyz; and
if the extension lacks the ordered pair h1, 1i, that makes Lxz false. Thus,
one of the extensions which make the sentence false is: {h1, 2i, h2, 1i}

3.2.3 Providing One Interpretation for Two Sentences

There’s yet another type of interpretation questions. In this type of questions,
you provide one interpretation for two sentences, and your interpretation
should make one sentence true and the other false. For example, let’s provide
an interpretation for ∃x∀yLxy and ∀y∃xLxy.
For simple sentences like ∃x∀yLxy or ∀y∃xLxy, you can easily fig-
ure out what these sentences mean, and based on the meanings of sentences,
you provide an interpretation which makes one sentence true and the other
false. In our example, the meaning of ∃x∀yLxy is “there’s at least one object
x which bears the relation L for all objects y” (if we take L as the predicate
“. . . loves . . . ”, the sentence just means that some love all); and the meaning
of ∀y∃xLxy is “for each object y there’s at least one object x which bears
the relation L to y” (or more concretely, “everyone is loved by someone”).
Thus, one of the interpretations which makes one sentence (∀y∃xLxy) true
and the other (∃x∀yLxy) false is

Domain = {1, 2, 3}
v(L) = {h1, 1i, h2, 2i, h3, 3i}.

What if you can’t figure out the meaning of sentences easily? For
example, the meanings of ∃x(Lxa → F a) and (∃xLxa → F a) are bit hard

99
to figure out. Then, write a truth tree for them as follows.

1. X ∃x(Lxa → F a) One of the sentences

2. X − (∃xLxa → F a) Negation of the other
3. X ∃xLxa Rule 8 to Line 2
4. −F a Rule 8 to Line 2
5. X (Lba → F a) EI to Line 1

6. −Lba Fa Rule 7 to Line 5

7. Lca × EI to Line 3

From the above tree, we can construct an interpretation which

makes two sentences in the initial list true; and such an interpretation makes
∃x(Lxa → F a) true and (∃xLxa → F a) false. This is exactly what we need.

Domain = {1, 2, 3}
v(a) = 1
v(b) = 2
v(c) = 3
v(L) = {h3, 1i}
v(F ) = ∅

(Note that if we start with the initial list {−∃x(Lxa → F a), (∃xLxa → F a)},
the tree is closed. So, if you tried this method and ended up with the closed
tree, don’t be discouraged; just start over by negating the other sentence.)

3.2.4 Problems
1.
Determine the truth values of the following sentences under the given inter-
pretations.

1. ∃x∀y−Lxy
Domain = {1, 2, 3}
v(L) = {h2, 1i, h2, 2i, h3, 2i, h3, 3i}

100
 2. ∀x∃y(Lxy → Lyx)
Domain = {1, 2, 3}
v(L) = {h1, 1i, h1, 2i, h2, 1i, h3, 3i}

3. ∃x∀y(Lxy → Lyx)
Domain = {1, 2, 3}
v(L) = {h1, 2i, h2, 3i, h3, 1i}

4. ∃x∀y(Rxy ↔ x = y)
Domain = {1, 2}
v(R) = {h2, 2i}

2.
For each of the following sentences specify an interpretation in which it is true
and another interpretation in which it is false. You can set up the domain
for each case freely.
In constructing an interpretation, try not to use the empty set or
the domain itself unless doing so is absolutely necessary.

1. ∀x∀y(Lxy → −Lyx)
2. −∃x∀y(Lxy ∧ Lyx)
3. ∀x(∀y(Kay → Kxy) → Kxa) (a is a name)
4. −∃x(Lax ∧ ∀y(Kay → Kxy)) (a is a name)
5. ∀x∀y∀z((Rxy ∧ Ryz) → Rxz)

3.
For each of the following pairs of sentences, construct an interpretation which
makes one sentence true but the other false.

1. ∀x∀y(Gyx ∨ Gxy), ∀x∀y(Gxx ∨ Gxy)

2. ∃x(Bx ∧ ∀yDyx), ∀x(Bx → ∀yDyx)

3.3 Truth Trees for L3

The rules are just the same as ones described in 2.4. In this section, we’re
gonna see some examples of truth trees for L3 .

101
3.3.1 Testing the satisfiability of a sentence
Let’s test the satisfiability of (∃x∀x(Dx → Hxz) → ∀x(Dx → ∃zHxz)). To
test the satisfiability of a sentence, we write a truth tree for the sentence
itself. If there is at least one finished open path, the sentence is satisfiable.

1. X (∃z∀x(Dx → Hxz) → ∀x(Dx → ∃zHxz))

2. X − ∃z∀x(Dx → Hxz) ∀x(Dx → ∃zHxz)

3. ∀z∃x−(Dx → Hxz) Rules 13 and 14 to Line 2
4. X ∃x−(Dx → Hxa) Rule 11 to Line 3
5. X − (Db → Hba) Rules 12 to Line 4
6. Db Rule 8 to Line 5
7. −Hba Rule 8 to Line 5

At this point, we notice that there’s nothing we can do for closing

the left path. No matter how many times we instantiate ∀z∃x−(Dx → Hxz),
all we get are the sentences of the forms “D . . .” and “−H . . .”; we’ll never
find any contradictory sentence with Db or −Hba. Thus, the sentence is
satisfiable.
And from the above finished open path, we can construct an inter-
pretation which makes the sentence true. There are two names in the left
path; this means that our domain should be comprised of two object. Let
our domain be {1, 2}, and let a and b be the names for 1 and 2 respectively.
We have Db as a line by itself; thus, the extension of D has to be {2}. On
the other hand, there’s no line in which a sentence of the form H . . . appears
as a line by itself; this means that the extension of H is empty. Thus, the
following interpretation makes the sentence true.

Domain = {1, 2}
Extension of a: 1
Extension of b: 2
Extension of D: {2}
Extension of H: ∅

102
3.3.2 Testing the Validity of a Sentence
Now we know that (∃x∀x(Dx → Hxz) → ∀x(Dx → ∃zHxz)) is satisfiable.
Is it valid? To test the validity of a sentence, we need to write a truth tree
for the negation of the sentence. If the tree is closed, the sentence is valid.

1. X − (∃z∀x(Dx → Hxz) → ∀x(Dx → ∃zHxz))

2. X ∃z∀x(Dx → Hxz) Rule 8 to Line 1
3. X − ∀x(Dx → ∃zHxz) Rule 8 to Line 1
4. X ∃x−(Dx → ∃zHxz) Rule 13 to Line 3
5. X − (Da → ∃zHaz) Rule 12 to Line 4
6. Da Rule 8 to Line 5
7. X − ∃zHaz Rule 8 to Line 5
8. ∀z−Haz Rule 14 to Line 7
9. ∀x(Dx → Hxb) Rule 12 to Line 2
10. X (Da → Hab) Rule 11 to Line 9

11. −Da Hab

12. × −Hab Rule 11 to Line 8
×

All the paths are closed; the sentence is valid.

3.3.3 Testing the Satisfiability, Again

Let’s test the satisfiability of (∀x∃y(F x → Gy) ↔ (∃xF x ∧ ∀y−Gy)).

103
1. X (∀x∃y(F x → Gy) ↔ (∃xF x ∧ ∀y−Gy))

2. ∀x∃y(F x → Gy) −∀x∃y(F x → Gy) Rule 9 to Line 1

3. X (∃xF x ∧ ∀y−Gy) −(∃xF x ∧ ∀y−Gy) Rule 9 to Line 1
4. X ∃xF x Rule 3 to Line 3
5. ∀y−Gy Rule 3 to Line 3
6. Fa Rule 12 to Line 4
7. X ∃y(F a → Gy) Rule 11 to Line 2
8. X (F a → Gb) Rule 12 to Line 7

9. −F a Gb Rule 7 to Line 8
10. × −Gb Rule 11 to Line 5
×

The left path is closed. Now let’s move on to the right path.

2. X − ∀x∃y(F x → Gy) Rule 9 to Line 1

3. X − (∃xF x ∧ ∀y−Gy) Rule 9 to Line 1
4. X ∃x∀y−(F x → Gy) Rules 13 and 14 to Line 2
5. ∀y−(F a → Gy) Rule 12 to Line 4

6. X − ∃xF x X − ∀y−Gy Rule 8 to Line 3

7. ∀x−F x Rule 14 to Line 6
8. X − (F a → Ga) Rule 11 to Line 5
9. Fa Rule 8 to Line 8
10. −Ga Rule 8 to Line 8
11. −F a Rule 11 to Line 7
12. × X ∃yGy Rules 13 and 2 to Line 6
13. Gb Rule 12 to Line 12
14. X − (F a → Gb) Rule 11 to Line 5)
15. Fa Rule 8 to Line 14
16. −Gb Rule 8 to Line 14
17. ×

All the paths are closed; therefore, the sentence is unsatisfiable.

104
 Do you want to know when the sentence is going to be false? If so,
write a truth tree for the negation of the sentence.

1. X − (∀x∃y(F x → Gy) ↔ (∃xF x ∧ ∀y−Gy))

2. ∀x∃y(F x → Gy) −∀x∃y(F x → Gy) Rule 10 to Line 1

3. X − (∃xF x ∧ ∀y−Gy) (∃xF x ∧ ∀y−Gy) Rule 10 to Line 1

4. X − ∃xF x −∀y−Gy Rule 4 to Line 3

5. ∀x−F x Rule 13 to Line 4
6. X ∃y(F a → Gy) Rule 11 to Line 2
7. X (F a → Gb) Rule 12 to Line 6

8. −F a Gb Rule 7 to Line 7
9. −F a Rule 11 to Line 5

The left-most path is (kinda) finished and open. (Why “kinda”

finished? The reason is as follows. Every time we instantiate the univer-
sal sentence ∀x∃y(F x → Gy), we’re gonna have a new name; and ∀x−F x
doesn’t do any good for closing the path with a new name.) At this point,
there are two names in the path: a and b. So, our domain is comprised of
two members {1, 2}. (And of course, a refers to 1, b to 2.) Moreover, no
predicate appears as a line by itself. Therefore, we can set up the extensions
of both predicates as empty. The following interpretation makes the sentence
false.

Domain = {1, 2}
Extension of a: 1
Extension of b: 2
Extension of F : ∅
Extension of G: ∅

(The above tree also tells us that ∀x∃y(F x → Gy) and (∃xF x ∧
∀y−Gy) are not logically equivalent.)

105
3.3.4 Testing the Validity of an Argument
Now let’s test the validity of the following argument.

∀x(∃yLxy → ∀zLzx)
∃x∃yLxy
∀x∀yLxy
To test the validity of an argument, we write a tree for the premises
themselves and the negation of the conclusion.

1. ∀x(∃yLxy → ∀zLzx)
2. X ∃x∃yLxy
3. X − ∀x∀yLxy
4. X ∃x − ∀yLxy Rule 13 to Line 3
5. X − ∀yLay Rule 12 to Line 4
6. X ∃y−Lay Rule 13 to Line 5
7. −Lab Rule 12 to Line 6
8. X ∃yLcy Rule 12 to Line 2
9. Lcd Rule 12 to Line 8
10. X (∃yLby → ∀zLzb) Rule 11 to Line 1

11. X − ∃yLby ∀zLzb Rule 7 to Line 10

12. ∀y−Lby Lab Rule 14 to Line 11; Rule 11 to Line 11
13. X (∃yLcy → ∀zLzc) × Rule 11 to Line 1

14. X − ∃yLcy ∀zLzc Rule 7 to Line 13

15. ∀y−Lcy −Lbc Rule 14 to Line 15; Rule 11 to 12
16. −Lcd Lbc Rule 11 to Line 16; Rule 11 to Line 14
× ×

The tree is closed; the argument is valid.

3.3.5 Testing the Equivalence between Sentences

Let’s figure out whether ∀x(F x → ∃yGya) and (∃xF x → ∃yGya) are logi-
cally equivalent.

106
1. X − (∀x(F x → ∃yGya) ↔ (∃xF x → ∃yGya))

2. ∀x(F x → ∃yGya) −∀x(F x → ∃yGya) Rule 10 to Line 1

3. X − (∃xF x → ∃yGya) (∃xF x → ∃yGya) Rule 10 to Line 1
4. X ∃xF x Rule 8 to Line 3
5. X − ∃yGya Rule 8 to Line 3
6. ∀y−Gya Rule 14 to Line 5
7. Fb Rule 12 to Line 4
8. X (F b → ∃yGya) Rule 11 to Line 2

9. −F b X ∃yGya Rule 7 to Line 8

10. × Gca Rule 12 to Line 9
11. −Gca Rule 11 to Line 6
×

The left side is closed. Let’s test the right side.

2. X − ∀x(F x → ∃yGya) Rule 10 to Line 1

3. X (∃xF x → ∃yGya) Rule 10 to Line 1
4. X ∃x−(F x → ∃yGya) Rule 13 to Line 2
5. X − (F a → ∃yGya) Rule 12 to Line 4
6. Fa Rule 8 to Line 5
7. X − ∃yGya Rule 8 to Line 5
8. ∀y−Gya Rule 14 to Line 7

9. X − ∃xF x X ∃yGya Rule 7 to Line 3

10. ∀x−F x Gba Rule 14 to Line 9; Rule 12 to Line 9
11. −F a −Gba Rule 11 to Line 10; Rule 11 to Line 8
× ×

The right path is also closed. Therefore, ∀x(F x → ∃yGya) and

(∃xF x → ∃yGya) are logically equivalent.

107
Chapter 4

Further Extension of L3

We’re gonna add a finishing touch to our subject by introducing two more
concepts: identity and function. This addition makes our language L3 what
is usually called first-order logic.

4.1 Identity
Identity is just a predicate; as such, it takes names and gives us back a
sentence. And its meaning is what you exactly expect: Something is identical
to something. For this sole purpose, we introduce a new symbol =. Different
from other predicates we’ve encountered so far, we adopt conventional infix
notation; namely, a = b means that a is identical to b.
As a starter, let’s take a look at the following simple argument.
a=b
b=c
a=c
The argument claims that if a is identical to b and b is identical to
c, then a is identical to c; in short, the identity relation is transitive. The
truth of it seems pretty obvious but we logicians never trust any claim unless
there’s a proof of it. So let’s prove it. The following are the truth-tree rules
for identity.

108
 15. a 6= a 16. a=b 17. a=b
× ...a... ...b...
...b... ...a...

Note that we don’t check off the identity sentence a = b in Rules 16 and
17; we can apply Rules 16 and 17 as many times as we want.

In the rule 15, a 6= a is just another notation for −a = a. Then, the

rule tells us that we can close the path where a sentence of the form a 6= a
appears. The rules 16 and 17 tells us that, if we have an identity sentence
a = b in the path, we can replace a with b (resp. b with a) in a sentence.
For example, if we have a = b and Lab in the same path, we can get Laa by
replacing b with a in Lab. And from Laa, we can get (or recover) Lab (yes,
you don’t have to replace both occurrences of a with b).
Now we’re ready for writing a truth tree for the above argument.
Since we want to test the validity of the argument, we need to start with the
premises and the negation of the conclusion of course.

1. a=b
2. b=c
3. a 6= c
4. a=c Rule 17 to Lines 1 and 2
×

Thus, as we expected, the argument is valid.

Can the above argument be generalized for any members of the
domain? This generalized claim is expressed in one sentence: ∀x∀y∀z((x =
y ∧ y = z) → x = z). If this sentence is proven to be valid, it would follow
that the identity relation is actually transitive. In order to test the validity
of this sentence, we start our tree with the negation of the sentence.

109
1. X − ∀x∀y∀z((x = y ∧ y = z) → x = z)
2. X ∃x∃y∃z−((x = y ∧ y = z) → x = z) 3 NQs to Line 1
3. X − ((a = b ∧ b = c) → a = c) 3 EIs to Line 2
4. X (a = b ∧ b = c) Rule 8 to Line 3
5. a 6= c Rule 8 to Line 3
6. a=b Rule 3 to Line 4
7. b=c Rule 3 to Line 4
8. a=c Rule 17 to Lines 6 and 7
×

The tree is closed; thus, transitivity does actually hold for the iden-
tity relation between any three members.
Now let’s figure out whether the negated version of the above claim
holds. The sentence the validity of which we’re gonna test is this: ∀x∀y∀z((x 6=
y ∧ y 6= z) → x 6= z).

1. X − ∀x∀y∀z((x 6= y ∧ y 6= z) → x 6= z)
2. X ∃x∃y∃z−((x 6= y ∧ y 6= z) → x 6= z) 3 NQs to Line 1
3. X − ((a 6= b ∧ b 6= c) → a 6= c) 3 EIs to Line 2
4. (a 6= b ∧ b 6= c) Rule 8 to Line 3
5. X − a 6= c Rule 8 to Line 3
6. a=c Rule 2 to Line 5
7. a 6= b Rule 3 to Line 4
8. b 6= c Rule 3 to Line 4
9. c 6= b Rule 16 to Lines 6 and 7
10. b 6= a Rule 17 to Lines 6 and 8

At this point, there’s nothing we can do any further; we did all we

could. Thus, the sentence is not valid. Let’s construct an interpretation on
which the sentence is going to be false.
First note that there are three names a, b, and c, so let’s set up our
domain as {1, 2, 3} and the extensions of a, b, c as 1, 2, 3 respectively. Now
the only atomic sentence which appears as a line by itself is a = c. This sen-
tence tells us that the extensions of a and c should refer to the same object
in the domain; we have to change the extension of either a or c to capture
this fact. So let’s change the extension of c to 1. What about the extension
of =? Well, since that is obvious enough, we usually omit the extension of

110
=. (If you’re a perfectionist, of course you can write down the extension; in
our case, it should be {h1, 1i, h2, 2i, h3, 3i}.) Thus, one of the interpretations
which makes the sentence false is:

Domain : {1, 2, 3}
Extension of a : 1
Extension of b : 2
Extension of c : 1.

In the above interpretation, although 1 is not identical to 2 and 2

is not identical to 1, 1 is identical to 1.

Let’s do two more examples in which predicates appear. First, con-

sider the following argument.

∀x∀y(F xy ∨ F yx)
a=b
∀x(F xa ∨ F bx)
For the validity checking, our tree of course starts with the premises
themselves and the negation of the conclusion.

1. ∀x∀y(F xy ∨ F yx)
2. a=b
3. X − ∀x(F xa ∨ F bx)
4. X ∃x−(F xa ∨ F bx) NQ to Line 3
5. X − (F ca ∨ F bc) EI to Line 4
6. −F ca Rule 6 to Line 5
7. −F bc Rule 6 to Line 5
8. ∀y(F by ∨ F yb) UI to Line 1
9. X (F bc ∨ F cb) UI to Line 9

10. F bc F cb Rule 5 to Line 9

11. × F ca Rule 17 to Lines 2 and 10
×

The tree is closed; the argument is valid.

111
 Next, the following argument.

∃xF xa
∀x(x = a → x = b)
∃xF xx

1. X ∃xF xa
2. ∀x(x = a → x = b)
3. X − ∃xF xx
4. ∀x − F xx NQ to Line 3
5. F ca EI to Line 1
6. X (a = a → a = b) UI to Line 2
7. X (b = a → b = b) UI to Line 2
8. X (c = a → c = b) UI to Line 2

9. a 6= a a=b Rule 7 to Line 6

×
10. b 6= a b=b Rule 7 to Line 7

11. c 6= a c=b Rule 7 to Line 8

12. −F cc −F cc UI to Line 4
13. −F bb c=a Rule 17 to Lines 9 and 11
14. −F aa −F ca Rule 16 to Lines 12 and 13
15. b 6= b × Rule 16 to Lines 9 and 10
×

The tree is finished (we instantiated all universal sentences with all
names); still, the second path from the left remains open (in order to bring
about a contradiction, we need −F ca but it’s impossible because a line of
the path clearly states that c is not equal to a (Line 11)).
We have two names in the path but two of them (a and b) are iden-
tical; thus, we can set up the domain and the extensions of the names as

Domain = {1, 2}
v(a) = 1
v(b) = 1

112
 v(c) = 2

For the extension of F , there’s only one line in which an F -sentence

appears by itself (Line 5); thus, the extension of F is

v(F ) = {2, 1}

4.1.1 Problems
Determine whether each of the following sentences is valid, unsatisfiable, or
neither of them by writing a truth tree. If the sentence is valid or unsatisfi-
able, construct an interpretation from your open path which makes it true or
false. If it’s neither of them, provide two interpretation one of which makes
it true and the other false.

1. (∀x x = a → (∃xF x → ∀xF x))

2. ∀x∀y x 6= y
3. ∃x∃y x 6= y
4. ∀x∀y((F x ↔ F y) → x = y)
5. ((∃xGax → −∃xGxa) → ∀x(Gxa → x 6= a))

4.2 Numerical Expressions

One of the benefits of introducing the identity predicate is that we can express
numerical expressions like “at least”, “at most”, or “exactly” with =. Let’s
see how in the below.

4.2.1 At Least
At least one
As we know (and actually you should know), we can express the “at least
one” type of expressions without the help of the identity predicate. For ex-
ample, “there’s at least one P ” can be expressed as follows.

∃xP x.

113
 We can also express the same sentence with the help of =.

∃x∀y(x = y → P y).

It might be a bit hard to understand why the above is equivalent to

∃xP x. Of course, you can convince yourself by writing a truth tree for their
equivalence. But here, let’s try to understand why conceptually.
First, let’s translate the above L3 -sentence into a quasi-English sen-
tence as follows. (If you’re not so sure about how to translate an L3 -sentence
into a quasi-English sentence, see Section 3.1.1.1)

There’s at least one x such that for each y, if x is identical to y, y

is P .

Here, note that a universal sentence can be thought of as a con-

junction; if a refers to the object referred to by x, and if a1 , . . . , an refer
to all the objects of thedomain, the above sentence can be thought of as
((a = a1 → P a1 ) ∧ . . . ∧ (a = an → P an )). Therefore, at least one of
a = a1 , . . . , a = an has to be true in order for the sentence to be true. And
actually, there’s always at least one object to which the object a refers to is
identical: the object a refers to.

At least two
Then, how about the “at least two” expressions? The first thought might be
that it’s enough to concatenate two existential sentences, namely, (∃xP x ∧
∃yP y) for “there are at least two P s”. However, (∃xP x ∧ ∃yP y) is going to
be true even when the extension of P contains just one member. We need
something more.
Although it’s not quite right, the basic idea above is on the right
track; we need two existential sentences to express the “at least two” sen-
tences. What we need further is to make sure that the references of these
existential sentences don’t refer to the same object. Thus, the right way to
express “there are at least two P s” is

∃x∃y(P x ∧ P y ∧ x 6= y).

At least three
We can express the “at least three” sentences in a very similar manner as

114
above; we need three existential sentences and make sure that the references
of these existential sentences don’t refer to the same thing. Thus, “there are
at least three P s” can be expressed as

∃x∃y∃z(P x ∧ P y ∧ P z ∧ x 6= y ∧ y 6= z ∧ z 6= x).

4.2.2 At Most
At most one
The phrase “there is at most one . . . ” can be paraphrased as “it’s not the
case that there are at least two . . . ”. And we know that how to express “at
least two” (and of course we also know how to express “it’s not the case that
. . . ”). Thus, “there is at most one P ” can be expressed as

−∃x∃y(P x ∧ P y ∧ x 6= y).

The above sentence can be transformed into

∀x∀y((P x ∧ P y) → x = y). (Verify this.)

The literal translation of the above sentence is “for any x and y,

if x and y are both P , then x is identical to y”. (In this form, it might be
clearer than the above negated existential sentence that there doesn’t have
to be any P in order for “there is at most one P ” to be true.)
The above sentence can be abbreviated further as

∃x∀y(P y → y = x).

At most two
In a similar fashion as above, the phrase “there are at most two . . . ” can be
paraphrased as “it’s not the case that there are at least three . . . ”. Thus,
“there are at most two P s” can be expressed as

−∃x∃y∃z(P x ∧ P y ∧ P z ∧ x 6= y ∧ y 6= z ∧ z 6= x).

The above sentence can be transformed into the following universal

sentence.

115
 ∀x∀y∀z((P x ∧ P y ∧ P z) → (x = y ∨ y = z ∨ z = x)). (Verify this.)

Again, in order for the sentence to be true, there doesn’t have to

be any P .

At most three
Let’s express a “there are at most three . . . ” sentence directly in the universal
sentential form.
From the above examples, we know that in order to express the
“there are at most n . . . ” sentences we need n + 1 universal quantifiers and
have to make sure that at least one pair of variables (instantiations of vari-
ables, to be exact) refers to the same object. Thus, “there are at most three
P s” can be expressed as

∀w∀x∀y∀z((P w ∧ P x ∧ P y ∧ P z) → (w = x ∨ w = y ∨ w = z ∨ x =
y ∨ x = z ∨ y = z)).

4.2.3 Exactly
The “exactly n” type of sentences can be expressed with the combination of
the “at least n” and “at most n” types of expressions. Once you understand
how to express the “at least” and “at most” sentences, it should be easy to
express the “exactly” sentences.

Exactly one
The “exactly one” sentences are expressed with the combination of the “at
least one” and “at most one” sentences. Thus, “there’s exactly one P ” can
be expressed as

(∃xP x ∧ −∃x∃y(P x ∧ P y ∧ x 6= y)).

We know that the second conjunct can be transformed into ∀x∀y((P x∧

P y) → x = y); thus, the sentence can be rewritten as

(∃xP x ∧ ∀x∀y((P x ∧ P y) → x = y)).

116
 Furthermore, we also know that the second conjunct can be abbre-
viated as ∃x∀y(P y → y = x); thus, the sentence can be abbreviated as

(∃xP x ∧ ∃x∀y(P y → y = x)). (This can be abbreviated as ∃x(P x ∧

∀y(P y → y = x)).)

Recall that ∃xP x is equivalent to ∃x∀y(y = x → P y). Thus, we

can rewritten the above as

(∃x∀y(y = x → P y) ∧ ∃x∀y(P y → y = x)).

In the above, we can factor out ∃x∀y in front of the sentence. Thus,
we get

∃x∀y((y = x → P y) ∧ (P y → y = x)).

Note that (y = x → P y) ∧ (P y → y = x) is nothing but (P y ↔

y = x). Thus, “there’s exactly one P ” can be expressed as

∃x∀y(P y ↔ y = x).

Exactly two
In a very similar manner as in the above, we can formalize the expression
“exactly two” as follows.

∃x∃y(P x ∧ P y ∧ x 6= y ∧ ∀z(P z → (z = x ∨ z = y)))

≡ ∃x∃y(x 6= y ∧ ∀z(P z ↔ (z = x ∨ z = y)))

4.2.3.1 Problem
By writing truth trees, show that the following sentences are all equivalent.

1. ∃x∀y(F y ↔ y = x)
2. ∃x(F x ∧ ∀y(F y → y = x))
3. (∃xF x ∧ ∀y∀z((F y ∧ F z) → y = z))

117
4.2.4 Definite Description
When it’s used with a singular noun, the definite article “the” refers to ex-
actly one object. Thus, a sentence where the word “the” appears can be
expressed with the “exactly one” expressions explained above. For example,
“the even prime‘is a number” can be expressed as

∃x(∀y((Ey ∧ P y) ↔ y = x) ∧ N x).

Expressing “The successor of any number is greater than that num-

ber” in L3 is a bit trickier. First, let’s translate it as the following quasi
L3 -sentence.

∀x(N x → the successor of x is greater than x).

And then, all we have to do is to translate “the successor of x is

greater than x”.

∀x(N x → ∃y∀z((Szx ↔ z = y) ∧ Gyx)).

118
 We can summarize how to express a definite description as the fol-
lowing rule.

Russell’s Rule

. . . the P . . . ⇒ ∃x(∀y(P y ↔ y = x) ∧ . . . x . . .)

4.2.5 Summary
To recap:

There is at least one P : ∃xP x; ∃x∀y(y = x → P y).

There are at least two P s: ∃x∃y(P x ∧ P y ∧ x 6= y).

There are at least three P s: ∃x∃y∃z(P x ∧ P y ∧ P z ∧ x 6= y ∧ y 6=

z ∧ z 6= x).

There is at most one P : ∀x∀y((P x ∧ P y) → x = y).

There are at most two P s: ∀x∀y∀z((P x ∧ P y ∧ P z) → (x = y ∨ y =

z ∨ z = x)).

There are at most three P s: ∀w∀x∀y∀x((P w ∧ P x ∧ P y ∧ P z) →

(w = x ∨ w = y ∨ w = z ∨ x = y ∨ x = z ∨ y = z)).

There is exactly one P : ∃x(P x ∧ ∀y(P y → y = x)); or ∃x∀y(P y ↔

y = x)

There are exactly two P s: ∃x∃y(P x ∧ P y ∧ x 6= y ∧ ∀z(P z → (z =

x ∨ z = y))); or ∃x∃y(x 6= y ∧ ∀z(P z ↔ (z = x ∨ z = y)))

4.2.6 Examples
Basically, for translating sentences with numerical expressions, all you have
to do is to take care of translating P in the above summary. However, in
some cases, you need some strategies. Let’s study some of them by translat-
ing some sentences.

119
Alma loves at least two persons.
Translation: ∃x∃y(Lax ∧ Lay ∧ x 6= y)
There should be no problem in translating this; just put Lax and Lay in the
places of P x and P y.

At most one person loves everyone.

Translation: ∀x∀y(∀z(Lxz ∧ Lyz) → x = y)
First, you need to replace P with some expression for “loving everyone”. We
know that “. . . loves everyone” is translated as ∀yL . . . y and those who love
are x and y in our sentence; so, in the places of P x and P y, we put ∀zLxz
and ∀zLyz respectively (you need to use a variable other than x or y for
∀ here), and then factor out ∀z in front of Lxz and Lyz (of course, in this
factoring-out, we need to introduce the brackets).

There are at most two persons who know someone who doesn’t
love Alma.
Translation: ∀x∀y∀z(∃w(−Lwa∧Kxw ∧Kyw ∧Kyz) → (x = y ∨y = z ∨z =
x))
This is an “at most” sentence; so we know that we need three variables for
denoting persons in question. Let these variables be x, y, z. And for these
x, y, z, it is said that they know someone who doesn’t love Alma. Thus, uti-
lizing one of the templates, the situation can be expressed as ∃w(−Lwa ∧
Lxw ∧ Lyw ∧ Lzw); and this is your P .

Everyone knows exactly one person who loves him/her.

Translation: ∀x∃y((Kxy∧Lyx)∧∀z((Kxz∧Kzx) → z = y)); or ∀x∃y∀z((Kxz∧
Lyz) ↔ z = y)
You cannot put ∀x right before (Kxy ∧ Lyx); if you did so, the meaning
of the translation would be “there’s exactly one person who love everyone
and everyone knows that person”. The original sentence doesn’t mean this;
rather, it means that each person knows his or her only lover. Thus, in order
to express this “each” aspect, we need to put ∀x before ∃y.

Exactly two persons know someone who knows everyone who loves
Alma.

120
Translation: ∃x∃y(∃z(∀v(Lva → Kzv)∧Kxz∧Kyz)∧x 6= y∧∀w(∃z(∀v(Lva →
Kzv) ∧ Kwz) → (w = x ∨ w = y))); or ∃x∃y(x 6= y ∧ ∀z(∃v(∀w(Lwa →
Kvw) ∧ Kzv) ↔ (z = x ∨ z = y)))
Essentially, if you can translate the “someone who knows everyone who loves
Alma” part, the rest is just a tedious taking-care of the variables. If we forget
about the variable-conflict for now, the “someone who” part is translated as
∃x∀y(Lya → Kxy); and exactly two persons know this guy x. Thus, the
above translation.

You think these are too tough? Even if so, don’t be discouraged.
What you’ll come across in the real life (I mean, in the exams or assignments)
are much easier than these.

4.2.7 Problems
Translate the following.

1. At least two persons love Alma.

2. Alma loves at most one person.
3. There are at most two persons who don’t love Alma.
4. Exactly one person knows exactly two persons who love Alma.

4.3 Functions
4.3.1 Basics
In our formal logic, a function receives a name (or names) as its input(s)
and returns one and only one name as its output. We call its input(s) an
argument (or arguments) and an output the value.
There’s also another condition which a function has to meet: For
each object of the domain, there has to be the value. Thus, the following
extension of a function f is not legitimate.

Domain : {1, 2}
Extension of f : {h1, 1i, h1, 2i}

121
 The reason why the above is not legitimate is:

1. There are two values for 1 (violating the condition 1).

2. There’s no value for 2 (violating the condition 2).

An example of proper extensions for f would be {h1, 1i, h2, 2i}.

1. For any input(s), a function has to return exactly one value.

2. For each object of the domain, a function has to return a value.

In one sentence: For each object of the domain, a function has to return
exactly one value.

We can think of an n-place function; and in order to explicitly

express we’re taking about an n-place function, we sometimes add a su-
perscript like f n (t1 , . . . , tn ) and write the extension for such a function as
{hht1 , . . . , tn i, valuei}. For example, if g 2 (x, y) is a function expressing the
sum of x and y, its extension would be {hh1, 1i, 2i, hh1, 2i, 3i, . . .}.

4.3.2 Translating with Functions

With functions, we can translate “exactly one” phrases much more easily.
For example, consider the following sentences.

1. Alma has exactly one father.

2. The father of Alma is older than Alma.
3. The father of any person is older than that person.

Translations of these sentences with predicates are as follows. (Here,

we use the predicates P x (x is a person), F xy (x is a father of y), Oxy (x is
older than y), and the name a for Alma.)

10 . ∃x∀y(F ya ↔ y = x)
20 . ∃x(∀y(F ya ↔ y = x) ∧ Oxa)
30 . ∀x(P x → ∃y(∀z(F zx ↔ z = y) ∧ Oyx))

122
 With a function, we can translate these sentences more succinctly.
(Here, we use the function f (x) for “the father of x”.)

100 . ∃xx = f (a)

200 . Of (a)a
300 . ∀x(P x → Of (x)x)

4.3.3 Truth-Tree Method for Functions

By introducing the concept of a function, we need to modify the rules for
the quantifiers a bit, and for that modification, we need to introduce the new
term terms.
Terms

1. Names are terms. Names are also called constants.

2. Variables are terms.

3. If t1 , . . . , tn are terms, so is f (t1 , . . . , tn ).

If a term doesn’t contain any variable, it’s called closed ; if it does, it’s
called open. For example, a, b, f (a), g(a, b) are all closed terms whereas
x, y, f (x), g(x, b), and g(x, y) are all open.

Now, the modified rules for the quantifiers are

Modified EI
If you have ∃x . . . x . . ., you can replace x in it with a new constant.

Modified UI
If you have ∀x . . . x . . ., you can replace x in it with any combination of
names and function symbols which are already in the path where the
universal sentence you’re going to instantiate appears.

The modification to EI is made in order to make clear that we

cannot replace a variable in an existential sentence with a functional form
like f (a). Thus, the rule isn’t essentially changed.
On the other hand, the modification to UI gives us more freedom
in instantiation. For example, let’s suppose we have f (a) and g(b, c) in the

123
path where the universal sentence we’re gonna instantiate appears; then, we
can instantiate the universal sentence not only with f (a) or g(b, c) but also
with any combination of a, b, c, f , and g like f (c), g(a, b), or f (g(c, f (b))).
(However, you seldom want to instantiate a universal sentence with such a
free combination; in most cases, simple forms like f (a) or g(b, c) would do.)

As an example, let’s write a truth tree for testing the validity of

∀x∃y(y = f (x) ∧ ∀z(z = f (x) → z = y)).

1. X − ∀x∃y(y = f (x) ∧ ∀z(z = f (x) → z = y))

2. X ∃x∀y−(y = f (x) ∧ ∀z(z = f (x) → z = y)) 2 NQs to Line 1
3. ∀y−(y = f (a) ∧ ∀z(z = f (a) → z = y)) EI to Line 2
4. −(a = f (a) ∧ ∀z(z = f (a) → z = a)) UI to Line 3

In instantiating ∀y−(y = f (a) ∧ ∀z(z = f (a) → z = y)) for the first

time, we use the simple name a.

1. X − ∀x∃y(y = f (x) ∧ ∀z(z = f (x) → z = y))

2. X ∃x∀y−(y = f (x) ∧ ∀z(z = f (x) → z = y)) 2 NQs to Line 1
3. ∀y−(y = f (a) ∧ ∀z(z = f (a) → z = y)) EI to Line 2
4. X − (a = f (a) ∧ ∀z(z = f (a) → z = a)) UI to Line 3

5. a 6= f (a) X − ∀z(z = f (a) → z = a) Rule 4 to Line 4

6. X ∃z−(z = f (a) → z = a) NQ to Line 5
7. X − (b = f (a) → b = a) EI to Line 5
8. b = f (a) Rule 8 to Line 7
9. b 6= a Rule 8 to Line 7

At this point, we did all we could do except instantiating Line 3

with other terms. So far, we have two names a and b, and one function f ;
thus, we can instantiate ∀y−(y = f (a) ∧ ∀z(z = f (a) → z = y)) with f (a) or
f (b). Let’s instantiate it with f (a). (You write down the following derivation
under both paths.)

124
10. X − (f (a) = f (a) ∧ ∀z(z = f (a) → z = f (a))) UI to Line 3

11. f (a) 6= f (a) X − ∀z(z = f (a) → z = f (a)) Rule 4 to Line 10

12. × X ∃z−(z = f (a) → z = f (a)) NQ to Line 11
13. X − (b = f (a) → b = f (a)) EI to Line 12
14. b = f (a) Rule 8 to Line 13
15. b 6= f (a) Rule 8 to Line 13
×

All the paths are closed; thus, the sentence is valid. (By the way,
this sentence is nothing but the condition a function has to meet.)

By the way, according to some textbooks (for example, see Bergmann

et al., The Logic Book, McGraw-Hill), it’s totally okay to instantiate the line
3 with f (a) in the line 4. Thus, the truth tree can be much shorter as follows.

1. X − ∀x∃y(y = f (x) ∧ ∀z(z = f (x) → z = y))

2. X ∃x∀y−(y = f (x) ∧ ∀z(z = f (x) → z = y)) 2 NQs to Line 1
3. ∀y−(y = f (a) ∧ ∀z(z = f (a) → z = y)) EI to Line 2
4. X − (f (a) = f (a) ∧ ∀z(z = f (a) → z = f (a))) UI to Line 3

5. f (a) 6= f (a) X − ∀z(z = f (a) → z = f (a)) Rule 4 to Line 4

6. × X ∃x−(z = f (a) → z = f (a)) NQ to Line 5
7. X − (b = f (a) → b = f (a)) EI to Line 6
8. b = f (a) Rule 8 to Line 7
9. b 6= f (a) Rule 8 to Line 7
×

The last example: Suppose we’re given the following pair of sen-
tences: −∀x x = f (x) and a 6= f (a). Now let’s find one interpretation which
makes one of the sentences true but the other false. In finding such an inter-
pretation, you can write a truth tree whose initial list is comprised of one of
the sentences and the negation of the other. (See ??.)

125
 1. X − ∀x x = f (x)
2. X − a 6= f (a)
3. a = f (a) Rule 2 to Line 2
4. X ∃x x 6= f (x) NQ to Line 1
5. b 6= f (b) EI to Line 4

All compound sentences are decomposed; the tree is finished and

has an open path. Let’s construct an interpretation from the open path. (See
2.4.4.)
First, collect all the names which appear in your tree and assign a
number to each name sequentially as follows.

Ext(a): 1
Ext(b): 2

These numbers which you just assigned to the names will be the objects of
our domain.
Now, we have to set up the extension for the function f . First,
recall that your function has to be total ; meaning, to each name there has
to be a value of f . Thus, the extension has to look like this.

Ext(f ): {h1, −i, h2, −i}

And according to the sentences in the tree, the value for 1 is 1 itself,
and the value for 2 is not 2. Since our domain has only two objects, there is
only one option for the value for 2: 1. Thus, the extension of f is:

Ext(f ): {h1, 1i, h2, 1i}

Taken the above together, the interpretation which makes one sen-
tence true and the other false is:

Domain: {1, 2}
Ext(a): 1
Ext(b): 2
Ext(f ): {h1, 1i, h2, 1i}.

126
Solutions

Solutions for Problems 1.1.4

1. →
2. ∧
3. ∨
4. →
5. −

Solutions for Problems 1.2.7

1. S1 S2
A B −A (− − A ∧ B) (−A ↔ B) (S1 → S2 )
T T F T F F
T F F F T T
F T T F T T
F F T F F T

2. S1 S2
D E H −D −H (D ∧ E) (−H ∨ S1 ) (−D ∧ S2 )
T T T F F T T F
T T F F T T T F
T F T F F F F F
T F F F T F T F
F T T T F F F F
F T F T T F T T
F E T T F F F F
F E F T T F T T

127
3. S1 S2 S3 S4
A B D −A −B −D (−A ∧ B) (−D ∨ −B) (D ↔ S1 ) −S3 (S4 ∨ S2 )
T T T F F F F F F T T
T T F F F T F T T F T
T F T F T F F T F T T
T F F F T T F T T F T
F T T T F F T F T F F
F T F T F T T T F T T
F F T T T F F T F T T
F F F T T T F T T F T

4. S1 S2 S3 S4
E F J −E −F −J (E ∨ F ) (−E ∧ −F ) (S1 ∧ S2 ) (J ∧ S3 ) (S4 → −J)
T T T F F F T F F F T
T T F F F T T F F F T
T F T F T F T F F F T
T F F F T T T F F F T
F T T T F F T F F F T
F T F T F T T F F F T
F F T T T F F T F F T
F F F T T T F T F F T

5. S1 S2 S3 S4 S5 S6
A B C −A (B ∧ C) (A ↔ S1 ) −S2 (B ↔ S3 ) −S4 (−A ↔ S5 ) −S6
T T T F T T F F T F T
T T F F F F T T F T F
T F T F F F T F T F T
T F F F F F T F T F T
F T T T T F T T F F T
F T F T F T F F T T F
F F T T F T F T F F T
F F F T F T F T F F T

Solutions for Problems 1.3.6

1. Valid/Satisfiable.
2. Valid/Satisfiable.

128
 3. Invalid/Unsatisfiable.
4. Valid/Satisfiable.
5. Valid/Satisfiable.

Solutions for Problems 1.4.1.1

1.

1. In order for this implication to fail, α on the right-hand side has to

be false. However, if α on the right-hand side is false, so is α on the
left-hand side. There’s no way to make α on the left-hand side true
but α on the right-hand side false. Therefore, the implication holds.

2. Suppose that Γ |= α holds but Γ, β |= α fails. In order to make this

happen, α has to be false. Then, Γ has to be false as well; otherwise,
Γ |= α is going to fail. Now, if Γ is false, so is {Γ, β} regardless of the
truth value of β. Then, Γ, β |= α is going to be valid. However, this
is contradictory to our assumption. Therefore, there’s no way to make
Γ |= α hold but Γ, β |= α fail. This proves the statement.

3. Suppose that Γ, ∆ |= β fails. This means that Γ, ∆ are true but β is

false. Now, we’re supposing the truth of Γ |= α and α, ∆ |= β. In order
for the latter to be the case, either α or ∆ has to be true. However,
we’re assuming the truth of ∆. Therefore, α has to be false. However,
if α is false, Γ |= α is going to fail. This contradicts the assumption
that Γ |= α holds. Therefore, if Γ |= α and α, ∆ |= β hold, Γ, ∆ |= β
must hold as well.

4. Suppose that Γ |= (α → β) fails. Then, Γ and α have to be true, and

β has to be false. If so, Γ, α |= β fails as well. This contradicts the
assumption. On the other hand, from the supposition that Γ, α |= β
fails, we can draw the same conclusion. Therefore, the statement holds.

5. Suppose that α |= γ fails. If so, α has to be true and γ has to be false.

Now, we’re assuming the truth of α |= β and β |= γ. If γ is false, β has
to be true. However, if so, α |= β is going to fail. This contradicts the
assumption. Therefore, the statement holds.

129
2.
1. Implication holds.
2. Implication fails. (Counterexample: A=T, B=F, C=T)
3. Implication holds.
4. Implication holds.

Solutions for Problems 1.4.2.1

1. These are all easy. Try to derive a contradiction from the assumption
that the implication doesn’t hold.

2.
1. Correct.
2. Incorrect.
3. Incorrect.
4. Correct.
5. Incorrect.

Solutions for Problems 1.5.1

1.

1. Suppose that the argument is not valid; thus, (α ∨ β) and −α are true,
but β is false. Since (α ∨ β) is true and β is false, α has to be true.
However, if so, −α is going to be false. Contradiction. The argument
is valid.

2. Suppose that the argument is not valid; thus, (α → β) and −β are

true, but −α is false. Since α → β is true and −α is false, β has to
be true. However, if so, β is going to be false. Contradiction. The
argument is valid.

3. Suppose that the argument is not valid; thus, (α → γ), (β → γ), (α∨β)
are all true, but γ is false. Since (α → γ), (β → β) are both true and γ
is false, both α and β have to be false. However, if so, (α ∨ β) is going

130
 to be false. Contradiction. The argument is valid.

2.
1. Invalid. (Counterexample: A=T, B=T, C=T/F)
2. Valid.
3. Invalid. (Counterexample: B=T, C=F, D=F)
4. Valid.
5. Invalid. (Counterexample: A=F, B=F, C=F)

Solutions for Problems 1.7.2.1

1. ((A ∧ −B ∧ C) ∨ (A ∧ −B ∧ −C) ∨ (−A ∧ B ∧ C) ∨ (−A ∧ −B ∧ C))
2. ((A ∧ B ∧ C) ∨ (A ∧ −B ∧ C) ∨ (A ∧ −B ∧ −C) ∨ (−A ∧ B ∧ C))
3. ((A ∧ B ∧ C) ∨ (A ∧ −B ∧ C) ∨ (A ∧ −B ∧ −C))
4. ((A ∧ B ∧ −C) ∨ (A ∧ −B ∧ C) ∨ (A ∧ −B ∧ −C) ∨ (−A ∧ B ∧ C) ∨
(−A ∧ B ∧ −C) ∨ (−A ∧ −B ∧ C) ∨ (−A ∧ −B ∧ −C))
5. ((A ∧ B ∧ −C) ∨ (A ∧ −B ∧ −C) ∨ (−A ∧ B ∧ −C) ∨ (−A ∧ −B ∧ C))

Solutions for Problems 1.8.1

1.
1. (α ∨ β) : ((α | α)|(β | β))
2. (α → β) : (α | (β | β))
3. (α ↓ β) : (((α | α) | (β | β)) | ((α | α) | (β | β)))

2.
1. −α : (α ↓ α)
2. (α ∧ β) : ((α ↓ α) ↓ (β ↓ β))
3. (α ∨ β) : ((α ↓ β) ↓ (α ↓ β))
4. (α → β) : (((α ↓ α) ↓ β) ↓ ((α ↓ α) ↓ β))
5. ((α | β) : (((α ↓ α) ↓ (β ↓ β)) ↓ ((α ↓ α) ↓ (β ↓ β)))

3.
1. (α ∨ β) : −(−α ∧ −β)

131
 2. (α → β) : −(α ∧ −β)
3. (α | β) : −(α ∧ β)
4. (α ↓ β) : (−α ∧ −β)

4.
1. (α ∧ β) : −(−α ∨ −β)
2. (α → β) : (−α ∨ β)
3. (α | β) : (−α ∨ −β)
4. (α ↓ β) : −(α ∨ β)

5.
1. (α ∧ β) : −(α → −β)
2. (α ∨ β) : (−α → β)
3. (α | β) : (α → −β)
4. (α ↓ β) : −(−α → β)

Solutions for Problems 1.9.3.1

1.
X (J → (K → J))

−J (K → J)

This tree is clearly open (you don’t have to decompose the right-side
path because the left-side path is open no matter what happens to the right-
side path. See Rule of Thumb 3); thus, the sentence is satisfiable. However,
we still need to decide whether it is valid or not.
X − (J → (K → J))
J
X − (K → J)
K
−J
×

This one is closed; thus, the sentence is valid.

132
2.

X ((E ↔ H) → (−E → −H))

X − (E ↔ H) X (−E → −H)

E −E −−E −H
−H H

The tree is open; thus, the sentence is satisfiable.

Now we gonna test its validity.

X − ((E ↔ H) → (−E → −H))

(E ↔ H)
X − (−E → −H)
−E
X − −H
H

E −E
H −H
× ×

The tree is closed; the sentence is valid.

3.

133
 X ((((C → D) ∧ (D → E)) ∧ C) ∧ −E)
X (((C → D) ∧ (D → E)) ∧ C)
−E
X ((C → D) ∧ (D → E))
C
X (C → D)
X (D → E)

−C D
×
−D E
× ×

The tree is closed; the sentence is unsatisfiable (and also invalid).

4.

X − (((A ∨ B) ∧ (B ∨ B)) ∧ (−A ∧ −B))

X − ((A ∨ B) ∧ (B ∨ B)) −(−A ∧ −B)

X − (A ∨ B) −(B ∨ B)
−A
B
The left-most path remains open no matter what happens to other
paths; thus, the sentence is satisfiable.
Now for the test for its validity.

134
 −−(((A ∨ B) ∧ (B ∨ B)) ∧ (−A ∧ −B))
X (((A ∨ B) ∧ (B ∨ B)) ∧ (−A ∧ −B))
X ((A ∨ B) ∧ (B ∨ B))
X (−A ∧ −B)
X (A ∨ B)
(B ∨ B)
−A
−B

A B
× ×

The tree is closed; the sentence is valid.

5.

X (−B → ((B ∨ D) → D))

−B ((B ∨ D) → D)

The tree is open (there’s nothing to do with the left-side path);

thus, the sentence is satisfiable.
We’re gonna test its validity.

X − (−B → ((B ∨ D) → D))

−B
X − ((B ∨ D) → D)
X (B ∨ D)
−D

B D
× ×

The tree is closed; the sentence is valid.

135
Solutions for Problems 1.9.4.1
1.

X (B ∨ (A ∧ −C))
X ((C → A) ↔ B)
X (−B ∨ A)
X − −(A ∨ C)
X (A ∨ C)

X (C → A) X − (C → A)
B −B
C
B X (A ∧ −C) −A

−B A B X (A ∧ −C)
× × A
−C
A C
×

−C A −C A
× A
−C

−B A
×
A C
×

The tree is open; the argument is invalid. A counterexamples are

given when A and B are both true, and C is either true or false.

136
2.
X − (Y ↔ A)
−Y
−A
−(W ∧ −W )

Y −Y
−A A
× ×

The tree is closed; the argument is valid.

3.
X (B ∨ B)
X ((−B → (−D ∨ −C)) ∧ ((−D ∨ C) ∨ (B ∨ C)))
−C
X (−B → (−D ∨ −C))
X ((−D ∨ C) ∨ (B ∨ C))

X (−D ∨ C) X (B ∨ C)

−D C B C
× ×
X − −B X (−D ∨ −C) X − −B X (−D ∨ −C)

−D −C −D −C

B B B B B B B B
B B

B B B B
The tree is open; the argument is invalid. A counterexample is given
when B is true and C and D are both false.

137
4.

X (((J ∧ T ) ∧ Y ) ∨ (−J → −Y ))
X (J → T )
X (T → Y )
X − (Y ↔ T )

Y −Y
−T T

−J T −J T
×
−T Y −T Y −T Y
× × × ×
X ((J ∧ T ) ∧ Y ) X (−J → −Y ) X ((J ∧ T ) ∧ Y ) (−J → −Y )

−−J −Y −−J −Y
J × J ×
× ×
X (J ∧ T ) X (J ∧ T )
J J
T T
Y XY
×

The tree is closed; the argument is valid.

138
5.
X ((A ∧ (B ∨ C)) ↔ (A ∨ B))
X (B → −B)
X − (C ∨ A)
−C
−A

X (A ∧ (B ∨ C)) X − (A ∧ (B ∨ C))
(A ∨ B) X − (A ∨ B)
A −A
(B ∨ C) −B
×
−A X − (B ∨ C)

−B −B
−B
−C

−B −B
The tree is open; the argument is invalid. A counterexample is given
when A, B, C are all false.

Solutions for Problems 1.9.5.1

1.
A
X (B ∧ C)
−B
B
C
×

The tree is closed; the implication holds.

139
2.

A
X (B ∨ C)
−B

B C
×

The tree is open; the implication fails. The counterexample is given

when A, C are true and B is false.

3.

X (K ∨ J)
X − (K ∨ J)
−K
−K
−J

K J
× ×

The tree is closed; the implication holds.

4.

140
 (W ∨ J)
X ((W → Z) ∨ (J → Z))
−Z
X − −(W ∧ J)
X (W ∧ J)
W
J

X (W → Z) X (J → Z)

−W Z −J Z
× × × ×

The tree is closed; the implication holds.

Solutions for Problems 1.9.6.1

1.

X − ((A → (B → A)) ↔ ((C ∧ −C) ∨ (A → A)))

(A → (B → A)) X − (A → (B → A))
X − ((C ∧ −C) ∨ (A → A)) ((C ∧ −C) ∨ (A → A))
−(C ∧ −C) A
−(A → A) X − (B → A)
A B
−A −A
× ×

The tree is closed; the equivalence holds.

141
2.

X − ((C ∧ (B ∨ A)) ↔ ((C ∧ B) ∨ A))

X (C ∧ (B ∨ A)) X − (C ∧ (B ∨ A))
X − ((C ∧ B) ∨ A) X ((C ∧ B) ∨ A)
C
X (B ∨ A) −C X − (B ∨ A)
X − (C ∧ B)
−A
X (C ∧ B) A
C
B A B
× ×
−C −B
× ×
−B
−A

(C ∧ B) A
C ×
B
×

The tree is open; the equivalence fails.

142
3.
X − ((−(D ∨ B) → (C → B)) ↔ (C → (D ∧ B)))

(−(D ∨ B) → (C → B)) X − (−(D ∨ B) → (C → B))

X − (C → (D ∧ B)) X (C → (D ∧ B))
C X − (D ∨ B)
X − (D ∧ B) X − (C → B)
C
X − −(D ∨ B) X (C → B) −B

−C B −C X (D ∧ B)
X (D ∨ B) × D
B
−D
D B −B
×
−D −B −D −B
× ×

The tree is open; the equivalence fails.

4.
−((A → (B → (A → B))) ↔ (B → (A → (B → A))))

(A → (B → (A → B))) X − (A → (B → (A → B)))
X − (B → (A → (B → A))) (B → (A → (B → A)))
B A
X − (A → (B → A)) X − (B → (A → B))
A B
X − (B → A) X − (A → B)
B A
−A −B
× ×

The tree is closed; the equivalence holds.

143
5.

X − ((F ∨ −(G ∨ −H)) ↔ ((H ↔ −F ) ∨ G))

X (F ∨ −(G ∨ −H)) X − (F ∨ −(G ∨ −H))

X − ((H ↔ −F ) ∨ G) X ((H ↔ −F ) ∨ G)
X − (H ↔ −F ) −F
−G X − −(G ∨ −H)
X (G ∨ −H)
F X − (G ∨ H)
X (H ↔ −F ) G
H −H
H −H G −H

−−F
F
−F −G
× −H −F

H −H
−F
G −H −−F
−−F × F
F ×
×

The tree is open; the equivalence fails.

Solutions for Problems 2.2.3.1

1. −∃x((Rx ∧ Ax) ∧ Dx)
2. ∃x((Rx ∧ Ax) ∧ Dx)
3. −∀x((Rx ∧ Ax) → Dx)

144
Solution for Problem 2.2.4.1
In order to show that two sentences are logically equivalent, you need to show
that these sentences are mutually implies; namely, given α and β, you need
to show α |= β and β |= α.

First, ∀x((P x ∧ N x ∧ −T x) → Ox) |= ∀x((P x ∧ N x) → (Ox ∨ T x)).

∀x((P x ∧ N x ∧ −T x) → Ox) (4.1)
≡ ∀x(−(P x ∧ N x ∧ −T x) ∨ Ox) (4.2)
≡ ∀x((−P x ∨ −N x ∨ −−T x) ∨ Ox) (4.3)
≡ ∀x((−P x ∨ −N x ∨ T x) ∨ Ox) (4.4)
≡ ∀x((−P x ∨ −N x) ∨ (Ox ∨ T x)) (4.5)
≡ ∀x(−(P x ∧ N x) ∨ (Ox ∨ T x)) (4.6)
≡ ∀x((P x ∧ N x) → (Ox ∨ T x)) (4.7)
Annotations:
(1) The starting sentence.
(2) Transformed a conditional to a disjunction using (α → β) ≡ (−α ∨ β)
(3) Applied one of the De Morgan’s laws (−(α ∧ β) ≡ (−α ∨ −β)) to
−(P x∧N x∧−T x). (Here, you need to apply it twice. Details: −(P x∧
N x ∧ −T x) |= −(P x ∧ (N x ∧ −T x)) |= (−P x ∨ −(N x ∧ −T x)) |=
(−P x ∨ (−N x ∨ −−T x)) |= (−P x ∨ −N x ∨ −−T x).)
(4) Canceled the double negations in −−T x.
(5) Changed the order and put the extra pair of the brackets.
(6) Applied the De Morgan to (−P x ∨ −N x).
(7) Changed a disjunction to a conditional.

Second, ∀x((P x∧N x) → (Ox∨T x)) |= ∀x((P x∧N x∧−T x) → Ox).

∀x((P x ∧ N x) → (Ox ∨ T x)) (4.1)
≡ ∀x(−(P x ∧ N x) ∨ (Ox ∨ T x)) (4.2)
≡ ∀x((−P x ∨ −N x) ∨ (Ox ∨ T x)) (4.3)
≡ ∀x((−P x ∨ −N x ∨ T x) ∨ Ox) (4.4)
≡ ∀x((−P x ∨ −N x ∨ −−T x) ∨ Ox) (4.5)
≡ ∀x(−(P x ∧ N x ∧ −T x) ∨ Ox) (4.6)
≡ ∀x((P x ∧ N x ∧ −T x) → Ox) (4.7)

145
Annotations:
(1) The starting sentence.
(2) Changed a disjunction to a conditional.
(3) Applied the De Morgan.
(4) Moved T x inside the first pair of the brackets.
(5) Added the double negations to T x.
(6) Applied the De Morgan.
(7) Changed a disjunction to a conditional.

Solutions for Problems 2.2.6

1.
1. ∀x(Cxm → Chx)
2. ∀x(Cmx → Chx)
3. ∀x(Cmx → Chx)
4. (∃xCxm → Chm)
5. (∀xCxm → Chm)
6. ∀x(Cxh → Cxm)
7. ∀x(Cxh → Cxm)

2.
∀x(Ex → Cx)
∀x(Lx → N x)
∀x(Dx → Ax)
∀x(−M x → −Bx)
∀x(Cx → Kx)
∀x(−Ex → −Rx)
∀x(Hx → −N x)
∀x(−Bx → −Kx)
∀x(−Rx → Dx)
∀x(M x → Lx)
∀x(Hx → Ax)

Solutions for Problems 2.4.6.4

Hint: The explanation can be broken down to the following three points.

146
 1. A tree stops after a finite number of the applications of the rules (de-
cidability); thus, the number of the sentences in the tree has to be
finite.

2. If the initial list is satisfiable, there has to be at least one open path in
the finished tree (soundness).

3. An interpretation (more precisely, a model) can be constructed from

an open path.

First, briefly explain the above points, and then, explain how the
claim follows from them.

Solutions for Problems 3.1.3

1.
1. The multiplication of an even number and any number is even.
2. The multiplication of two odd numbers is odd.
3. If the sum of two numbers is even, those two numbers are either both
even or both odd.
4. Every prime number other than 2 is odd.
5. There’s no largest prime number.

2.
1. ∀x(Lxa → Lax)
2. ∀x(Kxa → Lxa)
3. ∃x∀y(Lyy → Kxy)
4. ∀x(Lxa → ∀y(−Lya → Kxy))
5. ∀x(∃yLxy → ∃z(∃wLzw ∧ Lxz))
6. ∀x(∀y(Lya → Lxy) → Kxa)

3.
1. ∀x∃yLxy
2. ∀x(−Exz → ∃yGxy)
3. (−∃yLyz ∧ ∀x(−∃yLyx → Exz))
Or ∀x(−∃yLyx ↔ Exz)

147
4.
1. =: (−Lxy ∧ −Lyx)
2. 6=: (Lxy ∨ Lyx)

Solutions for Problems 3.2.4

1.
1. True. (The meaning of the sentence is: There’s someone who doesn’t
love anyone. In the extension of L, there’s no ordered pair of the form
h1, −i. Thus, 1 is such a person.)

2. True. (The meaning of the sentence is: For everyone, there’s someone
by whom his/her love is reciprocated. For 1 and 3, their love is recipro-
cated by themselves; and for 2, his/her love is reciprocated by 1. Thus,
everyone’s love is reciprocated by someone.)

3. False. (The meaning of the sentence is: There’s someone whose love
is always reciprocated. However, in the interpretation, no one’s love is
reciprocated.)

4. True. (It’s a bit hard to figure out the meaning of the sentence. So,
first transform the sentence into the disjunction of the conjunctions
(see pp. 97f), and see if the extension makes the sentence true.)

2.
1. If we take L as a predicate for “. . . loves . . . ”, the sentence can be trans-
lated as “no one’s love is reciprocated”. Thus, as long as the extension
of L doesn’t contain any pair of the forms ha, bi and hb, ai, the sentence
is going to be true. For example,
Domain = {1, 2, 3}
v(L) = {h1, 2i, h2, 3i, h3, 1i}
would do.
For the false part, since the sentence means that no one’s love is recip-
rocated, if there’s at least one reciprocated love, the sentence is going
to be false. For example

148
 Domain = {1, 2, 3}
v(L) = {h1, 2i, h2, 1i}
would do.

2. Again, if we take L as a predicate for “. . . loves . . . ”, the sentence can be

translated as “it’s not the case that someone loves everyone and his/her
love is always reciprocated”; in other words, the sentence claims that
everyone has at least one reciprocated love” (to make clear this reading,
transform the sentence into ∀x∃y(Lxy → Lyx)). Thus, the interpreta-
tion for the question 1 would do.
For the false part, since the sentence is the negation of “someone loves
everyone and his/her love is always reciprocated”, the following inter-
pretation makes the original sentence false:
Domain = {1, 2, 3}
v(L) = {h1, 1i, h1, 2i, h1, 3i, h2, 1i, h3, 1i}.

3. If we take K as a predicate for “. . . knows . . . ”, the sentence can be

translated as “Everyone who knows everyone a knows knows a”. Thus,
for example, the following interpretation makes the sentence true.
Domain = {1, 2, 3}
v(a) = 1
v(K) = {h1, 2i, h3, 1i, h3, 2i}
For the false part, if at least one person knows everyone a knows but
that person doesn’t know a, the sentence is going to be false. For
example, the following interpretation makes the sentence false
Domain = {1, 2, 3}
v(a) = 1
v(K) = {h1, 2i, h3, 2i}.

4. If we take L and K as in the above, the sentence can be translated as

“it’s not the case that someone a loves knows everyone a knows”; in
other words, the sentence claims that everyone a loves doesn’t know
someone a knows (to make clear this reading, transform the sentence
into ∀x(Lax → ∃y(Kay ∧ −Kxy))). Thus, for example, the following

149
 interpretation makes the sentence true.
Domain = {1, 2, 3}
v(a) = 1
v(L) = {h1, 2i}
v(K) = {h1, 3i}
For the false part, if at least one person a loves knows everyone a
knows, the sentence is going to be false. For example, the following
interpretation makes the sentence false.
Domain = {1, 2, 3}
v(a) = 1
v(L) = {h1, 2i}
v(K) = {h1, 3i, h2, 3i}

5. The sentence simply states that the transitivity law holds for the mem-
bers of the domain. Thus, for example, the following interpretation
makes the sentence true.
Domain = {1, 2, 3}
v(R) = {h1, 2i, h2, 3i, h1, 3i}
For the false part, the following interpretation makes the sentence false.
Domain = {1, 2, 3}
v(R) = {h1, 2i, h2, 3i}.

150
3.

1.

1. X − ∀x∀y(Gyx ∨ Gxy)
2. ∀x∀y(Gxx ∨ Gxy)
3. X ∃x∃y−(Gyx ∨ Gxy) NQ×2 to Line 1
4. X − (Gba ∨ Gab) EI×2 to Line 3 with a to x and b to y
5. −Gba Rule 6 to Line 4
6. −Gab Rule 6 to Line 4
7. X (Gaa ∨ Gab) UI×2 to Line 2 with a to x and b to y

8. Gaa Gab Rule 5 to Line 7

9. X (Gbb ∨ Gba) × UI×2 to Line 2 with b to x and a to y

10. Gbb Gba Rule 5 to Line 9

×

The leftmost path remains open; thus, from this open path, you can
construct the following interpretation.

Domain = {1, 2}
Ext(a) = 1
Ext(b) = 2
Ext(G) = {h1, 1i, h2, 2i}

Note that if you start your tree with ∀x∀y(Gyx∨Gxy) and −∀x∀y(Gxx∨
Gxy), your tree is gonna be closed. (So you may have to write two truth
trees if you’re unlucky. If that happens, don’t be discouraged; start writing
another tree right away.)

151
2.
1. X ∃x(Bx ∧ ∀yDyx)
2. X − ∀x(Bx → ∀yDyx)
3. X ∃x−(Bx → ∀yDyx) NQ to Line 2
4. X − (Ba → ∀yDya) EI to Line 3
5. Ba Rule 8 to Line 4
6. X − ∀yDyx Rule 8 to Line 4
7. X ∃y−Dya NQ to Line 6
8. −Dba EI to Line 7
9. X (Bc ∧ ∀yDyc) EI to Line 1
10. Bc Rule 3 to Line 9
11. ∀yDyc Rule 3 to Line 9
12. Dac UI to Line 11
13. Dbc UI to Line 11
14. Dcc UI to Line 11

(In the above, you need to instantiate ∀yDyc in Line 11 with all the names
in order to show that you did all you can do.)

From this open tree, you can construct an interpretation as follows.

Domain = {1, 2, 3}
Ext(a) = 1
Ext(b) = 2
Ext(c) = 3
Ext(B) = {1, 3}
Ext(D) = {h1, 3i, h2, 3i, h3, 3i}

Of course, this interpretation makes ∃x(Bx ∧ ∀yDyx) true and

∀x(Bx → ∀yDyx) false; thus, the interpretation gives you a correct answer.
However, in this case, there’s much simpler way to construct an interpre-
tation which makes one of the sentences true and the other false. Notice
that the former sentence is an existential sentence with a conjunction and
the latter is a universal sentence with a conditional. For the former to be
true, there has to be at least one object in the extension of B whereas, for
the latter to be true, the empty extension of B would suffice. Therefore, the
following interpretation would do as well.

152
 Domain = {1, 2, 3}
Ext(B) = ∅
Ext(D) = ∅

Solutions for Problems 4.1.1

1.
First let’s determine whether the sentence is satisfiable or not.

1. X (∀x x = a → (∃xF x → ∀xF x))

2. X − ∀x x = a (∃F x → ∀xF x)
3. X ∃xx 6= a
4. b 6= a

There’s nothing we can do further in order to close the left path.

Thus, the tree has at least one finished open path, no matter what’s gonna
happen to the right path. Therefore, the sentence is satisfiable.
According to the left path, there are two names: a and b. Therefore,
we can set up the domain as {1, 2} with the extensions of a and b as 1 and
2 respectively. This setting makes a 6= b true obviously.
How about the extension of F ? There’s no line where the predicate
F appears. Thus, we can set up the extension as empty. This makes ∃xF x
false and consequently makes (∃xF x → ∀xF x) true.
Next let’s determine whether the sentence is valid or not.

1. X − (∀x x = a → (∃xF x → ∀xF x))

2. ∀x x = a
3. X − (∃xF x → ∀xF x)
4. X ∃xF x
5. X − ∀xF x
6. X ∃x−F x
7. Fb
8. −F c
9. b=a
10. c=a
11. Fa
12. −F a

153
 The tree is closed; the sentence is valid.

2.
The satisfiability part.

1. ∀x∀y x 6= y
2. a 6= a
×

The tree is close; the sentence is unsatisfiable. Under what inter-

pretation is it going to be false? The next tree tells us that.

1. X − ∀x∀y x 6= y
2. X ∃x∃y x
3. a=b

There’s nothing we can do further; the tree is open. And according

to the tree, there are two names; but they refer to the same object in the
domain. Thus, one of the interpretations which makes the sentence false is:

Domain: {1}
Extension of a: 1
Extension of b: 1

3.

1. X ∃x∃y x 6= y
2. a 6= b

The tree is open; there has to be an interpretation makes the sen-

tence true. And according to the tree, there are two names which refer to
different objects of the domain. Thus, one of such interpretations is:

Domain: {1, 2}
Extension of a: 1
Extension of b: 2

Is the sentence valid? Let’s figure it out.

154
 1. X − ∃x∃y x 6= y
2. ∀x∀y x = y
3. a=a

The tree is open; there has to be at least one interpretation which

makes the sentence false. And according to the tree, there’s only one name:
a. Thus, if the domain is comprised of just one object, the sentence is going
to be false.

4.

1. ∀x∀y((F x ↔ F y) → x = y)
2. X ((F a ↔ F a) → a = a)

3. −(F a ↔ F a) a=a

The right path remains open, no matter what’s gonna happen to

the left path; thus, the sentence is satisfiable. One of the interpretations
which makes the sentence true is one whose domain is comprised of just one
member and which has the empty extension for F .
Now the validity part.

1. X − ∀x∀y((F x ↔ F y) → x = y)
2. X ∃x∃y−((F x ↔ F y) → x = y)
3. X − ((F a ↔ F b) → a = b)
4. X (F a ↔ F b)
5. a 6= b

6. Fa −F a
7. Fb −F b

The tree is open; the sentence can be false. And from the left path,
we can set up one of such interpretations as follows.

Domain: {1, 2}
Extension of a: 1
Extension of b: 2

155
 Extension of F : {1, 2}

5.

1. X ((∃xGax → −∃xGxa) → ∀x(Gxa → x 6= a))

2. X − (∃xGax → −∃xGxa) ∀x(Gxa → x 6= a)

3. X ∃xGax
4. X − −∃xGxa
5. X ∃xGxa
6. Gab
7. Gca

The left path remains open, no matter what’s gonna happen to the
other paths; thus, the sentence is satisfiable. Since there are three names
(a, b, c) in the path and there are two G-sentences in the line by themselves,
one of the interpretations which makes the sentence true is:

Domain: {1, 2, 3}
Extension of a: 1
Extension of b: 2
Extension of c: 3
Extension of G: {h1, 2i, h3, 1i}

Let’s move on to the validity part.

156
 1. X − ((∃xGax → −∃xGxa) → ∀x(Gxa → x 6= a))
2. X (∃xGax → −∃xGxa)
3. X − ∀x(Gxa → x 6= a)
4. X ∃x−(Gxa → x 6= a)
5. X − (Gba → b 6= a)
6. Gba
7. b=a

8. X − ∃xGax X − ∃xGxa
9. ∀x−Gax ∀x−Gxa
10. −Gaa −Gaa
11. −Gba −Gba
× ×

The tree is closed; the sentence is valid.

Solutions for Problems 4.2.3.1

In order to show that the sentences are equivalent with each other, it’s enough
to show that 1 implies 2, 2 implies 3, and 3 implies 1.

1 implies 2:

157
1. X ∃x∀y(F y ↔ y = x)
2. X − ∃x(F x ∧ ∀y(F y → y = x))
3. ∀x−(F x ∧ ∀y(F y → y = x)) NQ to Line 2
4. ∀y(F y ↔ y = a) EI to Line 1
5. X (F a ↔ a=a) UI to Line 4

6. Fa −F a Rule 9 to Line 5
7. a=a a 6= a Rule 9 to Line 5
8. X − (F a ∧ ∀y(F y → y = a)) × UI to Line 3

9. −F a −∀y(F y → y = a) Rule 4 to Line 8

10. × X ∃y−(F y → y = a) NQ to Line 10
11. X − (F b → b = a) EI to Line 10
12. Fb Rule 8 to Line 11
13. b 6= a Rule 8 to Line 11
14. X (F b ↔ b = a) UI to Line 4

15. Fb −F b Rule 9 to Line 14

16. b=a b 6= a
× ×

The tree is closed; 1 implies 2.

158
2 implies 3:

1. X ∃x(F x ∧ ∀y(F y → y = x))

2. X − (∃xF x ∧ ∀y∀z((F y ∧ F z) → y = z))

3. X − ∃xF x X − ∀y∀z((F y ∧ F z) → y = z) Rule 4 to Line 2

4. ∀x−F x X ∃y∃z−((F y ∧ F z) → y = z) NQ to Line 3
5. X (F a ∧ ∀y(F y → y = a)) X (F a ∧ ∀y(F y → y = a)) EI to Line 1

Let’s first finish the left path.

6. Fa Rule 3 to Line 5
7. ∀y(F y → y = a) Rule 3 to Line 5
8. −F a UI to Line 4
×

Next, the right path.

6. Fa Rule 3 to Line 5
7. ∀y(F y → y = a) Rule 3 to Line 5
8. X − ((F b ∧ F c) → b = c) EI to Line 4
9. X (F b ∧ F c) Rule 8 to Line 8
10. b 6= c Rule 8 to Line 8
11. Fb Rule 3 to Line 9
12. Fc Rule 3 to Line 9
13. (F b → b = a) UI to Line 7

14. −F b b=a Rule 7 to Line 13

15. × X (F c → c = a) UI to Line 7

16. −F c c=a Rule 7 to Line 15

17. × b=c Rule 17 to Line 14
×

The tree is closed; 2 implies 3.

159
 Lastly, 3 implies 1:

1. X (∃xF x ∧ ∀y∀z((F y ∧ F z) → y = z))

2. X − ∃x∀y(F y ↔ y = x)
3. X ∃xF x Rule 3 to Line 1
4. ∀y∀z((F y ∧ F z) → y = z) Rule 3 to Line 1
5. ∀x−∀y(F y ↔ y = x) NQ to Line 2
6. Fa EI to Line 3
7. X − ∀y(F y ↔ y = a) UI to Line 5
8. X ∃y−(F y ↔ y = a) NQ to Line 7
9. X − (F b ↔ b = a) EI to Line 8

10. Fb −F b Rule 10 to Line 9

11. b 6= a b=a Rule 10 to Line 9
12. X ((F b ∧ F a) → b = a) −F a UI to Line 4; Rule 16 to Line 6
×
13. X − (F b ∧ F a) b=a Rule 7 to Line 12
×
14. −F a −F b Rule 4 to Line 13
× ×

The tree is closed; 3 implies 1.

Now we know that (a) 1 implies 2, (b) 2 implies 3, and (c) 3 implies
1. Since implication is transitive, (d) 2 implies 1 (from (b) and (c)); therefore,
1 and 2 are equivalent (from (a) and (d)). Moreover, (e) 3 implies 2 (from
(c) and (a)), and (f) 1 implies 3. Therefore, 1 and 3 are equivalent (from (c)
and (f)), and 2 and 3 are equivalent (from (b) and (e)).

Solutions for Problems 4.2.7

1. ∃x∃y(Lxa ∧ Lya ∧ x 6= y)
2. ∀x∀y((Lax ∧ Lya) → x = y)
3. ∀x∀y∀z((−Lxa ∧ −Lya ∧ −Lza) → (x = y ∨ y = z ∨ z = x))
4. ∃x∀y(∃v∃w(v 6= w∧Kyv∧Kyw∧∀z(Lza ↔ (z = v∨z = w))) ↔ y = x)

160