Maths Part 1 - Chap 1 v1.pdf

1 Mathematical logic For example: Let's Study i) 2 is a prime number.  Statement ii) Ev...

1 Mathematical logic For example: Let's Study i) 2 is a prime number.  Statement ii) Every rectangle is a square.  Logical connectives iii) The Sun rises in the West.  Quantifiers and quantified statements iv) Mumbai is the capital of Maharashtra.  Statement patterns and logical Truth value of a statement: equivalence A statement is either true or false. The  Algebra of statements truth value of a ‘true’ statement is denoted by T (TRUE) and that of a false statement is denoted  Venn diagrams by F (FALSE). Introduction: Example 1: Observe the following sentences. Mathematics is an exact science. Every i) The Sun rises in the East. statement must be precise. There has to be ii) The square of a real number is negative. proper reasoning in every mathematical proof. Proper reasoning involves Logic. Logic related iii) Sum of two odd numbers is odd. to mathematics has been developed over last 100 iv) Sum of opposite angles in a cyclic rectangle years or so. The axiomatic approach to logic is 180°. was first propounded by the English philosopher Here, the truth value of statements (i) and and mathematician George Boole. Hence it is (iv) is T, and that of (ii) and (iii) is F. known as Boolean logic or mathematical logic Note: The sentences like exclamatory, or symbolic logic. interrogative, imperative are not considered as statements. The word ‘logic’ is derived from the Greek word ‘Logos’ which means reason. Thus Logic Example 2: Observe the following sentences. deals with the method of reasoning. Aristotle i) May God bless you! (382-322 B.C.), the great philosopher and ii) Why are you so unhappy? thinker laid down the foundations of study of logic in a systematic form. The study of logic iii) Remember me when we are parted. helps in increasing one’s ability of systematic iv) Don’t ever touch my phone. and logical reasoning and develop the skill of v) I hate you! understanding validity of statements. vi) Where do you want to go today? 1.1 Statement: The above sentences cannot be assigned A statement is a declarative sentence which truth values, so none of them is a statement. is either true or false but not both simultaneously. The sentences (i) and (v) are exclamatory. Statements are denoted by letters like p,q,r,.... The sentences (ii) and (vi) are interrogative. The sentences (iii) and (iv) are imperative. 1 Open sentences: Note: An open sentence is a sentence whose truth i) An open sentence is not considered a can vary according to some conditions which are statement in logic. not stated in the sentence. ii) Mathematical identities are true statements. Example 3: Observe the following. For example: i) x+4=8 a + 0 = 0 + a = a, for any real number a. ii) Chinese food is very tasty Each of the above sentences is an open sentence, because truth of (i) depends on the value of x; if x = 4, it is true and if x ≠ 4, it is false and that of (ii) varies as degree of tasty food varies from individual to individual. Activity: Determine whether the following sentences are statements in logic and write down the truth values of the statements. Sr. Sentence Whether it If ‘No’ then Truth value No. is a statement reason of or not (yes/No) statement 1. −9 is a rational number Yes –– False ‘F’. 2. Can you speak in French? No Interrogative –– 3. Tokyo is in Gujrat Yes –– False ‘F’. 4. Fantastic, let’s go! No Exclamatory –– 5. Please open the door quickly. No Imperative –– 6. Square of an even number is even. True ‘T’ 7. x + 5 < 14 8. 5 is a perfect square 9. West Bengal is capital of Kolkata. 10. i2 = − 1 (Note: Complete the above table) ii) The sum of interior angles of a triangle is EXERCISE 1.1 180° State which of the following sentences iii) You are amazing! are statements. Justify your answer if it is a iv) Please grant me a loan. statement. Write down its truth value. v) −4 is an irrational number. i) A triangle has ‘n’ sides vi) x2 − 6x + 8 = 0 implies x = −4 or x = −2. 2 vii) He is an actor. The words or group of words such as viii) Did you have lunch? “and”, “or”, “if... then”, “If and only if”, can be used to join or connect two or more simple ix) Have a cup of tea. sentences. These connecting words are called x) (x + y)2 = x2 + 2xy + y2 for all x, y ∈ R. logical connectives. xi) Every real number is a complex number. Note: ‘not’ is a logical operator for a single statement. It changes the truth value from T to F xii) 1 is a prime number. and F to T. xiii) With the sunset the day ends. Compound Statement: xiv) 1 ! = 0 A compound statement is a statement which is formed by combining two or more simple xv) 3 + 5 > 11 statements with the help of logical connectives. xvi) The number Π is an irrational number. The above four sentences are compound xvii) x2 − y2 = (x + y) (x − y) for all x, y ∈ R. sentences. xviii) The number 2 is the only even prime Note: number. i) Each of the statements that comprise xix) Two co-planar lines are either parallel or a compound statement is called a sub- intersecting. statement or a component statement. ii) Truth value of a compound statement xx) The number of arrangements of 7 girls in depends on the truth values of the sub- a row for a photograph is 7!. statements i.e. constituent simple statements xxi) Give me a compass box. and connectives used. Every simple xxii) Bring the motor car here. statement has its truth value either ‘T’ or ‘F’. Thus, while determining the truth value of xxiii) It may rain today. a compound statement, we have to consider xxiv) If a + b < 7, where a ≥ 0 and b ≥ 0 then all possible combinations of truth values of a 3 Solution: q : Nagpur is in Vidarbha i) Let p : An angle is right angle. The conjunction is q : Its measure is 90°. Then, p ∧ q is the symbolic form. p∧q : 5 > 3 and Nagpur is in Vidarbha. ii) Let p : Jupiter is plannet ii) p : a+bi is irrational number for all a ,b ∈ R; q:0!=1 q : Mars is a star. Then, p ∧ q is the symbolic form. The conjuction is iii) Let p :............. p∧q : a + bi is irrational number, q :............. for all a, b ∈ R and 0 ! = 1 Then,..................... Truth table of conjunction (p∧q) Ex. 2: Write the truth value of each of the following statements. Table 1.2 i) Patna is capital of Bihar and 5i is an p q p∧q imaginary number. T T T ii) Patna is capital of Bihar and 5i is not an T F F imaginary number. F T F iii) Patna is not capital of Bihar and 5i is an imaginary number. F F F iv) Patna is not capital of Bihar and 5i is not an From the last column, the truth values of imaginary number. above four combinations can be decided. Remark: Solution: Let p : Patna is capital of Bihar i) Conjunction is true if both sub-statements q : 5i is an imaginary number are true. Otherwise it is false. p is true; q is true. 4 i) True (T), since both the sub-statements are sense that first or second or both possibilities true i.e. both Patna is capital of Bihar and 5i exist. Hence it is called inclusive sense of ‘or’. In is an imaginary number are true. mathematics ‘or’ is used in the inclusive sense. (As T ∧ T = T) Thus p or q (p ∨ q) means p or q or both p and q. ii) False (F), since first sub-statement “Patna Example: Consider the followinig simple is capital of Bihar” is true and second sub- statements. statement 5i is not an imaginary number is i) 3 > 2 ; 2 + 3 = 5 p : 3 > 2 False. (As T ∧ F = F) q:2+3=5 iii) False (F), since first sub-statement “Patna The disjunction is p ∨ q : 3 > 2 or 2 + 3 = 5 is not capital of Bihar” is False and second ii) New York is in U.S.; 6 > 8 sub-statement 5i is an imaginary number is True. (As F ∧ T = F) p : New York is in U.S. iv) False (F), since both sub-statement “Patna q:6>8 is not capital of Bihar” and “5i is not an The disjunction is p ∨ q : New York is in imaginary number” are False. U.S. or 6 > 8. (As F ∧ F = F) Truth table of disjunction (p ∨ q) Table 1.3 B) Disjunction (∨): If p and q are two simple statements p q p∨q connected by the word ‘or’ then the resulting T T T compound statement ‘p or q’ is called the T F T disjunction of p and q, which is written in the symbolic form as ‘p ∨ q’. F T T Note: The word ‘or’ is used in English language F F F in two distinct senses, one is exclusive and the Note: other is inclusive. i) The disjunction is false if both sub- For example: Consider the following statements. statements are false. Otherwise it is true. i) Throwing a coin will get a head or a tail. ii) Disjunction of two statements is equivalent ii) The amount should be paid by cheque or by to ‘union of two sets’ in set theory. demand draft. SOLVED EXAMPLES In the above statements ‘or’ is used in the sense that only one of the two possibilities Ex. 1: Express the following statements in the exists, but not both. Hence it is called exclusive symbolic form. sense of ‘or’. i) Rohit is smart or he is healthy. Also consider the statements: ii) Four or five students did not attend the i) Graduate or employee persons are eligible lectures. to apply for this post. Solution: ii) The child should be accompanied by father i) Let p : Rohit is smart or mother. q : Rohit is healthy In the above statements ‘or’ is used in the Then, p ∨ q is symbolic form. 5 ii) In this sentence ‘or’ is used for indicating EXERCISE 1.2 approximate number of students and not Ex. 1: Express the following statements in as a connective. Therefore, it is a simple symbolic form. statement and it is expressed as i) e is a vowel or 2 + 3 = 5 p : Four or five students did not attend the lectures. ii) Mango is a fruit but potato is a vegetable. iii) Milk is white or grass is green. Ex. 2: Write the truth values of the following iv) I like playing but not singing. statements. v) Even though it is cloudy, it is still raining. i) India is a democratic country or China is a communist country. Ex. 2: Write the truth values of following ii) India is a democratic country or China is statements. not a communist country. i) Earth is a planet and Moon is a star. iii) India is not a democratic country or China ii) 16 is an even number and 8 is a perfect is a communist country. square. iv) India is not a democratic country or China iii) A quadratic equation has two distinct roots is not a communist country. or 6 has three prime factors. iv) The Himalayas are the highest mountains Solution: p : India is a democratic country. but they are part of India in the North East. q : China is a communist country. C) Negation (∼): p is true; q is true. The denial of an assertion contained in a i) True (T), since both the sub-statements are statement is called its negation. true i.e. both “India is a democratic country” The negation of a statement is generally and “China is a communist country” are formed by inserting the word “not” at some true. (As T ∨ T = T) proper place in the statement or by prefixing the ii) True (T), since first sub-statements “India statement with “it is not the case that” or “it is is a democratic country” is true and second false that” or “it is not true that”. sub-statement “China is not a communist The negation of a statement p is written as country” is false. (As T ∨ F = T) ∼ p (read as “negation p” or “not p”) in symbolic iii) True (T), since first sub-statements “India form. is not a democratic country” is false For example: and second sub-statement “China is a communist country” is true. (As F ∨ T = T) Let p : 2 is an even number ∼ p : 2 is not an even number. iv) False (F), since both the sub-statements “India is not a democratic country” and or ∼ p : It is not the case that 2 is an even “China is not a communist country” are number false. (As F ∨ F = F) or ∼ p : It is false that 2 is an even number 6  The truth table of negation (∼ p) D) Conditional statement (Implication, →) Table 1.4 If two simple statements p and q are p ∼p connected by the group of words “If... then...”, then the resulting compound statement “If p then T F q” is called a conditional statement (implication) F T and is written in symbolic form as “p → q” (read Note: Negation of a statement is equivalent to as “p implies q”). the complement of a set in set theory. For example: SOLVED EXAMPLES i) Let p : There is rain q : The match will be cancelled Ex. 1: Write the negation of the following statements. then, p → q : If there is rain then the match will be cancelled. i) p : He is honest. ii) Let p : r is a rational number. ii) q : p is an irrational number. q : r is a real number. Solution: then, p → q : If r is a rational number then r i) ∼ p : He is not honest is a real number. or ∼ p : It is not the case that he is honest The truth table for conditional statement or ∼ p : It is false that he is honest. (p → q) ii) ∼ q : p is not an irrational number. Table 1.5 or ∼ q : p q p→q or ∼ q : T T T T F F F T T EXERCISE 1.3 F F T 1. Write the negation of each of the following statements. SOLVED EXAMPLES i) All men are animals. ii) − 3 is a natural number. Ex. 1: Express the following statements in the iii) It is false that Nagpur is capital of symbolic form. Maharashtra i) If the train reaches on time, then I can catch iv) 2 + 3 ≠ 5 the connecting flight. 2. Write the truth value of the negation of each ii) If price increases then demand falls. of the following statements. Solution: i) 5 is an irrational number i) Let p : The train reaches on time ii) London is in England q : I can catch the connecting flight. iii) For every x ∈ N , x + 3 < 8. Therefore, p → q is symbolic form. 7 ii) Let p : price increases For example: q : demand falls i) Let p : Milk is white Therefore, p → q is symbolic form. q : the sky is blue Therefore, p ↔ q : Milk is white if and only Ex. 2: Write the truth value of each of the if the sky is blue. following statements. ii) Let p : 3 < 5 i) If Rome is in Italy then Paris is in France. q : 4 2 is an irrational number. ii) If Rome is in Italy then Paris is not in Therefore, p ↔ q : 3 < 5 if and only if 4 2 France. is an irrational number. iii) If Rome is not in Italy then Paris is in France. Truth table for biconditional (p ↔ q) iv) If Rome is not in Italy then Paris not in Table 1.6 France. p q p↔q T T T Solution: T F F p : Rome is in Italy F T F q : Paris is in France F F T p is true ; q is true. i) True (T), since both the sub-statements are SOLVED EXAMPLES true. i.e. Rome is in Italy and Paris is in France are true. (As T → T = T) Ex. 1: Translate the following statements (verbal form) to symbolic form. ii) False (F), since first sub-statement Rome is in Italy is true and second sub-statement i) Price increases if and only if demand falls. Paris in not in France is false. ii) 5 + 4 = 9 if and only if 3 + 2 = 7 (As T → F = F) Solution: iii) True (T), since first sub-statement Rome is i) Let p : Price increases not in Italy is false and second sub-statement Paris is in France is true. (As F → T = T) q : demand falls Therefore, p ↔ q is the symbolic form. iv) True (T), since both the sub-statements are false. i.e. Rome is not in Italy and Paris is ii) Let p : 5 + 4 = 9 not in France both are false. (As F → F = T) q : 3 + 2 = 7 Therefore, p ↔ q is the symbolic form. E) Biconditional (Double implication) (↔) or (⇔): Ex. 2: Write the truth value of each of the If two statements p and q are connected by following statements. the group of words “If and only if” or “iff”, then i) The Sun rises in the East if and only if the resulting compound statement “p if and only 4+3=7 if q” is called biconditional of p and q, is written in symbolic form as p ↔ q and read as “p if and ii) The Sun rises in the East if and only if only if q”. 4 + 3 = 10 8 iii) The Sun rises in the West if and only if ii) It is false that Nagpur is capital of India iff 4+3=7 3+2=4 iv) The Sun rises in the West if and only if iii) ABCD is a parallelogram but it is not a 4 + 3 = 10 quadrilateral. iv) It is false that 32 + 42 = 52 or 2 is not a Solution: rational number but 32 + 42 = 52 and 8 > 3. p : The Sun rises in the East; q : 4 + 3 = 7; Solution: p is true, q is true. i) Let p : quadrilateral is a square The truth value of each statement is given q : quadrilateral is a rhombus. by Then, p → ∼ q is symbolic form. i) True (T), since both the sub-statements (i.e. ii) Let p : Nagpur is capital of India “The Sun rises in the East” and “4 + 3 = 7”) q : 3 + 2 = 4 are true. (As T ↔ T = T) Then, ∼ p ↔ q is the symbolic form. ii) False (F), since both the sub-statements iii) Let p : ABCD is a parallelogram have opposite truth values (i.e. “The Sun rises in the East” is true but “4 + 3 = 10” is q : ABCD is a quadrilateral false.). (As T ↔ F = F) Then, p ∧ ∼ q is the symbolic form. iii) False (F), since both the sub-statements iv) Let p : 32 + 42 = 52 have opposite truth values (i.e. “The Sun q : 2 is a rational number rises in the East” is false but “4 + 3 = 7” is r : 8 > 3. true.). (As F ↔ T = F) Therefore, (∼ p ∨ ∼ q) ∧ (p ∧ r) is the iv) True (T), since both the sub-statements symbolic form of the required statement. have same truth values (i.e. they are false.) (As F ↔ F = T) Ex. 2: Express the following statements in Therefore, p ↔ q is the symbolic form. symbolic form and write their truth values. Note: i) It is not true that 2 is a rational number. i) The biconditional statement p ↔ q is the ii) 4 is an odd number iff 3 is not a prime factor compound statement “p → q” and “q → p” of 6. of two compound statements. iii) It is not true that i is a real number. ii) p ↔ q can also be read as – a) q if and only if p. Solution: b) p is necessary and sufficient for q. i) Let p : 2 is a rational number. Then ∼ p is the symbolic form. c) q is necessary and sufficient for p. Given statement, p is false F. d) p implies q and q implies p. ∴∼p≡T e) p implies and is implied by q. ∴ the truth value of given statement is T. Ex. 1: Express the following in symbolic form ii) Let p : 4 is an odd number. using logical connectives. q : 3 is a prime factor of 6. i) If a quadrilateral is a square then it is not a ∼ q : 3 is not a prime factor of 6. rhombus. 9  Therefore, p ↔ (∼ q) is the symbolic form. Ex. 3: If p and q are true and r and s are false, Given statement, p is false F. find the truth value of each of the following. q is true T. i) (p ↔ ∼ q) ∧ (r ↔ ∼ s) ∴ ∼ q is false F. ii) (p → r) ∨ (q → s) ∴ p ↔ (∼ q) ≡ F ↔ F ≡ T iii) ∼ [(p ∧ ∼ s) ∨ (q ∧ ∼ r)] ∴ the truth value of given statement is T. Solution: iii) Let p : i is a real number. i) Without truth table : (p ↔ ∼ q) ∧ (r ↔ ∼ s) ∴ ∼ p : It is not true that i is a real number. = (T ↔ ∼ T) ∧ (F ↔ ∼ F) Therefore, ∼ p : is the symbolic form. = (T ↔ F) ∧ (F ↔ T) p is false F. =F∧ F =F ∴ ∼ p : is true T. ∴ the truth value of the given statement is T. Construct truth table Table 1.7 p q r s ∼q ∼s p↔∼q r↔∼s (p ↔ ∼ q) ∧ (r ↔ ∼ s) T T F F F T F F F ii) Without truth table : Construct truth table (p → r) ∨ (q → s) = (T → F) ∨ (T → F) Table 1.9 =F∨F (Note: Construct truth table and complete =F your solution) Construct truth table EXERCISE 1.4 Table 1.8 Ex. 1: Write the following statements in p q r s p → r q → s (p → r) ∨ (q → s) symbolic form. T T F F F F F i) If triangle is equilateral then it is equiangular. ii) Without truth table : (Activity) ii) It is not true that “i” is a real number. ∼ [(p ∧ ∼ s) ∨ (q ∧ ∼ r)] iii) Even though it is not cloudy, it is still raining. = ∼ [( ∧∼ )∨( ∧ )] iv) Milk is white if and only if the sky is not = ∼ [( ∧ T) ∨ (T ∧ T)] blue. =∼( ∨ ) v) Stock prices are high if and only if stocks are rising. =∼( ) vi) If Kutub-Minar is in Delhi then Taj-Mahal = is in Agra. 10 Ex. 2: Find truth value of each of the following 1.2.1 Quantifiers and Quantified statements: statements. i) For every x ∈ R, x2 is non negative. We i) It is not true that 3 − 7i is a real number. shall now see how to write this statement ii) If a joint venture is a temporary partnership, using symbols. ‘∀x’ is used to denote “For then discount on purchase is credited to the all x”. supplier. Thus, the above statement may be written iii) Every accountant is free to apply his own in mathematical notation " z ∈ R, z2 ≥ 0. accounting rules if and only if machinery is The symbol ‘"’ stands for “For all values an asset. of”. This is known as universal quantifier. iv) Neither 27 is a prime number nor divisible by 4. ii) Also we can get x ∈ N such that x + 4 = 7. To write this in symbols we use the symbol v) 3 is a prime number and an odd number. ∃ x to denote “there exists x”. Thus, we have ∃ x ∈ N such that x + 4 = 7. Ex. 3: If p and q are true and r and s are false, find the truth value of each of the following The symbol ∃ stands for “there exists”. This compound statements. symbol is known as existential quantifier. i) p ∧ (q ∧ r) Thus, there are two types of quantifiers. ii) (p → q) ∨ (r ∧ s) a) Universal quantifier (") iii) ∼ [(∼ p ∨ s) ∧ (∼ q ∧ r)] b) Existential quantifier (∃) iv) (p → q) ↔ ∼ (p ∨ q) Quantified statement: v) [(p ∨ s) → r] ∨ ∼ [∼ (p → q) ∨ s] An open sentence with a quantifier becomes vi) ∼ [p ∨ (r ∧ s)] ∧ ∼ [(r ∧ ∼ s) ∧ q] a statement and is called a quantified statement. Ex. 4: Assuming that the following statements are true, SOLVED EXAMPLES p : Sunday is holiday, q : Ram does not study on holiday, Ex. 1: Use quantifiers to convert each of the find the truth values of the following following open sentences defined on N, into a statements. true statement. i) Sunday is not holiday or Ram studies on i) 2x + 3 = 11 holiday. ii) If Sunday is not holiday then Ram studies ii) x3 < 64 on holiday. iii) x + 5 < 9 iii) Sunday is a holiday and Ram studies on holiday. Solution: Ex. 5: If p : He swims i) ∃ x ∈ N such that 2x + 3 = 11. It is a true q : Water is warm statement, since x = 4 ∈ N satisfies 2x + 3 = 11. Give the verbal statements for the following symbolic statements. ii) x3 < 64 ∃ x ∈ N such that it is a true statement, since x = 1 or 2 or 3 ∈ N satisfies i) p↔∼q x3 < 64. ii) ∼ (p ∨ q) iii) ∃ x ∈ N such that x + 5 < 9. It is a true iii) q → p statement for x = 1 or 2 or 3 ∈ N satisfies iv) q ∧ ∼ p x + 5 < 9. 11 Ex. 2: If A = {1, 3, 5, 7} determine the truth For example: value of each of the following statements. i) (p ∨ q) → r i) ∃ x ∈ A, such that x2 < 1. ii) ∃ x ∈ A, such that x + 5 ≤ 10 ii) p ∧ (q ∧ r) iii) " x ∈ A, x + 3 < 9 iii) ∼ (p ∨ q) are statement patterns Solution: Note: While preparing truth tables of the given statement patterns, the following points should i) No number in set A satisfies x2 < 1, since be noted. the square of every natural number is 1 or greater than 1. i) If a statement pattern involves n component ∴ the given statement is false, hence its statements p, q, r,..... and each of p, q, r,..... truth value is F. has 2 possible truth values namely T and F, then the truth table of the statement pattern ii) Clearly, x = 1, 3 or 5 satisfies x + 5 ≤ 10. consists of 2n rows. So the given statement is true, hence truth value is T. ii) If a statement pattern contains “m” iii) Since x = 7 ∈ A does not satisfy x + 3 < 9, connectives and “n” component statements the given statement is false. Hence its truth then the truth table of the statement pattern value is F. consists of (m + n) columns. iii) Parentheses must be introduced whenever EXERCISE 1.5 necessary. Ex. 1: Use quantifiers to convert each of the For example: following open sentences defined on N, into a ∼ (p → q) and ∼ p → q are not the same. true statement. i) x2 + 3x − 10 = 0 SOLVED EXAMPLES ii) 3x − 4 < 9 iii) n2 ≥ 1 Ex. 1: Prepare the truth table for each of the iv) 2n − 1 = 5 following statement patterns. v) Y+4>6 i) [(p → q) ∨ p] → p vi) 3y − 2 ≤ 9 ii) ∼ [p ∨ q] → ∼ (p ∧ q) Ex. 2: If B = {2, 3, 5, 6, 7} determine the truth iii) (∼ p ∨ q) ∨ ∼ q value of each of the following. iv) (p ∧ r) ∨ (q ∧ r) i) " x ∈ B such that x is prime number. ii) ∃ n ∈ B, such that n + 6 > 12 Solution: iii) ∃ n ∈ B, such that 2n + 2 < 4 i) [(p → q) ∨ p) → p iv) " y ∈ B such that y2 is negative v) " y ∈ B such that (y − 5) ∈ N Truth table 1.10 p q p → q (p → q) ∨ p [(p → q) ∨ p] 1.3 Statement Patterns and Logical →p Equivalence: T T T T T A) Statement Patterns: T F F T T Let p, q, r,..... be simple statements. F T T T F A compound statement obtained from these F F T T F simple statements by using one or more of the connectives ∧, ∨, →, ↔, is called a statement ii) ∼ (p ∨ q) → ∼ (p ∧ q) pattern. 12  Truth table 1.11 p q p∨q ∼ (p ∨ q) (p ∧ q) ∼ (p ∧ q) ∼ (p ∨ q) → ∼ (p ∧ q) T T T F T F T T F T F F T T F T T F F T T F F F T F T T iii) (∼ p ∨ q) ∨ ∼ q iii) p ∨ (q ∨ r) ≡ (p ∨ q) ∨ (p ∨ r) Truth table 1.12 iv) ∼ r → ∼ (p ∧ q) ≡ ∼ (q → r) → ∼ p p q ∼p ∼q ∼p∨q (∼ p ∨ q) ∨ ∼ q Solution: T T F F T T i) ∼ (p ∧ q) ≡ ∼ p ∨ ∼ q T F F T F T Truth table 1.14 F T T F T T F F T T T T p q ∼ p ∼ q p ∧ q ∼ (p ∧ q) ∼ p ∨ ∼ q 1 2 3 4 5 6 7 iv) (p ∧ r) ∨ (q ∧ r) T T F F T F F Complete the following truth table : T F F T F T T Truth table 1.13 F T T F F T T p q r p∧r q∧r (p ∧ r) ∨ (q ∧ r) F F T T F T T T T T T T F From the truth table 1.14, we observe that F all entires in 6th and 7th columns are identical. F T T ∴ ∼ (p ∧ q) ≡ ∼ p ∨ ∼ q F F F T F ii) ∼ (p ∨ q) ≡ ∼ p ∧ ∼ q T F F Truth table 1.15 T p q ∼ p ∼ q p ∨ q ∼ (p ∨ q) ∼ p ∧ ∼ q F F F 1 2 3 4 5 6 7 B) Logical Equivalence: T T F F T F F Two or more statement patterns are said to T F F T T F F be logically equivalent if and only if the truth values in their respective columns in the joint F T T F T F F truth table are identical. F F T T F T T If s1 , s2 , s3 ,.... are logically equivalent From the truth table 1.15, we observe that statement patterns, we write s1 ≡ s2 ≡ s3 ≡... all entires in 6th and 7th columns are identical. ∴ ∼ (p ∨ q) ≡ ∼ p ∧ ∼ q. For example: Using a truth table, verify that i) ∼ (p ∧ q) ≡ ∼ p ∨ ∼ q ii) ∼ (p ∨ q) ≡ ∼ p ∧ ∼ q 13 iii) Activity p ∨ (q ∨ r) ≡ (p ∨ q) ∨ (p ∨ r) Truth table 1.16 p q r q∨r P∨ p∨q p∨r (p ∨ q) ∨ (p ∨ r) (q ∨ r) 1 2 3 4 5 6 7 8 T T T T T T T T F T T T F F T T T F T T F T T T F T T F T T F F From the truth table 1.16, we observe that all entires in 5th and 8th columns are identical. ∴ p ∨ (q ∨ r) ≡ (p ∨ q) ∨ (p ∨ r) iv) Activity ∼ r → ∼ (p ∧ q) ≡ ∼ (q → r) → ∼ p Prepare the truth table 1.17 p q r ∼p ∼r p∧q ∼ (p ∧ q) ∼r→ q→r ∼ (q → r) ∼ (q → r) ∼ (p ∧ q) →∼ p C) Tautology, contradiction, contingency: component statements is called a tautology. Tautology: For example: A statement pattern always having the truth Consider (p ∧ q) → (p ∨ q) value ‘T’, irrespective of the truth values of its 14  Truth table 1.18 In the table 1.20, the entries in the last column are not all T and not all F. Therefore, the p q p∧q p∨q (p ∧ q) → (p ∨ q) given statement pattern is a contingency. T T T T T T F F T T SOLVED EXAMPLES F T F T T Ex. 1: Using the truth table, examine whether F F F F T the following statement patterns are tautology, contradictions or contingency. In the above table, all the entries in the last column are T. Therefore, the given statement i) (p ∧ q) → p pattern is a tautology. ii) (∼ p ∨ ∼ q) ↔ ∼ (p ∧ q) iii) (∼ q ∧ p) ∧ q Contradiction: iv) p → (∼ q ∨ r) A statement pattern always having the truth value ‘F’ irrespective of the truth values of its Solution: component statements is called a contradiction. i) The truth table for (p ∧ q) → p For example: Truth table 1.21 Consider p ∧ ∼ p p q p∧q (p ∧ q) → p Truth table 1.19 T T T T p ∼p p∧∼p T F F T T F F F T F T F T F F F F T In the above truth table, all the entries in the In the table 1.21, all the entries in the last last column are F. Therefore, the given statement column are T. Therefore, the given statement pattern is a contradiction. pattern is a tautology. Contingency: ii) Activity: A statement pattern which is neither a tautology nor a contradiction is called a Prepare the truth table for (∼ p ∨ ∼ q) ↔ ∼ contingency. (p ∧ q) For example: Truth table 1.22 Consider (p → q) ∧ (q → p) p q ∼ p ∼ q p ∧ q ∼ (p ∧ q) (∼ p ∨∼ q) ( ∼ p ∨∼ q) ↔ ∼ ( p ∧ q) Truth table 1.20 p q p → q q → p (p → q) ∧ (q → p) T T T T T T F F T F F T T F F iii) The truth table for (∼ q ∧ p) ∧ q F F T T T 15  Truth table 1.23 i) q ∨ [∼ (p ∧ q)] p q ∼q ∼q∧p (∼ q ∧ p) ∧ q ii) (∼ q ∧ p) ∧ (p ∧ ∼ p) T T F F F iii) (p ∧ ∼ q) → (∼ p ∧ ∼ q) T F T T F iv) ∼ p → (p → ∼ q) F T F F F 3. Prove that each of the following statement F F T F F pattern is a tautology. In the table 1.23, all the entries in the last i) (p ∧ q) → q column are F. ii) (p → q) ↔ (∼ q → ∼ p) Therefore, the given statement pattern is a contradiction. iii) (∼ p ∧ ∼ q) → (p → q) iv) The truth table for p → (∼ q ∨ r) iv) (∼ p ∨ ∼ q) ↔ ∼ (p ∧ q) Truth table 1.24 4. Prove that each of the following statement p q r ∼q ∼q∨r p → (∼ q ∨ r) pattern is a contradiction. T T T F T T i) (p ∨ q) ∧ (∼ p ∧ ∼ q) T T F F F F ii) (p ∧ q) ∧ ∼ p T F T T T T iii) (p ∧ q) ∧ (∼ p ∨ ∼ q) T F F T T T iv) (p → q) ∧ (p ∧ ∼ q) F T T F T T 5. Show that each of the following statement F T F F F T pattern is a contingency. F F T T T T i) (p ∧ ∼ q) → (∼ p ∧ ∼ q) F F F T T T ii) (p → q) ↔ (∼ p ∨ q) In the table 1.24, the entries in the last iii) p ∧ [(p → ∼ q) → q] column are neither all T nor all F. iv) (p → q) ∧ (p → r) Therefore, the given statement pattern is a contingency. 6. Using the truth table, verify i) p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) EXERCISE 1.6 ii) p → (p → q) ≡ ∼ q → (p → q) 1. Prepare truth tables for the following iii) ∼ (p → ∼ q) ≡ p ∧ ∼ (∼ q) ≡ p ∧ q statement patterns. iv) ∼ (p ∨ q) ∨ (∼ p ∧ q) ≡ ∼ p i) p → (∼ p ∨ q) ii) (∼ p ∨ q) ∧ (∼ p ∨ ∼ q) 7. Prove that the following pairs of statement patterns are equivalent. iii) (p ∧ r) → (p ∨ ∼ q) i) p ∨ (q ∧ r) and (p ∨ q) ∧ (p ∨ r) iv) (p ∧ q) ∨ ∼ r ii) p ↔ q and (p → q) ∧ (q → p) 2. Examine whether each of the following iii) p → q and ∼ q → ∼ p and ∼ p ∨ q statement patterns is a tautology, a contradiction or a contingency iv) ∼ (p ∧ q) and ∼ p ∨ ∼ q. 16 D) Duality: SOLVED EXAMPLES Two compound statements s1 and s2 are said to be duals of each other, if one can be obtained Ex. 1: Write the duals of the following statements: from the other by replacing ∧ by ∨ and ∨ by ∧, and c by t and t by c, where t denotes tautology i) ∼ (p ∧ q) ∨ (∼ q ∧ ∼ p) and c denotes contradiction. ii) (p ∨ q) ∧ (r ∨ s) iii) [(p ∧ q) ∨ r] ∧ [(q ∧ r) ∨ s] Note: i) Dual of a statement is unique. Solution: The duals are given by ii) The symbol ∼ is not changed while finding i) ∼ (p ∨ q) ∧ (∼ q ∨ ∼ p) the dual. ii) (p ∧ q) ∨ (r ∧ s) iii) Dual of the dual is the original statement iii) [(p ∨ q) ∧ r] ∨ [(q ∨ r) ∧ s] itself. Ex. 2: Write the duals of the following statements: iv) The connectives ∧ and ∨, the special statements t and c are duals of each other. i) All natural numbers are integers or rational numbers. v) T is changed to F and vice-versa. ii) Some roses are red and all lillies are white. For example: Solution: The duals are given by i) Consider the distributive laws, i) All natural numbers are integers and rational p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)... (1) numbers. p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)... (2) ii) Some roses are red or all lillies are white. Observe that (2) can be obtained from (1) by replacing ∧ by ∨ and ∨ by ∧ i.e. interchanging EXERCISE 1.7 ∧ and ∨. 1. Write the dual of each of the following : Hence (1) is the dual of (2). i) (p ∨ q) ∨ r Similarly, (1) can be obtained from (2) by replacing ∨ by ∧ and ∧ by ∨. Hence, (2) is the ii) ∼ (p ∨ q) ∧ [p ∨ ∼ (q ∧ ∼ r)] dual of (1). iii) p ∨ (q ∨ r) ≡ (p ∨ q) ∨ r Therefore, statements (1) and (2) are called iv) ∼ (p ∧ q) ≡ ∼ p ∨ ∼ q duals of each other. 2. Write the dual statement of each of the following compound statements. ii) Consider De-Morgan’s laws : i) 13 is prime number and India is a ∼ (p ∧ q) ≡ ∼ p ∨ ∼ q... (1) democratic country. ∼ (p ∨ q) ≡ ∼ p ∧ ∼ q... (2) ii) Karina is very good or every body likes her. Statements, (1) and (2) are duals of each other. iii) Radha and Sushmita can not read Urdu. iv) A number is real number and the square of the number is non negative. 17 E) Negation of a compound statement: 3) Negation of negation: We have studied the negation of simple Let p be a simple statement. statements. Negation of a simple statement is Truth table 1.25 obtained by inserting “not” at the appropriate p ∼p ∼ (∼ p) place in the statement e.g. the negation of “Ram is tall” is “Ram is not tall”. But writing negations T F T of compound statements involving conjunction., F T F disjunction, conditional, biconditional etc. is not straight forward. From the truth table 1.25, we see that ∼ (∼ p) ≡ p 1) Negation of conjunction: Thus, the negation of negation of a In section 1.3(B) we have seen that statement is the original statement ∼ (∼ p) ≡ p. ∼ ( p ∧ q) ≡ ∼ p ∨ ∼ q. It means that negation of the conjunction of two simple statements is the For example: disjunction of their negation. Let p : 5 is an irrational number. Consider the following conjunction. The negation of p is given by “Parth plays cricket and chess.” ∼ p : 5 is not an irrational number. Let p : Parth plays cricket. ∼ (∼ p) : 5 is an irrational number. q : Parth plays chess. Therefore, negation of negation of p is Given statement is p ∧ q. ∼ (∼ p) i.e. it is not the case that 5 is not an You know that ∼ (p ∧ q) ≡ ∼ p ∨ ∼ q irrational number. ∴ negation is Parth doesn’t play cricket or OR it is false that 5 is not an irrational he doesn’t play chess. number. OR 5 is an irrational number. 2) Negation of disjunction: In section 1.3(B) we have seen that 4) Negation of Conditional (Implication): ∼ (p ∨ q) ≡ ∼ p ∧ ∼ q. It means that negation of You know that p → q ≡ ∼ p ∨ q the disjunction of two simple statements is the ∴ ∼ (p → q) ≡ ∼ (∼ p ∨ q) conjunction of their negation. ≡ ∼ (∼ p) ∧ ∼ q... by De-Morgan's law For ex: The number 2 is an even number or the number 2 is a prime number. ∴ ∼ (p → q) ≡ p ∧ ∼ q Let p : The number 2 is an even number. We can also prove this result by truth table. q : The number 2 is a prime number. Truth table 1.26 ∴ given statement : p ∨ q. p q p → q ∼ (p → q) ∼q p∧∼q You know that ∼ (p ∨ q) ≡ ∼ p ∧ ∼ q 1 2 3 4 5 6 ∴ negation is “The number 2 is not an T T T F F F even number and the number 2 is not a prime T F F T T T number”. F T T F F F F F T F F F 18  All the entries in the columns 4 and 6 of 5) Negation of Biconditional (Double table 1.26 are identical. implication): ∴ ∼ (p → q) ≡ p ∧ ∼ q Consider the biconditional p ↔ q. e.g. If every planet moves around the Sun Method 1: then every Moon of the planet moves around the We have seen that Sun. (p ↔ q) ≡ (p → q) ∧ (q → p) Negation of the given statement is, Every ∴ ∼ (p ↔ q) ≡ ∼ [(p → q) ∧ (q → p)] planet moves around the Sun but (and) every ≡ ∼ (p → q) ∨ ∼ (q → p) Moon of the planet does not move around the... by De-Morgans law Sun. ≡ (p ∧ ∼ q) ∨ (q ∧ ∼ p)... by negation of the conditional statement ∴ ∼ (p ↔ q) ≡ (p ∧ ∼ q) ∨ (q ∧ ∼ p) Method 2: We also prove this by using truth table 1.27. Truth Table 1.27 p q p ↔ q ∼ (p ↔ ∼ q) ∼p ∼q p ∧ ∼ q q ∧ ∼ p (p ∧ ∼ q) ∨ (q ∧ ∼ p) 1 2 3 4 5 6 7 8 9 T T T F F F F F F T F F T F T T F T F T F T T F F T T F F T F T T F F F Since all the entries in the columns 4 and 9 of truth table 1.27 are identical. ∴ ∼ (p ↔ q) ≡ (p ∧ ∼ q) ∨ (q ∧ ∼ p). For example: 2n is divisible by 4 if and only if For example: Consider the statement pattern n is an even integer. (∼ p ∧ q) ∨ (p ∨ ∼ q). Its negation is given by : Let p : 2n is divisible by 4 i.e. ∼ [(∼ p ∧ q) ∨ (p ∨ ∼ q)] q : n is an even integer. ≡ (p ∨ ∼ q) ∧ (∼ p ∧ q) 6) Negation of a quantified statement: Therefore, negation of the given statement is “2n is divisible by 4 and n is not an even integer While forming negation of a quantified or n is an even integer and 2n is not divisible statement, we replace the word ‘all’ by ‘some’, by 4”. “for every” by “there exists” and vice versa. Note: SOLVED EXAMPLES Negation of a statement pattern involving Ex. 1: Write negation of each of the following one or more of the simple statements p, q, r,... statements : and one or more of the three connectives ∧, ∨, ∼ can be obtained by replacing ∧ by ∨, ∨ by ∧ and i) All girls are sincere replaicng p, q, r....by ∼p, ∼q, ∼r..... 19 ii) If India is playing in world cup and Rohit is Converse: q → p the captain, then we are sure to win. i.e. If a man is happy then he is rich. iii) Some bureaucrats are efficient. Inverse: ∼ p → ∼ q i.e. If a man is not rich then he is not happy. Solution: Contrapositive: ∼ q → ∼ p i.e. If a man is i) The negation is, not happy then he is not rich. Some girls are not sincere ii) Let p : The train reaches on time. OR, There exists a girl, who is not sincere. q : I can catch the connecting flight. ii) Let p : India is playing world cup Therefore, the symbolic form of the given q : Rohit is the captain statement is p → q. r : We win. Converse, q → p i.e. The given compound statement is Inverse i.e. (p ∧ q) → r Contrapositive i.e. Therefore, the negation is, Ex. 3: Using the rules of negation, write the ∼ [(p ∧ q) → r] ≡ (p ∧ q) ∧ ∼ r negation of the following : India is playing world cup and Rohit is the i) (∼ p ∧ r) ∨ (p ∨ ∼ r) captain and we are not sure to win. ii) (p ∨ ∼ r) ∧ ∼ q iii) The negation is, all bureaucrats are not iii) The crop will be destroyed if there is a efficient. flood. Converse, Inverse and contrapositive: Solution: Let p and q be simple statements and i) The negation of (∼ p ∧ r) ∨ (p ∨ ∼ r) is let p → q be the implication of p and q. ∼ [(∼ p ∧ r) ∨ (p ∨ ∼ r)] Then, i) The converse of p → q is q → p. ≡ ∼ (∼ p ∧ r) ∧ ∼ (p ∨ ∼ r) ii) Inverse of p → q is ∼ p → ∼ q.... by De-Morgan's law iii) Contrapositive of p → q is ∼ q → ∼ p. ≡ (p ∨ ∼ r) ∧ (∼ p ∧ r) For example: Write the converse, inverse and... by De-Morgan's law and contrapositive of the following compound ∼ (∼ p) ≡ p and ∼ (∼ r) = r. statements. ii) The negation of (p ∨ ∼ r) ∧ ∼ q is i) If a man is rich then he is happy. ii) If the train reaches on time then I can catch ∼ [(p ∨ ∼ r) ∧ ∼ q] the connecting flight. ≡ ∼ (p ∨ ∼ r) ∨ ∼ (∼ q)... by De Morgan's law Solution: i) Let p : A man is rich. ≡ (∼ p ∧ r) ∨ q q : He is happy.... by De Morgan's law and ∼ (∼ q) ≡ q. Therefore, the symbolic form of the given statement is p → q. 20 iii) Let p : The crop will be destroyed. 2. Using the rules of negation, write the q : There is a flood. negations of the following : Therefore, the given statement is q → p i) (p → r) ∧ q and its negation is ∼ (q → p) ≡ q ∧ ∼ p ii) ∼ (p ∨ q) → r i.e. the crop will not be destroyed and there iii) (∼ p ∧ q) ∧ (∼ q ∨ ∼ r) is a flood. 3. Write the converse, inverse and contrapositive of the following statements. EXERCISE 1.8 i) If it snows, then they do not drive the 1. Write negation of each of the following car. statements. ii) If he studies, then he will go to college. i) All the stars are shining if it is night. ii) ∀ n ∈ N, n + 1 > 0 4. With proper justification, state the negation of each of the following. iii) ∃ n ∈ N, (n2 + 2) is odd number i) (p → q) ∨ (p → r) iv) Some continuous functions are differentiable. ii) (p ↔ q) ∨ (∼ q → ∼ r) iii) (p → q) ∧ r 1.4 Algebra of statements: The statement patterns, under the relation of logical equivalence, satisfy various laws. We have already proved a majority of them and the rest are obvious. Now, we list these laws for ready reference. 1. p∨p≡p Idempotent laws p∧p≡p 2. p ∨ (q ∨ r) Associative laws p ∧ (q ∧ r) ≡ (p ∨ q) ∨ r ≡ ( p ∧ q) ∧ r ≡p∨q∨r ≡p∧q∧r 3. (p ∨ q) ≡ q ∨ p Commutative laws p∧q≡q∧p 4. p ∨ (q ∧ r) Distributive laws p ∧ (q ∨ r) ≡ (p ∨ q) ∧ (p ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) 5. p∨c≡p Identity laws p∧c≡c p∨t≡t p∧t≡p 6. p∨∼p≡t Complement laws p∧∼p≡c ∼t≡c ∼c≡t 7. ∼ (∼ p) ≡ p Involution law (law of double negation) 8. ∼ (p ∨ q) DeMorgan’s laws ∼ (p ∧ q) ≡∼p∧∼q ≡∼p∨∼q 9. p→q Contrapositive law ≡∼q→∼p 21 Note: In case of three simple statements p,q,r, ≡ [(p ∧ ∼ p) ∨ (q ∧ ∼ p)] → q we note the following :... by Distributive law i) p ∧ q ∧ r is true if and only if p, q, r are all ≡ [(c ∨ (q ∧ ∼ p)] → q true and p ∧ q ∧ r is false even if any one of p, q, r is false.... by Complement law ii) p ∨ q ∨ r is false if and only if p, q, r are all ≡ (∼ p ∧ q) → q... by Commutative law false, otherwise it is true. ≡ ∼ (∼ p ∧ q) ∨ q... by ∼ ∼ (p → q) ≡ ∼ (p ∧ ∼ q) ≡ ∼ p ∨ q SOLVED EXAMPLES Ex. 1: Without using truth table, show that ≡ [(p ∨ ∼ q) ∨ q... by De Morgan's law i) p ∨ (q ∧ ∼ q) ≡ p ≡ p ∨ (∼ q ∨ q)]... by Associative law ii) ∼ (p ∨ q) ∨ (∼ p ∧ q) ≡ ∼ p ≡p∨t iii) p ∨ (∼ p ∧ q) ≡ p ∨ q ≡t Solution: EXERCISE 1.9 i) p ∨ (q ∧ ∼ q) ≡p∨c... by complement law 1. Without using truth table, show that ≡p... by Identity law i) p ↔ q ≡ (p ∧ q) ∨ (∼ p ∧ ∼ q) ii) ∼ (p ∨ q) ∨ (∼ p ∧ q) ii) p ∧ [(∼ p ∨ q) ∨ ∼ q] ≡ p ≡ (∼ p ∧ ∼ q) ∨ (∼ p ∧ q) iii) ∼ [(p ∧ q) → ∼ q] ≡ p ∧ q... by De Morgans law iv) ∼ r → ∼ (p ∧ q) ≡ [∼ (q → r)] → ∼ p v) (p ∨ q) → r ≡ (p → r) ∧ (q → r) ≡ ∼ p ∧ (∼ q ∨ q)... by Distributive law 2. Using the algebra of statement, prove that ≡∼p∧t i) [p ∧ (q ∨ r)] ∨ [∼ r ∧ ∼ q ∧ p] ≡ p... by Complement law ii) (p ∧ q) ∨ (p ∧ ∼ q) ∨ (∼ p ∧ ∼ q) ≡ ≡∼p... by Identity law p ∨ ∼ q) iii) p ∨ (∼ p ∧ q) iii) (p ∨ q) ∧ (∼ p ∨ ∼ q) ≡ (p ∨ ∼ q) ∧ (∼ p ∨ q) ≡ (p ∨ ∼ p) ∧ (p ∨ q)... by Distributive law 1.5 Venn Diagrams: ≡ t ∧ (p ∨ q)... by Complement law We have already studied Venn Diagrams while studying set theory. Now we try to ≡p∨q... by Identity law investigate the similarity between rules of logical connectives and those of various operations on Ex. 2: Without using truth table, prove that sets. [(p ∨ q) ∧ ∼ p] → q is a tautology. The rules of logic and rules of set theory go Solution: hand in hand. [(p ∨ q) ∧ ∼ p] → q 22 i) Disjunction in logic is equivalent to the iii) iv) union of sets in set theory. ii) Conjunction in logic is equivalent to the intersection of sets in set theory. A = B A∩B≠φ iii) Negation of a statement in logic is equivalent to the complement of a set in set theory. v) iv) Implication of two statements in logic is equivalent to ‘subset’ in set theory. v) Biconditional of two statements in logic is A ∩ B = φ equivalent to “equality of two sets” in set Fig. 1.1 theory. Main object of this discussion is actually to Observe the following four statements give analogy between algebra of statements in i) a) All professors are educated. logic and operations on sets in set theory. b) Equiangular triangles are precisely Let A and B be two nonempty sets equilateral triangles. i) The union of A and B is defined as ii) No policeman is a thief. iii) Some doctors are rich. A∪B = {x / x∈A or x∈B} iv) Some students are not scholars. ii) The intersection of A and B is defined as These statements can be generalized respectively A∩B = {x / x∈A and x∈B} as iii) The difference of A and B (relative a) All x’s are y’s c) Some x’s are y’s complement of B in set A) is defined as b) No x’s are y’s d) Some x’s are not y’s A−B = {x / x∈A, x∉B} a) Diagram for “All x’s are y’s” Note: One of the possible relationships between There are two possibilities two sets A and B holds. i) All x’s are y’s i.e. x ⊂ y i) A⊂B ii) x’s are precisely y’s i.e. x = y ii) B⊂A For example: iii) A = B i) Consider the statement iv) A ⊄ B , B ⊄ A and A ∩ B ≠ φ “All professors are educated” v) A ⊄ B , B ⊄ A and A ∩ B = φ Let p : The set of all professors. E : The set of all educated people. Figure: Let us choose the universal set as i) ii) u : The set of all human beings. A ⊂ B B⊂A P⊂E Fig. 1.2 23  The Venn diagram (fig. 1.2) represents the truth of the statement i.e. P ⊂ E. ii) Consider the statement India will be prosperous if and only if its citizens are hard working. E∩O=φ Let P : The set of all prosperous Indians. Fig. 1.5 H : The set of all hard working Indians. U : The set of all human beings. The Venn diagram (fig. 1.5) represents the truth of the statement i.e. E ∩ O = φ. c) Diagram for “Some X’s are Y’s” i) Consider the statement Fig. 1.3 Some even numbers are multiple of seven. The Venn diagram (fig. 1.3) represents the Let E : The set of all even numbers. truth of the statement i.e. P = H. M : The set of all numbers which are b) Diagram for “No X’s are Y’s” multiple of seven. i) Consider the statement Let us choose the universal set as No naval person is an airforce person. U : The set of all natural numbers. Let N : The set of all naval persons. A : The set of all airforce persons. Let us choose the universal set as U : The set all human beings. E∩M≠φ Fig. 1.6 The Venn diagram represents the truth of the statement i.e. E∩M ≠ φ N∩A=φ Fig. 1.4 ii) Consider the statement Some real numbers are integers. The Venn diagram (fig. 1.4) represents the Let R : The set of all real numbers. truth of the statement i.e. N ∩ A = φ. I : The set of all integers. ii) Consider the statement Let us choose the universal set as No even number is an odd numbers. U : The set of all complex numbers. Let E : The set of all even numbers. O : The set of all odd numbers. Let us choose the universal set as U : The set of all numbers. I⊂R Fig. 1.7 24  The Venn diagram (fig. 1.7) represents the SOLVED EXAMPLES truth of the statement i.e. I⊂R. Ex. 1: Express the truth of each of the following d) Diagram for “Some X’s are not Y’s” statement by Venn diagram. i) Consider the statement i) Equilateral triangles are isosceles. Some squares of integers are not odd ii) Some rectangles are squares. numbers. iii) No co-operative industry is a proprietary Let S : The set of all squares of integers. firm. O : The set of all odd numbers. iv) All rational numbers are real numbers. Let us choose the universal set as v) Many servants are not graduates. U : The set of all integers. vi) Some rational numbers are not integers. vii) Some quadratic equations have equal roots. viii) All natural numbers are real numbers and x is not a natural number. Solution: S−O ≠ φ i) Let us choose the universal set. Fig. 1.8 U : The set of all triangles. Let I : The set of all isosceles triangles. The Venn diagram (fig. 1.8) represents the E : The set of all equilateral triangles. truth of the statement i.e. S − O ≠ φ. ii) Consider the statement Some rectangles are not squares. Let R : The set of all rectangles. S : The set of all squares. E⊂I Let us choose the universal set as Fig. 1.10 U : The set of all quadrilaterals. The Venn diagram (fig. 1.10) represents the truth of the given statement i.e. E ⊂ I. ii) Let us choose the universal set. U : The set of all quadrilaterals. Let R : The set of all rectangles. S : The set of all squares. R−S ≠ φ Fig. 1.9 The Venn diagram (fig. 1.9) represents the truth of the statement i.e. R − S ≠ φ. R∩S≠φ Fig. 1.11 The Venn diagram (fig. 1.11) represents the truth of the given statement i.e. R ∩ S ≠ φ. 25 iii) Let us choose the universal set. vi) Let us choose the universal set. U : The set of all industries. U : The set of all real numbers. Let C : The set of all co-operative industries. Let Q : The set of all rational numbers. P : The set of all proprietary firms. I : The set of all integers. C∩P=φ Q−I≠φ Fig. 1.12 Fig. 1.15 The Venn diagram (fig. 1.12) represents the The Venn diagram (fig. 1.15) represents truth of the given statement i.e. C ∩ P = φ. truth of the given statement i.e. Q − I ≠ φ shaded portion. iv) Let us choose the universal set. U : The set of all complex numbers. vii) Let us choose the universal set. Let A : The set of all rational numbers. U : The set of all equations. B : The set of all real numbers. Let A : The set of all quadratic equations. B : The set of all quadratic equations having equal roots. A⊂B Fig. 1.13 B⊂A The Venn diagram (fig. 1.13) represents Fig. 1.16 truth of the given statement i.e. A ⊂ B. The Venn diagram (fig. 1.16) represents the v) Let us choose the universal set. truth of the given statement i.e. B ⊂ A. U : The set of all human beings. Let G : The set of all servants. viii) Let us choose the universal set. C : The set of all graduate people. U : The set of all complex numbers. Let N : The set of all natural numbers. R : The set of all real numbers. G−C≠φ Fig. 1.14 (a) (b) The Venn diagram (fig. 1.14) represents Fig. 1.17 truth of the given statement i.e. G − C ≠ φ. 26  The Venn diagram (fig. 1.17) represents the By Venn diagrams (fig. 1.19), we observe truth of the given statement. that truth set of statements (i) and (ii) are equal. Hence, statements (i) and (ii) are logically Ex. 2: Draw the Venn diagram for the truth of equivalent. the following statements. i) There are students who are not scholars. EXERCISE 1.10 ii) There are scholars who are students. 1. Represent the truth of each of the following iii) There are persons who are students and statements by Venn diagrams. scholars. i) Some hardworking students are obedient. Solution: ii) No circles are polygons. Let us choose the universal set. iii) All teachers are scholars and scholars U : The set of all human beings. are teachers. Let S : The set of all scholars. iv) If a quadrilateral is a rhombus, then it T : The set of all students. is a parallelogram. i) ii) iii) 2. Draw a Venn diagram for the truth of each of the following statements. i) Some sharebrokers are chartered accountants. ii) No wicket keeper is bowler, in a cricket Fig. 1.18 team. We observe that (by Venn diagram) truth 3. Represent the following statements by Venn set of statements (ii) and (iii) are equal. Hence, diagrams. statements (ii) and (iii) are logically equivalent. i) Some non resident Indians are not rich. ii) No circle is rectangle. Ex. 3: Using the Venn diagram, examine the logical equivalence of the following statements. iii) If n is a prime number and n ≠ 2, then it is odd. i) Some politicians are actors. ii) There are politicians who are actors. Let's Remember iii) There are politicians who are not actors. 1. Statement: Declarative sentence which Solution: is either true or false, but not both Let us choose the universal set. symultaneously. U : The set of all human beings. ∗ Imperative, exclamatory, interrogative Let P : The set of all politicians. and open sentences are not statements. A : The set of all actors. ∗ The symbol ‘∀’ stands for “all values of”. It is universal quantifier. i) ii) iii) ∗ The symbol ‘∃’ stands for “there exists”. It is known as existential quantifier. ∗ An open sentence with a quantifier Fig. 1.19 becomes a quantified statement. 27 2. Logical connectives: Sr. Name of the No. Compound Connective Symbolic form Negation statement 1. Conjunction and p∧q ∼p∨∼q 2. Disjunction or p∨q ∼p∧∼q 3. Negation not ∼p ∼ (∼ p) =p 4. Conditional or If... then p→q p∧∼q implication or p⇒q 5. Biconditional or If and only p↔q (p ∧ ∼ q) ∨ double implication if... iff... (or p ⇔ q) (~p ∧ q) 3. Tautology: A statement pattern which is always true (T) is called a tautology (t). Contradiction: A statement pattern which is always false (F) is called a contradiction (c). Contingency \: A statement pattern which is neither a tautology nor contradiction is called a contingency. 4. Algebra of statements : (Some standard equivalent statements) 1. p∨p≡p Idempotent laws p˄p≡p 2. p ∨ (q ∨ r) Associative laws p ∧ (q ∧ r) ≡ (p ∨ q) ∨ r ≡ (p ∧ q) ∧ r ≡p∨q∨r ≡p∧q∧r 3. p∨q≡q∨p Commutative laws p∧q≡q∧p 4. p ∨ (q ∧ r) Distributive laws p ∧ (q ∨ r) ≡ (p ∨ q) ∧ (p ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) 5. p∨c≡p Identity laws p∧c≡c p∨t≡t p∧t≡p 6. p∨∼p≡t Complement laws p∧∼p≡c ∼t≡c ∼c≡t 7. ∼ (∼ p) ≡ p Involution law (law of double negation) 8. ∼ (p ∨ q) DeMorgan’s laws ∼ (p ∧ q) ≡∼p∧∼q ≡∼p∨∼q 9. p→q Contrapositive law ≡∼q→∼p 28 i) p→q≡∼q→∼p≡∼p∨q 2. Which of the following is an open statement? ii) p ↔ q ≡ (p → q) ∧ (q → p) a) x is a natural number. ≡ (∼ p ∨ q) ∧ (∼ q ∨ p) b) Give me a glass of water. 5. Venn-diagrams : c) Wish you best of luck. i) All x’s are y’s d) Good morning to all. 3. Let p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r). Then, this law is known as.