Chapter One: Introduction to logic and mathematical proof

1.1 Introduction to logic and statement

Logic is the study of correct reasoning.
 It is studies arguments, which consist of a set of premises together with a conclusion.
 It includes both formal and informal logic.
 Formal logic is the science of deductively valid inferences or logical truths.
 Formal logic is also known as symbolic logic and is widely used in mathematical logic. It
uses a formal approach to study reasoning

Definition: A statement is a declarative sentence, or part of a sentence, that can be true or false.

The following are examples of statements.

1. 9 is prime number.
2. I am hungry.
3. 2 is an even number.
4. A triangle has four sides.
1.2 Propositional and predicate logic
1.2.1 Propositional logic
Definition: A proposition (or statement) is a sentence which has a truth value (either True or
False but not both).
Remark: Every proposition has a truth value, namely true (denoted by 𝑻) or false (denoted by 𝑭).
Example 1:
1. 1 is less than three T
2. 14 is odd number F

Types of proposition

1. Simple proposition
2. Compound proposition

1
1. Simple proposition: The proposition having one subject and one predicate is called a simple
proposition.

 Has single idea.

 Cannot be broken down into simpler propositions.
 Does not contain logical connectives.

Example 2:

1. Every even number is divisible by 2.

2. 9 is prime number.

2. Compound proposition

Definition: The proposition formed by joining two or more propositions by connective(s) is

called a compound statement.

 Has more than one idea

 Can be broken down into two or more simpler propositions
 Formed using connectives or logic operators

Example 3:

1. The earth is round and revolves around the sun.

2. A triangle is equilateral if and only if its three sides are equal.
3. If you study hard, then you will get good grades.

Activity 1

Write simple proposition if it is a simple proposition, compound proposition if it is a compound

proposition.

1. Math is fun.
2. Two is the smallest prime number.
3. My favorite subject is Mathematics.
4. I can sing and dance.
5. What’s your favorite movie?
6. Read the newspaper.

2
Logical connectives

 Negation (“not”), denoted ¬

 Conjunction (“and”), denoted ∧
 Disjunction (“or”), denoted ∨
 Conditional (“if-then” or “implication”), denoted
 Bi-conditional (“if and only if” or “double implication”), denoted

Negation

Given any proposition , we can form the proposition called the negation of . The truth
value of is 𝐹 if is and if is 𝐹.

The proposition is false when is true, and true when is false

Example 4: Let : Addis Ababa is the capital city of Ethiopia. (True)

: Addis Ababa is not the capital city of Ethiopia. (False)

Activity 2

State the negation of each of the following statements.

a) √2 is a rational number.
b) 0 is not a negative integer.
c) 111 is a prime number.

Conjunction

When two propositions are joined with the connective “and,” the proposition formed is a logical
conjunction. “and” is denoted by “∧”. So, the logical conjunction of two propositions, and , is
written:

∧ , read as “ and ,” or “ conjunction ”.

3
  and are called the components of the conjunction.
 ∧ is true if and only if is true and is true.

The truth table for conjunction is given as follows:

Example 5: Consider the following propositions:

: 3 is an odd number. (True)

: 27 is a prime number. (False)

𝑟: Addis Ababa is the capital city of Ethiopia. (True)

a) ∧ : 3 is an odd number and 27 is a prime number. (False)

b) ∧ 𝑟: 3 is an odd number and Addis Ababa is the capital city of Ethiopia. (True)

Disjunction

When two propositions are joined with the connective “or,” the proposition formed is called a
logical disjunction. “or” is denoted by “∨”. So, the logical disjunction of two propositions, and
, is written:

∨ read as “ or ” or “ disjunction .”

 ∨ is false if and only if both and are false.

The truth table for disjunction is given as follows:

4
Example 6: Consider the following propositions:

is an odd number. (True)

is a prime number. (False)

: Nairobi is the capital city of Ethiopia. (False)

a) ∨ is an odd number or 27 is a prime number. (True)

b) ∨ is a prime number or Nairobi is the capital city of Ethiopia. (False)

Implication

When two propositions are joined with the connective “implies,” the proposition formed is called
a logical implication. “implies” is denoted by “ ” So, the logical implication of two
propositions, and , is written:

read as “ implies .”

The function of the connective “implies” between two propositions is the same as the use of “If
… then …” Thus can be read as “if , then .” is false if and only if is true and
is false.

The following is the truth table for implication.

Examples 7: Consider the following propositions:

: 3 is an odd number. (True)

: 27 is a prime number. (False)

𝑟: Addis Ababa is the capital city of Ethiopia. (True)

5
 : If 3 is an odd number, then 27 is prime. (False)

𝑟: If 3 is an odd number, then Addis Ababa is the capital city of Ethiopia. (True)

Bi-implication

When two propositions are joined with the connective “bi-implication,” the proposition formed
is called a logical bi-implication or a logical equivalence. A bi-implication is denoted by “ ”.
So the logical biimplication of two propositions, and, is written:

is false if and only if and have different truth values.

The truth table for bi-implication is given by:

Example 8: a) Let : 2 is greater than 3. (False)

: 5 is greater than 4. (True)

Then

: 2 is greater than 3 if and only if 5 is greater than 4. (False)

b) Consider the following propositions:

: 3 is an odd number. (True)

: 2 is a prime number. (True)
: 3 is an odd number if and only if 2 is a prime number. (True)

Activity 3

1. Let : 15 is an odd number.

: 21 is a prime number.

6
2. State each of the following in words, and determine the truth value of each.

a) ∨ e) .

b) ∧ . f) .

c) ∨ . g) .

d) ∧ . h) .

The possible truth values of a proposition are often listed in a table, called a truth table.

If and are propositions, then there are four possible combinations of truth values for and
.

, 𝐹, 𝐹 and 𝐹𝐹

If and 𝑟 are propositions, then there are eight possible combinations of truth values for ,
and 𝑟.

In general, a truth table involving “ ” propositions , ,…, contains possible

combinations of truth values.

For these propositions, a truth table showing these combinations would have columns and
rows.

 Phrases translations:

Phrase Logical translation

P, but Q P∧Q

Either P or Q P∨Q

P or Q, but not both (P∨Q)∧ ¬(P∧Q)

P if Q Q P

P is necessary for Q Q P

P is sufficient for Q P Q

7
 P only if Q P Q

P is equivalent to Q P Q

P whenever Q Q P

Definition: Two compound propositions and are said to be equivalent if they have the
same truth value for all possible combinations of truth values for the component propositions
occurring in both and . In this case we write .

Example 9:

Activity 4

Let ( ∨ )∨

∨( ∨ )

Check p and q are equivalent or not

 Given the conditional , we give the related conditional propositions:-

 : Converse of
 : Inverse of
 : Contrapositive of

8
Definition: A compound proposition is a tautology if it is always true regardless of the truth
values of its component propositions. If, on the other hand, a compound proposition is always
false regardless of its component propositions, we say that such a proposition is a contradiction.

Definition:

 A tautology is a proposition which is always true.

For example: P V P

 A contradiction is a proposition which is always false.

For example: P  P

 A contingency is a proposition which neither a tautology nor a contradiction.

For Example: (P V Q) R

Remark:

1. In a truth table, if a proposition is a tautology, then every line in its column has as its
entry; if a proposition is a contradiction, every line in its column has 𝐹 as its entry.

2. Two compound propositions and are equivalent if and only if “ ” is a tautology.

Predicate logic

Definition: A predicate is a function. It takes some variable(s) as arguments; it returns either

True or False (but not both) for each combination of the argument values.

In contrast, a proposition is not a function. It does not have any variable as argument. It is either
True or False (but not both). The variables are always associated with a universe (or domain) of
discourse, which tells us what combinations of the argument values are allowed.

Example 10: Here are some open propositions (predicate):

a) is the day before Sunday. (predicate)

 Monday is the day before Sunday. (proposition)
b) is a city in Africa. (predicate)
 London is a city in Africa. (proposition)

9
 c) is greater than . (predicate)
 5 is greater than 9. (proposition)

There are two types of quantifier

1. Universal quantifier: ( ) is true for every in the universe, ( )

 For all ( ); For every ( )

2. Existential quantifier: ( ) is true for some in the universe, ( )

 There exists an such that ( ) For some ( ); For at least one , ( ) I can
find an x such that ( )

Remarks:

i. To show that ( ) ( ) is 𝐹, it is sufficient to find at least one such that ( ) is 𝐹.

Such an element is called a counter example.

ii. ( ) ( ) is 𝐹 if we cannot find any having the property .

Example 11: Write the following statements using quantifiers.

a) For each real number .

Solution: ( )( ).

b) There is a real number such that .

Solution: ( )( ).

Example 12: Find the truth value for the following if :

1) ( )( )=T

2) ( )( )=F b/c is a counterexample

3) ( )( )=T since such that .

10
Quantifiers Occurring in Combinations

The following are the simplest forms of combinations:

1. ( )( ) ( )

 “For all and for all the relation ( ) holds”;

2. ( )( ) ( )
 “There is an and there is a for which ( ) holds”;
3. ( )( ) ( )
 “For every there is a such that ( ) holds”;
4. ( )( ) ( )
 “There is an which stands to every in the relation ( ).”

Example 13: Let The set of integers.

Let ( ) .

a) ( )( ) ( ) = T, for x = 4 and y = 1
b) ( )( ) ( )=F
 There is an integer such that for every , .
c) ( )( ) ( )=T
 For every integer , there is an integer such that
 Let , then will always be an integer

d) ( )( ) ( )=F

 For every integer and for every integer , .

Argument and Validity

An argument is formed when we try to connect bits of evidence (premises) in a way that will
force the audience to draw a desired conclusion.

Definition: An argument (logical deduction) is an assertion that a given set of statements

, called hypotheses or premises, yield another statement , called the
conclusion. Such a logical deduction is denoted by:

11
or

Example 14: Consider the following argument:

If you study hard, then you will pass the exam.

You did not pass the exam.

Therefore, you did not study hard.

Let : You study hard.

: You will pass the exam.

Then, the argument form can be written as:

Definition: An argument form is said to be valid if is true whenever all

the premises are true; otherwise it is invalid.

There are two ways of determining validity of an argument:

1. using a truth table

2. using rules of inferences (exercise)

12
Example 15: Investigate the validity of the following argument:

p  q, q p
p  q, qr  p

Remark:

1. What is important in validity is the form of the argument rather than the meaning or
content of the statements involved.

2. The argument form is valid iff the statement

( ∧ ∧ ∧ ∧ ) is a tautology.

1.3 Methods of proof

1.3.1 Direct Proof
Direct Proof: A direct proof shows that a conditional statement is true by showing that
if is true, then must also be true, so that the combination true and false never occurs. In a
direct proof, we assume that is true and use axioms, definitions, and previously proven
theorems, together with rules of inference, to show that must also be true.
Definition: The integer is even if there exists an integer such that , and is odd if
there exists an integer k such that . (Note that every integer is either even or odd, and

13
no integer is both even and odd.) Two integers have the same parity when both are even or both
are odd; they have opposite parity when one is even and the other is odd.

There are two steps to directly proving

1. Assume p is true.
2. Demonstrate that q must follow from p.

Example: 16

Proposition: if is odd, then is odd.

Proof. Suppose is odd.

then for some by definition of an odd number.

Thus ( ) ( )

So where is the integer

Thus, by definition, is odd.

Example 17:

Proposition: Sum of an even integer and an odd integer is odd.

Proof: Suppose is even and is odd. Then

( ) ( for integer )

( ) ( ) ( for integer )

( ) (taking 2 as common factor)

( and addition is closed on integers)

odd (definition of odd)

14
1.3.2 Proof by Contraposition
Proof by Contraposition Proofs by contraposition make use of the fact that the conditional
statement is equivalent to its contrapositive, . This means that the conditional
statement can be proved by showing that its contrapositive, , is true. In a proof
by contraposition of , we take as a premise, and using axioms, definitions, and
previously proven theorems, together with rules of inference, we show that must follow. the
proof by contraposition can succeed when we cannot easily find a direct proof.
Recall that first- order shows that the statement is equivalent to
1. Assume is true.
2. Show that must be true.
3. Observe that by contraposition.
Example 18
Prove that if is an integer and is odd, then is odd.
Proof: Assume that is even. Then, . Substituting for , we find that
( ) ( ) ( ) .
This tells us that is even (because it is a multiple of 2), and therefore not odd. This is the
negation of the premise of the theorem.
Example 19

Proposition: Suppose If is even, then is odd.

Proof: (Contrapositive) suppose is not odd.

Thus is even, so for some integer

Then ( ) ( )

Therefore where is the integer

Consequently is not even.

Therefore is not even.

15
Example 20

Proposition: Suppose If is even, then is odd.

Proof. (Contraposition) Suppose is not odd.

Thus is even, so for some integer .

So ( ) ( )

( )

Therefore, where is the integer

Consequently is odd.

Therefore, is not even.

1.3.3 Proof by Contradiction

Proofs by Contradiction Suppose we want to prove that a statement is true. Furthermore,
suppose that we can find a contradiction q such that is true. Because is false, but
is true, we can conclude that is false, which means that is true. How can we find a
contradiction q that might help us prove that is true in this way? Because the statement 𝑟 ∧ 𝑟
is a contradiction whenever 𝑟 is a proposition, we can prove that p is true if we can show that
(𝑟 ∧ 𝑟) is true for some proposition 𝑟. Proofs of this type are called proofs by
contradiction.
Steps to proving a theorem by contradiction:
1. Assume is true.
2. Assume is true.
3. Demonstrate a contradiction.

16
Example 21

Proposition: √ is irrational.

Proof: Suppose √ is the simplest rational.

√ (m, n have no common factors, )

(squaring and simplifying)

(definition of even)

(why?)

for some integer (definition of even)

( ) (substitute m)

(simplify)

(definition of even)

(why?)

are even (previous results)

have a common factor of 2 (definition of even)

Contradiction! Hence, the proposition is true.

Example: 22

Prove that if is an integer and is odd, then n is even

Rephrased: If is odd, then is even

Proof: Assume is true and is false

Assume that is odd, and is odd

for some integer (definition of odd numbers)

( ) ( )

17
 As ( ) is 2 times an integer, it must be even

Contradiction!

1.4 Elementary number properties

There are four basic properties of numbers: commutative, associative, distributive, and identity.

Commutative Property

a) Addition: When two numbers are added, the sum is the same regardless of the order in
which the numbers are added.

Example 23: or
b) Multiplication: When two numbers are multiplied together, the product is the same
regardless of the order in which the numbers are multiplied.

Example 24: or

The commutative property states that changing the order of addends or factors does not
change the sum or the product.

Associative Property

a) Addition: When three or more numbers are added, the sum is the same regardless of the way
in which the numbers are grouped.
( ) ( )
Example 25: 6 + (4 + 3) = 13 or (6 + 4) + 3 = 13
b) Multiplication: When three or more numbers are multiplied, the product is the same
regardless of the way in which the numbers are grouped.
( ) ( )

Example 26: ( ) or ( )

18
Distributive Property

The sum of two numbers times a third number is equal to the sum of each addend times the third
number.

( )

Example 27: ( ) 𝑟

Identity Property

a) Addition: The sum of any number and zero is that number.

Example 28: 12 + 0 = 12

b) Multiplication: The product of any number and one is that number.

Example 29: 18 x 1 = 18

19