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
3. Construct a truth table for [(p → ~q) ∧ (r → p) ∧ r] → ~p
