MATHEMATICS As LEVEL(FORM FIVE) NOTES – LOGIC(1)

LOGIC

Logic concerns the study and analysis of methods of reasoning which lead to certain conclusions or statements.

Example

If it rains today, we shall play football. It rained, but we did not play football.

Simple and Compound Sentences

Consider the following sentences:

1. The medians of a triangle meet at a point.
2. The diagonals of any quadrilateral are parallel.

Sentences (i) and (ii) are simple sentences.

iii) The median of a triangle meets at a point and the diagonals of a quadrilateral are parallel.

Sentence (iii) is a compound sentence.

Other connecting words are: or, but, while.

Truth Value of a Sentence

2 × 3 = 5 has a truth value “false”.

2 × 2 = 4 has a truth value “true”.

The number 23 is prime. Truth value: “true”.

Propositions

A proposition is any statement which is free from ambiguity and has a property: it is either true or false, but not both nor neither.

Consider the following sentences:

1. Birds have no wings (p).
2. The sun rises from the west (p).
3. 8 = 6 + 2 (p).
4. The grass is green (p).
5. I am feeling hungry (not a proposition).

Truth Table

A truth table is a matrix whose entries are truth values.

E.g. F T or T F

A Complete Truth for Conjunction

Note: A conjunction is a compound proposition connected by the word “and”.

E.g. The sun rises from the west and 8 = 6 + 2.

The above proposition has a truth value false.

The proposition having “and” or “but”: if both sentences are true, then the truth value will be true.

The word “but” carries the same meaning as the word “and”.

Questions

Find the components or simple sentences of the following conjunctions:

1. 3 < 5 and there are infinitely many prime numbers.
   1. 3 < 5
   2. There are infinitely many prime numbers
2. 4 is divisible by 2 and 4 is a prime number.
   1. 4 is divisible by 2
   2. 4 is a prime number
3. 2 < 3 and 5 < 3.
   1. 2 < 3
   2. 5 < 3
4. The sun rises from the west and is irrational.
   1. The sun rises from the west
   2. is irrational
5. 2 is an odd number and it is false that 5 is even.

A Complete Truth Table for Conjunction

Let P and Q be any general propositions.

Required to find the truth table for P and Q.

Now P and Q is written as P ∧ Q.

P ∧ Q has truth value true only when both P and Q are true.

Truth table for P ∧ Q:

Negation

A negation is a sentence which has an opposite truth value to the given one.

One way of forming a negation is to put the word “not” with a verb.

Example: 6 is divisible by 3.

Negation: 6 is not divisible by 3.

It is not true that 6 is divisible by 3.

It is false that 6 is divisible by 3.

Given a statement P, its negation is denoted ~P.

The complement of ~P is P.

Truth table for negation:

Disjunction

Another word used to combine sentences is the word “or”.

Consider the sentences:

i) 43 < 3

ii) 5 > 3

Combining them with the word “or”: 43 < 3 or 5 > 3.

The connective word “or” is called a disjunction and is symbolized by “∨”.

The truth value for disjunction is false only when both components are false.

If P and Q are statements, then P or Q is symbolized as P ∨ Q.

P ∨ Q has a truth value false only when both P and Q are false.

Truth table for disjunction:

Implications

These are statements of the form “if … then …”.

Example: If a quadrilateral is a parallelogram, then the pair of opposite sides are parallel.

The phrase “a quadrilateral is a parallelogram” is called the hypothesis or antecedent.

The phrase “the pair of opposite sides are parallel” is called the conclusion or consequent.

If P is the hypothesis and Q is the conclusion, then the statement “if P then Q” is written as P → Q.

Consider the statement: If 43 < 3 then 5 > 3 (True).

If the hypothesis is true and the conclusion is false, then the implication is false.

Note: The compound statement P → Q is false only when P is true and Q is false.

Truth table for P → Q:

Propositions which carry the same meaning as “if P then Q”:

1. If P, Q
2. Q if P
3. Q provided that P
4. P only if Q
5. P is a sufficient condition for Q
6. Q is a necessary condition for P

Exercise

1. Determine the truth values of the following:

1. If 2 < 3 then 2 + 3 = 5 (True)
2. If 3 < 2 then 3 + 2 = 5 (True)
3. If 2 + 3 = 5 then 3 < 2 (False)
4. If 2 + 1 = 2 then 1 = 0 (True)

2. Find the components of the following compounds:

1. If 3 < 5 then 10 + m = 9
   1. 3 < 5
   2. 10 + m = 9
2. a + b = c + d only if p + q = r²
   1. a + b = c + d
   2. p + q = r²
3. If Galileo was born before Descartes then Newton was born before Shakespeare
   1. Galileo was born before Descartes
   2. Newton was born before Shakespeare

3. Write a truth table for:

1. (P ∧ Q) ∨ (P ∨ Q)
2. (P → Q) ∧ P
3. ((P → Q) → Q)

Bi-conditional Statement

Consider the truth table for (P → Q) ∧ (Q → P).

The statement (P → Q) ∧ (Q → P) is known as a bi-conditional statement and is abbreviated as P ↔ Q.

Truth Table for P ↔ Q

Note: P ↔ Q is read as “P if and only if Q”.

P ↔ Q is true when both P and Q are true or when both P and Q are false.

Converse, Contrapositive, Inverse

Given a proposition: If a quadrilateral is a parallelogram then its opposite sides are parallel, P → Q.

Converse: If the opposite sides are parallel, then the quadrilateral is a parallelogram, i.e., Q → P.

Contrapositive: If the opposite sides are not parallel, then the quadrilateral is not a parallelogram, i.e., ~Q → ~P.

Inverse: If a quadrilateral is not a parallelogram, then the opposite sides are not parallel, i.e., ~P → ~Q.

Truth Table for Implication, Converse, Contrapositive, Inverse

Equivalent Statements

Two propositions are logically equivalent if they have exactly the same truth values.

E.g. P ∨ Q and Q ∨ P are logically equivalent.

Solution: Draw truth tables for P ∨ Q and Q ∨ P.

Compound Statements

Compound statements with three components P, Q, R.

Consider the following compound statement:

Triangles have all three sides and either the area of a circular region of radius r is πr² or it is false that the diagonals of a parallelogram do not meet.

Solution (to symbolize the above statement):

Let P: triangles have three sides.

Let Q: circular region of radius r has area πr².

Let R: diagonals of parallelogram do not meet.

Symbolic form: P ∧ (Q ∨ ~R).

To find the truth values of the above statement:

The statement has a truth value true.

Tautology

A tautology is a proposition which is always true under all possible truth conditions of its component parts.

Example:

Show whether or not ~ (P ∧ Q) ∨ (~P → ~Q) is a tautology.

Since column 8 has all truth values true (T), it is a tautology.

Laws of Algebra of Propositions

1. Idempotent laws
   • a) P ∨ P ≡ P
   • b) P ∧ P ≡ P
2. Commutative laws
   • a) P ∨ Q ≡ Q ∨ P
   • b) P ∧ Q ≡ Q ∧ P
3. Associative laws
   • a) (P ∨ Q) ∨ R ≡ P ∨ (Q ∨ R)
   • b) (P ∧ Q) ∧ R ≡ P ∧ (Q ∧ R)
4. Distributive laws
   • a) P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)
   • b) P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)
5. Identity laws
   • a) P ∨ f ≡ P
   • b) P ∧ t ≡ P
   • c) P ∨ t ≡ t
   • d) P ∧ f ≡ f
6. Complementary laws
   • a) P ∨ ~P ≡ t
   • b) P ∧ ~P ≡ f
   • c) ~~P ≡ P
   • d) ~t ≡ f or t~ ≡ f
   • e) ~f ≡ t or f~ ≡ t
7. De Morgan’s laws
   • a) ~(P ∨ Q) ≡ ~P ∧ ~Q
   • b) ~(P ∧ Q) ≡ ~P ∨ ~Q

Examples

Using the laws of algebra of propositions, simplify (P ∨ Q) ∧ ~P.

Solution:

(P ∨ Q) ∧ ~P ≡ (~P ∧ P) ∨ (~P ∧ Q) (distributive law)

≡ f ∨ (~P ∧ Q) (complement law)

≡ (~P ∧ Q) (identity)

Questions

1. Simplify the following propositions using the laws of algebra of propositions:
   1. ~(P ∨ Q) ∨ (~P ∧ Q)
   2. (P ∧ Q) ∨ [~R ∧ (Q ∧ P)]
2. Show using the laws of algebra of propositions that (P ∧ Q) ∨ [P ∧ (~Q ∨ R)] ≡ P.
3. Construct a truth table for [(P → ~Q) ∧ (R → P) ∧ R] → ~P.