bilangan 4

CHAPTER 4: PROPOSITIONAL CALCULUS

4.1: Statements and Logical Connectives
4.2: Logical Equivalence
4.3: Formal Proof

4.1 STATEMENTS AND LOGICAL CONNECTIVES
Propositions
A proposition is a declarative sentence that is either true or false, but not both. In propositional calculus we are not concerned with the content of a statement but only with its true/false value.

Example 1:
Determine whether the following sentences are propositions or not.
(a) p: Kuala Lumpur is the capital city of Malaysia.
(b) q: Malaysia is a member of ASEAN.
(c) s: 4 + 5 = 9
(d) u: 3 – 2 = 4
(e) p: x + y = z
(f) q: He was a president of USA
Solution:






Note: The statements which involve pronouns such as he, she, it or a mathematical variable are
not readily decidable as true or false and hence they are not propositions.

Compound Propositions
Two or more propositions may be combined to form a new proposition called compound proposition. A compound proposition is constructed from the existing propositions using logical connectives (logical operators).








Logical Connectives
Logic studies ways of constructing complex statements from simple ones by means of
operations called, logical connectives. The most important connectives are described below. In what follows, the value true will be abbreviated to T and the value False will be abbreviated to F.
 Negation (logical not, ¬, ~)
Let p be a proposition. Negation of p is the proposition denoted by ¬p and defined by the following table.

p  p
T
F


Result: Complement / opposite of the original statement.

Example 2:
Find the negation of the following:
(a) Chew is a smart boy
(b) 4 + 3 > 5
(c) There is no test in this course
(d) Today is a holy day
Solution:







 Conjunction (logical and, )
Let p and q be propositions. Conjunction of p and q is the proposition denoted by p q and defined by the following table.

p q pq
T
T
F
F T
F
T
F

Result: True only if Both statements are true



Example 3:
Combine the following two propositions using conjunction.
(a) p: Today is Monday, q: John has gone to church.
(b) p: Chan wrote English examination, q: Chan scored 65%.
(c) p: Mr. Suresh is Malaysian, q: Mr. Suresh is an Indian.
(d) p: 3 + 6 = 9, q: 3 × 6 = 18.
Solution:











 Disjunction (logical or, )
Let p and q be propositions. Disjunction of p and q is the proposition denoted by pq and defined by the following table.


p q p  q
T
T
F
F T
F
T
F


Result: True if either one of the statement is true. Note that the disjunction is
“inclusive or”.

Example 4:
Let p: Today is Friday, q: It is raining today. Then
pq :







 Exclusive or ()
Let p and q be propositions. The exclusive or of p and q denoted by pq and defined by the following table.

p q p  q
T
T
F
F T
F
T
F

Result: True when exactly one of the statement is true

Example 5:
(a) p: A student can join Inti college. q: A student can join MMU.
p  q: A student can join Inti college or MMU, but not both.

(b) p: The bus may go to KL. q: The bus may go to Johor.
p  q:

(c) p: Mary is 26 years old. q: Mary is 42 years old.
p  q :

 Implication (logical if — then, )
Let p and q be propositions. The implication pq is the proposition that is False when p is true and q is false and true otherwise. In this implication p is called hypothesis (or antecedent or premise) and q is called the conclusion or converse. Implication from p to q denoted by pq and defined by the following table.


p q pq
T
T
F
F T
F
T
F
Symbolic form English Equivalent
pq If p then q
p only if q
q, if p
q whenever p
p is sufficient for q
q is necessary for p





 Biconditional ()
Let p and q be propositions. The biconditional p  q is the proposition that is true when p and q have the same truth values and is false otherwise.

That is the biconditional p  q is precisely true when both the implications
p  q and q  p are true. Because of this the terminology “p if and only if q” is used for the biconditional.

The truth table for biconditional is given below:


Truth Table Biconditional
p q p  q
T
T
F
F T
F
T
F
Symbolic form English Equivalent
p  q p if and only if q

p is necessary and sufficient q






Converse, Contra Positive and Inverse
If p q is an implication, then the Converse of p q is the implication q p, the contra positive of p q is the implication q and Inverse of p q is the implication, q.

Example 6:
Write the converse, contra positive and inverse versions of the following sentences:
If the program is readable, then it is well structured.
Solution:















Example 7:
Write the converse and contrapositive versions of the following sentences:
(a) If Mike is a lawyer, then he is rich.
(b) If today is Monday, then I have a hockey match.
Solution:


















Note: Precedence levels of the logical operators: , , , , .






















Example 8:
Given the following propositions:
p: “Jon is happy” q: “Steve is in pain” r: “Mary is angry”

Write the following symbolic forms in statement:
(i) ~p
(ii) p q
(iii) p ~q
(iv) p  q
(v) p q
(vi) (p q)  r
(vii) p (q ~r)
(viii) p (q r)
Solution:
















Example 9:
Let p, q and r be the propositions.

p: Grizzly bears have been seen in the area.
q: Hiking is safe on the trail.
r: Berries are ripe along the trail.

Write each of the following statements in symbolic form.

(i) If berries are ripe along the trail, then hiking is safe if and only if grizzly bears have not been seen in the area.
(ii) Grizzly bears have not seen in the area and hiking on the trail is safe, but berries are ripe along the trail.
Solution:


Example 10:
Let p and q be the propositions.

p: Chong drives over 120 km per hour.
q: Chong gets a speeding ticket.

Write each of the following statements in symbolic form.

(i) Driving over 120 km per hour is sufficient for getting a speeding ticket.
(ii) If Chong does not get a speeding ticket, then he does not drive over 120 km per hour.
(iii) Driving over 120 km per hour is necessary and sufficient for getting a speeding ticket.
Solution:










4.2 LOGICAL EQUIVALENCE

It is very important in a mathematical argument that we know how to replace a statement with another statement with the same truth value. Because of this, methods used to produce propositions with the same truth value as a given compound proposition are used extensively in mathematical argument. We shall introduce the following two methods in this lecture;
• Using truth table
• Identities of logical equivalence


Some Terminologies Used In Logical Equivalences

1. Tautology
A compound proposition that is always true irrespective of the truth values of constituent propositions is called a tautology.

Example: pp is a tautology.

Example for Tautology
p p pp
T
F
F
T T
T
2. Contradiction
A proposition that is always false irrespective of the truth values of its constituent propositions is called a contradiction.

Example: p  p is a contradiction

Example for Contradiction
p  p p p
T
F
F
T F
F

3. Contingency
A proposition that is neither a tautology nor a contradiction is called a contingency


Logical Equivalence

 Definition: Compound propositions that have the same truth values in all possible
cases are said to be logically equivalent.

 The propositions p and q are logically equivalent if p  q is a tautology.

 The notation p  q denotes p and q are logically equivalent.

Example 1:
Construct truth tables for the following expressions. In each case, state whether the expression is
a tautology, a contradiction, or contingent.
(i) (p q) ↔ (¬p ¬q)
(ii) [(p r) (q r)] → (p → ¬q)
Solution:














Example 2:
Using the truth table show that the following propositions are logically equivalent:
(a) (p  q)  p  q
(b) p  q  p  q
(c) p  (q  r)  (p  q)  (p  r)
(d) p  q  (p  q)  (p  q)
Solution:


























Example 3:
Construct a truth table for the following expression. Hence, state whether the expression is
tautology, a contradiction, or contingent.

Solution:








Identities Of Logical Equivalence
We can also show logical equivalence by making use of identities or laws of equivalence. In the following identities T denotes a proposition that is always true and F denotes a proposition that is always false.

p  T  p
p  F  p
Identity laws
p  T  T
p  F  F
Domination laws
p  p  p
p  p  p
Idempotent laws
(p)  p
Double negation law
p  q  q  p
p  q  q  p
Commutative laws
(p  q)  r  p  (q  r)
(p  q)  r  p  (q  r)
Associative laws
p  (q  r)  (p  q)  (p  r)
p  (q  r)  (p  q)  (p  r)
Distributive laws
(p  q)  p  q
(p  q)  p  q
De Morgan’s laws
p  (p  q)  p
p  (p  q)  p
Absorption laws
p  p  T
p  p  F
p  q (p  q) Other laws











Example 4:
Show that the following compound propositions are logically equivalent.
(a) (p  (p  q))  p  q
(b) (p  q)  (p  q) is a tautology
(c) p  (p  q)  p
(d) p (p q) p q
Solution:







































Example 5:
Simplify the following logical expression using the Laws of Logic.
(a)
(b)
Solution:















4.3 FORMAL PROOF

Rules Of Inference

 Modus ponens or law of detachment

The argument may be written as





The tautology is the basis of the rule of inference called Modus ponens. Modus ponens states that if both an implication and its hypothesis are known to be true, then the conclusion of the implication is also true.
For example, in the argument “If it is rainy, then I will not go to your house”. It is rainy. Therefore, by modus ponens it follows that “I will not go to your house” is true.

Example 1:
Is this argument valid?
If taxes are lowered, then income rises.
Income rises
Taxes are lowered.

Solution:

 Addition

The argument may be written as


For example, for the argument “It is rainy now”. Therefore by the addition rule the conclusion is that it is either rainy or it is cloudy now.

Example 2:
Alice is a computer student.
Solution:




 Simplification

The argument may be written as



For example, Alice studies mathematics for computing and Java programming. Therefore by the simplification rule the conclusion is that Alice studies mathematics for computing.

Example 3:
Whale is a mammal and it is a protected animal.
Solution:




 Conjunction

The argument may be written as



For example, 2 +3 = 5, 2  3 = 6. Therefore, by the conjunction rule the conclusion is that 2 + 3 = 5 and 2  3 = 6.


Example 4:
The sun rises in the east.
Whale is a mammal.
Solution:




 Modus tollens

The argument may be written as



For example,
“If it rains, then the swimming pool will be closed.”
“The swimming pool is not closed.”

Therefore by the modus tollens rule it does not rain.

Example 5:
If you come late to class, then you will miss an important section of the lecture.
You do not miss an important section of the lecture.
Solution:




 Hypothetical syllogism

The argument may be written as



For example,
“If I don’t submit my assignment today, then I will get zero mark.”
“If I get zero mark, then I will fail my course work.”

Therefore, by the hypothetical syllogism rule if I don’t submit my assignment today I will fail in my course work.

Example 6:
If 2 + 7 = 9, then 4  8 =32
If 4  8 = 32, then 9 – 5 = 4
Solution:




 Disjunctive syllogism

The argument may be written as


For example,
“This morning the weather is either hazy or foggy.”
“ It is not hazy.”

Therefore, by the disjunctive syllogism, the weather is foggy.

Example 7:
For your birthday I will either take you out to eat or I will buy you a present.
I do not take you out to eat.
Solution:





















Fallacies
There are many fallacies arise from incorrect arguments. Let’s consider some common fallacies.


For example,
If you pass all the assessments in this course, then you will pass MAT252.
You pass MAT252.
Therefore, you pass all the assessments in this course.

This is an example of incorrect argument using the fallacy of affirming the conclusion. It is possible for you to pass MAT252 without having to pass all the assessments. For instance, you can pass some of the assessments.

The correct argument should be




Or





Another common fallacy is as follows






Using the same example as before,

If you pass all the assessments in this course, then you will pass MAT252.
You do not pass all the assessments in this course.

Therefore, you do not pass MAT252.

This is again an incorrect reasoning as you can still pass MAT252 even though you do not pass all the assessments in this course. This is because course work only takes up certain weighting this course. This form of fallacy is called fallacy of denying the hypothesis.


Methods Of Proof

Direct Proof
In a direct proof of an implication, we start with an assumption that p is true and we use the rules of inference and other theorems to show that q must also be true.

Example 8:
Prove that, if x is any number of the form 3k+1 for some integer k, then x2 is also of that form.
Solution:











Example 9:
Give a direct proof of the theorem “The sum of any two even numbers is an even number”.
Solution:









Example 10:
Give a direct proof of the theorem “The product of two odd numbers is odd”.
Solution:


Indirect Proof (The Contrapositive and Equivalent Forms)
The contrapositive of the implication p  q is the implication q  p. These are equivalent forms. Sometimes it is easier to prove a result in the contrapositive form rather than in the original conditional form. Proving the contrapositive might also be done as a direct proof, by induction or by contradiction. The only one that need to take care is that the contrapositive is formed correctly. For example the contrapositive of the statement ``If x is odd then 5x is odd'' is the statement ``If 5x is not odd then x is not odd'' or better still, ``If 5x is even then x is even''.
Since the implication p  q is equivalent to its contra positive q  p, the implication p  q can be proved by showing its contra positive q  p is true. An argument of this type is called indirect proof.

Example 11:
Give an indirect proof of the theorem “If 3n + 2 is odd, then n is odd.”
Solution:











Example 12:
Prove that, if x2 is even, then x is even.
Solution:















Mathematical Induction
Mathematical induction is an important technique to prove results about the complexity of algorithms, correctness of certain types of computer program, theorem about graphs and trees and many others.
Many theorems state that P(n) is true for all positive integer n, where P(n) is a propositional function, such as


Mathematical induction is a technique for proving theorems of this kind. A proof by mathematical induction that P(n) is true for every positive integer n consists of two steps. They are:
1) Basis step: The proposition P(1) is shown to be true.
2) Inductive step: The implication P(k)  P(k + 1) is shown to be true for every positive
integer k.
When we complete both steps of the proof by mathematical induction, we have proved that P(n) is true for all positive integers n, that is n, P(n) is true.
[P(1) k(P(k)P(k+1 ))]  n P(n)

Example 13:
Show by mathematical induction
2 + 10 + 24 + … + n (3n – 1) = n2 ( n + 1 )
for all positive integers n.
Solution:
















Example 14:
Use the principle of mathematical induction to prove that
22 + 42 + … + (2n) 2 =
for all positive integers n.
Solution:

















Example 15:
Show by mathematical induction
1(2) + 2(3) + 3(4) + … + n (n+1) =
for all positive integers n.
Solution:

















Example 16:
Use the principle of mathematical induction to prove that

for all positive integers n.
Solution:






















Example 17:
Use mathematical induction to prove the identity n < 2n for all positive integers n.
Solution:















Example 18:
Show by mathematical induction n! 2n-1, for n = 1, 2, …
Solution:



















Example 19:
Show that 2n > n2 whenever n is an integer greater than 4.
Solution:





















Example 20:
Use mathematical induction to prove that n3 – n is divisible by 3 whenever n is positive integer.
Solution:











Example 21:
Use induction to show that 5n – 1 is divisible by 4 for n = 1, 2, …
Solution:





















Example 22:
Use the principle of mathematical induction to prove that 4n + 2 is divisible by 3 for all integers
n 0 .
Solution: