Logic Module 2 PDF

LOGIC 2.1 Propositions and logical operations, Truth tables 2.2 Equivalence, Implications 2.3 Laws of logic, Normal Forms 2.4 Predicates and Quantifiers 2.5 Mathematical Induction  LOGIC Logic is the study of the logic relationships between objects and forms...

LOGIC 2.1 Propositions and logical operations, Truth tables 2.2 Equivalence, Implications 2.3 Laws of logic, Normal Forms 2.4 Predicates and Quantifiers 2.5 Mathematical Induction  LOGIC Logic is the study of the logic relationships between objects and forms the basis of all mathematical reasoning and all automated reasoning  PROPOSITION Definition: A proposition or statement is a declarative sentence which is either true or false, but not both. Are the following sentences propositions? Examples : (i) There are seven days in a week. (ii) 2+2=5 (iii) The earth is flat. (iv) The equation x2 + x + 1 = 0 has no real root. (v) It will rain tomorrow. (vi) Four is even. (vii) 43 ≥ 21 (viii) 4  { 1, 3, 5 }  NOT PROPOSITIONS 1. x+3=5 2. Bring that book ! 3. When is your interview? 4. What a beautiful painting ! 5. This statement is false. 6. C++ is the best language. 7. When is the pretest? 8. Do your homework  PROPOSITIONAL LOGIC Propositional Logic – the area of logic that deals with propositions Propositional Variables – variables that represent propositions: p, q, r, s E.g. Proposition p – “Today is Friday.” Truth values – T, F  LOGICAL OPERATIONS Logical operators are used to form new propositions from two or more existing propositions. The logical operators are also called connectives Negation (e.g., a or !a or ā) AND or logical Conjunction (denoted ) OR or logical Disjunction (denoted ) XOR or exclusive or (denoted ) Imply on (denoted  or →) Bi-conditional (denoted  or ) IFF We define the meaning (semantics) of the logical connectives using truth tables  LOGICAL CONNECTIVE: NEGATION p, the negation of a proposition p, is also a proposition p p Examples: 0 1 p: Today is Monday 1 0 Solution: ~p: It is not the case that today is Monday. In simple English, “Today is not Monday.” or “It is not Monday today.” p:At least 10 inches of rain fell today in Mumbai Solution: ~p: It is not the case that at least 10 inches of rain fell today in Mumbai. In simple English, “Less than 10 inches of rain fell today in Mumbai.”  LOGICAL CONNECTIVE: LOGICAL CONJUNCTION (AND) If p and q are statements the compound statement 'p and q' is called as the conjunction of p and q; and is denoted by p Ʌ q Example 1 : Let P : The sun is shining. q : The birds are singing. Then p  q is the statement : The sun is shining and the birds are singing. Example 2 : Let P : 2 is a prime number. q : John is an intelligent boy. Then p  q is the statement : 2 is a prime number and John is an intelligent boy.  LOGICAL CONNECTIVE: LOGICAL DISJUNCTION (OR) If p and q are statements, then the compound statement 'p or q' is called as the disjunction of p and q , and is denoted p v q Example 1: Let p : There is an error in the program. q : The data is wrong. Then p  q: There is an error in the program or the data is wrong.  LOGICAL CONNECTIVE: LOGICAL DISJUNCTION (OR)  LOGICAL CONNECTIVE: CONDITIONAL (IF….THEN) Conditional (If …then) If p and q are statements, the compound statement 'If p then q', denoted by p → q is called a Conditional Statement or implication p is called the antecedent or hypothesis, while q is called the consequent. Let p : Peter works hard. q : Peter will pass the exam. Then p→ q : If Peter works hard, then he will pass the exam.  1.1 PROPOSITIONAL LOGIC Example: Let p be the statement “Maria learns discrete mathematics.” and q the statement “Maria will find a good job.” Express the statement p → q as a statement in English. Solution: Any of the following - “If Maria learns discrete mathematics, then she will find a good job. “Maria will find a good job when she learns discrete mathematics.” 12  CONVERSE, INVERSE AND CONTRAPOSITIVE PROPOSITIONS If p → q is the conditional statement then 1. q → p is called its Converse. 2. ~p → ~q is called its Inverse. 3. ~q →~ p is called its Contrapositive.  LOGICAL CONNECTIVE: CONDITIONAL (IF….THEN) State the converse, inverse and contrapositive of the following. (i) If it is cold then he wears hat. Let p: It is cold , q: He wears hat. Converse (q → p) : If he wears hat then it is cold. Contrapositive (~q →~ p) : If he does not wear hat, then it is not cold. Inverse (~p → ~q) : If it is not cold then he does not wear hat. (ii) If integer is multiple of 2, then it is even. Converse (q → p) : If integer is even, then it is multiple of 2. Inverse (~p → ~q) : If integer is not multiple of 2 then it is not even. Contrapositive (~q →~ p) : If integer is not even, then it is not multiple of 2.  BI-CONDITIONAL (IF AND ONLY IF) If p and q are statements, the compound statement 'p if and only if q', denoted by , is called a biconditional statement. Often "if and only if" is shortened as"iff" p  q is also read as "If p then q, and conversely". Examples : (i) An integer is even if and only if it is divisible by 2. (ii) A right angled triangle is isosceles if and only if the other two angles are each equal to forty-five degrees. (iii) Two lines are parallel if and only if they have the same slope  PROPOSITIONAL OR STATEMENT FORM Using the logical connectives, we can construct or form an expression, involving the statement variables. The following are examples of statement forms : (i)  (p  q) → p (ii) (p → q)  (p   q) (iii) ( ( p  q)  (p   r) ) → ( ( p  r)  q )  PRECEDENCE OF LOGICAL OPERATORS As in arithmetic, an ordering is imposed on the use of logical operators in compound propositions However, it is preferable to use parentheses to disambiguate operators and facilitate readability  p  q   r  (p)  (q  (r)) To avoid unnecessary parenthesis, the following precedences hold: 1. Negation () 2. Conjunction () 3. Disjunction () 4. Implication (→) 5. Biconditional ()  STATEMENT FORM Ex. 1 : Let p denotes Raju is rich, q denotes Raju is happy. Write each of the following in symbolic form. 1. Raju is poor but happy 2. Raju is neither rich nor happy 3. Raju is either rich or unhappy 4. Raju is poor or else he is rich and unhappy Soln. : 1. pq 2. pq 3. pq 4.  p  (p   q)  STATEMENT FORM Ex. 2 : Express the proposition 'Either my program runs and it contains no bugs, or my program contains bugs' in symbolic form. Soln. : Let p : My program runs. q : My program contains bugs. The proposition can be written in symbolic form as, ( p   q )  q.  STATEMENT FORM Ex. 3 : Using the following statements : p: I will study discrete structures. q: I will go to a movie. r: I am in a good mood. Write the following statements in symbolic form : (i) If I am not in a good mood, then I will go to a movie. (ii)I will not go to a movie and I will study discrete structures. (iii)I will go to a movie only if I will not study discrete structures. (iv)I will not study discrete structures, then I am not in a good mood. Solution: (i)~r → q (ii)~qɅp (iii) ~p →q (iv)~p → ~r  STATEMENT FORM Ex. 4 Translate the following statement into symbolic form : If the utility cost goes up or the request for additional funding is desired, then a new computer will be purchased if and only if we can show that the current computing facilities are indeed not adequate. Soln. : p:The utility cost goes up q:The request for additional funding is desired r:A new computer will be purchased s:We can show that the current computing facilities are indeed adquate. Then (p  q) → (r   s) is the required symbolic form.  STATEMENT FORM Ex. 5 : Let 'a' be the proposition 'high speed driving is dangerous' and 'b' be the proposition 'Rajesh was a wise man.' Write down the meaning of the following proposition. 1. ab 2. ab 3.  (a  b) 4. (a  b)  ( a   b) Soln. : 1. a  b : High speed driving is dangerous and Rajesh was a wise man. 2.  a  b : High speed driving is not dangerous and Rajesh is a wise man. 3.  (a  b) : Either high speed driving is not dangerous or Rajesh is not a wise man. 4. (a  b)  ( a   b) : High speed driving is dangerous and Rajesh was a wise man or neither high speed driving is dangerous nor Rajesh is a wise man.  STATEMENT FORM Ex. 6: How can this English sentence be translated into a logical expression? “You cannot ride the roller coaster if you are under 4 feet tall unless you are older than 16 years old.” Soln: Let q : You can ride the roller coaster. r : You are under 4 feet tall. s : You are older than 16 years old. The sentence can be translated into: (r Λ ¬ s) → ¬q  TRUTH TABLES OF COMPOUND PROPOSITIONS We can use connectives to build up complicated compound propositions involving any number of propositional variables, then use truth tables to determine the truth value of these compound propositions. Example: Construct the truth table of the compound proposition (p ν ¬q) → (p Λ q). p q ¬q p ν ¬q pΛq (p ν ¬q) → (p Λ q) T T F T T T T F T T F F F T F F F T F F T T F F  TRUTH TABLES OF COMPOUND PROPOSITIONS Construct the truth table for the following compound proposition (( p  q ) q ) p q pq q (( p  q ) q ) 0 0 0 1 1 0 1 0 0 0 1 0 0 1 1 1 1 1 0 1  TRUTH TABLES OF COMPOUND PROPOSITIONS Construct the truth table for the formula : ~ [ p  (p  ~ q ) ] p q ~q p~q p  (p  ~ q) ~ [ p  (p  ~ q) ] T T F T T F T F T T T F F T F F F T F F T T F T  TAUTOLOGY AND CONTRADICTION A statement form is called a Tautology if it always assumes the truth value "T" irrespective of the truth values assigned to its variables. A statement form is called a contradiction if it is always assumes the truth value "F" irrespective of the truth values assigned to its variables. A statement form which is neither a tautology nor a contradiction is called a contingency.  TAUTOLOGY AND CONTRADICTION p q pq (p  q) → p T T T T F T F T T F F T F F F T p q ~p (~ p  q) p  (~ p  q) ~q (p  (~ p  q) )  ~ q T T F T T F F T F F F F T F F T T T F F F F F T T F T F  LAWS OF LOGIC 1. Idempotent laws : 5. Identity laws : 7. Implication law : pp p p  False  p p→q ~pq pp p p  True  True 8. Complement laws / Inverse law : 2. Commutative laws : p  False  False p  ~ p  True pq qp p  True  p p  ~ p  False pq  qp ~ (~ p)  p 6. Absorption law : 3. Associative laws : ~ True  False and ~ False  True p  (p  q)  p (p  q)  r  p  (q  r) 9. De Morgan's law : p  (p  q)  p (p  q)  r  p  (q  r) ~ (p  q)  ~ p  ~ q 4. Distributive laws : ~ (p  q)  ~ p  ~ q p  (q  r)  (p  q)  (p  r) p  (q  r)  (p  q)  (p  r) EXAMPLES Ex. : Use the laws of logic to show that [ ( p → q) ~ q ] → ~ p is a tautology. Soln. : [ (p → q)  ~ q ] → ~ p   [ ( p  q)  ~ q ] ~ p Implication law   [  q  (~ p  q) ]  ~ p Commutative law   [ ( q  ~ p) ( ~ q  q) ] ~ p Distributive law   [ ( q  ~ p)  (q  ~ q) ] ~ p Commutative law   [ ( q  ~ p)  F ] ~ p Complement law   ( q  ~ p) ~ p Identity law  (  q  ~ ~ p) ~ p De-morgan's law  (q  p) ~ p Complement law  q  (p ~ p) Associative law  qT - Inverse law  T - Identity law [ ( p → q) ~ q ] → ~ p is a tautology. Ex. : Show that the following statement is tautological. (p  (p → q ) ) → q.. Soln. : (p  (p → q) ) → q  ~ (p  (~ p  q) )  q Implication Law  (~ p  ~ (~ p  q) )  q  (~ p  (~~p  ~ q) )  q De-Morgan’s Law  (~ p  (p  ~ q) )  q Complement Law  ((~p  p )  (~ p  ~ q))  q Distributive Law  (T  (~ p  ~ q) ) q Complement law  (~ p  ~ q) q Indentity Law  ~ p  (~ q  q ) Associative Law  ~ p  True Complement law  True Identity law  Ex. : Prove: [ (~ p  ~ q) → (p  q  r)]  p  q i) L.H.S. ( ~ p  ~ q) → (p  q  r) ~ (~ p  ~ q)  (p  q  r) - Implication law (p  q)  (p  q  r) - De morgan's law Let p  q be x x  (x  r)  x - Absorption law p  q Ex. : Prove the distributive law. p  (q  r)  (p  q)  (p  r)  QUANTIFIER Consider the following sentences : (i) “x is tall and handsome.” (ii) “x + 3 = 5.” (iii) “x + y  10.” These sentences are not propositions, since they do not have any truth value. However, if values are assigned to the variables, each of them becomes, which is either true or false. For example, the above sentences can be converted into. (i) “He is tall and handsome”. (ii) “2 + 3 = 5” (true statement). (iii) “2 + 5  10” (false statement).  PREDICATE An assertion that contains one or more variables is called a Predicate; its truth value is predicated after assigning truth values to its variables. A predicate P containing n variables x 1, x2, … , xn is called an n - place predicate. Examples (i) and (ii) are ‘one -place predicate’, while Example (iii) is a ‘2 - place predicate.’ If we want to specify the variables in a predicate, we denote the predicate by P (x 1, x2, … , xn). Each variable xi is also called as an argument. For example, (i) “x is a city in India” is denoted by P(x). (ii) “x is the father of y” is denoted by P(x,y) (iii) “x + y  z” is denoted by P(x, y, z) The values which the variables may assume constitute a collection or set called as the universe of discourse.  BINDING A predicate becomes a proposition only when all its variables are bound. Consider the following examples : (i) P(x) : x + 3 = 5 Let the universe of discourse be the set of all integers. Binding x by putting x = – 1, we get a false proposition. Binding x by putting x = 2, we get a true proposition. (ii) P(x,y) : x + y = 10 Let the universe of discourse be the set of natural numbers. Putting x = 1, we get the one-place predicate P(1,y) : 1 + y = 10. Further setting y = 9, we obtain the proposition P(1,9) which is true. However if we set y = 10, p (1,10) is a false proposition. In each case, we have bound both the variables (x by 1, y by 9 and y by 10).  UNIVERSAL QUANTIFIER If P(x) is a predicate with the individual variable x as an argument, then the assertion “For all x, P(x)” which is interpreted as “For all values of x, the assertion P(x) is true,” is a statement in which the variable x is said to be universally quantified. We denote the phrase “For all” by , called the universal quantifier. The meaning of  is “for all” or “for every” or “for each”. If P(x) is true for every possible value of x, then  x P(x) is true; otherwise  x P(x) is false. Example : Let P(x) be the predicate x  0 ; where x is any positive integer. Then the proposition  x P(x) is true.  EXISTENTIAL QUANTIFIER Suppose for the predicate P(x), x P(x) is false, but there exists at least one value of x for which P(x) is true, then we say that in this proposition, x is bound by existential quantification. We denote the words “there exists” by the symbol . Then the notation  x P(x) means “there exists a value of x (in the universe of discourse) for which P(x) is true”.  QUANTIFIER Ex. : If M(x) is "x is man" C(x) is "x is clever" Then translate the following statements into English. (i) ∃ x ( M(x) → C(x)) (ii) ∀ x (M(x)  C(x)) Soln. : (i) There exists a man who is clever. (ii) For all men x is man and x is clever.  QUANTIFIER Ex. : Write the following two propositions in symbols. (i)‘For every number x there is a number y such that y = x + 1.’ (ii)‘There is a number y such that, for every number x, y = x + 1.’ Soln. : Let p(x,y) denote the predicate 'y = x + 1'. (i) The first proposition is :  x  y P(x, y) (ii) The second proposition is :  y  x P(x,y)  QUANTIFIER Ex. : Transcribe the following into logical notation. Let the universe of discourse be the real numbers. (i)For any value of x, x 2 is non-negative. (ii)For every value of x, there is some value of y such that x · y = 1. (iii)There are positive values of x and y such that x · y > 0. (iv)There is a value of x such that if y is positive, then x + y is negative. Soln. : (i)  x [x2  0] (ii)  x  y [x  y = 1] (iii)  x  y [ (x > 0)  (y > 0)  (x  y > 0)] (iv)  x  y [ (y > 0) → (x + y < 0) ].  QUANTIFIER Ex. : For the universe of all integers, let P(x), Q(x), R(x), S(x) and T(x) be the following statements : P(x) : x > 0. Q(x) : x is even. R(x) : x is a perfect square. S(x) : x is divisible by 4. T(x) : x is divisible by 5. Write the following statements in symbolic form : (i) Atleast one integer is even. (ii) There exists a positive integer that is even. (iii) If x is even, then x is not divisible by 5. (iv) There exists an even integer divisible by 5. (v) If x is even and x is a perfect square, then x is divisible by 4. Soln. : (i)  x Q (x) (ii)  x [ P(x)  Q(x) ] (iii)  x [ Q (x) → ~ T(x) ] (iv)  x [ Q (x)  T(x) ] (v)  x [ (Q (x)  R (x)) → S(x) ]  QUANTIFIER Ex. : Transcribe the following into logical notation. Let the universe of discourse be the real numbers. (i) For any value of x, x 2 is non-negative. (ii) For every value of x, there is some value of y such that x · y = 1. (iii) There are positive values of x and y such that x · y > 0. (iv) There is a value of x such that if y is positive, then x + y is negative. Soln. : (i)  x [x2  0] (ii)  x  y [x  y = 1] (iii)  x  y [ (x > 0)  (y > 0)  (x  y > 0)] (iv)  x  y [ (y > 0) → (x + y < 0) ].  NORMAL FORMS When the statements consist of more variables or are of complex form, then the method of employing truth table is not efficient. Thus we will have to reduce the statement to so called ‘Normal forms’. 1. Disjunctive Normal form denoted by DNF. 2. Conjunctive Normal form denoted by CNF.  DISJUNCTIVE NORMAL FORM (DNF) An expression of 'n' variables x1, x2, … xn is said to be a ‘minterm’ if it is of the form. x1  x2  x3 …  xn An expression is said to be in 'disjunctive normal form' if it is a join of minterms. Example : (x1  x2  x3)  (x1  x2  x3) A statement which consists of a disjunction of fundamental conjunctions is called disjunctive normal form.  EXAMPLES OF DNF i. (p  q)  ~ q ii. (~ p  q)  (p  q)  q iii. (p  q  r)  (p  ~ r)  (q  r) iv. (p  ~ q)  (p  r) v. ((p  q  r)  ~ r) (Note :  = join)  DNF Ex. : Obtain the DNF of the form p Ù (p ® q) Soln.: p  (p → q)p  (~ p  q)  (p  ~ p)  (p  q) F  (p  q) (p  q)  CONJUNCTIVE NORMAL FORM (CNF) An expression of 'n' variables x 1, x2, … , xn is said to be a ‘maxterm’, if it is of the form x1  x2  x3  …  xn An expression is said to be in conjunctive normal form if it is a meet of maxterms. Ex. : (x1  x2  x3)  (x1  x2  x3) Note that a CNF is a tautology if and only if every fundmental disjunction contained in it is a tautology. Ex. : (i) pq (ii) ~ p  (p  q) (iii) (p  q  r)  (~ p  r)  CNF Ex. : Obtain the CNF of the form (~ p → r)  (p  q) Soln.: (~ p → r)  (p  q)  (~ p → r)  (p  q))  (~ p → r)  ((p → q)  (q → p))  (~ (~ p)  r)  ((~ p  q)  (~ q  p))  (p  r)  (~ p  q)  (~ q  p)  CNF Ex. : Obtain the CNF of the form (p  q)  (~ p  q  r) Soln.:  (p  (~ p  q  r))  (q  (~ p  q  r)) Distributive law  ((p  ~ p)  (p  q)  (p  r))  ((q  ~ p)  (q  q)  (q  r))  (p  q)  (p  r)  (q  ~ p)  q  (q  r)  DNF USING TRUTH TABLE Ex. :Find the DNF of the form (~ p → r)  (p  q) p q r p  p→r p q ( p → r)  (p  q) T T T F T T T T T F F T T T T F T F T F F T F F F T F F F T T T T F F F T F T F F F F F T T T T T F F F T F T F Consider the rows of p, q, r in which T appears in the last column. Then the required DNF is (p  q  r)  (p  q   r)  ( p   q  r)  CNF, DNF Ex. : Obtain the CNF and DNF of  (p  q) (p  q) Soln.:  (p  q) (p  q)  (  (p  q) → (p  q) ) ( (p  q) →  (p  q) )  ( (p  q)  (p  q))  ( (p  q)   (p  q))  ( (p  q)  (p  q) )  ( ( p   q)  ( p   q) )  (p  q)  (( p   q   p)  ( p   q   q))  (p  q)  ( p   q)  ( p   q)  (p  q)  ( p   q)  CNF Further, (p  q)  ( p   q) ((p  q)   p)  ((p  q)   q) (p   p)  (q   p)  ((p   q)  (q   q) F  (q   p)  (p   q)  F (q   p)  (p   q)  DNF  MATHEMATICAL INDUCTION In Mathematics, we are often required to generalize a particular solution. In order to do this, we look for a pattern in the particular solution. Mathematical induction generalizes this pattern of solutions by proving that it is always possible to extend the solution to a group that is one larger than the previous. The generalization is achieved by using a statement involving a variable natural number. To the software engineer, mathematical induction is an important tool in algorithm verification, to check whether a program statement is loop invariant, that is, whether it is true before and after every pass through a programming loop.  MATHEMATICAL INDUCTION Let P(n) be a statement involving a natural number n. Basis of induction 1. If P(n) is true for n = n 0 and Induction step 2. Assuming P(k) is true, (k  n0) we prove P(k + 1) is also true, then P(n) is true for all natural numbers n  n0 The assumption that P(n) is true for n = k is called as the Induction hypothesis. MATHEMATICAL INDUCTION