35113923_BCA114

46 Mathematics Examples: ~ (p  q) 1. If p : x = 3, then ~ p : x ≠ 3. F 2. If p : sun is shining, then ~ p : sun is not shining. T The truth values of ~ p relative to p are: T T p ~p TF ~p~q FT F F Double negative is positive and can be justified in the following ways: F T p ~ p ~ (~ p) TFT FTF Example 1: With the help of truth tables, prove that ~ p  ~ q = ~ (p  q). p q ~p ~q ~p ~q pq TTF F FT TFFTTF F TT F T F FFTTTF Example 2: With the help of truth table, prove that ~ (p  q) = ~ (p  ~ q). p q pq ~ (p  q) ~p ~q TTTF F F T FTF FT F TT F T F FFFTTT CU IDOL SELF LEARNING MATERIAL (SLM)

Modern Algebra 1 47 Example 3: With the help of truth table, prove that p  q = ~ (~ p  ~ q). p q pq ~p ~ q ~ p  ~ q ~ (~ p  ~ q) T T T F FF T T F T F TF T F T T T FF T F F F T TT F 4.5 Summary Logic has variety of applications in each course of day-to-day life and many other engineering applications like designing of electronic circuits, computer and other robotic programming, etc. A proposition is a declarative statement which is either true or false but not both. Composed of subproposition and various connectives discussed subsequently. Such composite propositions are called compound proposition. There are some basic logical operators are given as (a) Conjunction: When two or more statements are joined by connective, denoted by the symbol, , the compound statement formed so is called as conjunction. (b) Disjunction: When two or more statements are joined by the connective or denoted by symbol, , the compound statement formed so is called disjunction. (c) Negation: If p is statement, then negation (or not) of p, denoted by ~ p is defined to form a statement that is true when p is false and false when p is true. The negation of statement p is read as ‘not p'. 4.6 Key Words/Abbreviations  Proposition is a declarative statement which is either true or false but not both.  The relationship between the truth values of proposition can be tabulated. CU IDOL SELF LEARNING MATERIAL (SLM)

48 Mathematics 4.7 Learning Activity 1. Construct a truth table for the following: (a) q  (p → q) → p (b) (p → q) ↔ q → p (c) p → (q → (q → p)) 4.8 Unit End Questions (MCQ and Descriptive) A. Descriptive Type Questions Exercise 1. With the help of truth table, prove that: (i) p  ~q = (p  q)  ~ (p  r) (ii) p  q = ~ (~ p  ~ q) (iii) ~ (p  q) = ~ p  ~ q 2. If p and q are two statements, then show that p  q is equivalent to (p  ~ q)  (~ p  q). Ans: (p  ~ q)  (~ p  q) F T T F B. Multiple Choice/Objective Type Questions 1. The proposition is p  (~ p  q) is . (a) A tautology (b) A contradiction (c) (a) and (b) (d) None CU IDOL SELF LEARNING MATERIAL (SLM)

Modern Algebra 1 49 2. The conjunctive normal form of p  (p → q) is . (a) p  q (b) q  ~ p (c) ~ q  ~ p (d) None 3. (p → q)  (r → q) is equivalent to . (a) (p  r) → q (b) p  (r → p) (c) p  (r → q) (d) None 4. (p  p)  (p → (q  q)) is equivalent to . (a) p → q (b) p  q (c) p  q (d) q → p 5. [(p → q)  (q → r)] → (p → r) is a . (a) Tautology (b) Contradiction (c) Disjoint (d) None Answers: 1. (c), 2. (a), 3. (a), 4. (c), 5. (a) 4.9 References References of this unit have been given at the end of the book. CU IDOL SELF LEARNING MATERIAL (SLM)

50 Mathematics UNIT 5 MODERN ALGEBRA 2 Structure: 5.0 Learning Objectives 5.1 Introduction 5.2 Connectives 5.2.1 NAND 5.2.2 NOR or Joint Denial 5.2.3 XOR 5.3 Tautologies 5.4 Contradiction 5.5 Summary 5.6 Key Words/Abbreviations 5.7 Learning Activity 5.8 Unit End Questions (MCQ and Descriptive) 5.9 References 5.0 Learning Objectives After studying this unit, you will be able to:  Explain the tautologies.  Discuss the contradictions.  Analyse the use of AND-OR in truth table CU IDOL SELF LEARNING MATERIAL (SLM)

Modern Algebra 2 51 5.1 Introduction In this chapter, we will come across tautologies and contradiction. The final column of truth table of given compound proposition contains both T and F. There are some compositions whose truth values are always T or F. 5.2 Connectives 5.2.1 NAND It is negation after ANDing of two statements. For example, if p and q are two statements, then NANDing of p and q is denoted by p ↑ q is a false statement when both p and q are true, otherwise true for other cases. p q p↑q TTF TFT FTT FFT 5.2.2 NOR or Joint Denial It is the negation after ORing of two statements. For example, if p and q are two statements, then NORing of p and q, denoted by p ↓ q is a true statement when both p and q are false. p q p↓q TTF TFF FTF FFT 5.2.3 XOR If p and q are two statements, then XORing of p and q denoted by p  q is a true statement when either p or q is true but not both and vice versa. The truth values of p  q are given in truth table. CU IDOL SELF LEARNING MATERIAL (SLM)

52 Mathematics p q pq TTF TFT FTT FFF Example: Make truth table for: (a) (p ↓ q)  (p ↓ r) p q r p↓q p ↓ r (p ↓ q)  (p ↓ r) T T T F FF T T F F FF T F T F FF T F F F FF F T T F FF F T F F TF F F T T FF F F T T TT (b) p ↑ q ↑ r pq r p↑r p↑q ↑r TT TFT TT FFT TF TTF TF FTT FT TTF FT FTT FF TTF FF FTT CU IDOL SELF LEARNING MATERIAL (SLM)

Modern Algebra 2 53 (c) p  q  r p q r pq pqr TTTFT TTFFF TFTTF TFFTT FTTTF FTFTT FFTFT FFFFF 5.3 Tautologies There are certain compound statements that always are true regardless of truth or falsity of compound statement. Compound statement which have this characteristic are called as tautology. In other words, tautologies is a compound statement if it is true for all truth value assignments for its compound statements. Truth tables only contain T for tautology. Importance Tautology helps conclude some statements from some given statements. For example, if the statement p  q is a tautology, then it is easy to conclude the truth of q from the truth of p. Thus, with the help of tautology, we move from some given statement to some concluding statement in a step-by-step manner. Example 1: Show that statement (p  q)  q is a tautology. Solution: p q pq pqq TTTT TFFT FTFT FFFT All entries have truth value T, therefore (p  q)  q is tautology. CU IDOL SELF LEARNING MATERIAL (SLM)

54 Mathematics Example 2: Show that statement p  ~ p is tautology. Solution: p ~p p~p TFT FTT i.e., either p is true or p is false, there is no middle possibility. 5.4 Contradiction If a compound statement is false for all true values assignment for its component statement, then it is called contradiction, i.e., a compound statement is said to be contradicting its truth value if it is false (F) for all its entries in the truth table. Example 1: Show that statement p  ~ q is a tautology or contradiction. p ~p p~p TF F FT F All values are false, hence contradiction. Example 2: Establish ~ (p  q)  (~ p  ~ q) as tautology. p q p  q ~ (p  q) ~ p ~ q ~ p  ~ q ~ (p  q)  (~ p  ~ q) T TTT F FF F T T TFF T FT T T FTF T TF T FFF T TT T Example 3: Show that statement (p  q)  (p  q) is not a tautology. p q pq pq (p  q)  (p  q) T TTTT F F TFTF T FTTF FFFF All entries not T. Therefore, it is not tautology. CU IDOL SELF LEARNING MATERIAL (SLM)

Modern Algebra 2 55 5.5 Summary The final column of truth table of given compound proposition contains both T and F. There are some connectives given as NAND: It is negation after ANDing of two statements. NOR or Joint Denial: It is the negation after ORing of two statements. XOR: If p and q are two statements, then XORing of p and q denoted by p  q is a true statement when either p or q is true but not both and vice versa. The other point discussed is of tautologies. The importance of tautology is to help us to conclude some statements from some given statements. And a contradiction is also discussed as If a compound statement is false for all true values assignment for its component statement, then it is called contradiction, i.e., a compound statement is said to be contradicting its truth value if it is false (F) for all its entries in the truth table. 5.6 Key Words/Abbreviations  Tautology helps conclude some statement from some given statement. For example, if the statement p  q is a tautology, then it is easy to conclude the truth q from truth of p.  If a statement is contradiction, then its negation will be a tautology. 5.7 Learning Activity 1. Show that the statement (p  q)  (p  q) is tautology. 2. Show that the statement p  ~p is a tautology or contradiction. CU IDOL SELF LEARNING MATERIAL (SLM)

56 Mathematics 5.8 Unit End Questions (MCQ and Descriptive) A. Descriptive Type Questions Exercise 1. If p and q are two statements, then show that the statements (p ↑ q)  (p ↑ q) is equivalent to (p  q)  (p↓ q). Ans: (p  q)  ( p ↓ q) F F F F 2. If p and q are 2 statements, then show that p  q is equivalent to (p  ~ q)  (~ p  q). Ans: (p  ~ q)  (~ p  q) F T T F 3. If p and q are two statements, show that (p  q)  (p ↓ q) is equivalent to p ↑ q. Ans: (p  q)  (p ↓ q) F T T T 4. By means of truth table, show that statement p  ~ (p  q) is a tautology. 5. Show that (p  q) ~ ~ (p  q) is a fallacy or contradiction. 6. Establish ~ (p  q)  (~ p  ~ q) as a tautology. B. Multiple Choice/Objective Type Questions 1. Which of the following propositions is tautology? (a) (p  q) → p (b) p  (q → p) (c) p  (p → q) (d) None CU IDOL SELF LEARNING MATERIAL (SLM)

Modern Algebra 2 57 2. Let P, Q and R be three atomic propositional assertions. Let x denote (P  Q) → R and y denote (P → R)  (Q → R). Which one of the following is a tautology? (a) x  y (b) x → y (c) y → x (d) y → x 3. (p → q)  (r → q) is equivalent to . (a) (p  r) → q (b) p  (r → q) (c) p  (r → q) (d) p → (q → r) 4. Let p and q be propositions. Using only the truth table, decide whether p  q does not imply p → q is . (a) True (b) False (c) Otherwise (d) None 5. Is this statement p  ~ (p  q) is tautology? (a) True (b) False (c) (a) or (b) (d) None Answers: 1. (c), 2. (b), 3. (a), 4. (b), 5. (a) 5.9 References References of this unit have been given at the end of the book. CU IDOL SELF LEARNING MATERIAL (SLM)

58 Mathematics UNIT 6 MODERN ALGEBRA 3 Structure: 6.0 Learning Objectives 6.1 Introduction 6.2 Algebra of Propositions 6.2.1 Idempotent Law 6.2.2 Associate Law 6.2.3 Commutative Law 6.2.4 Law of Disjunctive 6.2.5 Law of Conjunctive 2.2.6 Law of Negation 6.2.7 Law of Contrapositive 6.2.8 De Morgan's Laws 6.2.9 Distributive Laws 6.2.10 Identity Laws 6.2.11 Absorption Laws 6.2.12 Law of Complement 6.3 Summary 6.4 Key Words/Abbreviations 6.5 Learning Activity CU IDOL SELF LEARNING MATERIAL (SLM)

Modern Algebra 3 59 6.6 Unit End Questions (MCQ and Descriptive) 6.7 References 6.0 Learning Objectives After studying this unit, you will be able to:  Explain the Commutative Law  Discuss about the Associative Law  Analyse about the DeMorgan Law  Describe the Law of Complement 6.1 Introduction If two statements p and q have the same truth values in every possible case, then such statements are said to be logically equivalent or simply equivalent. Logical equivalence of statement p and q is denoted by p  q. 6.2 Algebra of Propositions The mathematical structure (statements,  ,  , ~) has many properties that are used for regulating manipulations on statements which are used in finding out new relations and equivalence among some of them. The propositions have the following properties: 6.2.1 Idempotent Law Idempotent Law according to this law, the given statement does not change by conjunction and disjunction with another statement such as: (a) p ^p Ξp (b) p Vp Ξp For example, in ordinary algebra, a + 0 = a where 0 is additive identity, similarly a.1 = a, where 1 is multiplicative identity. CU IDOL SELF LEARNING MATERIAL (SLM)

60 Mathematics 6.2.2 Associate Law According to this law, a compound statement consists of three statements remaining unchanged with the change in position of three statements with same connectives. (a) p  (q  r)  (p  q)  r (b) p  (q  r)  (p  q)  r 6.2.3 Commutative Law According to this law, order is irrelevant. (a) p  q  q  p (b) p  q = q  p 6.2.4 Law of Disjunctive (a) p  (p  q) (b) q  (p  q) (c) (p  q)  ~ p  q (d) (p  q)  ~ q  p 6.2.5 Law of Conjunctive (a) (p  q)  p (b) p  q  q 6.2.6 Law of Negation (a) ~ (~ p)  p (b) ~ (p  q)  ~ p  ~ q (c) ~ (p  q)  ~ p  ~ q CU IDOL SELF LEARNING MATERIAL (SLM)

Modern Algebra 3 61 6.2.7 Law of Contrapositive In logic and mathematics, contraposition refers to the inference of going from a conditional statement into its logically equivalent contrapositive and an associated proof method known as proof by contraposition. The contrapositive of the statement has its antecedent and consequent inverted and flipped: the contrapositive of P  Q is thus ~Q  ~P. For instance, the proposition “All cats are mammals” can be restated as the conditional “If something is a cat, then it is a mammal”. The law of contraposition says that a statement is true if, and only if, its contrapositive (in this case “If something is not a mammal, then it is not a cat”) is true Inversion (the inverse), ~P  ~Q “If something is not a cat, then it is not a mammal.” Unlike the contrapositive, the inverse's truth value is not at all dependent on whether or not the original proposition was true, as evidenced here. The inverse here is clearly not true. Conversion (the converse), Q  P “If something is a mammal, then it is a cat.” The converse is actually the contrapositive of the inverse, and so always has the same truth value as the inverse (which as stated earlier does not always share the same truth value as that of the original proposition) Negation, ~ (P  Q) “It is not the case that if something is cat, then it is a mammal”, or equivalently, “There exists a cat that is not a mammal.” If the negation is true, then the original proposition (and by extension the contrapositive) is false. In this example, the negation is false. 6.2.8 DeMorgan’s Laws According to this law, a statement remains unchanged if we change and () by or () and or () by and (), provided, universal of constituent statement exists. (a) ~ (p  q)  (~ p)  (~ q) (b) ~ (p  q)  (~ p)  (~ q) CU IDOL SELF LEARNING MATERIAL (SLM)

62 Mathematics 6.2.9 Distributive Laws According to this law, if connectives or distributes over and from the left, then this is left distributive. Similarly, if connectives or distributes over and form the right, then this is left distributive. (a) p  (q  r)  (p  q)  (p  r) p  (q  r)  (p  q)  (p  r) (b) (p  q)  r  (p  r)  (q  r) (p  q)  r  (p  r)  (q  r) 6.2.10 Identity Laws In ordinary algebra, 1 and 0 are multiplicative and additive identities respectively. Similarly, in Boolean algebra, identity elements are denoted by T (tautology) and F (fallacy) such that: (a) p  T  T (b) p  T  P (c) p  T  P (d) p  F  F 6.2.11 Absorption Laws (a) p  (p  q)  p (b) p  (p  q)  P 6.2.12 Law of Complement (a) p  ~ p  T (b) p  ~ p  F (c) ~ (~p)  P (d) ~ T  F and ~ F  T CU IDOL SELF LEARNING MATERIAL (SLM)

Modern Algebra 3 63 The implication operation for statements have the following properties: 1. (p  q)  ((~ p)  q) 2. (p  q)  ((~ q)  ~ p) 3. (p  q)  ((p  q)  (q  p)) 4. ~ (p  q)  (p  ~ q) 5. ~ (p  q)  ((p  ~ q)  (q  ~ p)) Example: Show that p  (q  r)  (p  q)  (p  r). pq r qr p  (q  r) (p  q) pr (p  q)  (p  r) T T T TTT T T T T T T T T TTF F T T T T T T T TFT F T T F F F T F TFF F T F F F FTT T T FTF F F FFT F F FFF F F Example 2: Using truth table, prove that (a) p  (q  r)  (p  q)  r pqr qr p  (q  r) pq (p  q)  r TTT T T T T TFT T T T T F TT T T T T FFT T T F T TTF T T T T TFF F T T T CU IDOL SELF LEARNING MATERIAL (SLM)

64 Mathematics FTF T T TT FFF F F FF 6.3 Summary Logical equivalence of statement p and q is denoted by p  q. We have discussed about the algebra of propositions with reference to the following points (a) Indempotent Law (b) Associate Law (c) Commutative Law (d) Law of disjunctive (e) Law of Conjuctive (f) Law of Negation (g) Law of Contrapositive (h) DeMorgan’s Laws (i) Distributive Laws (j) Identity Laws (k) Absorption Laws (l) Law of complement 6.4 Key Words/Abbreviations  The following statements are equivalent: 1. It is not true that, for all a  A, P(a) is true. 2. There exists an a  A such that P(a) is false.  DeMorgan’s Law:- ~ (p  q)  (~ p)  (~ q)  Absorption Law: p  (p  q)  p  Law of Complement: p  ~ p  T  Identity law: p  T  T CU IDOL SELF LEARNING MATERIAL (SLM)

Modern Algebra 3 65 6.5 Learning Activity 1. Show that: (a) (p  q)  ((~p)  q) (b) (p  q)  ((~q)  ~p) (c) ~ (p  q)  (p  ~q) 6.6 Unit End Questions (MCQ and Descriptive) A. Descriptive Type Questions Exercise 1. Using truth table, prove that p  (q  r)  (p  q)  r. 2. If p, q and r are any three statements, using truth table, prove that p  (q  r)  (p  q)  (p  r). 3. If p, q and r are three statements, using truth table, prove that p  (q  r)  (p  q)  (p  r). 4. Using truth table, prove that (p  q)  r  (p  r)  (q  r). 5. Using truth table, prove the following: (i) p  (p  r)  (p  q) (ii) (p  q)  (p  r)  (p  r) (iii) ~ (p  q)  ~ p  ~q (iv) ~ p  ~q  ~ (p  q) (v) p  (q  r)  (p  q)  (p  r) CU IDOL SELF LEARNING MATERIAL (SLM)

66 Mathematics 6. By means of truth table, prove that: (i) (p  q)  r  (p  r)  (q  r) (ii) (p  q)  r  (p  r)  (q  r) B. Multiple Choice/Objective Type Questions 1. Law of negation is . (a) ~ (~ p)  p (b) (p  q) (c) (p  q) (d) None 2. Identity law is . (a) p  T  T (b) p  ~ p  F (c) p  ~ q  T (d) None 3. Commutative law is . (a) p  q  q  p (b) ~ (~ p)  P (c) p  T  T (d) None 4. Consider the statement, “It is not the case that roses are red and violets are blue”. This statement can be written as . (a) ~ (p  q) (b) ~ p  ~q (c) (p  q) (d) Both (a) and (b) 5. “If p then q”, such statements are called . (a) Negation (b) Conditional (c) Biconditional (d) None Answers: 1. (a), 2. (a), 3. (a), 4. (d), 5. (b) 6.7 References References of this unit have been given at the end of the book. CU IDOL SELF LEARNING MATERIAL (SLM)

Modern Algebra 4 67 UNIT 7 MODERN ALGEBRA 4 Structure: 7.0 Learning Objectives 7.1 Introduction 7.2 Mathematical Induction Principle 7.3 DeMoivre's Theorem 7.4 The Second Principle of Mathematical Induction 7.5 Quantifiers 7.5.1 Universal Quantifier 7.5.2 Existential Quantifier 7.6 Summary 7.7 Key Words/Abbreviations 7.8 Learning Activity 7.9 Unit End Questions (MCQ and Descriptive) 7.10 References 7.0 Learning Objectives After studying this unit, you will be able to learn:  Mathematical induction principle  Quantifier with Universal Quantifier CU IDOL SELF LEARNING MATERIAL (SLM)

68 Mathematics 7.1 Introduction One of the most important techniques to prove many mathematical statements or formulae which cannot be easily derived by direct methods are sometimes derived by using the principle of mathematical induction. In this principle, the word induction is associated with the inductive reasoning by which a conclusion is drawn from a large number of special case. Actually, mathematical induction is deductive by nature. It is employed in proving the validity of a statement involving all positive integer values of n. 7.2 Mathematical Induction Principle Let Pn be a statement involving the natural numbers. 1. If P1 is true and 2. Truth of Pk  Truth of Pk+1 for each position integer k, then Pn is true for all natural numbers. Theorem: To show, by mathematical induction, the cardinality of (X) = 2n, if X has n elements. Proof: Suppose that n = 0, then X = . Accordingly, (X) = 1. Also, 2° = 1. Thus, the cardinality of (X) = 2n in this case. Suppose that the cardinality of (x) = 2k in X has k elements. We shall know that, the result is true for n = k + 1. Suppose X has (k + 1) elements. Take y  X.  X – {y} has k elements.  The cardinality of (X – {y}) is 2k. Now, there is a bijection between the set A in X – {y} and the sets A  {y} in X. Hence, the cardinality of sets containing y = cardinality of the sets not containing y. Therefore, the cardinality of X = the cardinality of set not containing y + the cardinality of sets not containing y.  The cardinality of X = 2 (the cardinality of X – {y}) = 2·2k = 2k+1 CU IDOL SELF LEARNING MATERIAL (SLM)

Modern Algebra 4 69 Hence, by mathematical induction, the cardinality of (x) = 2n, if X has n elements. 7.3 DeMoivre’s Theorem Theorem: For all positive integers, cos   isin n  cos   isin  . Proof: For n = 1, we have (cos   isin )1  cos(1 )  isin(1) and hence the result. Assume the result for n = k, we get (cos   isin ) k  cos k isin k  Now, (cos isin )k1  (cos isin )k (cos isin )1  (cos k  isin k) (cos   isin )  cos k cos   isin k cos   i cos ksin   i2 sin ksin    cos k cos   sin ksin   i(sin k cos   cos ksin )  cos(k  )  isin(k  )  cos(k  1)  isin(k  1)  Thus, the result is for n = k + 1. Hence, the result holds for all positive integers n ≥ 1. Theorem: For every positive integer n, (x  a)n  xn n C1xn1an C2 xn2a 2 ⋯ an . Proof: The proof by induction on n is Put n = 1. Then (x  a)1  x1  a1. Hence, the result is true in this case. Assume that (x  a)k  xk k C1xk1ak C2xk2a 2 ⋯  ak Now, (x  a)k1  (x  a)k (x  a) CU IDOL SELF LEARNING MATERIAL (SLM)

70 Mathematics  (x  a)(xk k C1xk1a ⋯  ak ) k x k 1r a r  a k 1   xk1  k C  k C  r r1 r1 But k Cr k Cr1  k1Cr k Hence, (x  a)k1  xk1  k1Cr xk1rar  ak1 r1  xk1  (k1C1 )xka ⋯ ak1 Thus, theorem is true for n = k. Therefore, it is valid for all positive integer n. 7.4 The Second Principle of Mathematical Induction Suppose 1. P(1) is true, and 2. If P(1), P(2), ..., P(k) are true, then P(k + 1) is also true. then P(n) is true for all positive integers. Example 1: Prove by mathematical induction that n 1  n .  (i  1)i n 1 i1 Solution: For n = 1, we have 1  n  1  1 1 (2) n  1 1 1 2 Hence, the result holds true for n = 1. Now, assume result is true for n = k. k 1 k i1 i(i  1) k  1 For n = k + 1, we have CU IDOL SELF LEARNING MATERIAL (SLM)

Modern Algebra 4 71 k1 1 k 1 1  i1 i(i  1) i1 i(i  1) (k  1)  (k  2)  k  1 k  1 (k  1)  (k  2)  k(k  2)  1 (k  1)  (k  2)  (k  1)2 (k  1)  (k  2)  k 1 k2 Example 2: Prove by mathematical induction 1  2  3 ⋯ n  n(n  1) , n = positive integer. 2 Solution: For n = 1, we have 1  1(1 1)  1  1 2 Hence, proposition is true in this case. Assume that it is true for some n = k. We have 1  2  3 ⋯ k  k(k  1) 2 For n = k + 1, we have, 1  2 ⋯ k  (k  1)  k(k  1)  k  1 2  k2  k  2k  2 2 CU IDOL SELF LEARNING MATERIAL (SLM)

72 Mathematics  k 2  3k  2 2  (k  1)(k  2) 2  (k  1)[(k  1)  1] 2 This implies it is valid for n = k + 1. Thus, it valid for all positive integers n. Example 3: Show that 12  22  32 ⋯ n2  n(n  1)(2n  1) . 6 Solution: For n = 1, we have 12  1(1 1)(2  1)  1  6  1 66 Hence, result is true for n = 1. Assume that result is true for n = k. But then 12  22  32 ⋯  k2  k(k  1)(2k  1) 6 Let n = k + 1 12  22  32 ⋯  k2  (k  1)2  k(k  1)(2k  1)  (k  1)2 6  (k  1)[k(2k  1)  6(k  1)] 6  (k  1)[2k 2  7k  6] 6  (k  1)(k  2)(2k  3) 6  (k  1)[(k  1)  1][(2(k  1)  1] 6 CU IDOL SELF LEARNING MATERIAL (SLM)

Modern Algebra 4 73 The result is true for n = k + 1. Therefore, it is valid for all n. Hence, 12  22  32 ⋯  n2  n(n  1)(2n  1) 6 Example 4: Show that 2n > n. Solution: Let n = 1. Then 21 > 1. Thus, it holds true for n = 1. Assume the result is true for n = k. But then 2k > k Let n = k + 1 2k+1 >k +1  2k+1 = 2k · 2 > k + 1 =k+k >k+1 Hence, the result holds good, if n = k + 1. Therefore, its true for all positive integers by mathematical induction. 7.5 Quantifiers 7.5.1 Universal Quantifier Some statements assert that a property is true for all values of a variable in a particular domain, known as universe of discourse. Definition: “A proposition P(x) is true for all the values of x in a universe of discourse”, is the universal quantification of P(x). It is denoted by x P(x) . The following phrases also represent Universal Quantification: For all For every For each CU IDOL SELF LEARNING MATERIAL (SLM)

74 Mathematics Example 1: Let W(x) be the proposition “the birds having a wing”. Since all birds have wings, the proposition is “for all birds”. Hence, x (W (x)) is true. Example 2: Let R(x) represent the statement “x > x – 1”. If the universal of discourse is the set of all real numbers, then R(x) is true for all real numbers, i.e., x R(x) is true. 7.5.2 Existential Quantifier Definition: The proposition, “there exists an element x in the universe of discourse such that P(x) is true” is known as existential quantifiers of P(x). The symbol x represents the existential quantifier. It represents each of the following phrases: For some x, Some x such that, There is at least one x such that, Example: Let P(x) be “x2 < 10” and the universe of discourse be set of integers. There exists integers –3, –2, –1, 0, 1, 2, and 3 for which P(x) is true, i.e., P(–3), P(–2), P(–1), P(0), P(1), P(2) and P(3) are true. Therefore, x P(x) is true. Example I: Consider the propositional functional statement (x)(y) p(x, y, z). In this, the variable x is bound by existential quantifier and y is bounded by universal quantifier, but variable z is free because it is not bounded by any quantifier and no value is assigned to it. Example II: Let the universe consist of set of all integers and let P(x): x is prime Q(x): x is positive E(x): x is even D(x): x is divisible by 10 S(x): x is a perfect square Express each of the following statement in symbolic form. CU IDOL SELF LEARNING MATERIAL (SLM)

Modern Algebra 4 75 (a) x is even or x is not a perfect square (b) If x is perfect square, then x is even (c) If x is divisible by 10, then x is even (d) x is prime only if x is positive (e) There is no number divisible by 10 (f) No prime number which is even (g) If x is not positive, then it is not perfect square (h) x is not positive or x is divisible by 10 (i) Every prime number is positive Solution: (b) S(x) → E(x) (a) E(x)  ~S(x) (d) Q(x) → P(x) (c) D(x) → E(x) (f) E(x) → ~ P(x) (e) x ~ D(x) (g) ~ Q(x) → ~ S(x) (h) ~ Q(x)  D(x) (i) P(x) → Q(x) Example III: Let the universe of discourse consist of integers 1, 2, 4, 8, 16 and 32. Let P(x): x is an even integer Q(x): x is divisible by 8 R(x, y): x is divisible by y Find truth value of following: P(8), P(16), Q(4), Q(32), R(1, 16), R(16, 1), P(8)  R(8, 4), R(1, 8) → Q(4). Solution: P(8), P(16): 8 and 16 are even integers. Therefore, true. Q(4): 4 is not divisible by 8. Hence, Q(4) is false. Q(32): 32 is true, since 32 is divisible by 8. CU IDOL SELF LEARNING MATERIAL (SLM)

76 Mathematics R(1, 16), R(16, 1): 1 is not divisible by 16 but 16 is divisible by 1. So, R(1, 16) is false and R(16, 1) is true. P(8)  R(8, 4): As both P(8) and R(8, 4) are true, P(8)  R(8, 4) is true. R(1, 8) → Q(4): We know that F → F is true. So, R(1, 8) → Q(4) is true as 1 is not divisible by 8 and Q(4) is false. 7.6 Summary Mathematical induction is a mathematical proof technique. Mathematical Induction is a special way of proving things. It has only 2 steps: Step 1. Show it is true for the first one Step 2. Show that if any one is true then the next one is true Then all are true That is how Mathematical Induction works. In the world of numbers we say: Step 1. Show it is true for first case, usually n=1 Step 2. Show that if n=k is true then n=k+1 is also true The Theorem: To show, by mathematical induction, the cardinality of (X) = 2n, if X has n elements is given in the unit. And De Moivre’s theorem gives a formula for computing powers of complex numbers with theorem for all positive integers, cos  isinn  cos  isin . There are types of Quantifiers as given below: (a) Universal Quantifier (b) Existential Quantifier CU IDOL SELF LEARNING MATERIAL (SLM)

Modern Algebra 4 77 7.7 Key Words/Abbreviations  Let P(n) be a statement or proposition defined by set of positive integers I such that it is either true or false for all n  I. For given statement P(n), if we can prove that: (a) P(n) is true for n = n0 and (b) P(n) is true for n = k + 1 assuming that it is true for n = k (k ≥ n0). 7.8 Learning Activity 1. Prove the following using Mathematical Induction: (a) 4 + 8 + 12 + ... + 4n = 2n(n + 1) (b) 72n + 16n is divisible by 64 (c) n(n2 – 1) is divisible by 24; n is positive odd integer. 7.9 Unit End Questions (MCQ and Descriptive) A. Descriptive Type Questions Exercise 1. Prove by mathematical induction, n2 > 2n + 1 for n ≥ 3. 2. Show that 2n < n! for n ≥ 4. 3. Prove by mathematical induction: (1 + x)n > 1 + nx for all x > 0 and n > 1. 4. Prove by mathematical induction that the Fibonacci number f3n is divisible by 2. CU IDOL SELF LEARNING MATERIAL (SLM)

78 Mathematics 5. Prove by mathematical induction, n3 – n is divisible by 3, where n is positive integer. 6. Show that 3n – 1 is divisible by mathematical induction. 7. Show that 13  23 ⋯ 43  n 2 (n  1)2 by mathematical induction. 4 8. Let the universe constant of integers 1, 2, 3, 4, 6, 8, 12, 16, 24, 32. Let E(x): x is an even integer D(x): x is divisible by 6 Q(x, y): x is divisible by x Find the truth value of E(6), E(3), D(3), D(24), Q(12, 24), Q(32, 8). 9. Translate these specification into English, where L(p) is “the person p who cannot do the work” B(p) is “the person who is busy on other work” N(ω) is the “work not done” Q(ω) is “the work to be done after the present work” (a) p(L(p)  B(p))  N() (b) p B(p)  Q() (c) N()  (p B(p)  Q()) 10. Use quantifiers and predicates with more than one variables to express these statements: (a) Every computer science student needs a course in discrete mathematics. (b) Every computer science student knows one programming language completely. (c) There are some computer science students who do not have personal computers. CU IDOL SELF LEARNING MATERIAL (SLM)

Modern Algebra 4 79 B. Multiple Choice/Objective Type Questions . 1. Let a and b be any integers. Then a  0 and a  0 iff (a) a > 0 (b) a = 0 (c) a < 0 (d) None 2. P be the proposition defined on integer n  1 such that . (a) P(1) is true (b) P(1) is false (c) P(1) = 1 (d) None 3. What is the sum of first n positive integers? (a) n(n  1) (b) n(n 1) 2 2 n2 (n  1) (d) None (c) 2 4. What is the sum of square of first n positive integers? n2 (n  1) (b) n(n  1)(2n  1) (a) 6 2 (d) None n2 (n 1)(n  1) (c) 2 5. What is the sum of cubes of first n positive integers? (a) n(n  1)(2n  1) (b) n(n  1) 6 2 n 2 (n  1)2 (d) None (c) 4 Answers: 1. (b), 2. (a), 3. (a), 4. (b), 5. (c) 7.10 References References of this unit have been given at the end of the book. CU IDOL SELF LEARNING MATERIAL (SLM)

80 Mathematics UNIT 8 MATRICES 1 Structure: 8.0 Learning Objectives 8.1 Introduction 8.2 Definition 8.3 Types of Matrix 8.4 Summary 8.5 Key Words/Abbreviations 8.6 Learning Activity 8.7 Unit End Questions (MCQ and Descriptive) 8.8 References 8.0 Learning Objectives After studying this unit, you will be able to:  Analyse the various types of matrix.  Discuss the transpose of a matrix. 8.1 Introduction The father of matrix, Arthur Cayley, an English Mathematician and lawyer first published an abstract definition of matrix in his memoir on the theory of matrices in 1858, thus establishing it as a branch of mathematics. Matrices were actually discovered by John James Sylvester, a 19th century mathematician but it was Arthur who developed aspect of matrices. CU IDOL SELF LEARNING MATERIAL (SLM)

Matrices 1 81 8.2 Definition A set of mn numbers (real or complex numbers) arranged in the form of a rectangular array having m rows and n columns is called on m × n matrix. Different notations used for matrix are [ ], ( ) and ||. We are using notation [ ]. Examples: 1. 1 2 3 1 3 No. of rows  1 No. of columns  3 2 2 No. of rows  2 2. 4  42 2 No. of columns  2  3. 12 No. of rows  3 No. of columns  1 3 31 8.3 Types of Matrix 1. Row Matrix: A matrix containing one row and n number of columns is called Row Matrix. Examples: (a) 1 2 3 No. of rows  1 No. of columns  3  No. of rows  1 (b) 5 7 No. of columns  2 2. Column Matrix: A matrix containing m number of rows and one column is called Column Matrix. CU IDOL SELF LEARNING MATERIAL (SLM)

82 Mathematics Examples: 1 (a) 2 No. of rows  3 No. of columns  1 331  5 No. of rows  2 (b) 7 No. of columns  1    3. Zero Matrix or Null Matrix: A matrix whose elements are all zero is called null matrix. Denoted by “O”. Examples: (a) 0 0  (b) 0 0 0  0 0 0 (c) 0 0  4. Unit Matrix or Identity Matrix: A square matrix each of whose diagonal elements are 1 and non-diagonal elements are 0 are called unit matrix. Denoted by “Im×n”. Examples: 1 0 1 0 0 (a)   (b) 0 1 0 0 12  2 0 0 13 3 5. Square Matrix: A matrix whose number of rows is equal to number of columns, i.e., m = n is called square matrix. Examples: (b) a b fc (c) 111 a b d e (a)   g h i33 c d2  2 6. Scalar Matrix: A diagonal matrix whose all diagonal elements are equal is called scalar matrix. CU IDOL SELF LEARNING MATERIAL (SLM)

Matrices 1 83 Examples: 4 0 0 3 0 (b) 0 4  (a)   0 0 32  2 0 0 43 3 7. Transpose of a Matrix: The matrix obtained from a given matrix, by interchanging its rows and columns, is called Transpose of a matrix. If a matrix m × n contains m rows and n columns, then its transpose contains n rows and m columns. If the given matrix is A, then its transpose is denoted by A'. Example: A = 22 6 54 , A' =  2 2  52 5 6 5     5  2 7  5 4 7 B = 13 22, 1 3 3   B' =   3 8 2 2 8  8. Skew Symmetric: A matrix A is called skew symmetric matrix if aij = –aji for all i and j. Therefore, every diagonal element of a skew symmetric matrix should be zero. Examples: (a) A =  0 4 , A = 0  4  4    0 4 0  which is – A =  0 4   4 0  – A = A   0 2  3  0  2 3 (b) A =  2 0 1, A =  2 0 1   3 1 0  3 1 0 CU IDOL SELF LEARNING MATERIAL (SLM)

 Mathematics  84 0 2  3 – A =  2 0 1 0  3 1 – A = A  9. Symmetric matrix: A square matrix in which aij = aji ( i = number of rows and j = number of columns) is called symmetric matrix, i.e., A = AT is called symmetric matrix. Examples: (a)  3  6 and AT =  3  6 A=  6 3  6 3 A= AT   a h g a h g (b) A = h b f  and AT = h b f  g f c g f c  A= AT 10. Diagonal Matrix: A diagonal matrix is a square matrix with all the non-diagonal elements 0. The diagonal matrix is completely defined by the diagonal elements. Diagonal elements are represented by aixj , where i = j. Example: A = 20 0 00, B = 4 0 , C = [7] 5     0 8 0 0 9    8.4 Summary Matrices were actually discovered by John James Sylvester, a 19th century mathematician but it was Arthur who developed aspect of matrices and published a treatise on geometric transformations using matrices that were not rotated versions of the coefficients being investigated as had previously been done. Instead he defined operations such as addition, CU IDOL SELF LEARNING MATERIAL (SLM)

Matrices 1 85 subtraction, multiplication, and division as transformations of those matrices The size of a matrix is defined by the number of rows and columns that it contains. A matrix with m rows and n columns is called an m × n matrix or m-by-n matrix, while m and n are called its dimensions. For example, the matrix A above is a 3 × 2 matrix. The different types of matrix are as below discussed in this unit (a) Row matrix (b) Column Matrix (c) Null Matrix (d) Identity Matrix (e) Square Matrix (f) Scalar Matrix (g) Transpose of a matrix (h) Skew symmetric (i) Symmetric Matrix (j) Diagonal Matrix 8.5 Key Words/Abbreviations  Rows are sleeping lines (m).  Columns are standing lines (n).  In simple terms, a matrix can be written as A = [aij]m×n. 8.6 Learning Activity 1. If A 2 3 1 and B  2 6 08, then find: (i) A' and (ii) B'. 4 2 5  3 5     CU IDOL SELF LEARNING MATERIAL (SLM)

 Mathematics   86 2. Check where the following matrices are symmetric or not.  0 2  3 2  6 5 A   2 0 1  and B  2 5 4   3 1 0  5  2 7      8.7 Unit End Questions (MCQ and Descriptive) A. Descriptive Type Questions Exercise 1. Given matrix A = 55, B= 14 23 839 and C = a4 b4 27 20 7     Answer the following: (a) State the order of matrix. (b) Which of these given matrices is a column matrix? 2. State which of the following matrix is of equal order. 3  2 21, C = 2 22, 25 4 11 A= ,B=  6    2 D= 3 4  3  3. Which of the following matrix is zero matrix? 1 0 D= 00 A = [2], B = [0], C =  , 0 0 0 4. Which of the following matrix is scalar matrix? 1 0 2 0 21, D = 0 0 A=  ,C=   0, B = 0 0 0 0 2 3 CU IDOL SELF LEARNING MATERIAL (SLM)

 87  2. A and C 4. None Matrices 1 Answers:1. (a) 3 × 1, 2 × 3, 2 × 2; (b) A 3. B and D B. Multiple Choice/Objective Type Questions 1. If A is a matrix of order m × n, then it contains (a) n rows (b) m rows (c) m × n rows (d) None of these 2. A row matrix is of order (a) 1 × n (b) 1 × m (c) n × n (d) All above 3. If A matrix of order 2 × 3, then its transpose order is (a) 3 × 2 (b) 2 × 2 (c) 3 × 3 (d) All above 4. A matrix with all elements of value zero is called (a) Null matrix (b) Zero matrix (c) (a) and (b) both (d) All above 5. The order of matrix will be given by (a) m × n (b) m × m (c) n × n (d) None of these Answers: 1. (b), 2. (a), 3. (a), 4. (b), 5. (a) 8.8 References References of this unit have been given at the end of the book. CU IDOL SELF LEARNING MATERIAL (SLM)

88 Mathematics UNIT 9 MATRICES 2 Structure: 9.0 Learning Objectives 9.1 Introduction 9.2 Addition of Matrix 9.3 Subtraction of Matrix 9.4 Multiplication of Scalar Matrix 9.5 Summary 9.6 Key Words/Abbreviations 9.7 Learning Activity 9.8 Unit End Questions (MCQ and Descriptive) 9.9 References 9.0 Learning Objectives After studying this unit, you will be able to:  Explain how to add 2 matrices with same order.  Discuss how to subtract 2 matrices with same order.  Analyse the multiplication of matrix if row of first matrix is equal to column of other matrix meaning that the order is different. CU IDOL SELF LEARNING MATERIAL (SLM)

Matrices 2 89 9.1 Introduction 1. A matrix is arrangement of mn numbers in m rows and n columns, written in rectangular or round bracket. 2. Rows are sleeping lines. 3. Columns are standing lines. 4. In simple terms, a matrix can be written as A = [aij]m×n  a11 a12 a13 ⋯ a1n  a21 a22 a23 ⋯ a 2n  ⋯ ⋯ ⋯  5. A  ⋯ ⋯ ⋯  ⋯ ⋯ ⋯ ⋯  ⋯ ⋯ ⋯ ⋯ ⋯  am1 am 2 am3 ⋯ a mn  mn Equal Matrices: Two matrices are equal if they have the same dimension or order and the corresponding elements are identical.  2 6 1 P =0 5 3   2 6 1 Q = 0 5 3 Matrices P and Q are equal. 1 2  A =  3 4     5 6    1 2 3 B = 4 5 6 Matrices A and B are not equal because their dimensions or order is different. CU IDOL SELF LEARNING MATERIAL (SLM)

90 Mathematics 9.2 Addition of Matrix If A = [aij] and B = [bij] are two matrix of the same order, m × n, then the sum of the two matrices A and B is another matrix C = [cij] of the same order m × n, where cij = aij + bij. Example 1: Add the following matrices: 0 1 2  6 5 4     9 8 7 3 4 5  Solution: We need to add two matrices and then, simplify the final answer: 0 1 2  6 5 45 0  6 1 5 2  54 6 6 6  8   4 9  3 8 4 2  1 2 12 12 9 7 3   6 6 6 12 12 12  Perform the indicated operation, or explain why it is not possible. 1 2  4 5 6    8 9 0 3 7  Since matrices are added entry-wise, we have to add the 1 and the 4, the 2 and 5, the 0 and the 7, and the 3 and the 8. But what do we add to the 6 and to the 9? There are no corresponding entries in the first matrix that can be added to these entries in the second matrix. So, the answer is: We can't add these matrices, because they are not of the same size. This is always the case: To be able to add two matrices, they must be of the same size. If they are not the same size (if they do not have the same “dimensions”), then the addition is “not defined” (doesn't make mathematical sense). Example 2: If A = 2 5 and B = 3 73, find 2A + 3B. 1 4 6  Also prove that 2(A+B) = 2A + 2B. CU IDOL SELF LEARNING MATERIAL (SLM)

Matrices 2 91 Solution: 4 10  9 21  13 31 2A + 3B = 8  18 9  20 17 2  2 5  3 7 = 2 21 3 5  7  2(A + B) = 2 4 6 3 6 4  3 1 =2 5 12  10 24 7 7  14 14 4 10  6 14  10 24 = 2(A + B). And 2A + 2B = 8  12 6  14 14 2 Example 3: If A = 2 – 1 , B = 3 – 2   – 1 , find a matrix X such that 2A + X = 3B. 4 3  4 Solution: X = 3B – 2A X = 3  3 – 2 – 2 2 –1 – 1 4 4 3 = 9 –6 – 4 –2  5 –4 –3 12 8 6 -11 6 3 2 – 5 and B = 4 7 9 Example 4: If A = 0 – 3 0 , find A + B and B + A. 10 6 2 Solution: A+B =  3 2 – 5 + 4 7 9 1 0 6 0 – 3 0 2 =  3 4 27 – 5  92 7 9 4 1 0 – 3 60 0  7 6 2 CU IDOL SELF LEARNING MATERIAL (SLM)

  92 Mathematics B+ A =  4 7 9 + 3 2 – 5 – 3 0 2 10 6 0  =  43 72 9 – 5 = 7 9 4 – 3  10 06 2  0 7 6 2  A + B = B+ A. Example 5: If A = 9 1 , B = 1 5  , find the matrix X such that 3A + 5B + 2X = 0.    12 4 3 7  Solution: 3A + 5B + 2X = 0    2X = –3A – 5B = –3 9 1 – 5 1 5  4 3 7 12  2X = – 27 – 3 +  –5 – 25 – 12 – 9 – 35 – 60  2X =  –27 – 5 –12 – 35 –3 – 25 = – 32 – 28 –9 – 60 – 47 – 69  X= 1 – 32 – 28 2 – 47 – 69  X =  –16 – 47/2 ––6194/2.   9.3 Subtraction of Matrix    If A = aij and B = bij are two matrices of the same order, m × n, then the subtraction of the  two matrices A and B is another matrix C = c ij of the same order m × n, where, cij = aij – bij. Example: Find A – B and A – C, or explain why you cannot. CU IDOL SELF LEARNING MATERIAL (SLM)

Matrices 2 93 Solution: A= – 1 2 0 , B = 0 –4 – 33, C = 0 – 44.  3   –4 9 – 0 6 9 A and B are the same size, each being 2 × 3 matrices, so I can subtract, working entry-wise: A – B = – 1 2 0  0 4 3  3   4  3 0 6 9 = – 1 0 2  (4) 0  3 3  (4) 6  (3)  09  =  –1 2 4  33  1 6  3  9 3 4   9 7 9 6 However, A and C are not the same size, since A is 2 × 3 and C is 2 × 2. So, this subtraction is not defined. A–B=  –1 6  3  9 7  9   A – C is not defined, because A and C are not the same size. Equal Matrices: Two matrices are equal if they have the same dimension or order and the corresponding elements are identical.  2 6 1 P =0 5 3   2 6 1 Q = 0 5 3  Matrices P and Q are equal. CU IDOL SELF LEARNING MATERIAL (SLM)

94 Mathematics Example 1: Find the values of x and y given the following equation:  3 0x  4 61  1 7 2 y  3  5 1  Solution: First, we'll simplify the left-hand side a bit by adding entry-wise:  3 0x  4 61  3  4 x  6 2 y  3 2 y  3 0  1  = 1 x  61  1 71. 2y  3  5  Since matrix equality works entry-wise, we can compare the entries to create simple equations that we can solve. In this case, the 1, 2-entries tell us that x + 6 = 7, and the 2,1-entries tell me that 2y – 3 = –5. Solving, we get: x+6=7 x= 1 2y – 3 = –5 2y = –2 y= –1. Example 2: Solve for x, y and z given that matrix A = matrix B. Solution: x  y 1 3  A   3 xz 3y   z  y x x  y  z  B   7 1 63 3 6   3 5 6 CU IDOL SELF LEARNING MATERIAL (SLM)

 95  Matrices 2 We have already seen that if A = B, then the corresponding (i, j) entries must be equal. Therefore, given the above, by equating corresponding entries, you should see that: x+ y = 7 x–z =6 3y = 6 z– y = –3 x=5 x+y+z = 6 From just inspecting the two matrices, we have already solved for x x=5 Similarly, we can choose which equation to use to find y. x+ y = 7 y= 7–5 y=2 This is the same result you would obtain regardless of which equation you used to solve for y z can be solved by picking any of the equations it appears in and substituting x or y depending on which one is needed x+y+z=6 z= 6 – x – y z= 6 – 5 – 2 z = –1. 9.4 Multiplication of Scalar Matrix If a matrix A = [aij] of order m × n is to be multiplied by a scalar k, where k is not = 0, then the scalar multiplication KA of the matrix A is obtained by multiplying every element of A by scalar constant K. Hence, KA = [kaij]. CU IDOL SELF LEARNING MATERIAL (SLM)