Search for notes by fellow students, in your own course and all over the country.
Browse our notes for titles which look like what you need, you can preview any of the notes via a sample of the contents. After you're happy these are the notes you're after simply pop them into your shopping cart.
Document Preview
Extracts from the notes are below, to see the PDF you'll receive please use the links above
A Problem Course
in
Foundations of Mathematics,
Sets & Logic
Version 1
...
Copyright
Ddumba & Kimuli
foundation of mathematics
Page 1 of 113
Contents
1 Sets and Counting
1
...
1
...
1 Definition
...
1
...
1
...
2
...
1
...
3
...
1
...
2 Equality of Sets
...
4 Special Sets
...
4
...
1
...
2 The Null or Void Set
...
4
...
1
...
4 Finite and Infinite Sets
...
4
...
1
...
6 Cardinality
...
5 Set Operations
...
5
...
1
...
2 Union of Sets
...
5
...
1
...
4 Complement of a set
...
6 Venn-Diagram
...
7 Special sets
...
7
...
1
...
2 Integers Z
...
7
...
1
...
4 Irrational numbers Q0
...
7
...
1
...
6 Complex numbers C
...
8 Closed under an operation
...
8
...
1
...
2 Subtraction
...
8
...
1
...
4 Division
...
9 Examples
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
1 Language
...
1
...
2
...
2 Propositions
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
2
2
...
4
2
...
1
...
2
...
4 Informal Conventions
...
1
...
2
...
6 Rearrangement of symbols in Lp
...
1
...
2
...
8 Examples
...
2
...
1 Truth Assignments
...
2
...
2
...
3 Truth table for Implication (→)
...
2
...
2
...
5 Truth table for disjunction (∨)
...
2
...
2
...
Preposition Equivalences
...
3
...
Predicates and quantifiers
...
...
...
...
...
...
...
(↔)
...
...
...
0
...
3
...
2 Sufficient Condition
...
0
...
3
...
4 Validity of Statements
...
1 Direct Proof
...
1
...
3
...
3
...
1 Principle of Mathematical Induction
3
...
2 Proof by Mathematical Induction
...
3 By Contradiction
...
3
...
3
...
2 Proof by Contradiction
...
3
...
3
...
4 more examples
...
3
...
3
...
3
...
1 More details
...
5 Truth Table
...
1 Factorials
...
2 Permutation
...
3 Combination
...
4 Further Examples
...
5 Summary
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
71
71
71
74
77
86
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
1 Practice Questions
...
1 Practice Questions
...
2 Exam2005/2006
...
3 Solutions 2005/2006
6
...
6
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
Page 1 of 113
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
90
90
94
97
103
106
Chapter 1
Sets and Counting
1
...
1
...
1
...
2
Set Notation
A set is always abbreviated with a capital letter (Sets are usually denoted by upper case
letters A, B, C, D,
...
and are enclosed in braces, {}
...
Hence x ∈ A means x is a member of
the set A
...
Thus x 6∈ A is read ”x is not a member of the set A
...
2
Basic Concepts and Symbolism
1
...
1
Symbolism
There are two ways of representing sets:
(a) Tabular notation/listing members
(b) Set-builder notation
(1) Tabular Notation
A set can be represented by listing its members, such a set is said to be defined
...
and read ”the set whose members are
{x, y
...
2
...
2
...
Thus, A = {−1, −2}
...
” The members
that satisfy this requirements are, U, g, a, n, d
...
(c) The set C can be read as: ”C is the set of letters of the alphabet that are consonants”
The letters that satisfy this requirement are: b, c, d, f, g, h, j, k, l, n, p, q, r, s, t, v, w, x, y, z
...
” The
numbers that satisfy this condition are 3, 5, 7, 9
...
(e) The set F can be rad as ”F is the set of the digits in the number 1997
...
Thus E = {1, 9, 7}
...
A general letter, like x, is then used to represent any arbitrary
member in the set
...
If the members of a set E are all even numbers then in the set-builder notation this is
written as: E = {x : x is even}
...
”
In general a set in set-builder notation is written as {x : x satisfies some rule}
...
2
...
(i) A = {a, e, i, o, u}
(ii) B = {1, 2,
...
}
(iv) D = {3, 6, 9, 12, 15,
...
}
The description of a set in set-builder notation is not unique
...
The following answers are not only the ways these sets could be
described
...
(ii) B = {x : x are counting numbers from one to ten}
(iii) C = {x : x is a prime number}
...
(v) E = {x : x is a square number}
...
3
...
2
...
Then we can write:
(i) a is a member of the set A as a ∈ A
...
2
...
(a) A = {x : x ∈ N and x < 5}
(b) B = {x : x + 2 = 7}
(c) C = {x : −1 ≤ x ≤ 3}
(d) D = {1, 8, 27, 64,
...
}
(a) 1, 2, 3, 4, ∈ A but 6, 7, ∈
/A
(b) 5 ∈ B but 4, 6, ∈
/B
(c) −1, 0, 1, 2, 3, ∈ C but − 2, 4, ∈
/C
(d) 1, 8, 27, 64 ∈ D but 2, 10, ∈
/D
(e) 5, 10, 15, ∈ Ebut11, 16, ∈
/E
1
...
3
...
We write A ⊆ B to mean that A is a subset of B
...
If the set a is a subset of a set B and A is not equal to B then A is said to be a proper subset
of B
...
Example 1
...
1 If A = {1, 2, 3, 4} what are the possible proper subsets of the set A?
The possible proper subsets are : B = , the empty set;
C = 1; D = {2}; E = {3}; F = {4}; G = {1}; H = {1, 2};
I = {1, 3}; J = {1, 4}; K = {2, 3}; L = {2, 4}; M = {3, 4};
N = {1, 2, 3};
O = {1, 2, 4}; P = {2, 3, 4}; Q = {1, 2, 3, 4}
...
The
number of subsets of a set with n element is 2n
...
The set R = {1, 2, 5} is not a subset of A since 5 ∈ R but 5 ∈
/ A
...
This can be shown in set-builder
notation as {x : x ∈ B, x ∈
/ A}
...
this subset
is called the difference of the set A and B denoted by A − B
...
Theorem 1
...
1 Every set is a subset of itself
...
Proof 1
...
Then any x ∈ A is an element of A
...
Page 4 of 113
Ddumba & Kimuli foundation of mathematics
1
...
SPECIAL SETS
1
...
2
Equality of Sets
Two sets A and B are said to be equal denoted by A = B if and only if (iff)
(i) A ⊆ B and
(ii) B ⊆ A
A ⊆ B means that very member of the set A is contained in the set B, and B ⊆ A means that
every member of the set B is contained in the set A
...
In order to show the equality of two sets A and B, it is sufficient to show that A ⊆ B and
B ⊆ A
...
Definition 1
...
1 Two sets are equal if they have the same members
...
3
...
3
...
Then A = B
...
Which of the sets A, B and C are equal?
(c) {5, 1} = {1, 5, 1}
Sets A and B are equal to each other
...
1
...
4
...
This set
depends on the nature if the problem
...
Example 1
...
1 (a) If we have the set A = {a, e, i, o, u} then a possible universal set could
be;
ε = {the letters of the alphabet }
...
What are the possible universal sets
for this set?
Some possible universal sets for this set could be
(i) ε = {a subject in the school curriculum }
(ii) ε = {a science subject in the curriculum }
Ddumba & Kimuli
foundation of mathematics
Page 5 of 113
1
...
SPECIAL SETS
1
...
2
The Null or Void Set
The empty set or void set is a set that contains no elements
...
Example 1
...
2 Let S = {x : x is a human being with two heads} This set has no elements
thus S = φ or {}
...
4
...
Hence the set A is the null set or the empty set
...
4
...
Example 1
...
4 Find the members of the power set of the set
A = {1, 2, 3}
...
In this case, the set, A
has 3 members, hence its power set has 23 = 8 subsets
...
Example 1
...
5 Find the power
of the set A ={p, q}
...
4
...
This means we can have a terminating
count of its members, otherwise the set is said to be infinite
...
4
...
(i) A = {a, e, i, o, u}
(ii) P = {x : xis the world population}
(iii) D = {x : xis a district in Uganda}
(iv) B = {x : xis a letter in the word ”Mississippi” }
(b) The following are examples of infinite sets (can you see why?):
(i) L = the set of line that are parallel to the x - axis
...
(iii) A = {x : xis an odd number}
(iv) B = the set of numbers that are multiples of 10
...
Page 6 of 113
Ddumba & Kimuli foundation of mathematics
1
...
SET OPERATIONS
1
...
5
Disjoint Sets
Two sets a and B are said to be disjoint if they have any members in common
...
Example 1
...
7 (a) Let A = {4, 5, 6} and B = {1, 3, 7} then A and B are disjoint since
A ∩ B = φ
...
4
...
The two sets have no
members in common, the sets are therefore disjoint
...
4
...
For example
(i) If A = {a, c, d}, =⇒ |A| = 3
(ii) If B = {1, 0, 1, −1}, =⇒ |B| = 3
(iii) If C = {9, 12, −3, 0}, =⇒ |C| = 4
(iv) If A = {}, =⇒ |A| = 0
1
...
Otherwise sets a and B are
non-comparable
...
Example 1
...
1 (a) Let A − {a, b, c} and B = {q, b, c, d}
...
(b) Let R = {1, 2} and S = {2, 3, 4}
...
1
...
1
Intersection of Sets
Given any two sets A and B
...
The intersection of A and B is denoted by A ∩ B, and read
”A ∩ B” or A ∩ B”
...
Example 1
...
2 A = {1, 2, 3, 4, 5}, B = {3, 4, 6} Then A ∩ B = {3, 4}
...
5
...
(b) Let A = {a, b, c, d, e} and B = {a, c, e, g}
...
The elements that are in both sets are a, c, e, thus; A ∩ B = {a, c, e}
...
Find A ∩ B
...
Therefore, A ∩ B = φ
...
Ddumba & Kimuli
foundation of mathematics
Page 7 of 113
1
...
SET OPERATIONS
1
...
2
Union of Sets
Given two sets A and B
...
The union of A and B is denoted by A ∪ B read ”A ∪ B” or ”A ∩ B”
...
5
...
5
...
Find A ∪ B
...
Thus
A ∪ B = {p, q, r, s, t}
...
Theorem 1
...
1 If A and B are two given sets then A ∪ B = B ∪ A that is, the union of A
and B is equal to the union of B and A
...
2 The proof consists of showing that all members of A ∪ B are members of B ∪ A and
conversely that all members of B ∪ A are members of A ∪ B
...
This is the same as x ∈ B or x ∈ B hence ∈ A ∪ B and (B ∪ A) ⊂ (A ∪ B)
...
This is the same as x ∈ Aorx ∈ B hence
x ∈ AcupB and (B ∪ A) ⊂ (A ∪ B)
...
1
...
3
Difference of Sets
Given two sets A and B
...
The difference of A and B is denoted by A − B and read
”AminusB” In the set-builder notation the difference of A and B is written as:
A − B = {x : x ∈ but x ∈
/ B}
...
1
...
4
Complement of a set
To each event A, we define a new event A” or Ac known as the complement of A and consists of
all outcomes in a sample space not in A
...
Example 1
...
6
(a) Let A = {1, 2, 3, 4} and B = {3, 4, x, y}
...
Thus A − B = {1, 2}
...
Thus B − A = {x, y}
...
5
...
5
...
, 10}
Find
(i) A ∩ B
(ii) A ∪ C
(iii) C 0
(iv) (A ∪ B) ∩ C
(v) (A ∪ C)0
(vi) (A ∩ C) ∪ B 0
Ddumba & Kimuli
foundation of mathematics
Page 9 of 113
1
...
VENN-DIAGRAM
1
...
The diagram below will help you compute complementary events that are associated with
union and intersection of complements
...
6
...
Find n(A ∩ B) First find A ∩ B = {2, 5}
...
First find A ∪ B = {1, 2, 3, 4, 5, 7}
hence n(A ∪ B) = 6
...
5 can be re written as: For two interesting
sets: n(A) + n(B) = n(A ∪ B) − n(A ∩ B)
If the sets A and B are disjoint then n(A) + n(B) = n(A ∪ B)
...
If you have sets A, B and C then
(i) n(A) + n(B) = n(C) = n(A ∪ B ∪ C) + n(A ∩ B) + n(B ∩ C) + n(A ∩ C) − n(A ∩ B ∩ C)
(ii) n(A ∩ B ∩ C 0 ) = n(A ∩ B) − n(A ∩ B ∩ C)
(iii) n(A ∩ B 0 ∩ C 0 ) = n(A) − n(A ∩ B ∩ C 0 ) = n(A ∩ B 0 ∩ C) − n(A ∩ B ∩ C)
These relations are useful in the solution of arithmetic problems involving sets
...
6
...
6
...
7
...
6
...
6
...
The owner
informs the manager that 25 of the computers are ATs, 40 have 640K memory, 10 have color
monitors and 640K memory but are not ATs, 55 are color monitors , 10 are ATs with color
monitors, 15 are ATs with 640K memory, and 5 are ATs with monochrome monitors that do
not have 640K memory
...
5
(ii) 640K memory, monochrome monitors, and are not ATs
...
50
Example 1
...
6 There are 512 computer science majors at State University, and they each
own a personal computer
...
How many computers science majors own a computer with monochrome monitor and no printer
or hard-disk drive?
126
Example 1
...
7 In a Bsc I class, all 50 students take Mathematics, 18 take Chemistry, 17 take
Biology, and 24 take physics
...
Only 2 students take all the four
subjects
...
6
...
During a certain week 7 boys had clean boots, 9 practiced and 9 came on
time
...
7 practiced
and came on time
...
5
1
...
Who would question the value of numbers? They can add credibility
to an argument, clinch a deal, or simply illuminate an issue
...
Can we really rely on the statistics we read? We use numbers
every day and tend to take them for granted
...
The ancient Egyptians were using special symbols, known as pictographs, to write
Ddumba & Kimuli
foundation of mathematics
Page 11 of 113
1
...
SPECIAL SETS
down numbers over 3, 000 years ago
...
Today, we use numbers based
on the Hindu-Arabic system
...
The ancient Egyptians developed number
systems to keep accounts of what was bought and sold
...
In fact, many of the classifications are subsets of other classifications
...
e , their own symbols
...
1
...
1
Natural numbers N
The natural numbers are the positive integers ; hence
N = {1, 2, 3, · · · }
The natural numbers were the first numbers system developed and were used primarily, at one
time, for counting
...
Among the Natural numbers are the even
and odd numbers;
Even numbers could be defined as the numbers divisible by 2
Or even numbers are those that can be divided evenly into groups of two
...
Odd numbers can NOT be divided evenly into groups of two
...
Even numbers always end with a digit of 0, 2, 4, 6
or 8
...
Alternatively Odd numbers always end with a digit of 1, 3, 5, 7, or 9
...
The natural numbers are
only closed under the operation of addition and multiplication
...
g 2 − 7 = −5, and 72 are both not
natural numbers
...
We list the first few prime numbers: 2, 3, 5, 7, 11, 13, 17, 19, · · ·
1
...
2
Integers Z
The Integers are those real numbers
· · · , −3, −2, −1, 0, 1, 2, 3, · · ·
We denote the integers by Z ; hence Z = {· · · , −3, −2, −1, 0, 1, 2, 3, · · · } The Integers
are also refered to as ”whole” numbers
...
Notice that the quotient (division) of the
integers, say 3 and 7, need not to be an integer, hence integers are not closed under division
...
7
...
Accordingly,
p
Q = {x ; x = , gcd(p, q) = 1, where p, q ∈ Z}
q
Page 12 of 113
Ddumba & Kimuli foundation of mathematics
1
...
SPECIAL SETS
For example, { 13 , − 25 , 27 } etc
Notice that, every integer is also a rational number since for example 5 = 51 hence Z is
a subset of <
...
In other words, the
sum, difference, product and quotient of two rational numbers is a rational number
...
7
...
That is, the set of
irrational numbers is the compliment of the set of rational number Q in the real numbers <
...
√
√
Q0 = { 3, π, 2, · · · }
1
...
5
Real Numbers <
One of the most important properties of the real numbers is that they can be represented by
points on a straight line
...
We refer to this line as the real line
...
The numbers to the right of 0, i
...
The numbers 0 itself is neither positive nor
negative
...
8
...
7
...
e
...
2 + 2i e
...
c
Notice that, the set of Complex number is the superset of real numbers
...
e < ⊂ C
...
1
...
8
...
1
...
2
Subtraction
If the difference (subtraction) between any two elements in the set, the answer you get is in
that set
...
8
...
Page 14 of 113
Ddumba & Kimuli foundation of mathematics
1
...
EXAMPLES
1
...
4
Division
If the quotient (division) of any two elements in the set, the answer you get is in that set
...
8
...
9
Examples
(1) Given the sets A = {5, 6, 7, 8, 9, 10}, B = {2, 3, 5}, C = {1, 2, 3, 4, 5, 6},
ξ = {1, 2, 3,
...
(ii) |A|
...
(b) List the power set of B
0
(2) (a) Given that n(ξ) = 18, n(A) = 7, n(B) = 8, n(A ∩ B ) = 4 , compute
(i)
(ii)
(iii)
(iv)
n(A ∩ B)
...
0
0
n(A ∩ B )
...
(b) With relevant examples, define the following :
(i) A set
...
(iii) Greatest Common Divisor
...
Ddumba & Kimuli
foundation of mathematics
Page 15 of 113
1
...
EXAMPLES
(i2) a subset of a set
...
(b)
(i) Which of the following sets are equal
A = {1, 5, 3}
C = {1, 5, 2, 3}
B = {3, 5, 1, 3}
D = {3, 1, 5, 3}
State the cardinality of set C
...
(ii) List down the elements in the set
(i1) {n2 : n ∈ {1, 2, 3, 5, 7}}
(i2) {(−1)n : n ∈ N}
(c) During an entertainment session in the Nkoyoyo hall, two showings of the latest Christian
movies were presented
...
(i) How many of the 600 ICT students attended twice
...
(d) Given that n(A) = 10, n(B) = 7, n(A0 ∩ B 0 ) = 4 and n() = 18
...
(b)
(i) When is a set of numbers said to be closed under a mathematical operation for
example under addition
...
, −2, −1, 0, 1, 2,
...
(a)
Z⊆Q
(c) Q ∩ R = Q
(d)
(b)
Q⊆R
(d) C ∪ R = R
(i) Using the number 223, Explain fully the divisibility test of 7
(ii) Show whether the number 9236556329 ?
Page 16 of 113
Ddumba & Kimuli foundation of mathematics
Chapter 2
Propositional Logic
2
...
then
...
Definition 2
...
1 A language is a set of symbols and rules for assembling symbols into formulas
of the language
...
1
...
1
...
Parentheses: ( and )
...
2
...
3
...
, An ,
...
g He came to class
...
We still need to specify the ways in which the symbols of LP can be put together
...
1
...
1
...
Example 2
...
1 The following statements are examples of simple propositions
...
(b) I am a student of mathematics
...
(d) It is wet
...
17
2
...
LANGUAGE
(f) I ate some bread
...
Example 2
...
2 The following statements are examples of statements that are not propositions
...
(b) What a lovely day
...
1
...
1
...
1
...
Every atomic formula is a formula
...
If α is a formula, then (¬α) is a formula
...
If α and β are formulas, then (α → β) is a formula
...
No other sequence of symbols is a formula
...
1 All formulas in
Chapters 3
...
4 will be assumed to be formulas of LP unless stated otherwise
...
¬ and → are supposed to represent the connectives not and if
...
The atomic formulas, A0 , A1 ,
...
”
Thus, one might translate the English sentence “If the moon is red, it is not made of cheese”
into the formula (A0 → (¬A1 )) of LP by using A0 to represent “The moon is red” and A1 to
represent “The moon is made of cheese
...
Using the interpretations just given of A0 and A1 , the formula (A0 → (¬A1 )) is
true, but if we instead use A0 and A1 to interpret “My telephone is ringing” and “Someone is
calling me”, respectively, (A0 → (¬A1 )) is false
...
1
...
For example,
A1123 , (A2 → (¬A0 )), and (((¬A1 ) → (A1 → A7 )) → A7 ) are all formulas, but X3 , (A5 ),
()¬A41 , A5 → A7 , and (A2 → (¬A0 ) are not
...
Page 18 of 113
Ddumba & Kimuli foundation of mathematics
2
...
LANGUAGE
Problem 2
...
1
...
(A7 ← A4 )
3
...
(A8 A9 → A1043998
5
...
2 Show that every formula of LP has the same number of left parentheses as it has
of right parentheses
...
1 Show that the set of formulas of LP is countable
...
1
...
then
...
We will use the symbols ∧, ∨, and ↔ to
represent and , or ,2 and if and only if respectively
...
Namely,
1
...
) The disjunction
α∨β
is short for
((¬α) → β)
3
...
(Of course this is really (¬(A0 → (¬A1 ))), i
...
“It is not the case that if the moon is green, it is not made of cheese
...
2
We will use or inclusively, so that “A or B” is still true if both of A and B are true
...
1
...
1
...
3 Take a couple of English sentences with several connectives and translate them
into formulas of LP
...
Exercise 2
...
John will come and wait or peter will wait
...
Yesterday was cloudy but today will either be clear or rainy
...
If and only if yesterday was cloudy, will today be clear
...
If its clear today, then it will not be rainy and cold
...
If either the students or the administration are stubborn, then the strike will be settled
if and only if the government gets a court order but the troops are not sent onto compus
...
If South Africa fails to qualify for Ghana 2008 African cup, then the 2010 world cup will
be a disappointment for the host nation unless it gives Brazilian players nationality
...
1
...
M
N
E
A
G
:
:
:
:
:
Man United to win
Newcastle to win
Everton to win
Arsenal to be in the first place
Godwin to gain/win the bet
M ∨ N ∧ E → ¬A ∧ ¬G
(M ∨ (N ∧ E)) → (¬A ∧ ¬G)
Example 2
...
4 If and only if the students do the test and pass it, will they pass the final
examination and go ahead to graduate
...
1
...
1
...
(i) P → ¬(Q ∧ R)
P → ¬(Q ∧ R)
P → ¬(¬(Q → ¬R))
(P → ¬(¬(Q → ¬R)))
(ii) A ∧ B ∨ C
A ∧ B ∨ C ≡ (A ∧ B) ∨ C
But (A ∧ B) ≡ ¬(A → ¬B)
A ∧ B ∨ C ≡ (A ∧ B) ∨ C
≡ ¬(A → ¬B) ∨ C
≡ ¬(¬(A → ¬B)) → C
(iii) (α ∨ β) ∧ (β → α)
(α ∨ β) ∧ (β → α) ≡ ((¬α → β) ∧ (β → α))
≡ ¬ ((¬α → β) → ¬(β → α))
Problem 2
...
For the sake of readability, we will occasionally use some informal conventions that let us get
away with writing fewer parentheses:
2
...
6
Rearrangement of symbols in Lp
Theorem 2
...
1 We will let ¬ take precedence over → when parentheses are missing, so
¬α → β is short for ((¬α) → β), and fit the informal connectives into this scheme by letting
the order of precedence be
¬, ∧, ∨, →, and ↔
Theorem 2
...
2 We will usually drop the outermost parentheses in a formula, writing
α→β
instead of
(α → β)
and
¬α
instead of
(¬α)
Ddumba & Kimuli
foundation of mathematics
Page 21 of 113
2
...
LANGUAGE
Theorem 2
...
3 Finally, we will group repetitions of →, ∨, ∧, or ↔ to the right when
parentheses are missing, so
α→β→γ
is short for
(α → (β → γ))
or
¬α ∧ β ∧ γ ∨ ε → δ ↔ κ
is a short form for
((((((¬α) ∧ β) ∧ γ) ∨ ε) → δ) ↔ κ)
Just like formulas using ∨, ∧, or ¬, formulas in which parentheses have been omitted as above
are not official formulas of LP , they are convenient abbreviations for official formulas of LP
...
Problem 2
...
The following notion will be needed later on
...
1
...
1
...
The set of subformulas of ϕ, S(ϕ), is defined as follows
...
If ϕ is an atomic formula, then
S(ϕ) = {ϕ}
2
...
If ϕ := α → β, then
S(ϕ) = S(α) ∪ S(β) ∪ {(α → β)}
Example 2
...
6 If
ϕ = (((¬A1 ) → A7 ) → (A8 → A1 ))
then
S(ϕ) = A1 , A7 , A8 , (¬A1 ), (A8 → A1 ), ((¬A1 ) → A7 ), (((¬A1 ) → A7 ) → (A8 → A1 ))
Example 2
...
7 If
ϕ = ¬(¬A1 → A2 )
then
S(ϕ) = A1 , A2 , (¬A1 ), ((¬A1 ) → A2 ), ¬(¬A1 → A2 )
Note 2
...
1 If you write out a formula with all the official parentheses, then the subformulas
are just the parts of the formula enclosed by matching parentheses, plus the atomic formulas
...
Page 22 of 113
Ddumba & Kimuli foundation of mathematics
2
...
LANGUAGE
Note 2
...
2 Note that some subformulas of formulas involving our informal abbreviations ∨,
∧, or ↔ will be most conveniently written using these abbreviations
...
1
...
(As an exercise, where did (¬A1 ) come from?)
...
Example 2
...
9 Obtain the subformulas of the formula
ϕ = ¬((¬A2 ) → A2 )
S(ϕ) =
=
=
=
=
=
S(¬((¬A2 ) → A2 ))
S(((¬A2 ) → A2 )) ∪ {¬((¬A2 ) → A2 )}
S(¬A2 ) ∪ S(A2 ) ∪ {((¬A2 ) → A2 )} ∪ {¬((¬A2 ) → A2 )}
S(A2 ) ∪ {¬A2 } ∪ A2 ∪ {((¬A2 ) → A2 )} ∪ {¬((¬A2 ) → A2 )}
A2 ∪ {¬A2 } ∪ A2 ∪ {((¬A2 ) → A2 )} ∪ {¬((¬A2 ) → A2 )}
{A2 , ¬A2 , ((¬A2 ) → A2 ), ¬((¬A2 ) → A2 )}
Example 2
...
10 Obtain the subformulas of the formula
ϕ = ¬A1 ∨ A2 = ¬¬A1 → A2
S(ϕ) =
=
=
=
=
=
S(¬¬A1 → A2 )
S(¬¬A1 ) ∪ S(A2 ) ∪ {¬¬A1 → A2 }
S(¬A1 ) ∪ {¬¬A1 } ∪ {A2 } ∪ {¬¬A1 → A2 }
S(A1 ) ∪ {¬A1 } ∪ {¬¬A1 } ∪ {A2 } ∪ {¬¬A1 → A2 }
A1 ∪ {¬A1 } ∪ {¬¬A1 } ∪ {A2 } ∪ {¬¬A1 → A2 }
{A1 , A2 , ¬A1 , ¬¬A1 , ¬¬A1 → A2 }
Example 2
...
11 Obtain the subformulas of the formula
ϕ = A1 → A2 → ¬A3 = A1 → (A2 → ¬A3 )
S(ϕ) =
=
=
=
=
S (A1 → (A2 → ¬A3 ))
S(A1 ) ∪ S(A2 → ¬A3 ) ∪ {A1 → (A2 → ¬A3 )}
S(A1 ) ∪ S(A2 ) ∪ S(¬A3 ) ∪ {A2 → ¬A3 } ∪ {A1 → (A2 → ¬A3 )}
{A1 } ∪ {A2 } ∪ {A3 } ∪ {¬A3 } ∪ {A2 → ¬A3 } ∪ {A1 → (A2 → ¬A3 )}
{A1 , A2 , A3 , ¬A3 , A2 → ¬A3 , A1 → (A2 → ¬A3 )}
Ddumba & Kimuli
foundation of mathematics
Page 23 of 113
2
...
LANGUAGE
Exercise 2
...
6 Find all the subformulas of each of the following formulas
...
(¬((¬A56 ) → A56 ))
2
...
¬A0 ∧ ¬A1 ↔ ¬(A0 ∨ A1 )
Theorem 2
...
4 (Unique Readability Theorem) A formula of LP must satisfy exactly one
of conditions 1–3 in Definition 2
...
4
...
1
...
1
...
1
...
1
...
1
...
N
I
L
S
E
:
:
:
:
:
Network server is on
Typing a query command
Log will be updated
Typed from a secure terminal
Error is flagged
N ∧T →L↔S∨E
(N ∧ T ) → ((L ↔ S) ∨ E)
(ii) If you have a valid tax ticket or if you have a driver’s permit and you have at least a
credit in O-level English in which case you should not be less than 23 years old, then you
will be hired for the job
...
1
...
(i) C → ¬(R ∧ S)
If today is clear, then its not true that its rainy and cold
(ii) Y ↔ C
If and only if yestarday was cloudy, will today be clear
(iii) Y ∧ (C ∨ R)
Yestarday was cloudy but today will either be clear or rainy
(iv) (Y → R) ∨ C ↔ (R ∧ ¬S) ∨ Y
((Y → R) ∨ C) ↔ ((R ∧ ¬S) ∨ Y )
Ddumba & Kimuli
foundation of mathematics
Page 25 of 113
2
...
LANGUAGE
if and only if either yesterday was cloudy then will today be
rainy, or today will be clear then either today is rainy but not cold or yesterday was
cloudy
Example 2
...
16 Let the atomic formulas W, R and S be given by the following:
W : It is windy
R : It is rainy
S : It is sunny
Translate the following English statements into LP formulas (statements)
...
R → (W ∧ ¬S)
(b) It is not raining, if either the sun is shining or it is not windy
...
(W → R) ∨ (¬S → R)
(d) It is windy and not sunny only if it is raining
...
R → (W ∧ ¬S)
Page 26 of 113
Ddumba & Kimuli foundation of mathematics
2
...
TRUTH ASSIGNMENTS AND TRUTH TABLES
2
...
For example, if ϕ is the atomic formula A2 and we interpret it as
“2 + 2 = 4”, it is true, but if we interpret it as “The moon is made of cheese”, it is false
...
We will also
get a reasonable definition of what it means for a formula of LP to follow logically from other
formulas
...
2
...
2
...
v(An ) is defined for every atomic formula An
...
For any formula α,
v( (¬α) ) =
T if v(α) = F
F if v(α) = T
...
For any formulas α and β,
v( (α → β) ) =
F if v(α) = T and v(β) = F
T otherwise
...
Note that we have not defined how to
handle any truth values besides T and F in LP
...
For an example of how non-atomic formulas are given truth values on the basis of the truth
values given to their components, suppose v is a truth assignment such that v(A0 ) = T and
v(A1 ) = F
...
2
...
In turn, v( (¬A1 ) ) is determined from of v(A1 )
according to clause 2 and v( (A0 → A1 ) ) is determined from v(A1 ) and v(A0 ) according to clause
3
...
Thus v( (¬A1 ) ) = T and v( (A0 → A1 ) ) = F , so
v( ((¬A1 ) → (A0 → A1 )) ) = F
...
3 Can you come up with the truth assignments of ∧, ∨ and ↔
A convenient way to write out the determination of the truth value of a formula on a given
truth assignment is to use a truth table: list all the subformulas of the given formula across the
top in order of length and then fill in their truth values on the bottom from left to right
...
For the example above, one gets something like:
A0 A1 (¬A1 ) (A0 → A1 ) (¬A1 ) → (A0 → A1 ))
T F
T
F
F
In a summary
Ddumba & Kimuli
foundation of mathematics
Page 27 of 113
2
...
TRUTH ASSIGNMENTS AND TRUTH TABLES
2
...
2
Truth table for Negation (¬)
α ¬α
T F
F T
The negation of a proposition is its denial
...
A negation
proposition is therefore one that states ”it is false that p
...
However,
the simple insertion of ”NOT” in some propositions is generally not sufficient for obtaining a
negation of that proposition
...
If we try to form
the negation of this proposition by insertion of NOT will yield; ”this tea is NOT hot”
...
2
...
3
Truth table for Implication (→)
α
T
* T
F
F
α→β
T
F
T
T
β
T
F
T
F
Consider the following compound conditional propositions and interpret the statements
...
The conditional propositions b, c and d are all true
...
2
...
4
Truth table for conjunction (∧)
α
* T
T
F
F
β
T
F
T
F
α∧β
T
F
F
F
Example 2
...
1 Consider the following compound propositions: Interpret the conjunction
statement
...
(c) Kampala is in Uganda and 3 + 3 = 6
(d) Kampala is in America and 3 + 3 = 7
Page 28 of 113
Ddumba & Kimuli foundation of mathematics
2
...
TRUTH ASSIGNMENTS AND TRUTH TABLES
It is only the conjunction statement (c) which is true since both the simple propositions are true
...
2
...
5
Truth table for disjunction (∨)
α β α∨β
T T
T
T
T F
F T
T
F
* F F
Consider the following composite propositions and interpret the disjunction statements
...
It is only the disjunction statement a, b and c that are true since at least one of the simple
propositions is true
...
2
...
6
Truth table for Bi-implication, iff (↔)
α β α↔β
* T T
T
T F
F
F
F T
T
* F F
Consider the following composite propositions and interpret the bi-conditional statements
...
Example 2
...
2 Construct the truth table for P → (Q → R)
P
T
T
T
T
F
F
F
F
Ddumba & Kimuli
Q
T
T
F
F
T
T
F
F
R
T
F
T
F
T
F
T
F
(Q → R) P → (Q → R)
T
T
F
F
T
T
T
T
T
T
F
T
T
T
T
T
foundation of mathematics
Page 29 of 113
2
...
TRUTH ASSIGNMENTS AND TRUTH TABLES
Example 2
...
3 Construct the truth table for ¬C → ¬B
B
T
T
F
F
C ¬B ¬C ¬C → ¬B
T
F
F
T
F
F
T
F
T
F
T
T
F
T
T
T
Problem 2
...
¬A2 → ¬A3
We can use two methods, the truth assignment or the truth tables
...
¬A2 → A3
3
...
A0 ∨ A1
5
...
Proposition 2
...
Then u(δ) = v(δ)
...
2
...
Then u = v, i
...
u(ϕ) = v(ϕ) for every formula ϕ
...
2
...
3 If α and β are formulas and v is a truth assignment, then:
1
...
2
...
v(α ∧ β) = T if and only if v(α) = T and v(β) = T ;
4
...
v(α ↔ β) = T if and only if v(α) = v(β)
...
For example, if α and β are any formulas and we know that α is
true but β is false, then the truth of (α ∧ (¬β)) can be determined by means of the following
table:
α β (¬β) (α ∧ (¬β))
T F
T
T
Example 2
...
4 Construct the truth table for (P → Q ∨ R) ∧ (P ∨ ¬Q)
TTTFFFTT
Example 2
...
5 Construct the truth table for P → (Q ∨ R)
TTTFTTTT
Definition 2
...
2 If v is a truth assignment and ϕ is a formula, we will often say that v
satisfies ϕ if v(ϕ) = T
...
We will say that ϕ (respectively, Σ) is satisfiable if there is some
truth assignment which satisfies it
...
2
...
i
...
Definition 2
...
4 A formula ψ is a contradiction if there is no truth assignment which satisfies
it
...
e v(ϕ) = F ; ∀v
...
2
...
Example 2
...
7 α ∧ ¬α is a contradiction
...
2
...
One can check whether a given formula is a tautology,
contradiction, or neither, by grinding out a complete truth table for it, with a separate line
for each possible assignment of truth values to the atomic subformulas of the formula
...
Ddumba & Kimuli
foundation of mathematics
Page 31 of 113
2
...
TRUTH ASSIGNMENTS AND TRUTH TABLES
Note 2
...
1 Note that, by Proposition 2
...
Another way to show a tautology or a contradiction, is to use the method of contradiction
...
For example,
if α is any formula, then the table
α (α → α) (¬(α → α))
T
T
F
F
T
F
demonstrates that (¬(α → α)) is a contradiction, no matter which formula of LP α actually
is
...
4 If α is any formula, then ((¬α) ∨ α) is a tautology and ((¬α) ∧ α) is a
contradiction
...
5 A formula β is a tautology if and only if ¬β is a contradiction
...
Definition 2
...
5 A set of formulas Σ implies a formula ϕ, written as Σ |= ϕ, if every truth
assignment v which satisfies Σ also satisfies ϕ
...
e if v(δ) = T then v(ϕ) = T , ∀ δ ∈ Σ
...
In the case where Σ is empty, we will
usually write |= ϕ instead of ∅ |= ϕ
...
For example, { A3 , (A3 → ¬A7 ) } |= ¬A7 , but { A8 , (A5 → A8 ) } 6|= A5
...
) Note that a formula ϕ is a
tautology if and only if |= ϕ, and a contradiction if and only if |= (¬ϕ)
...
2
...
)
Example 2
...
10 6|= ¬(P ∨ Q ↔ Q ∨ P )
(its to show that its a contradiction )
Example 2
...
11 |= (P ∨ Q) ∨ (P → Q)
Example 2
...
12 |= A ∧ (A → B) → B
Example 2
...
13 |= ¬B ∧ (A → B)¬A
Example 2
...
14 |= (A ∧ B → C) → (A → (B → C))
Example 2
...
15 |= (A → B) ∧ (A → C) ↔ (A → B ∧ C)
Example 2
...
16 Prove whether the following statements are true
(i) A0 , A0 → A1 |= A1
Yes
(ii) A8 , (A5 → A8 ) |= A5
No
Page 32 of 113
Ddumba & Kimuli foundation of mathematics
2
...
TRUTH ASSIGNMENTS AND TRUTH TABLES
2
...
7
More Examples
Example 2
...
17 Prove that ¬ (P ∧ (P → (Q → P )) → (Q → P )) is a contradiction
...
2
...
Determine the truth values of the following:
(i) (¬P ∧ Q) ∨ ¬R → S
T
(ii) P ∧ R → R ∨ S
T
(iii) R ∨ ¬S → (P → S)
T
(iv) R ∨ (P → (R ↔ S))
T
(v) (P ∧ ¬Q) ∨ ¬R → (S ∨ ¬P )
T
Example 2
...
19 Construct truth tables for
(i) (A ∧ ¬B) ∨ (C ↔ ¬D)
A
T
T
T
T
T
T
T
T
F
F
F
F
F
F
F
F
B
T
T
T
T
F
F
F
F
T
T
T
T
F
F
F
F
C
T
T
F
F
T
T
F
F
T
T
F
F
T
T
F
F
D (A ∧ ¬B) (C ↔ ¬D) (A ∧ ¬B) ∨ (C ↔ ¬D)
T
F
F
F
F
F
T
T
T
F
T
T
F
F
F
F
T
T
F
T
F
T
T
T
T
T
T
T
F
T
F
T
T
F
F
F
F
F
T
T
T
F
T
T
F
F
F
F
T
F
F
F
F
F
T
T
T
F
T
T
F
F
F
F
(ii) (¬P → Q) → ((¬Q → P ) → ¬P )
P Q (¬P → Q) (¬Q → P ) ((¬Q → P ) → ¬P ) (¬P → Q) → ((¬Q → P ) → ¬P )
T T
T
T
F
F
T F
T
T
F
F
F T
T
T
T
T
F F
F
F
T
T
Ddumba & Kimuli
foundation of mathematics
Page 33 of 113
2
...
TRUTH ASSIGNMENTS AND TRUTH TABLES
(iii) R → P → Q ∨ R
R→P →Q∨R ≡
≡ R → P → (Q ∨ R)
≡ R → (P → (Q ∨ R))
P
T
T
T
T
F
F
F
F
Q
T
T
F
F
T
T
F
F
R
T
F
T
F
T
F
T
F
(Q ∨ R) (P → (Q ∨ R)) (R → (P
T
T
T
T
T
T
F
F
T
T
T
T
T
T
F
T
→ (Q ∨ R)))
T
T
T
T
T
T
T
T
Exercise 2
...
) A → B ∧ C
2
...
) ¬(P → P → P )
4
...
5 Prove that
(a)
|= P ∨ Q ↔ Q ∨ P
(b)
|= (P ∨ Q) ∨ (P → Q)
(c)
|= A ∧ (A → B) → B
(d)
|= ¬B ∧ (A → B)¬A
(e)
|= (A ∧ B → C) → (A → (B → C))
(f)
|= (A → B) ∧ (A → C) ↔ (A → B ∧ C)
(g)
6|= ¬(P ∨ Q ↔ Q ∨ P )
Page 34 of 113
Ddumba & Kimuli foundation of mathematics
2
...
PREPOSITION EQUIVALENCES
2
...
3
...
If the proposition p is logically equivalent to the proposition p then
proposition q is true, if and only if q is true
...
Example 2
...
1 Show that the proposition (p → q) and (p ∧ ¬q) are logically equivalent That
is, p → q ≡ ¬(p ∧ ¬q)
...
These can be drawn on separate tables or on
the same as shown below
...
The two propositions are therefore logically equivalent
...
(ii) Drawing on the table, we can obtain the same results as
p
T
T
F
F
q
T
F
T
F
¬q
F
T
F
T
p→q
T
F
T
T
p ∧ ¬q
F
T
F
F
¬(p ∧ ¬q)
T
F
T
T
We conclude that p → q ≡ ¬(p ∧ ¬q)
Ddumba & Kimuli
foundation of mathematics
Page 35 of 113
2
...
PREPOSITION EQUIVALENCES
Example 2
...
2 Show that ¬(p ∧ q) ≡ ¬p ∨ ¬q
...
3
...
3
...
4
...
4
Predicates and quantifiers
As noted in the Introduction, propositional logic has obvious deficiencies as a tool for mathematical reasoning
...
It does have enough in common with propositional logic to let us
recycle some of the material in Chapters seen
...
In mathematics
one often deals with structures consisting of a set of elements plus various operations on them
or relations among them
...
In most such cases, one frequently
uses symbols naming the operations or relations in question, symbols for variables which range
over the set of elements, symbols for logical connectives such as not and for all , plus auxiliary
symbols such as parentheses, to write formulas which express some fact about the structure in
question
...
A formal language
to do as much will require some or all of these: symbols for various logical notions and for
variables, some for functions or relations, plus auxiliary symbols
...
For a concrete example, consider elementary number theory
...
One might need symbols or
names for certain interesting numbers, say 0 and 1; for variables over N such as n and x; for
functions on N, say · and +; and for relations, say =, <, and |
...
A statement of mathematical English
such as “For all n and m, if n divides m, then n is less than or equal to m” can then be written
as a cool formula like
∀n∀m (n | m → (n < m ∧ n = m))
...
First, there are
many first-order languages one might wish to use, practically one for each subject, or even
problem, in mathematics
...
4
As with LP , our formal language for propositional logic, first-order languages are defined
by specifying their symbols and how these may be assembled into formulas
...
4
...
Parentheses: ( and )
...
Connectives: ¬ and →
...
Quantifier: Universal quantifier ∀ and existential quantifier ∃
...
However, trying to actually do most mathematics in such a language is so hard as to be
pointless
...
Ddumba & Kimuli
foundation of mathematics
Page 37 of 113
2
...
PREDICATES AND QUANTIFIERS
4
...
, vn ,
...
Equality: =
...
A (possibly empty) set of constant symbols
...
For each k ≥ 1, a (possibly empty) set of k-place function symbols
...
For each k ≥ 1, a (possibly empty) set of k-place relation (or predicate) symbols
...
Note 2
...
1 It is possible to define first-order languages without =, so = is considered a nonlogical symbol by many authors
...
Observe that any first-order language L has countably many logical symbols
...
Unless explicitly
stated otherwise, we will assume that every first-order language we encounter has only countably many non-logical symbols
...
Just as in LP , the parentheses are just punctuation while the connectives, ¬ and →, are
intended to express not and if
...
However, the rest of the symbols are new and are
intended to express ideas that cannot be handled by LP
...
g
...
The constant
symbols are meant to be names for particular elements of the structure under discussion
...
k-place relation symbols are intended to name
particular k-place relations among elements of the structure
...
Example 2
...
1 Since the logical symbols are always the same, first-order languages are usually
defined by specifying the non-logical symbols
...
• Constant symbols: 0 and 1
• Two 2-place function symbols: + and ·
• Two binary relation symbols: < and |
Each of these symbols is intended to represent the same thing it does in informal mathematical
usage: 0 and 1 are intended to be names for the numbers zero and one, + and · names for
the operations of addition and multiplications, and < and | names for the relations “less than”
and “divides”
...
For example, “n is prime” is a 1-place relation on the natural numbers, < is a 2-place or binary
relation on the rationals, and ~a × (~b × ~c) = ~0 is a 3-place relation on R3
...
e
...
Page 38 of 113
Ddumba & Kimuli foundation of mathematics
2
...
PREDICATES AND QUANTIFIERS
language to talk about a different structure – say the real numbers, R, with 0, 1, +, ·, and <
representing what they usually do and, just for fun, | interpreted as “is not equal to”
...
) We will usually use the same symbols in our formal languages that we use
informally for various common mathematical objects
...
Example 2
...
2 Here are some other first-order languages
...
4
...
1
...
2
...
A language for set theory, LS :
• 2-place relation symbol: ∈
4
...
Another language for elementary number theory, LN :
• Constant symbol: 0
• 1-place function symbol: S
• 2-place function symbols: +, ·, E
Here 0 is intended to represent zero, S the successor function, i
...
S(n) = n + 1, and E
the exponential function, i
...
E(n, m) = nm
...
A “worst-case” countable language, L1 :
• Constant symbols: c1 , c2 , c3 ,
...
• For each k ≥ 1, k-place relation symbols: P1k , P2k , P3k ,
...
It remains to specify how to form valid formulas from the symbols of a first-order language L
...
In fact, we first need to define a type of
expression in L which has no counterpart in propositional logic
...
4
...
4
...
Every variable symbol vn is a term
...
Every constant symbol c is a term
...
If f is a k-place function symbol and t1 ,
...
tk is also a term
...
Nothing else is a term
...
For example, in LN T or LN , +v0 v1 (informally, v0 + v1 ) is a
term, though precisely which natural number it represents depends on what values are assigned
to the variables v0 and v1
...
8 Which of the following are terms of one of the languages defined in Examples
2
...
1 and 2
...
2? If so, which of these language(s) are they terms of; if not, why not?
1
...
+0 · +v6 11
3
...
(< E101 → +11)
5
...
f43 f72 c4 v9 c1 v4
7
...
< v6 v2
9
...
Note 2
...
2 All capital letters except F, G, and H will be used to abbreviate predicates
...
4
...
4
...
B: —–is between —-and —b : the blue car
d : the red car
k : the truck
Ddumba & Kimuli
foundation of mathematics
Page 41 of 113
2
...
PREDICATES AND QUANTIFIERS
Bbdk
• Fred wrote Tom Jones but not Moll Flanders
W: —–wrote —f : Fred
j : Tom Jones
m : Moll Flanders
Wfj and not Wfm
• John loves Mary and Carol
Ljm and Ljc
• Lean Cassius stabbed Julius in the stomach or the chest
...
• If John is taller than Mary, then if Mary is taller that Ann, John is taller than Ann
...
5
...
Or
(∀x) (Ox → Mx ) ∨ (Cx → Mx )
• Every voter is a multipartist or movement
(∀x) (Vx → (Px ∨ Mx ))
2
...
(ii) List the symbols in the formal propositional language Lp
...
(b)
(i) Write the following as formulas using only the symbols of Lp
(i) α ↔ β → δ
(ii) α ∧ β ∨ δ
(ii) Write out (A ∨ B) ∧ B −→ A and ¬(A ←→ ¬D) ∧ B −→ ¬A −→ C with missing
parentheses included
...
(ii) If you have an A-level principal pass in mathematics or if you have two A-level
passes in subjects other than mathematics and you have at least a credit in O-level
mathematics in which case you should be less than 20 years old,then you will be
admitted
...
5
...
(ii) A formula A in Lp is a tautology
...
(i) ((P → Q) ∧ (Q → R)) → (P → R)
(ii) (A ∧ (A → B) → B)
(d)
(i) What does it mean to say ” A set of formulas Σ implies a formula ϕ, written as
Σ |= ϕ”
...
(ii) The symbols of LP are:
(a) Parentheses: ( and )
...
(b) Connectives: ¬ and →
...
, An ,
...
g He came to class
...
(iii) The order of precedence is ¬, ∧, ∨, →, and ↔
...
5
...
(p ∨ (l ∧ c ∧ y)) → a
Ddumba & Kimuli
foundation of mathematics
Page 45 of 113
2
...
QUESTIONS WITH ANSWERS
Question 2 Solutions
(a)
(i) The formulas of LP are those finite sequences or strings of the symbols which satisfy
the following rules:
i
...
ii
...
iii
...
iv
...
(ii) Suppose ϕ is a formula of LP
...
i
...
ii
...
iii
...
(ii1) S(¬A1 ∨ A2 ) = S(¬¬A1 → A2 )
=
=
=
=
=
S(¬¬A1 ) ∪ S(A2 ) ∪ {¬¬A1 → A2 }
S(¬A1 ) ∪ {¬¬A1 } ∪ {A2 } ∪ {¬¬A1 → A2 }
S(A1 ) ∪ {¬A1 } ∪ {¬¬A1 } ∪ {A2 } ∪ {¬¬A1 → A2 }
A1 ∪ {¬A1 } ∪ {¬¬A1 } ∪ {A2 } ∪ {¬¬A1 → A2 }
{A1 , A2 , ¬A1 , ¬¬A1 , ¬¬A1 → A2 }
(ii2) S(A1 → A2 → ¬A3 ) = S(A1 → (A2 → ¬A3 ))
=
=
=
=
(b)
S(A1 ) ∪ S(A2 → ¬A3 ) ∪ {A1 → (A2 → ¬A3 )}
S(A1 ) ∪ S(A2 ) ∪ S(¬A3 ) ∪ {A2 → ¬A3 } ∪ {A1 → (A2 → ¬A3 )}
{A1 } ∪ {A2 } ∪ {A3 } ∪ {¬A3 } ∪ {A2 → ¬A3 } ∪ {A1 → (A2 → ¬A3 )}
{A1 , A2 , A3 , ¬A3 , A2 → ¬A3 , A1 → (A2 → ¬A3 )}
(i) If v is a truth assignment and ϕ is a formula, we will often say that v satisfies ϕ if
v(ϕ) = T
...
We will say that ϕ (respectively, Σ) is satisfiable if there
is some truth assignment which satisfies it
...
i
...
(c) Lets use truth tables
(i) ((P → Q) ∧ (Q → R)) → (P → R)
P
T
T
T
T
F
F
F
F
Q
T
T
F
F
T
T
F
F
R P → Q Q → R (P → Q) ∧ (Q → R) P → R (P → Q) ∧ (Q → R) → (P → R
T
T
T
T
T
T
F
T
F
F
F
T
T
F
T
F
T
T
F
F
T
F
F
T
T
T
T
T
T
T
F
T
F
F
T
T
T
T
T
T
T
T
F
T
T
T
T
T
Page 46 of 113
Ddumba & Kimuli foundation of mathematics
2
...
QUESTIONS WITH ANSWERS
Thus a tautology
...
(d)
(i) A set of formulas Σ implies a formula ϕ, written as Σ |= ϕ, if every truth assignment
v which satisfies Σ also satisfies ϕ
...
e if v(δ) = T then v(ϕ) = T , ∀ δ ∈ Σ
...
(ii) A8 , (A5 → A8 ) |= A5 ?
Given v(A8 ) = T and v(A5 → A8 ) = T , Is v(A5 ) = T ? v(A5 → A8 ) = T
A5 A8 A5 → A8
T T
T
T F
F
F T
T
F F
T
v(A5 → A8 ) = T for rows 1,3 and 4
...
In
those row, v(A5 ) = T and v(A5 ) = F so we can not conclude that always v(A5 ) = T ,
thus not implied
...
e A8 , (A5 → A8 ) 6|= A5
Ddumba & Kimuli
foundation of mathematics
Page 47 of 113
Chapter 3
Methods of proofs
3
...
1
Necessary Condition
If A and B are two given conditions A is said to be a necessary condition for B if the condition
B cannot occur unless condition A also occurs
...
3
...
2
Sufficient Condition
Condition A is a sufficient condition for B if condition B always occurs when condition A
occurs
...
This can also be
written as;
if A, then B
...
0
...
This means that condition A occurs if and
only of condition B occurs
...
3
...
4
Validity of Statements
In logic we are concerned with determining the truth values of propositions from related propositions
...
3
...
,
An important class of compound propositions consists of those that are always true no matter
what the truth values of the variables p, q, etc are
...
But why one could be interested in a proposition that is always true and hence
48
3
...
DIRECT PROOF
boring ? The answer is that, you could be dealing with some rather complicated-looking
propositions which you hope to show are true ; and the only way you could show their truth
will be by using other propositions that are known to be true always
...
Clearly, a
compound proposition X is a contradiction if and only if ¬X is a tautology
...
If one asked you, which of the two ; a tautology or a contradiction, could be a valid statement ?
I believe many are going to say a tautology, but the answer is ’neither of the two’, though some
tautologies are valid arguments
...
ie it’s premises
force it’s conclusion to be true
...
Otherwise, a deductive
argument is said to be invalid
...
The following argument is valid, because it is
impossible for the premises to be true and the conclusion to nevertheless be false:
If the difference is not yet clear, consider the following examples :
Example 3
...
1
Either Elizabeth owns a Honda or she owns a TVS
...
Therefore, Elizabeth owns a TVS
...
An argument is valid if the premises and conclusion are
related to each other in the right way so that if the premises were true, then the conclusion
would have to be true as well
...
Consider, then an argument such as the following:
All toasters are items made of gold
...
Therefore, all toasters are time-travel devices
...
It may be hard to imagine these premises
being true, but it is not hard to see that if they were true, their truth would logically guarantee
the conclusion’s truth
...
A
valid argument may still have a false conclusion
...
A sound argument is one that is not
only valid, but begins with premises that are actually true
...
However, the following argument is both valid and sound:
No felons are eligible voters
...
Ddumba & Kimuli
foundation of mathematics
Page 49 of 113
3
...
DIRECT PROOF
Therefore, some professional athletes are not eligible voters
...
Therefore, so is the conclusion
...
It should be noted that both invalid, as well as
valid but unsound, arguments can nevertheless have true conclusions
...
Whether or not the premises of an argument are true depends on their specific content
...
The logical form of an argument is that
which remains of it when one abstracts away from the specific content of the premises and the
conclusion, i
...
, words naming things, their properties and relations, leaving only those elements
that are common to discourse and reasoning about any subject matter, i
...
, words such as ”all”,
”and”, ”not”, ”some”, etc
...
For example, consider
these two arguments:
All tigers are mammals
...
Therefore, no tigers are creatures with scales
...
No elephants are animals
...
These arguments share the same form:
All A are B ;
No B are C ;
Therefore, No A are C
...
Because they have this form, the examples above are
valid
...
Now consider:
All basketballs are round
...
Therefore, the Earth is a basketball
...
Page 50 of 113
Ddumba & Kimuli foundation of mathematics
3
...
DIRECT PROOF
Benedict xvi resides at the Vatican
...
These arguments also have the same form:
All A’s are F ;
X is F ;
Therefore, X is an A
...
This is easy to see with the first example
...
It could have been
possible for the premises to be true and the conclusion false
...
While it is accepted by most contemporary logicians that logical validity and invalidity is determined entirely by form, there is some dissent
...
Therefore, it is not square shaped
...
Therefore, he is not married
...
Arguments of this form are not valid as a rule
...
However, many logicians would respond to these complications in various ways
...
It might also be suggested, especially with the first argument, that while (even
without the additional premise) there is a necessary connection between the premise and the
conclusion, the sort of necessity involved is something other than ”logical” necessity, and hence
that this argument (in the simple form) should not be regarded as logically valid
...
The logical form of a statement is not always as easy to discern as one might expect
...
Take for example the two statements:
Ddumba & Kimuli
foundation of mathematics
Page 51 of 113
3
...
DIRECT PROOF
(1) Patrick is a ferocious tiger
...
Despite their apparent similarity, only (1) has the form ”x is a A that is F ”
...
One cannot validly infer from (2) that David is a duck
...
Consider
the statement:
(3) The King and Queen are visiting dignitaries
...
Either there are dignitaries that the
King and Queen are visiting, in which case the sentence (3) has the same logical form as ”The
King and Queen are playing violins,” or the King and Queen are themselves the dignitaries
who are visiting from somewhere else, in which case the sentence has the same logical form as
”The King and Queen are sniveling cowards
...
Consider:
The King and Queen are visiting dignitaries
...
Therefore, the King and Queen are doing something boring
...
Because of the difficulty in identifying the logical form of an argument, and the potential
deviation of logical form from grammatical form in ordinary language, contemporary logicians
typically make use of artificial logical languages in which logical form and grammatical form
coincide
...
The use of an artifically constructed language makes it easier to specify
a set of rules that determine whether or not a given argument is valid or invalid
...
Note 3
...
1 Validity of logical reasoning does not depend on the morality of the speaker
...
First, one must ask if the
premises provide support for the conclusion by examining the form of the argument
...
Then, one must ask whether the premises are true or false in
actuality
...
However, if an argument
does not pass these tests, its conclusion may still be true, despite that no support for its truth
is given by the argument
...
In that context, a formula (on its own) written in a
logical language is said to be valid if it comes out as true (or ”satisfied”) under all admissible or
standard assignments of meaning to that formula within the intended semantics for the logical
language
...
In trying to discover the difference between a tautology, a contradiction, a valid and a sound
argument, we have been able to get the tools used in identifying fallacious and valid arguments,
but ”how can we prove the Validity of statements ?”
...
Page 52 of 113
Ddumba & Kimuli foundation of mathematics
3
...
MATHEMATICAL INDUCTION
(ii) Use of rule of inference to construct proofs
...
3
...
1
Notion of a Proof
A proof is a valid argument that shows a given statement is logically true
...
A conclusion follows from the initial premises
...
The validity of an argument does not depend on the truth of its premises and conclusions
as you already saw in lecture 19
...
(ii) Euler’s circle diagrams can be drawn to test the validity of an argument
...
1
...
This means an argument must be
convincing for it to constitute a proof
...
But there are some generally accepted ones; such as proof by Mathematical
Induction
...
2
Mathematical Induction
In mathematics some statements or propositions are written in general terms such as:
n(n + 1)(2n + 1)
, n∈N
6
Sn = 1 + 3 + 5 +
...
Sn = 12 + 22 + 32 +
...
One can try to demonstrate or establish the truth of such expressions by making intelligent
guesses and assigning particular small values for n into the expression and finally concluding
that the sum of the n terms of the type Sn is equal to say n2
...
This means, we cannot prove a given
statement or expression by just checking a few cases that work, whatever method is used to
choose those cases
...
3
...
1
Principle of Mathematical Induction
A given proposition p(n) is true for every n ∈ N As long as p(1) is true, and for every k in N
...
Ddumba & Kimuli
foundation of mathematics
Page 53 of 113
3
...
MATHEMATICAL INDUCTION
3
...
2
Proof by Mathematical Induction
The proof by mathematical induction involves the following procedure:
1
...
2
...
The hypothesis
...
Finally, we show that the assumption made in (2) above guarantees that the equality of
the expression is also true for the value of n equal to k + 1
...
If the expression is true for n = 2, the it is also true for the
new value of n = 1 + 1, that is 2 + 1 = 3 and so on
...
this confirms that the
expression is true for all positive integers
...
P
Example 3
...
1 Show that ni=1 i = n2 (n + 1)
Step 1 Prove for n = 1
1
X
i = 1
i=1
n
1
(n + 1) =
(1 + 1) = 1
2
2
Step 2 Suppose
Pk
i=1
i = k2 (k + 1)
Step 3 Prove for n = k + 1
k+1
X
i=1
k+1
X
i =
k
X
i + (k + 1) =
i=1
i =
i=1
k
(k + 1)
(k + 1) + (k + 1) =
(k + 2)
2
2
(k + 1)
(k + 1)
((k + 1) + 1) =
(k + 2)
2
2
The LHS = RHS for all steps, thus proved
...
2
...
+ (2n − 1) = n2
n ∈ N
...
e Show that
Pn
i=1 (2i
− 1) = n2
Step 1 Prove for n = 1
1
X
(2i − 1) = 2(1) − 1 = 1
i=1
n2 = 1 2 = 1
Page 54 of 113
Ddumba & Kimuli foundation of mathematics
3
...
MATHEMATICAL INDUCTION
Step 2 Suppose
Pk
i=1 (2i
− 1) = k 2
Step 3 Prove for n = k + 1
k+1
k
X
X
(2i − 1) =
(2i − 1) + 2(k + 1) − 1 = k 2 + (2k + 1) = k 2 + 2k + 1 = (k + 1)2
i=1
i=1
n
2
= (k + 1)2
The LHS = RHS for all steps, thus proved
...
2
...
+ n2 =
i
...
Example 3
...
4 Prove by induction
• (1 × 2) + (2 × 3) + · · · + n(n + 1) = 31 n(n + 1)(n + 2)
• 13 + 23 + 33 +
...
+ (2n − 1)3 = n2 (2n2 − 1)
Pn
1
2
2
•
i=1 (2i − 1) = 3 n(4n − 1)
Pn
1
3
2n+3
•
i=1 n(n+2) = 4 − 2(n+1)(n+2)
•
Pn
i=1
arn−1 = a
1−rn
1−r
• 3 + 8 + · · · + (n2 − 1) = 61 n(n − 1)(2n + 5)
Ddumba & Kimuli
foundation of mathematics
Page 55 of 113
3
...
BY CONTRADICTION
3
...
We wish to be able to say with absolute certainty
that a property holds for all numbers or all cases, not just those we’ve tried, and not just because
it sounds convincing or would be quite nice if it were so
...
The ”Proof by Contradiction” is also known as reductio ad absurdum, which is probably
Latin for ”reduce it to something absurd”
...
3
...
If p is any statement, then symbolically, the law of contradiction can be stated as:- If p
is true then ¬p is false, and If p is false then ¬p is true
...
3
...
1
...
2
...
3
...
This means if the
hypothesis is false then the desired conclusion is established
...
3
...
3
Methodology
A proof by contradiction establishes the truth of a given proposition by the supposition that it
is false and the subsequent drawing of a conclusion that is contradictory to something that is
proven to be true
...
Example 3
...
1 Let a, b, and c be positive integers, prove that if (ab) is an odd number then
a and b are both odd, by contradiction
...
Hence ab = 2cb is
an even number
...
This means that the initial
assumption that a and b are not both odd is false
...
The next two types of proof are of limited significance but they are
introduced here all the same
...
3
...
Example 3
...
2 Consider the sentence ”If it is raining, then there are clouds in the sky”
...
3
...
q denotes, there are clouds in the sky
...
It’s converse q → p reads, ”If there are clouds in the sky, then it is
raining”
...
The contrapositive ¬q → ¬p says : ”If there
are no clouds in the sky, then it is not raining”
...
The example above illustrates that the truth of p → q does not imply that q → p is true, but
suggests that the truth of the Contrapositive ¬q → ¬p follows from that of p → q
...
If carol doesn’t buy a lottery ticket, then she will not win Sh 180M
...
We are not concerned with whether Carol wins Sh 180M [That is carol’s problem], but with
whether carol’s winning Sh 180M follows logically from previous two assertions
...
The first sentence only tells us that carol will not win Sh 180M if she doesn’t buy the ticket
...
(e
...
The reasoning
isn’t valid
...
But what is the formal frame work with which to analyze arguments of such as these ??
If H1 ∧ H2 ∧ · · · Hn ⇒ C with H1 , H2 , · · · , Hn the premises of a conclusion C, then
(a) ¬C ⇒ ¬(H1 ∧ H2 ∧ · · · Hn ) is the contrapositive
...
Its contrapositive is ”If m ≤
36 and n ≤ 36 then m + n ≤ 72” which is easier to prove than the original proposition
...
(b) ¬C ∧ H1 ∧ H2 ∧ · · · Hn ⇒ a contradiction, is another way to prove by contradiction
...
√
√
Example 3
...
3 We wish to prove that 2 is irrational
...
e x = 2 ⇒ x2 = 2 is an
irrational number
...
e x = pq where p, q, ∈ Z and q 6= 0
...
Thus (2k)2 = 2q 2 ⇒ q 2 = 2k 2 ⇒ q 2 is an even number,
which implies q is an even number, hence can be written as q = 2z
...
Hence 2 is irrational
...
3
...
If I study or if am a genius, then i will pass the course
...
Therefore, if Am not allowed to take the
next course, then Am not a genius
...
3
...
(2) If I pass the course, then I will be allowed to take the next course
...
By (3), it means Am not allowed to take the next course yet am a genius
...
Thus the original statement
”If I study or if am a genius, then i will pass the course
...
Therefore, if Am not allowed to take the next
course, then Am not a genius
...
To prove that the statement is invalid using
contradiction, consider the argument
...
Villa plays and wins
...
After contradicting the conclusion, we get the following statements;
(1) If Villa does not win the game, then KCC will lift the trophy
...
(3) KCC did lift the trophy
...
Villa plays
and wins
...
Note 3
...
1 A Contradiction is associated with several notorious paradoxes
...
In other words, according to the predicate calculus, no matter what p and q
mean, if p and ¬p are both true, then q is true
...
Thus, for example, the following argument is strictly valid, i
...
the premise logically entails the conclusion:
”If 5 is both even and odd, then God exists”
...
Note that the premise shared by both arguments is incorrect; 5 is odd, but is not even
...
Nonetheless, perhaps most people find it odd that, if 5 were both even and odd, one could
logically conclude anything about such an apparently unrelated matter as the existence
of God
...
3
...
3
...
If you reach a contradiction with something
you know is true, then the only possible problem can be in your initial assumption that X is
false
...
Unfortunately, this proof technique can really cause problems for amateurs
...
Somewhere in the confusion, a mistake is made, which leads to a contradiction
...
Even if someone points out the
mistake and the author tries to correct it, the same thing can happen again (either with a new
mistake in the corrected version, or with a different mistake that was already present in the
first attempt)
...
How can one create such confidence?
Unfortunately, I don’t have much of an answer
...
Beyond that, all I can do is offer some advice about structuring a
proof by contradiction
...
If they sound weird, or even false, is that because you’ve made a mistake, or
because you’ve reached the contradiction? To avoid this issue, it’s often best to try to build up
as much of the framework for the proof as possible outside of the actual proof by contradiction
...
If you can, I recommend
stating and proving them first, before making the initial assumption one hopes to disprove
...
If you
make the actual proof by contradiction as short and simple as possible, then it will help you
avoid mistakes and help other people check your work
...
3
...
You start a proof by contradiction by supposing that the statement
S is false
...
Since the
assumption that S is false led to a contradiction, the statement ”S is false” must itself be false;
in other words, S must be true!
Note 3
...
3 One final note: Proof by contradiction should not be used if you can think of a
more ”constructive” proof, i
...
a proof that starts only from the assumptions of the problem
and makes a connected logical argument to arrive at the desired conclusion
...
3
...
After a few minutes trying to figure out how to prove this statement you’ll probably realize
that it’s pretty difficult to prove that a given number is irrational
...
3
...
Given that: r is a rational number, and x is an irrational number
...
Proof: Seeking a contradiction, suppose that r + x is rational
...
Thus (r + x) + (−r) = x is rational; this contradicts our original hypothesis that x is
irrational
...
e
...
Note that in the proof above, we made up some notation; we let r represent an arbitrary
rational number, and chose x to represent an arbitrary irrational number
...
It is also worth noting that if
you look up the answer to this problem in the back of the book it says simply ”if r and r + x
are rational, then x = (r + x) − r is rational
...
Example 3
...
6 If m and n are integers and mn is odd, then m is odd and n is odd
...
3
...
Let m is rational and n is rational
Exercise 3
...
Exercise 3
...
3 There is no rational number solution to the equation
x5 + x4 + x3 + x2 + 1 = 0
Exercise 3
...
Exercise 3
...
√
(ii) 5 is irrational
...
Exercise 3
...
Page 60 of 113
Ddumba & Kimuli foundation of mathematics
3
...
PROOF BY COUNTER-EXAMPLE
3
...
These cases provide evidence of the conjecture or probable
inference
...
We usually try to disprove the conjecture by logical reasoning but not by observation or measurement
...
The single special case is called a counter example of the original statement
...
it is interesting to note that
it is easier to prove that a given statement is false than it is to prove that it is true since just
a single counter example is sufficient to disprove a statement
...
Example 3
...
1 Prove the statement that p = n2 − n + 41 is always a prime number for every
non-negative n
...
If n = 2 then P =
=
=
But if n = 41 =
=
(2)2 − 2 + 41
4 − 2 + 41
43, This is a prime number
...
The case n = 41 disproves the statement
...
Example 3
...
2 Prove (disprove) the proposition that if x is a real number whose square is
16, then x is greater than 3
...
If x is a real number whose square
is 16, then x is greater than 3 is false since when x = −4 then x2 = 16 yet x is less than 3
...
3
...
1
More details
What of statements like ”Every even integer greater than 4 is the sum of two prime numbers”
...
We will often be
able to prove such propositions by using an important technique mathematical induction
...
So to disprove such a compound
proposition, it’s enough to show that one of its propositions is false
...
e a
counter example
...
Gerald ford is a counterexample to the assertion that ”All American presidents have
been right handed”
...
Ssentamu is a counterexample to the assertion that ”All England
archbishops are whites”
...
5
...
If you guess it’s true, then analyze the situation to see why it’s true
...
If you fail to find the proof, you can see why ? then you
might discover a counter example
...
Note 3
...
1 As we end the chapter, you should always remember that: The constant emphasis
on logic and proofs is what sets mathematics apart from other pursuits
...
Consequently, one must recognize
and separate factual information from subjective content
...
Exercise 3
...
Example 3
...
3 All students in this class are ugandans
Example 3
...
4 For example, consider the assertion that for all integers n, n > 1, there
are no positive integer solutions for x, y, and z to the equation xn + y n = z n
...
For n > 2,
however, the statement is true and is known as F ermat0 s Last Theorem
...
Example 3
...
5 For example, if you’re trying to prove the statement ”All cheesecakes are
baked in Alaska
...
Exercise 3
...
(ii) Every girl put on skirts
...
(iv) An islands is on land
...
(vi) All American presidents have been right-handed
...
5
Truth Table
Validity of an Argument
An argument arises from propositions called premises and result in a proposition called a
conclusion
...
An argument that is valid , if all the premises used in a sequence of reasoning are true
then conclusion drawn from them must be true for the argument to be valid
...
An argument
is usually presented in the form:
P1 : premise
P2 : premise
Therefore C: conclusion
Page 62 of 113
Ddumba & Kimuli foundation of mathematics
3
...
TRUTH TABLE
(i) Valid: if true whenever all premises are true
...
(iii) Fallacy: if true and false whenever all premises are true
...
pn
Premise (s)
Conclusion
(iii) Check the rows in which all the premises are true
...
Example 3
...
1 Determine the validity of the following argument
...
Therefore C: Opolot did not pass his Examination
...
p
T
T
F
F
q
T
F
T
F
Premises
p→q
T
F
T
T
Premises
¬p
F
F
T
T
Conclusions
¬q
F
T
F
T
(iii) Check the rows containing true values for the premises and the corresponding truth value
for the conclusion
...
5
...
Example 3
...
2 Find out if the following argument is valid
...
Therefore C: Express wins and Villa lifts the trophy
...
This is therefore a valid argument
...
pn ) is a tautology, where p1 , p2
...
We proceed as follows:
(i) Write the argument in symbolic notation
...
pn ) → q
...
Example 3
...
3 Determine the validity of the following argument
...
P2 : You do not return the books on time
...
The symbolic form of the argument
Let p = return book bank books on time
q = have no results
...
Now the argument is
P1 : p ∨ q
P2 : ¬p
therefore C : q
Page 64 of 113
Ddumba & Kimuli foundation of mathematics
3
...
TRUTH TABLE
(i) The truth-table associated with [(p ∨ q) ∧ ¬p] → q is
p
T
T
F
F
q
T
F
T
F
p∨q
T
T
T
F
¬p
F
F
T
T
(p ∨ q) ∧ ¬p
F
F
T
F
[(p ∨ q) ∧ ¬p] → q
T
T
T
T
(iii) The entries of the last column are all true values, the proposition is a Tautology
...
Or we can stick to method before All the rows containing true values for the premises (row 3
p
T
T
F
F
q
T
F
T
F
p∨q
T
T
T
F
¬p
F
F
T
T
only) have a corresponding true value in the conclusion
...
(a) Modus Ponens
P1 : p → q
P2 : p
Therefore C : q
In p → q, p is an antecedent and q is a consequent A statement in the modus ponens form
requires that if both premises p → q and p are true than the conclusion q must also be
true
...
(b) Modus Tollens
P1 : p → q
P2 : ¬q
Therefore C : ¬p
A statement in the modus tollens form requires that if p occurs, q occurs, but q is not occurring
hence p is not occurring
...
5
...
P1 : p → q
P2 : ¬p
Therefore C : ¬q
(iii) Hypothetical syllogism
P1 : p → q
P2 : q → r
Therefore C : p → r
The statement in a hypothetical syllogism requires that if the premises p → q and q → r
are true then the conclusion p → r must also be true
...
Examples of invalid arguments resembling hypothetical syllogic are:
(i)
P1 : p → q
P2 : p → r
Therefore C : q → r
(ii)
P1 : q → p
P2 : r → p
Therefore C : q → r
Page 66 of 113
Ddumba & Kimuli foundation of mathematics
3
...
TRUTH TABLE
Example 3
...
4 Brown, Jones and Smith are suspectected of a crime
...
• Jones : If Brown is guilty then so is Smith
...
Let b, j and s be statements ”Brown is innocent”, ”Jones is innocent”,and ”Smith is innocent”
...
which from which?
(c) Assuming everyone is innocent, who committed perjury?
(d) Assuming all testimony is true, who is innocent and who is guilty ?
(e) assuming that the innocent told the truth, and the guilty told lies, who is innocent and
who is guilty?
The testimonies are
• B : ¬j ∧ s
• J : ¬b → ¬s
• S : s ∧ (¬b ∨ ¬j)
b
T
T
T
T
F
F
F
F
j
T
T
F
F
T
T
F
F
s
T
F
T
F
T
F
T
F
¬j ∧ s ¬b → ¬s s ∧ (¬b ∨ ¬j)
F
T
F
F
T
F
T
T
T
F
T
F
F
F
T
F
T
F
T
F
T
F
T
F
(a) Yes by line 3 of the table
...
In other words,
Smith’s testimony follows from Brown’s
...
e Brown and Smith lied
...
Thus Brown and Smith are innocent,
while Jones is guilty
...
Hence
we are in line 6 of the table
...
Example 3
...
5 Kato Walubwama, the gifted but caustic stand up comedian, has been murdered by one of the four suspects now appearing on Lie Detector
...
But we aren’t told which three
...
5
...
’
Dinwiddlie : ’Walubwama was killed by Adorno
...
’
Barchester : ’Dinwiddlie murdered him
...
’
Adorno : ’No I didn’t kill him
...
a
T
T
T
T
F
F
F
F
d
T
T
F
F
T
T
F
F
g
T
F
T
F
T
F
T
F
¬g
F
T
F
T
F
T
F
T
a
T
T
T
T
F
F
F
F
d ¬a
T F
T F
F F
F F
T T
T T
F T
F T
Which row meets the requirement of three false responses? Row 7, columns iv, v and vi
shows three false responses: ¬g; a; d are all three false in Row 7
...
Look at the value of Row 8, who lied? Barchester, Dinwiddie, and Glass are the liars
...
This will mean that two
people Adorn and Glass killed, which is impossible
...
5
...
(Two of the three statements are true
...
Example 3
...
7 Who killed Gudula? (Three and only three of the following statements are
false
...
Page 68 of 113
Ddumba & Kimuli foundation of mathematics
3
...
TRUTH TABLE
Lydia : Gudula was murdered by Steven
...
5
...
Either he is good in logic or
bad in history
...
If he is good in logic, he is good in
history
...
h∨s
Either Tom is good in logic or bad in history
...
s→l
If he is good in logic, he is good in history
...
Notice that l & h
...
Example 3
...
9 Four friends have been identified as suspects for an unauthorized access into
a computer system
...
Alice : ’Carlos did it
...
(ii) If the authorities also know that exactly one is lying, who did it? Explain your reasoning
...
5
...
By contradiction
Example 3
...
11
If you do every problem in this handout, then you will learn computational maths
...
Ddumba & Kimuli
foundation of mathematics
Page 69 of 113
3
...
TRUTH TABLE
Therefore, you did every problem in this handout
...
5
...
If we do not have a barbecue today, then we will have a barbecue tomorrow
...
Let
p : it rains today
q : To have a barbecue today
r : To have a barbecue tomorrow
To have the premises and conclusion as
p → ¬q
¬q → r
Therefore, p → r
p
T
T
T
T
F
F
F
F
q
T
T
F
F
T
T
F
F
r
T
F
T
F
T
F
T
F
p → ¬q ¬q → r p → r
F
F
T
F
T
F
T
T
T
T
F
F
T
T
T
T
T
T
T
T
T
T
F
T
Rows 3, 5, 6, 7 will make the argument VALID
Page 70 of 113
Ddumba & Kimuli foundation of mathematics
Chapter 4
Permutation and Combination
Any finite number of elements can be put together in groups based on certain rules
...
The sets can comprise from 0 elements to infinity
...
The number sets are the most important mathematically
...
In the
case of the alphanumerical sets, mathematics works with the indices, indexes of the respective
elements
...
No, they are the mysterious fluorescent fungus growing on those trees
...
But if youre going for a Math score above 700, you should know how to deal
with them
...
4
...
So, if
you become a wedding planner and youre asked how many different ways six people can sit at
a table with six chairs, the answer is 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720
4
...
A permutation, however, is an
ordering of elements
...
2
...
2
...
If there are six candidates running, and the candidates are celebrities who
dont care which office theyre elected to, how many different ways can the Hall government be
71
4
...
PERMUTATION
composed? Except that Hall politics are funny, this question is no different from the question
about the ordering of six people in six chairs
...
If you are wondering how ?, consider ;
Example 4
...
1 Given the letters EM GP , in how many ways can you arrange them ? Since
n! = 4! = 24 ways
...
what if you
have four books you want to arrange in the shelves , still 24 ways you can do it
...
The first place can have 4 alteranatives ( can have any of the 4 in the first place)
...
In 3rd have 2 options only , and can get any of the two there
...
i
...
Thus 4 × 3 × 2 × 1 = 24
...
The same
six candidates are still running
...
2
...
Instead of multiplying everything out, you could have canceled out the 3 × 2 × 1 in both
numerator and denominator, and just multiplied 6 × 5 × 4 = 120
...
2
...
4 P2
=
4!
4!
4×3×2×1
=
=
= 12
(4 − 2)!
2!
2×1
Clearly
Page 72 of 113
Ddumba & Kimuli foundation of mathematics
4
...
PERMUTATION
ME EG PE
MG EP PM
MP PG EM
GM
GE
GP
Which are 12 ways you can arrange the 2 letters from 4 (one can form
12 arrangements )
...
The first place can have 4 alteranatives ( can have any of the 4 in the first place)
...
Thus 4 and 3 possible ways to occupy the positions
...
Example 4
...
3 How many ways can one draw 5 cards in a deck of 52 cards
...
Alternately since 4 letters EM GP , lets have 1st 2nd 3rd 4th places to fill with them
...
For the 2nd place , since already put one of the cards in the first position, then you are
left with 51 options, and can have any in 2nd place
...
In 4th place , you are left with 49 options only
...
Coming up to 52 and 51 and 50 and 49 and 48 possible ways to occupy the positions
...
Theorem 4
...
3 Circular Permutation :
The number of permutation of n-distinct objects arranged in a circle are (n − 1)!
In a circle you have to first fix one of them in one place so that you arrange the remaining since
if not it will be very confusing to know who was next to the other as every one in a circle can
have two neighbors
...
2
...
(n − 1)! = (5 − 1)! = 4!
Theorem 4
...
4 : The number of permutations of n-objects of which n1 of one kind , n2 of
the second kind upto nk kind is
n!
(n1 ! n2 ! · · · nk !)
Example 4
...
5 Suppose that the 4 letters M EGP in the above had 2 of one kind and 2 of
the other kind the number of permutation is
4!
4×3×2×1
=
= 6 ways
(2! 2!)
(2 × 1)(2 × 1)
Clearly
Ddumba & Kimuli
foundation of mathematics
Page 73 of 113
4
...
COMBINATION
MEME
MEEM
MMEE
EMEM
EMME
EEMM
It should have been all the 24 ways , but only 6 are right since the others are just a repetition
of these
...
2
...
2
...
2
...
3
Combination
The combinations are the best-known element of the four mathematical sets
...
The random number
generation of the arrangements is actually closer to the lotto drawings
...
The random number
generation of the combinations in PermuteCombine
...
A combination is an unordered grouping of a set
...
An example of
a combination scenario in which order doesnt matter is a hand of cards: a king, an ace, and a
five is the same as an ace, a five, and a king
...
Because the order of the elements in a given subgroup doesnt matter, this
means that n Cr will be less than n Pr
...
In counting problems where order matters, r-permutations are permutation are clearly relevant
...
The
n
number
is read ” n Choose r” is what is called the number of combinations of n things
r
taken r at a time
...
3
...
3
...
How many ways can this be done? In this example, the order in which
the leaders are assigned to positions doesnt matter - the leaders arent distinguished from one
another in any way, unlike in the Hall of residence example
...
So, to figure out how
many different groups of three can be taken from a group of six, do this:
6 C3
=
6!
= 20
3! 3!
There are only 20 different ways to elect three leaders, as opposed to 120 ways when the
leadership jobs were differentiated
...
3
...
someone could be tempted to say:- M EP , but it’s the same combination of subjects like
P EM though the arrangement (permutation) could be different
...
3
...
g
...
g
...
Formula:
5 C3
=
5×4×3×2×1
5!
=
= 5 × 2 = 10
((5 − 3)! 3!)
(2 × 1 × 3 × 2 × 1)
How would we work out this problem?
Let’s look into this and see where the formula comes from for determining the number of ways
of choosing 3 people from a group of 5
...
It is often written in symbols as ”m Cn ” or
”C(m, n)”
...
But instead of just memorizing a magical formula, let’s look at what the formula means
...
Let’s suppose first that there is an election with five candidates, and the three candidates with
the highest vote totals get the offices of president, vice president, and assistant vice president,
Ddumba & Kimuli
foundation of mathematics
Page 75 of 113
4
...
COMBINATION
respectively
...
So the ”5 × 4 × 3” in the numerator of ”5 choose 3” is the number of ways of choosing three
objects from a group of five if the order of selection is important
...
The order of
selection is not important; this is the situation where the concept of ”5 choose 3” applies
...
How many of the entries in the list of the 60 possible outcomes of the election
have the same combination of candidates A, B, and C but in different orders? Well, any one of
the three could have been the top vote getter; and for each of those three possibilities, either
of the other two could have been the next highest vote getter, giving 3 × 2 = 6 possible orders
for the first two of the three; and for each of those six possible orders, there would be only
one possibility for the third-place vote getter
...
So the ”3 × 2 × 1” in the denominator of ”5 choose 3” is the number of different orders in which
any particular group of three could have been chosen
...
The fraction with
”5 × 4 × 3” in the numerator and ”3 × 2 × 1” in the denominator thus represents the number
of different ways of choosing 3 out of 5 if order is not important
...
These numbers mean that there are 60 ways to order any
In numbers, 5 C3 = 5×4×3
3×2×1
6
three of five objects, and for each particular group of three there are six ways to order them;
so the number of distinct groups of three out of five objects is 60 divided by 6
...
4
...
For a final quick review of what we have presented above, here is the thinking when you want
to find the value of ”9 choose 4”: 9 C4 = number of ways to choose 4 out of 9
=
=
number of ways to choose 4 out of 9 if order is important
number of different orders to choose each group of 4
(four factors starting with 9 and decreasing by 1 each time)
(four factors starting with 4 and decreasing by 1 each time)
9×8×7×6
4×3×2×1
Simillary, without all the words, just showing the numbers:
=
10
C7 =
10 × 9 × 8 × 7 × 6 × 5 × 4
7×6×5×4×3×2×1
Example 4
...
3 : From four boys A, B, C, D and 2 girls (X, Y ) find the number of committees
that can be formed with 2 boys and one girl:
Getting 2 boys from 4 boys and 1 girl from 2 girls
4!
2!
4
2
4
2
and
=
...
4
Further Examples
Exercise 4
...
(i) If each digit can be used once ?
Realize there are 7 digits, but to have a 3-digit number, the digit 0 can’t start eg we
can’t say 021 is a three digit number, so
1st
6
2nd
6
3rd
5
=
180 ways
(ii) How many of them are odd numbers?
An odd number of 3 digits, should have its last digit as {1, 3, 5}, so 3 ways you can
write the last digit and then, 5 ways you can write the first digit since already one
digit is put at the last position and yet 0 can’t start, and finally 5 ways for the 2nd
digit
1st
5
2nd
5
3rd
3
=
75 ways
(iii) How many are greater than 330
...
In how many ways can the
3 runners from team A finish first, second and third and the runner in B finish fourth,
fifth and sixth?
(3 × 2 × 1) and (3 × 2 × 1) = (3 × 2 × 1)
...
4
...
In how many ways will no guest receive the
proper hat?
(1 × 3 × 1 × 1) or (1 × 3 × 1 × 1) or (1 × 3 × 1 × 1) = 3 + 3 + 3 = 9 ways, if
let A get a hat of B or of C or of D
...
4
...
(4) Four couples have bought 8 seats in a row for a concert
...
(F1 M1 ), (F2 M2 ), (F3 M3 ), (F4 M4 ),
now the problem is of how to arrange those 4 couples, which is 4 × 3 × 2 × 1 = 4!
ways
(iii) If all men sit together to the right of females
...
How many selections of 9 apples are
possible if 3 of each colour are to be selected
...
4
5
6
4
5
6
and
and
=
...
= 800 selections
3
3
3
3
3
3
(7) In how many ways can the word ”W hite” end with a vowel?
Vowels are a, e, i, o, u In ”W hite” there are only 2 vowels
...
In how many ways can one arrange to go
on one of the these tours ?
The possible tours are six in a day = 6 P1 , thus for 3 days, = 3 (6 P1 ) = 18 tours
...
(i) How many ways can a student check off one answer
...
And it is the same for Qns 1 and 2 and 3
and 4 and 5
...
Page 78 of 113
Ddumba & Kimuli foundation of mathematics
4
...
FURTHER EXAMPLES
(ii) How many ways can a student check off one answer to each question and get all the
questions wrong
...
Exercise 4
...
How many committees can be chosen
from this class consisting
(a) Seven people
(b) Three men and four women
(c) Seven women or seven men
(2) (a) How many committees consisting of 4 people can be chosen from 9 people
...
(3) How many committees consisting of 4 men and 4 women can be chosen from a group of
8 men and 6 women
...
(5) In how many ways can the letters a, b, c, d, e, f be arranged
(a) So that the letters a and b are adjacent
...
(6) In how many ways can 19 students be divided into five groups, two of five and 3 groups
of three so that each group studies a different topic?
(7) From a total of 15 people, 3 committees consisting 3, 4 and 5 people respectively are to
be chosen
...
(a) In how many ways can this be done
...
4
...
Each box is to be filled up either with a red or a
green ball in such a way that at least 1 box contains a green ball and the boxes containing
greination in how many ways
...
50
(c) If the instruction now change to; A student must answer seven of the ten questions
were atleast three are selected from the first five
...
) * In how many ways can ten (identical) dimes be distributed among five children if,
14
(i) no restriction
(ii) each child gets at least one dime
(iii) the oldest child gets at least two dimes
C10
9
C5
12
C8
Consider 3 letters A, B, C
...
In all these, the first letter may be A or B or C
...
Once the first letter has been chosen, there are two
letters remaining - so there are two ways in which we can choose the second letter to arrange
...
Hence in all, there are 3x2x1 = 3! = 6 ways of arranging 3 letters
A, B, C
...
All in all, there are 4 × 3 × 2 × 1 = 4! = 24 ways of arranging 4 letters A, B, C, D
...
4
...
4
...
4
...
4
...
4
...
453600
(iii) if the word must start and end with M
...
4
...
If the letters of the word CALCULATOR are arranged in a line, find the probability that
2880
1
the word begins with C and ends with A
...
Ten pupils are placed on a bench
...
(a) How many numbers greater than 40000 can be formed from the digits 2, 3, 4, 5, 6 if
each digit is used once?
72
(b) How many of these end with 2?
(c) What is the probability that the number id divisible by 5?
18
12
72
Example 4
...
6
1
...
2
...
3
...
What is the probability that the two
that do not light are next to each other?
Since circular, number of ways is (n − 1! = 5 If the bulbs that do not light are next to
each other then as single bulb first we have 4 bulbs arranged in 4!ways, and then 2 that
2!4!
cannot light, to give 2!4! ways
...
One white, one blue, one red and two yellow beads are to be threaded on a ring to make
a bracelet
...
Since there are two yellows, the total number of ways of arranging the beads is
4!
(2!)
= 12
If red and white are next each other, the number of ways of arranging them is 2! and then
there are 3 more to arrange in 3! ways but on a ring with two yellows to give
2!3!
(2!)
= 6 therefore Prob (the red and white are next to each other)
6
12
=
1
2
Example 4
...
7
Out of 5 Mathematicians and 7 Physicists, a committee of 2 Mathematicians and 3 Physicists
is t be formed