LOGIC

Logic concerns with the study of analysis of methods of reasoning which lead to certain conclusion or statement.

Example

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

Simple and compound sentence

Consider the following sentence

i) The medians of a triangle meet at a point

ii) The diagonals of any quadrilateral are parallel

i) and ii) are simple sentence

iii) The median of a triangle meet at a point and the diagonal of a quadrilateral are parallel

iii) Is a compound sentence

Other connecting words are: or, but, while

TRUTH VALUE OF A SENTENCE

2 x 3 = 5 has a truth value ” false”

2 x 2 = 4 has a truth value ” True”

The number 23 is prime. “True”

Propositions

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

Consider the following sentence;

i) Birds have no wings (p)

ii) The sun rises from the west. (p)

iii) 8 = 6 + 2 (p)

iv) The grass is green (p)

v) I am feeling hungry (not 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/ but, if both of the sentence are true, then only truth value will be true.

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

QUESTIONS

Find the components or simple sentence of the following conjunctions

a) 3< 5 and three are infinitely many prime numbers.

i) 3< 5

ii) There are infinitely many prime numbers

b) 4 is divisible by 2 and 4 is a prime number

i) 4 is divisible by 2

ii) 4 is a prime number

c) 2 < 3 and 5 < 3

i) 2< 3

ii) 5< 3

d) The sun rises from the west and is irrational

i) The sun rises from the west

ii) is irrational

e) 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 proposition

Required to find the truth table for P and Q

Now P and Q is written as P ∧ Q

P ∧ Q has truth value 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

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

The complement of ~ P is P

Truth Table for negation

Disjunction

Another word used to combine sentence is the word ” or “

Consider the sentence

i) 43 < 3 ii) 5 > 3

– combining them with the word ” or ” i.e. 43 < 3 or 5 > 3

– The connective word ” or ” is called a disjunction and is symbolized by ” V “

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

If P and Q are statement,then P or Q is symbolized as P V Q

P V Q has a truth value false in one case 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” called hypothesis or antecedent

The phrase “the pair of opposite sides are parallel” is called a conclusion or constituent

If P hypothesis

Q conclusion

Then the statement if P then Q its implication in short we write P Q

Consider the statement

If 43 < 3 then 5 > 3 T

If 43 < 3 then 5 < 3 T If hypothesis is T and conclusion is F 43 > 3 then 5 < 3 F then the implication is T

→Note: The compound statement P → Q is false only in one case P is true and Q is false.

Truth Table for P Q

Propositions which carry the same meaning as if P then Q

i) If P, Q

ii) Q if P

iii) Q provided that P

iv) P only if Q

v) P is a sufficient condition for Q

vi) Q is a necessary condition for P

EXERCISE

1. Determine the truth values of the following

a) If 2 < 3 then 2 + 3 = 5 T

b) If 3 < 2 then 3 + 2 = 5 T

c) If 2 + 3 = 5 then 3 < 2 F

d) If 2 + 1 = 2 then 1 = 0 T

2. Find the components of the following compound

i) If 3 < 5 then 10 + m = 9

a) 3 < 5

b) 10 + m = 9

ii) a + b = c + d only if p + q = r2

a) a + b = c + d

b) p + q = r2

iii) If Galileo was born before Descartes then Newton was born before Shakespeare

a) Galileo was born before Descartes

b) Newton was born before Shakespeare

3. Write a truth table for

i) (P ∧ Q) V (P V Q) ii) (P → Q) ∧ P iii) ((P → Q) → Q)

Solutions

i) (P ∧ Q) V (P V Q)

ii) (P → Q) ∧ P

iii) ((P → Q) → Q)

BI CONDITIONAL STATEMENT

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

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

Truth table for P Q

Note: P Q is read P if and only if Q

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

Example. The truth value of 43 > 3 if and only if 5< 3 (F)

43 < 3 if and only if 3 < 5 (F)

43< 3 if and only if 5 < 3 (T)

43> 3 if and only if 5 > 3 (T)

CONVERSE, CONTRA POSITIVE, 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.

Contra positive: If the positive 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, contra positive, inverse

Column 3 has exactly truth value as column 7

i. e P → Q ~Q → ~ P

Q → P ~ P → ~Q

EQUIVALENT STATEMENTS

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

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

Solution: Draw truth for P V Q and Q V P

1 2 3 4

Since column 3 has exactly the same truth values as column 4 then

P V Q Q V P

Questions

Show whether or not the following propositions are logically equivalent

i)P → Q, ~ P V Q

i)P → Q, ~ P V Q

Since column 3 and 5 have exactly the same truth value therefore

P → Q ~ P V Q

P → Q ~ P V Q

ii) P → (P V Q); P → Q

Since column 4 does not have exactly same truth value as column 5 then p → (P V Q) P → Q

iii) P → Q: ~ P → Q

Since column 3 does not have exactly same truth values as column 5 therefore

P → Q ~ P → Q

iv) P → Q; Q → P

Since column 3 does not have exactly same truth values as column 4 therefore P → Q Q → P

v) ~ (P → Q);PV ~ Q

(5) (6)

(5) (6)

Since column 5 does not have exactly same truth value as column 6 therefore ~ (P → Q) P V ~Q

vi) ~ (P V Q); ~P ∧ ~Q

Since column 6 has exact same truth values as column 7 therefore ~ (P V Q) →( ~P ∧ ~Q)

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 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 is

Let R diagonals of parallelogram do not meet

P ∧ (Q V ~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 that whether or not ~ (P ∧ Q) V (~P → ~Q) is a tautology

(6) (7)

(6) (7)

Since column 8 has all the truth values True (T) therefore it is TAUTOLOGY

Since column 8 has truth value true throughout then, ~ (P ∧ Q) V (~ P → ~Q) is a tautology

Questions

1. Show whether the given compound statements are tautology or not

i) (P ∧ Q) → P

Since column 4 has truth value true throughout then (P ∧ Q) → P is a tautology.

ii) P → (P ∧ Q)

Since column 4 does not have truth value true throughout then P → (P ∧ Q) is not a tautology.

iii) P → ~P

Since column 3 does not have the truth value true throughout then

P → ~ P is not a tautology.

iv) (P → Q) → (~ P → Q)

Since column 6 does not have the truth value true throughout then (P → Q) →(~ P → Q) is not a tautology

v) (P → Q) V (Q → P)

Since column 5 has all truth values true throughout then (P → Q) V (Q → P) is a tautology.

2. Express the following in symbolic form and then find its truth value

i) 2 is a prime, and either 4 is even or it’s not true that 5 is even

Solution

Let P 2 is a prime

Let Q 4 is even

Let R 5 is even

P ∧ (Q V ~R)

P ∧ (Q V ~R) has a truth value true.

ii) 7 is odd, or either London is in France and it is false that Paris is not in Denmark

Let P 7 is odd

Q London is in France

R Paris is not in Denmark

P V (Q ∧ ~R)

P V (Q ∧ ~R) has a truth value True

3. Find the truth values of P ∧ (Q V ~R) if

i) P, Q, R all has truth value T

ii) If P, Q, R all have truth value of F

iii) If P is true, Q is false and R is false

A complete truth table for general cases

1. Only one compound P

Two rows

Two rows

2. Two components P and Q

Four rows

Four rows

3. Three components P, Q, R

Eight Rows

Eight Rows

4. Four components P, Q, R, S

Sixteen rows

Sixteen rows

Example constructs a truth table for the compound statement

((P → Q) Λ R) Q

LAWS OF ALGEBRA OF PROPOSITIONS

1. Idempotent laws

a) P V P P

b) P Λ P P

2. Commutative

a) P V Q Q V P

b) P Q Q Λ P

3. Associative laws

a) (P V Q) V R P V (Q V R)

b) (P Λ Q) Λ R P Λ (Q Λ R)

4. Distributive laws

a) P V (Q Λ R) (P V Q) Λ (P V R)

b) P Λ (Q V R) (P Λ Q) V (P Λ R)

5. Identity laws

a) P V f P

b) P Λ t P

c) P V t t

d) P Λ f f

6. Complementary laws

a) P V ~ 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 law

a) ~ (P V Q) ~ P Λ ~ Q

b) ~ (P Λ Q) ~ P V ~ Q

Examples

Using the laws of algebra of proposition simplify (P V Q) ∧ ~ P

Solution

(P V Q) Λ ~ P (~ P Λ P) V (~ P Λ Q) ……distributive law

f V (~ P Λ Q) ………compliment law

(~ P Λ Q) ………..identity

Questions

1. Simplify the following propositions using the laws of algebra of propositions

i) ~ (P V Q) V (~P Λ Q)

ii) (P Λ Q) V [~ R Λ (Q Λ P)]

2. Show using the laws of algebra of propositions (P Λ Q) V [P Λ (~Q V R)] P