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