File

Report
PREDICATES
Predicates:
Ex: x is a student

Subject





Predicate
Predicate refer to a property that the subject of the
statement can have.
The logic based upon the analysis of predicates in any
statement is called predicate logic.
Predicates are denoted by capital lettersA,B,C,……..P,Q,R,S…..
Subjects are denoted by small letters a,b,c…….
Any statement of the type p is Q where Q is a predicate
and p is the subject can be denoted by Q(p).
 1-Place
Predicate: one object
Ex: John is a bachelor
 2-Place Predicate: 2 objects
Ex: Rohit is elder than Rahul
 3-Place Predicate:3 objects
Ex: Santosh is brother of Rohit and Rahul
 n-Place Predicate: n objects
 Predicate connectives:
 Negation of a Predicate: not
Ex: G(s): Shivani is a good girl
¬ G(s) : Shivani is not a good girl.
 Conjunction:
and
Ex: B(s): Shiva is a boy T(s): Shiva is a student
B(s) ∧ T(s) : Shiva is a boy and shiva is a student
 Disjunction: or
Ex: M(s): sravan is a man L(s): sravan is a lord
M(s) v L(s): Sravan is a man or sravan is a lord
 Implication: if…….then
Ex: C(s): Santosh is a scholar P(r): Rahul is a player
C(s) → P(r): If Santosh is a scholar then rahul is a
player
 Quantifiers:
 Existential
Quantifier(∃ ): for some , there exists
Ex: ∃ x, P(x): x is a prime number
 Universal Quantifier(∀ ): for all, for every, for
each, for any
∀ x , P(x): x is a prime number
The statement functions and variables:
 Simple statement function of one variable: Predicate
symbol and one variable
Ex: M(r): Ravi is a man
 Compound statement function of one variable:
One or more simple statement functions with logical
connectives
Ex: G(x): x is a girl , B(x): x is a boy
¬ G(x) , G(x) ∧ B(x), G(x) v B(x),G(x) → B(x)
Statement function of two variables:
Predicate symbol and two individual variables
Ex: if r represents Rohit and s represents santhosh and the
statement function of two variables is C(x , y): x is
cleverer than v
C(r , s): Rohit is cleverer than santhosh
C(s , r): santhosh is cleverer than Rohit

 Free
and Bound Variables:
When a quantifier is used on the variable x or
when we assign a value to this variable , we say
that this occurrence of the variable is bound. An
occurrence of a variable that is not bound by a
quantifier is said to be free.
Rules of Inference:-- Argument:
Compound proposition of the form

( p1  p 2  p 3 .......... . p n )  c
is called an argument
p1 , p 2 , p 3 ,..... p n are called premises of the argument
and c is called conclusion of the argument
We write the above argument in the following form
p1
p2
p3
.
.
pn
c
 Consistency
of Premises:
 The premises p1, p2, p3,…..pn of an argument
are said to be inconsistent if their conjunction
(p1 ∧ p2 ∧ p3 ∧ …. ∧ pn) is false in every
possible situation
 The premises p1, p2, p3,…..pn of an argument
are said to be consistent if their conjunction (p1
∧ p2 ∧ p3 ∧ …. ∧ pn) is true in at least one
possible situation

Ex: Consider the Premises (p v q) and ¬p
p
q
¬p
(p v q)
(p v q) ∧ ¬p
T
T
F
T
F
T
F
F
T
F
F
T
T
T
T
F
F
T
F
F
Therefore the Premises (p v q) and ¬p are consistent
 Ex: Consider the Premises p and (¬p ∧ q)
p
q
¬p
(¬p ∧ q)
P ∧(¬p ∧ q)
T
T
F
F
F
T
F
F
F
F
F
T
T
T
F
F
F
T
F
F
Therefore the premises p and (¬p ∧ q) are inconsistent
 Valid
and Invalid Arguments:
An argument is said to be valid if whenever each of
premises p1, p2, p3,…..pn is true then the conclusion c
is true.
In other words the argument
( p1  p 2  p 3 .......... . p n )  c is valid
When ( P1  p 2  p 3 .....  p n )  c
 In an argument the premises are always taken to be true
where as the conclusion may be true or false
 Conclusion is true- valid argument
 Conclusion is false- invalid argument
 The
following rules are called rules of inference
 Rule of conjunctive simplification:
For any propositions p, q
if p ∧ q is true then p is true
(p ∧ q) ⇒ p
Rule of disjunctive Amplification:
For any propositions p, q
if p is true then p v q is true
p ⇒ (p v q)
Rule of syllogism:
For any propositions p, q , r
If p → q is true and q → r is true then p → r is true
(p → q) ∧ (q → r) ⇒ (p → r)
Rule of syllogism:
For any propositions p, q , r
If p → q is true and q → r is true then p → r is true
(p → q) ∧ (q → r) ⇒ (p → r)
Or
(p → q)
(q → r)
 (p → r)
Modus pones (Rule of detachment):
If p is true and (p → q) is true then q is true
p ∧ (p → q) ⇒ q
Or
p
(p → q)
 q
Modus Tollens:
If (p → q) is true and q is false then p is false
(p → q) ∧ ¬q ⇒ ¬p

 Direct
Proof:
1.First assume that p is true
2.Prove that q is true
3. conclusion: p → q is true.
Ex 1: Give a direct proof of the statement “The
square of an odd integer is an odd integer”.
Soln: We have to prove that
“if n is an odd integer then n2 is an odd integer”.
Assume that n is an odd integer
Then n= 2k+1 for integer k
n2 = (2k+1)2 = 4k2+4k+1
n2 is not divisible by2. this means that n2 is an odd
integer
 Ex
2: Prove that for all integers k and l, if k and l
are both odd then (k + l) is even and kl is odd.
Soln: take any two integers k and l
Assume that both k and l are odd then
K=2m+1 , l=2n+1
K + l = 2m+1+2n+1
=2m+2n+2
= 2(m+n+1)
And kl= (2m+1)(2n+1)
=4mn+2m+2n+1
(K +l) is divisible by 2 and kl is not divisible by2
Therefore (k + l) is even integer and kl is odd integer
 Indirect
Proof:
 A conditional p → q and its contra positive is
¬ q → ¬ p is logically equivalent
1. Given conditional p → q and write its contra
positive
2. Assume ¬ q is true
3. Prove that ¬ p is true
Conclusion : p → q is true.
Ex 1: Let n be an integer. Prove that if n2 is odd then n is
odd.
Soln: here the conditional p → q where
P: n2 is odd and q: n is odd
Assume that ¬ q is true that is
Assume that n is not an odd integer
Then n=2k where k is an integer
n2 =(2k)2 = 2(2k2)
So that n2 is not odd
That is p is false
That is ¬ p is true
This proves that ¬ q → ¬ p is true
Therefore p → q is true
Ex 2:Give an indirect proof of the statement
“The product of two even integers is an even integer”
Soln: The given statement is
“If a and b are even integers then ab is an even integer”
Let p: a and b are even integers
q : ab is an even integer
Assume that ¬ q is true that is
Assume that ab is not an even integer
That means that ab is not divisible by 2
That is a is not divisible by b2 and b is not divisible by 2
i.e., a is not an even integer and b is not an even integer
P is false so ¬ p is true
This proves contra positive
Therefore p → q is true

 Provide
an indirect proof of the following
statement.
“ For all positive real numbers x and y , if the
product xy exceeds 25, then x > 5 or y > 5
The given statement is p →(q v r)
Its contra positive is (¬ q ∧ ¬ r) → ¬ p
Suppose (¬ q ∧ ¬ r) is true
Then ¬ q is true and ¬ r is true
That is x ≤ 5 and y ≤ 5
This gives x ≤ 25, so that ¬ p is true
Contra positive is true
So p →(q v r) is true
 Provide
an indirect proof of the following
statements
1. For all integers k and l if kl is odd , then both k
and l are odd
2. For all integers k and l if k+l is even , then k and l
are both even or both odd.
3. Let m and n be integers. Prove that n2 = m2 if and
only if m = n and m = -n
 Proof
by Contradiction:
1. Assume that p → q is false that is p is true and q
is false
2. Starting with q is false and employing the rules of
logic and other known facts ,infer that p is false.
This contradicts the assumption that p is true.
3. Conclusion: Because of the contradiction arrived
in the analysis we infer that p → q is true
1. Provide a Proof by contradiction of the following
statement:
“For every integer n, if n2 is odd then n is odd”
Soln: The given statement is in the form of p → q
where p: n2 is odd q: n is odd
Assume that p → q is false that is p is true and q is
false
Now q is false means n is even
n=2k for some integer k
n2= (2k)2 = 4k2
From this n2 is even ,that is p is false
This contradicts the assumption that p is true
Therefore p → q is true.
2.Prove the statement “The square of an even integer
is even” by the method of contradiction.
Soln: The given statement is in the form of p → q
where p:n is an even integer q: n2 is an even
integer
Assume that p → q is false that is p is true and q is
false
From q is false n2 is odd
n2 = n*n not divisible by 2
So n is not divisible by 2
That is n is not an even integer ,that is p is false
This contradicts the assumption that p is true
Therefore p → q is true.
3. Prove that if m is an even integer then m+7 is an
odd integer
Soln: p: m is an even integer q: m+7 is an odd
integer
Assume that p → q is false that is p is true and q is
false
i.e., m+7 is an even integer
Then m+7 = 2k for some integer k
m = 2k-7
m= (2k-8)+1
Which shows that m is odd
This means that p is false, which contradicts the
assumption that p is true.
Therefore p → q is true
4. Prove that, for all real numbers x and y, if
x+y ≥ 100 then x ≥50 or y ≥50
Soln: p: x+y ≥ 100 q: x ≥50 r: y ≥50
Given statement is p → (q v r)
Assume that p is true and q v r is false
i.e., ¬ (q v r) = ¬q ∧ ¬ r
This means that x<50 and y<50
This yields x+y <100
Thus p is false
This contradicts the assumption that p is true
Therefore p → (q v r) is true.
5. Prove that there is no rational number whose
square is 2.
6. Using proof by contradiction show that
rational number
Soln: let p:
2
is not a

similar documents