Mathematical Foundation of Computer Science Notes PDF

Mathematical Foundation of Computer Science RAJEEV GANDHI MEMORIAL COLLEGE OF ENGINEERING AND TECHNOLOGY MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE NOTES (A0504193) II B.Tech – I SEM (R19) Departm...

Mathematical Foundation of Computer Science RAJEEV GANDHI MEMORIAL COLLEGE OF ENGINEERING AND TECHNOLOGY MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE NOTES (A0504193) II B.Tech – I SEM (R19) Department of Computer Science and Engineering Dept of CSE,RGMCET Page 1  Mathematical Foundation of Computer Science UNIT-I Mathematical Logic Syllabus Mathematical Logic: Statements and notations, Connectives, Well-formed formulas, Truth Tables, tautology, converse, inverse and contrapositive ,equivalence, implication, Normal forms. Introduction to Discrete Mathematics Discrete maths are the study of discrete structures which mathematical models dealing with discrete objects and relationships between them. Example of discrete objects are like Sets,Permutations,grpahs and etc. Why it is important for computer science  In the world of computers, all the information is stored in bits, units of information that can take the value of either 0 or 1. It‘s not like in nature, where something can take all the values in between 0 and 1 as well. Instead, everything is binary.  Since the bits are the building blocks of everything that happens in computer software, everything becomes discrete. For instance, the hard drive on the laptop I‘m using right now can store 1 845 074 329 600 bits of information.  The study of algorithms is also firmly in the discrete world. An algorithm is a step-by- step list of instructions to the computer and it‘s what makes computer programs possible. When determining how much time an algorithm needs to run, you count the number of operations it needs to perform. Notice the word count. Again, discrete mathematics. In continuous mathematics (the opposite of discrete), the calculation would go like this: ∫ =[1/2∗x2]50=52 /2−0=12.5 In discrete mathematics, the equivalent calculation would go like this:∑ 0+1+2+3+4=10 Dept of CSE,RGMCET Page 2  Mathematical Foundation of Computer Science Applications of discrete mathematics with computer applications 1)Computer networks 2)Programming languages 3)Finite state automata or compilers 4)Databases Symbolic logic is used in framing algorithms and their verification and in automatic theorem proving. Set theory, Graph Theory, trees etc are used in storage and retrieval of information (data structures),Algorithms and their complexity studies also uses tools from discrete mathematics. Formal Languages, Automata theory, Turing machines etc are themselves part of discrete mathematics and so is Recursive Function Theory.Undecidability of many problems are established using Turing machines which is the Mathematical model for studying theoretical limitations of Computation.Lattices and Boolean Algebra are used in Computer Science as well as in communications and networking. Mathematical Logic Logic It is the study of the principles and methods that distinguishes between valid and invalid argument. 1.Proposition Logic Proposition or Statement A proposition or a statement can defined has a declarative sentence to which we can assign one and only one of the truth values either true (or) false but not a both is called a proposition. The true or false of a proposition is called truth value of a proposition These two values true and false are denoted by the symbols T and F respectively. Sometimes these are also denoted by the symbols 1 and 0 respect. Dept of CSE,RGMCET Page 3  Mathematical Foundation of Computer Science Proposition truth value Ex: 1) India capital is new Delhi True 2) 2*3=5 false 3) 5 is a prime number true These are propositions (or statements) because they are either true or false. Next consider the following sentences: 4) How beautiful are you? 5) Wish you a happy new year 6) x + y = z 7) Take one book. These are not propositions as they are not declarative in nature, that is, they do not declare a definite truth value T or F. Types of Propositions 1)Atomic proposition 2)Compound Proposition 1)Atomic proposition A Proposition which cannot be divided further is called an atomic proposition. Examples: 1)India capatial is New Delhi 2)2*3=5 2) Compound Proposition Two or more atomic propositions can be combined to form a compound proposition with help of Connectives. Compound Proposition also called as Propositional function. Dept of CSE,RGMCET Page 4  Mathematical Foundation of Computer Science Examples of Compound statements ―3+2=5‖ and ―delhi is a capatial of india‖. ―the grass is green‖ or ―it is hot today‖. Discrete mathematics is not difficult to me. Here and, or ,not are called connectives. Notations Statements are symbollically represented as A,B,C,..P,Q,R,S… Those are called propostional variables or notations. Examples: P=―Delhi is the capital of india‖. Q=―17 is divisible by 3. Logical Connectives  The words or phrases or symbols which are used to make a compound proposition by two or more atomic propositions are called logical connectives or simply connectives.  There are five basic connectives called negation, conjunction, disjunction, conditional and biconditional. Connectivity Symbol Word Negation ~ Not Disjunction ∨ OR Conjunction ∧ AND Conditional → IF AND THEN Biconditional ↔ If and only if Dept of CSE,RGMCET Page 5  Mathematical Foundation of Computer Science Negation (~) or(¬) The negation of a statement is generally formed by writing the word ‗not‗ at a proper place in the statement (proposition) or by prefixing the statement with the phrase (~).It is not the case that‗. If p denotes a statement then the negation of p is written as p and read as not p‗. If the truth value of p is T then the truth value of p is F. Also if the truth value of p is F then the truth value of p is T. Ex:~P Truth table for Negation P ~P F T Disjunction (OR) If P and Q are any two propositions then P or Q symbollicaly written as P V Q. P V Q is a proposition whose truth values is false only when both P and Q are false other wise True. Truthtable for Disjunction P Q PVQ F F F F T T T F T T T T P: I shall go to the game. Q : I shall watch the game on television. P V Q: I shall go to the game OR I shall watch the game on television. Dept of CSE,RGMCET Page 6  Mathematical Foundation of Computer Science Conjunction (AND(^))  IF P and Q are any two propositions then P and Q Symbollically written as P ∧ Q.  P ∧ Q is a proposition whose truth value is true only when both are P and Q are true.  Whole truth value is false when either P or Q are false and both are false. Truth table for Conjunction P Q P∧Q F F F F T F T F F T T T P : It is raining today. Q: There are 10 chairs in the room. P ∧ Q: It is raining today AND There are 10 chairs in the room. Conditional (or) Implication(→) If P and Q are any two statements (or propositions) then the statement P → Q which is read as, If P , then Q‗ is called a conditional statement (or proposition) or implication and the connective is the conditional connective. Dept of CSE,RGMCET Page 7  Mathematical Foundation of Computer Science Truth table for conditional P Q P→ Q F F T F T T T F F T T T In this conditional statement, P is called the hypothesis or premise or antecedent and Q is called the consequence or conclusion. Biconditional (If and only if) If P and Q are any two propostions then P if and only if Q Written as P ↔Q. It‘s truth value is true only when both P & Q have same truth values. P q p↔q T T T T F F F T F F F T TAUTOLOGY AND CONTRADICTION Tautology: A proposition is said to be a tautology if its truth value is T for any assignment of truth values to its components. Example: :The proposition P V ~P is a tautology. Contradiction A proposition is said to be a contradiction if its truth value is F for any assignment of truth values to its components. Example: The proposition P ∧ ¬Pis a contradiction. Dept of CSE,RGMCET Page 8  Mathematical Foundation of Computer Science Contingency: A statement formula which is neither a tautology nor a contradiction is known as a contingency. Example: P->Q Tautology: A statement formula which is true regardless of the truth values of the statements which replace the variables in it is called a universally valid formula or a logical truth or a tautology. How to prove given compound proposition is tautology 1)By Constructing truth table 2)By using substitution method 1)Constructing truth table Show that following function is tautology a)(PVQ) V ~P Solution P Q ~P PVQ (PVQ)V~P F F T F T F T T T T T F F T T T T F T T In the above table (PVQ) V ~P is givig all truth values are true so it is a tautology. Dept of CSE,RGMCET Page 9  Mathematical Foundation of Computer Science b)Show that given propostion function is a tautology ((P → Q) ∧ (Q→R)) →(P→ R) P Q R P → Q→R ((P → Q) ∧ (Q→R) P→ R ((P → Q) ∧ (Q→R)) →(P→ R) Q F F F T T T T T F F T T T T T T F T F T F F T T T F F F T F F T F T T T T T T T T F T F T F T T T T F T F F F T T T T T T T T T Implication: If P and Q are any two propositions then P->Q or If P then Q P->Q is proposition whose truth value is false only when P is true and Q is false. P->Q Here P is antecedent and Q is Consequent. Dept of CSE,RGMCET Page 10  Mathematical Foundation of Computer Science P Q P→ Q F F T F T T T F T T T T When ever P is false P->Q is true i.e false antecedent P implies any proposition Q When ever Q is true P->Q is also true i.e a true consequent Q implied by any propositional ‗P‘. from the implication statement we can write another three statements which are converse, inverse and contrapositive Converse, Inverse and Contrapositive If P → Q is a conditional statement, then (1). Q → P is called its converse (2). ¬P → ¬Q is called its inverse (3). ¬Q → ¬P is called its contrapositive. Example: P: Today is Sunday Q: It is a holiday Converse Statement: If it is a holiday, then today is Sunday. Inverse Statement: If today is not Sunday, then it is not a holiday. Contrapositive Statement- If it is not a holiday, then today is not Sunday. Dept of CSE,RGMCET Page 11  Mathematical Foundation of Computer Science Here Implication and Contrapositive are equal. Converese and inverse are opposite propostions. Well formed formulas(wff): Not all strings can represent propositions of the predicate logic. Those which produce a proposition when their symbols are interpreted must follow the rules given below, and they are called wffs(well-formed formulas) of the first order predicate logic. Rules for constructing Wffs A predicate name followed by a list of variables such as P(x, y), where P ispredicate name, and x and y are variables, is called an atomic formula. A well formed formula of predicate calculus is obtained by using the following rules. 1. An atomic formula is a wff. 2. If A is a wff, then 7A is also a wff. 3. If A and B are wffs, then (A V B), (A ٨ B), (A → B) and (A D B). 4. If A is a wff and x is a any variable, then (x)A and ($x)A are wffs. 5. Only those formulas obtained by using (1) to (4) are wffs. Since we will be concerned with only wffs, we shall use the term formulas for wff. We shall follow the same conventions regarding the use of parentheses as was done in the case of statement formulas. Wffs are constructed using the following rules: 1. True and False are wffs. 2. Each propositional constant (i.e. specific proposition), and each propositional variable (i.e. a variable representing propositions) are wffs. 3. Each atomic formula (i.e. a specific predicate with variables) is a wff. 4. If A, B, and C are wffs, then so are A, (A B), (A B), (A B), and (A B). 5. If x is a variable (representing objects of the universe of discourse), and A is a wff, then so are x A and x A. Dept of CSE,RGMCET Page 12  Mathematical Foundation of Computer Science For example, "The capital of Virginia is Richmond." is a specific proposition. Hence it is a wff by Rule 2. Let B be a predicate name representing "being blue" and let x be a variable. Then B(x) is an atomic formula meaning "x is blue". Thus it is a wff by Rule 3. above. By applying Rule 5. to B(x), xB(x) is a wff and so is xB(x). Then by applying Rule 4. to them x B(x) x B(x) is seen to be a wff. Similarly if R is a predicate name representing "being round". Then R(x) is an atomic formula. Hence it is a wff. By applying Rule 4 to B(x) and R(x), a wff B(x) R(x) is obtained. In this manner, larger and more complex wffs can be constructed following the rules given above. Note, however, that strings that can not be constructed by using those rules are not wffs. For example, xB(x)R(x), and B( x ) are NOT wffs, NOR are B( R(x) ), and B( x R(x) ). More examples: To express the fact that Tom is taller than John, we can use the atomic formula taller(Tom, John), which is a wff. This wff can also be part of some compound statement such as taller(Tom, John) taller(John, Tom), which is also a wff. If x is a variable representing people in the world, then taller(x,Tom), x taller(x,Tom), x taller(x,Tom), x y taller(x,y) are all wffs among others. However, taller( x,John) and taller(Tom Mary, Jim), for example, are NOT wffs. Logical Equivalence Two formulas A and B are said to equivalent to each other if and only if A↔ B is a tautology.If A↔B is a tautology, we write A ⇔ B which is read as A is equivalent to B. Note : 1. ⇔ is only symbol, but not connective. A ↔ B is a tautology if and only if truth tables of A and B are the same. Equivalence relation is symmetric and transitive. (or) Let P and Q are two propositional functions P is Equivalent to Q. Symbolically written as P⇔ Q or P ≡ Q if P and Q have same truth table. Dept of CSE,RGMCET Page 13  Mathematical Foundation of Computer Science Ex:P->Q ⇔ ~P V Q. Method I. Truth Table Method: One method to determine whether any two statement formulas are equivalent is to construct their truth tables. Example: Prove (P → Q) ⇔ (¬P ∨ Q). P Q P→Q ¬P ¬P∨Q T T T F T T F F F F F T T T T F F T T T In the above table both P → Q and ¬P∨Q are have same truth values. So that (P → Q) ⇔ (¬P ∨ Q). Equivalence Formulas: 1. Idempotent laws: (a) P ∨ P ⇔ P (b) P ∧ P ⇔ P 2. Associative laws: (a) (P ∨ Q) ∨ R ⇔ P ∨ (Q ∨ R) (b) (P ∧ Q) ∧ R ⇔ P ∧ (Q ∧ R) 3. Commutative laws: (a) P ∨ Q ⇔ Q ∨ P (b) P ∧ Q ⇔ Q ∧ P 4. Distributive laws: P∨(Q∧R)⇔(P∨Q)∧(P∨R) P∧(Q∨R)⇔(P∧Q)∨(P∧R) Identity laws (or) 5. Domination Law (a) (i) P ∨ F ⇔ P (ii) P ∨ T ⇔ T Dept of CSE,RGMCET Page 14  Mathematical Foundation of Computer Science (b) (i) P ∧ T ⇔ P (ii) P ∧ F ⇔ F 6. Component laws: (a) (i) P ∨ ¬P ⇔ T (ii) P ∧ ¬P ⇔ F. (b) (i) ¬¬P ⇔ P (ii) ¬T ⇔ F , ¬F ⇔ T 7. Absorption laws: (a) P ∨ (P ∧ Q) ⇔ P (b) P ∧ (P ∨ Q) ⇔ P 8.Demorgan‘s Laws (a) ¬(P ∨ Q) ⇔ ¬P ∧ ¬Q (b) ¬(P ∧ Q) ⇔ ¬P ∨ ¬Q Dept of CSE,RGMCET Page 15  Mathematical Foundation of Computer Science Tautological Implications. A statement formula A is said to tautologically imply a statement B if and only if A → B is a tautology.In this case we write A ⇒ B, which is read as ‗A implies B‗. Note: ⇒ is not a connective, A ⇒ B is not a statement formula. A ⇒ B states that A → B is tautology. Clearly A ⇒ B guarantees that B has a truth value T whenever A has the truth value T.One can determine whether A ⇒ B by constructing the truth tables of A and B in the same manner as was done in the determination of A ⇔ B. Example: Prove that (P → Q) ⇒ (¬Q → ¬P ). P Q ¬P ¬Q P→Q ¬Q→¬P (P→Q)→(¬Q→¬P) T T F F T T T T F F T F F T F T T F T T T F F T T T T T Since all the entries in the last column are true, (P → Q) → (¬Q → ¬P ) is a tautology. Hence (P → Q) is Tautological Implications to (¬Q → ¬P ). So that (P → Q) ⇒ (¬Q → ¬P ). In order to show any of the given implications, it is sufficient to show that an assignment of the truth value T to the antecedent of the corresponding condi-tional leads to the truth value T for the Dept of CSE,RGMCET Page 16  Mathematical Foundation of Computer Science consequent. This procedure guarantees that the conditional becomes tautology, thereby proving the implication. Example: Prove that ¬Q ∧ (P → Q) ⇒ ¬P. Solution: Assume that the antecedent ¬Q ∧ (P → Q) has the truth value T , then both ¬Q and P →Q have the truth value T , which means that Q has the truth value F , P → Q has the truth value T. Hence P must have the truth value F.Therefore the consequent ¬P must have the truth value T. ¬Q∧(P→Q)⇒¬P. Another method to show A ⇒ B is to assume that the consequent B has the truth value F and then show that this assumption leads to A having the truth value F. Then A → B must have the truth value T. Example: Show that ¬(P → Q) ⇒ P. Solution: Assume that P has the truth value F. When P has F , P → Q has T , then ¬(P → Q) has F.Hence ¬(P → Q) → P has T. So that ¬(P→Q)⇒P. Normal Forms If a given statement formula A(p1, p2,...pn) involves n atomic variables, we have 2n possible combinations of truth values of statements replacing the variables. The formula A is a tautology if A has the truth value T for all possible assignments of the truth values to the variables p1, p2,...pn and A is called a contradiction if A has the truth value F for all possible assignments of the truth values of the n variables. A is said to be satisable if A has the truth value T for atleast one combination of truth values assigned to p1, p2,...pn. The problem of determining whether a given statement formula is a Tautology, or a Contradiction is called a decision problem. Dept of CSE,RGMCET Page 17  Mathematical Foundation of Computer Science The construction of truth table involves a finite number of steps, but the construction may not be practical. We therefore reduce the given statement formula to normal form and find whether a given statement formula is a Tautology or Contradiction or at least satisfiable.It will be convenient to use the word product in place of conjunction and sum in place of disjunction. A product of the variables and their negations in a formula is called an elementary Product. Similarly, a sum of the variables and their negations in a formula is called an elementary sum. Let P and Q be any atomic variables Then P,~P∧Q, ¬Q∧P∧~P,Q∧~P are some example of elementary products. On the other hand P,~P∨ Q, ¬Q∨ P∨ ~P,Q∨ ~P. are some examples of elementary sums. Types of Normal forms 1) Disjunctive Normal forms 2) Conjunctive Normal forms. Disjunctive Normal Form (DNF) A formula which is equivalent to a given formula and which consists of a sum of elementary products is called a disjunctive normal form of the given formula. Example: Obtain disjunctive normal forms of (a) P ∧ (P → Q) P∧(P→Q)⇔P∧(¬P∨Q) (apply distributive law P∧(Q∨R)⇔(P∧Q)∨(P∧R) ⇔ (P∧¬P)∨(P∧Q) b)¬(P ∨ Q) ↔(P ∧ Q) ¬(P ∨ Q) ↔(P ∧ Q)⇔ (¬(P ∨ Q) ∧ (P ∧ Q)) ∨ ((P ∨ Q) ∧ ¬(P ∧ Q)) [using R↔S⇔(R∧S)∨(¬R∧¬S)] ⇔((¬P ∧ ¬Q) ∧ (P ∧ Q)) ∨ ((P ∨ Q) ∧ (¬P ∨ ¬Q)). ⇔(¬P∧¬Q∧P∧Q)∨((P∨Q)∧¬P)∨((P∨Q)∧¬Q). ⇔(¬P∧¬Q∧P∧Q)∨(P∧¬P)∨(Q∧¬P)∨(P∧¬Q)∨(Q∧¬Q). Which is the required disjunctive normal form.Note: The DNF of a given formula is not unique. Dept of CSE,RGMCET Page 18  Mathematical Foundation of Computer Science Conjunctive Normal Form (CNF) A formula which is equivalent to a given formula and which consists of a product of elementary sums is called a conjunctive normal form of the given formula. The method for obtaining conjunctive normal form of a given formula is similar to the one given for disjunctive normal form. Again, the conjunctive normal form is not unique. (a) P ∧ (P → Q) obtain the conjuctive normal form P ∧ (P → Q) ⇔ P ∧ (¬P ∨ Q) (b).¬(P ∨ Q)↔ (P ∧ Q) ⇔ (¬(P∨Q)→(P∧Q))∧((P∧Q)→¬(P∨Q)) ⇔ ((P∨Q)∨(P∧Q))∧(¬(P∧Q)∨¬(P∨Q)) ⇔ [(P∨Q∨P)∧(P∨Q∨Q)]∧[(¬P∨¬Q)∨(¬P∧¬Q)] ⇔ (P∨Q∨P)∧(P∨Q∨Q)∧(¬P∨¬Q∨¬P)∧(¬P∨¬Q∨¬Q) Principal Disjunctive Normal Form In this section, we will discuss the concept of principal disjunctive normal form (PDNF). Minterm: For a given number of variables, the minterm consists of conjunctions in which each statement variable or its negation, but not both, appears only once. Let P and Q be the two statement variables. Then there are 22 minterms given by P ∧ Q, P ∧ ¬Q, ¬P ∧ Q, and ¬P ∧ ¬Q Minterms for three variables P , Q and R are P ∧ Q ∧ R, P ∧ Q ∧ ¬R, P ∧ ¬Q ∧ R,P∧ ¬Q ∧ ¬R, ¬P∧ Q ∧ R, ¬P ∧ Q ∧ ¬R, ¬P ∧ ¬Q ∧ R and ¬P ∧ ¬Q ∧ ¬R. Dept of CSE,RGMCET Page 19  Mathematical Foundation of Computer Science From the truth tables of these minterms of P and Q, it is clear that. P Q P∧Q P∧¬Q ¬P∧Q ¬P∧¬Q T T T F F F T F F T F F F T F F T F F F F F F T (i). no two minterms are equivalent (ii). Each minterm has the truth value T for exactly one combination of the truth values of the variables P and Q. PDNF Definition: For a given formula, an equivalent formula consisting of disjunctions of minterms only is called the Principal disjunctive normal form of the given formula. The principle disjunctive normal formula is also called the sum-of-products canonical form. Methods to obtain the PDNF of a given formula. (a). By Truth table: (b). without constructing the truth table (a). By Truth table: (i). Construct a truth table of the given formula. (ii). For every truth value T in the truth table of the given formula, select the minterm which also has the value T for the same combination of the truth values of P and Q. (iii). The disjunction of these minterms will then be equivalent to the given formula Dept of CSE,RGMCET Page 20  Mathematical Foundation of Computer Science Example: Obtain the PDNF of P → Q. Solution: From the truth table of P → Q P Q P→Q Minterm T T T P∧Q T F F P∧¬Q F T T ¬P∧Q F F T ¬P∧¬Q The PDNF of P → Q is (P ∧ Q) ∨ (¬P ∧ Q) ∨ (¬P ∧ ¬Q). Obtain the PDNF for (P ∧ Q) ∨ (¬P ∧ R) ∨ (Q ∧ R). Solution: P Q R Minterm P∧Q ¬P∧R Q∧R (P∧Q)∨(¬P∧R)∨(Q∧R) T T T P∧Q∧R T F T T T T F P∧Q∧¬R T F F T T F T P∧¬Q∧R F F F F T F F P∧¬Q∧¬R F F F F F T T ¬P∧Q∧R F T T T F T F ¬P∧Q∧¬R F F F F F F T ¬P∧¬Q∧R F T F T F F F ¬P∧¬Q∧¬R F F F F The PDNF of (P ∧ Q) ∨ (¬P ∧ R) ∨ (Q ∧ R) is (P∧Q∧R)∨(P∧Q∧¬R)∨(¬P∧Q∧R)∨(¬P∧¬Q∧R). (b). Without constructing the truth table: In order to obtain the principal disjunctive normal form of a given formula is con- structed as follows: Dept of CSE,RGMCET Page 21  Mathematical Foundation of Computer Science (1). First replace →, by their equivalent formula containing only ∧, ∨ and ¬. (2). Next, negations are applied to the variables by De Morgan‗s laws followed by the application of distributive laws. (3). Any elementarily product which is a contradiction is dropped. Minterms are ob-tained in the disjunctions by introducing the missing factors. Identical minterms appearing in the disjunctions are deleted. Example: Obtain the principal disjunctive normal form of (a) ¬P∨ Q (b) (P ∧ Q) ∨ (¬P ∧ R) ∨ (Q ∧ R). (a) ¬P∨ Q ¬P∨Q ⇔ (¬P∧T)∨(Q∧T) ⇔ (¬P∧(Q∨¬Q))∨(Q∧(P∨¬P)) [∵P∨¬P⇔T] ⇔ (¬P∧Q)∨(¬P∧¬Q)∨(Q∧P)∨(Q∧¬P) ⇔ (¬P∧Q)∨(¬P∧¬Q)∨(P∧Q) [∵P∨P⇔P] (b) (P ∧ Q) ∨ (¬P ∧ R) ∨ (Q ∧ R) (P ∧ Q) ∨ (¬P ∧ R) ∨ (Q ∧ R) ⇔ (P∧Q∧T)∨(¬P∧R∧T)∨(Q∧R∧T) ⇔ (P∧Q∧(R∨¬R))∨(¬P∧R∧(Q∨¬Q))∨(Q∧R∧(P∨¬P)) ⇔ (P∧Q∧R)∨(P∧Q∧¬R)∨(¬P∧R∧Q) ∨ (¬P∧R∧¬Q) ∨ (Q∧R∧P)∨(Q∧R∧¬P) ⇔ (P∧Q∧R)∨(P∧Q∧¬R)∨(¬P∧Q∧R)∨(¬P∧¬Q∧R) Principal Conjunctive Normal Form The dual of a minterm is called a Maxterm. For a given number of variables, the maxterm consists of disjunctions in which each variable or its negation, but not both, appears only once. Each of the maxterm has the truth value F for exactly one combination of the truth values of the variables. Now we define the principal conjunctive normal form. For a given formula, an equivalent formula consisting of conjunctions of the max-terms only is known as its principle conjunctive normal form. This normal form is also called the product-of- sums canonical form.The method for obtaining the PCNF for a given formula is similar to the one described previously for PDNF. Dept of CSE,RGMCET Page 22  Mathematical Foundation of Computer Science Example: Obtain the principal conjunctive normal form of the formula (¬P→R)∧(Q↔P) Solution: (¬P→R)∧(Q↔P) ⇔[¬(¬P)∨R]∧[(Q→P)∧(P→Q)] ⇔ [(P∨R)∧[(¬Q∨P)∧(¬P∨Q)] ⇔ ( P∨R∨F)∧[(¬Q∨P∨F)∧(¬P∨Q∨F)] ⇔ [(P∨R)∨(Q∧¬Q)]∧[¬Q∨P)∨(R∧¬R)]∧[(¬P∨Q)∨(R∧¬R)] ⇔ (P∨R∨Q)∧(P∨R∨¬Q)∧(P∨¬Q∨R)∧(P∨¬Q∨¬R)∧(¬P∨Q∨R)∧(¬P∨Q∨¬R) Dept of CSE,RGMCET Page 23  Mathematical Foundation of Computer Science Unit-II Syllabus: Predicates: Rules of inference, Consistency, Predicate calculus: Free and bounded variable, Quantifiers: Universal Quantifiers, Existential Quantifiers. Rules of inference: The two rules of inference are called rules P and T. Rule P: A premise may be introduced at any point in the derivation. Rule T: A formula S may be introduced in a derivation if s is tautologically implied by any one or more of the preceding formulas in the derivation. Before proceeding the actual process of derivation, some important list of implications and equivalences are given in the following tables. Implications I1 P٨Q =>P } Simplification I2 PQ٨ =>Q I3 P=>PVQ } Addition I4 Q =>PVQ I5 7P => P→ Q I6 Q => P→ Q I7 7(P→Q) =>P I8 7(P → Q) => 7Q I9 P, Q => P ٨ Q I10 7P, PVQ => Q ( disjunctive syllogism) I11 P, P→ Q => Q ( modus ponens ) I12 7Q, P → Q => 7P (modus tollens ) I13 P → Q, Q → R => P → R ( hypothetical syllogism) I14 P V Q, P → Q, Q → R => R (dilemma) Equivalences Dept of CSE,RGMCET Page 24  Mathematical Foundation of Computer Science E1 77P P E2 P ٨ Q Q ٨ P } Commutative laws E3 P V Q Q V P E4 (P ٨ Q) ٨ R P ٨ (Q ٨ R) } Associative laws E5 (P V Q) V R PV (Q V R) E6 P ٨ (Q V R) (P ٨ Q) V (P ٨ R) } Distributive laws E7 P V (Q ٨ R) (P V Q) ٨ (PVR) E8 7(P ٨ Q) 7P V7Q E9 7(P V Q) 7P ٨ 7Q } De Morgan‘s laws E10 P V P P E11 P ٨ P P E12 R V (P ٨ 7P) R E13 R ٨ (P V 7P) R E14 R V (P V 7P) T E15 R ٨ (P ٨ 7P) F E16 P → Q 7P V Q E17 7 (P→ Q) P ٨ 7Q E18 P→ Q 7Q → 7P E19 P → (Q → R) (P ٨ Q) → R E20 7(PD Q) P D 7Q E21 PDQ (P → Q) ٨ (Q → P) E22 (PDQ) (P ٨ Q) V (7 P ٨ 7Q) Dept of CSE,RGMCET Page 25  Mathematical Foundation of Computer Science Example 1.Show that R is logically derived from P → Q, Q → R, and P Solution. {1} (1) P→Q Rule P {2} (2) P Rule P {1, 2} (3) Q Rule (1), (2) and I11 {4} (4) Q→R Rule P {1, 2, 4} (5) R Rule (3), (4) and I11. Example 2.Show that S V R tautologically implied by ( P V Q) ٨ ( P → R) ٨ ( Q → S ). Solution. {1} (1) PVQ Rule P {1} (2) 7P → Q T, (1), E1 and E16 {3} (3) Q→S P {1, 3} (4) 7P → S T, (2), (3), and I13 {1, 3} (5) 7S → P T, (4), E13 and E1 {6} (6) P→R P {1, 3, 6} (7) 7S → R T, (5), (6), and I13 {1, 3, 6) (8) SVR T, (7), E16 and E1 Example 3. Show that 7Q, P→ Q => 7P Solution. {1} (1) P → Q Rule P {1} (2) 7P → 7Q T, and E 18 {3} (3) 7Q P {1, 3} (4) 7P T, (2), (3), and I11. Example 4.Prove that R ٨ ( P V Q ) is a valid conclusion from the premises PVQ , Q → R, P → M and 7M. Solution. {1} (1) P→M P {2} (2) 7M P {1, 2} (3) 7P T, (1), (2), and I12 {4} (4) PVQ P Dept of CSE,RGMCET Page 26  Mathematical Foundation of Computer Science {1, 2 , 4} (5) Q T, (3), (4), and I10. {6} (6) Q→R P {1, 2, 4, 6} (7) R T, (5), (6) and I11 {1, 2, 4, 6} (8) R ٨ (PVQ) T, (4), (7), and I9. There is a third inference rule, known as rule CP or rule of conditional proof. Rule CP: If we can derives s from R and a set of premises , then we can derive R → S from the set of premises alone. Note. 1. Rule CP follows from the equivalence E10 which states that ( P ٨ R ) → S óP → (R → S). 2. Let P denote the conjunction of the set of premises and let R be any formula The above equivalence states that if R is included as an additional premise and S is derived from P ٨ R then R → S can be derived from the premises P alone. 3. Rule CP is also called the deduction theorem and is generally used if the conclusion is of the form R → S. In such cases, R is taken as an additional premise and S is derived from the given premises and R. Example 5.Show that R → S can be derived from the premises P → (Q → S), 7R V P , and Q. Solution. {1} (1) 7R V P P {2} (2) R P, assumed premise {1, 2} (3) P T, (1), (2), and I10 {4} (4) P → (Q → S) P {1, 2, 4} (5) Q → S T, (3), (4), and I11 {6} (6) Q P {1, 2, 4, 6} (7) S T, (5), (6), and I11 {1, 4, 6} (8) R → S CP. Dept of CSE,RGMCET Page 27  Mathematical Foundation of Computer Science Example 6.Show that P → S can be derived from the premises, 7P V Q, 7Q V R, and R → S. Solution. {1} (1) 7P V Q P {2} (2) P P, assumed premise {1, 2} (3) Q T, (1), (2) and I11 {4} (4) 7Q V R P {1, 2, 4} (5) R T, (3), (4) and I11 {6} (6) R→S P {1, 2, 4, 6} (7) S T, (5), (6) and I11 {2, 7} (8) P→S CP Example 7. ” If there was a ball game , then traveling was difficult. If they arrived on time, then traveling was not difficult. They arrived on time. Therefore, there was no ball game”. Show that these statements constitute a valid argument. Solution. Let P: There was a ball game Q: Traveling was difficult. R: They arrived on time. Given premises are: P → Q, R → 7Q and R conclusion is: 7P {1} (1) P → Q P {2} (2) R → 7Q P {3} (3) R P {2, 3} (4) 7Q T, (2), (3), and I11 {1, 2, 3} (5) 7P T, (2), (4) and I12 Dept of CSE,RGMCET Page 28  Mathematical Foundation of Computer Science Consistency of premises: Consistency A set of formulas H1, H2, …, Hm is said to be consistent if their conjunction has the truth value T for some assignment of the truth values to be atomic appearing in H1, H2, …, Hm. Inconsistency If for every assignment of the truth values to the atomic variables, at least one of the formulas H1, H2, … Hm is false, so that their conjunction is identically false, then the formulas H1, H2, …, Hm are called inconsistent. A set of formulas H1, H2, …, Hm is inconsistent, if their conjunction implies a contradiction, that is H1٨ H2٨ … ٨ Hm => R ٨ 7R Where R is any formula. Note that R ٨ 7R is a contradiction and it is necessary and sufficient that H1, H2, …,Hm are inconsistent the formula. Indirect method of proof In order to show that a conclusion C follows logically from the premises H1, H2,…, Hm, we assume that C is false and consider 7C as an additional premise. If the new set of premises is inconsistent, so that they imply a contradiction, then the assumption that 7C is true does not hold simultaneously with H1٨ H2٨..… ٨ Hm being true. Therefore, C is true whenever H1٨ H2٨..… ٨ Hm is true. Thus, C follows logically from the premises H1, H2 ….., Hm. Example 8 Show that 7(P ٨ Q) follows from 7P٨ 7Q. Solution. We introduce 77 (P٨ Q) as an additional premise and show that this additional premise leads to a contradiction. {1} (1) 77(P٨ Q) P assumed premise {1} (2) P٨ Q T, (1) and E1 {1} (3) P T, (2) and I1 Dept of CSE,RGMCET Page 29  Mathematical Foundation of Computer Science {1} {4) 7P٨7Q P {4} (5) 7P T, (4) and I1 {1, 4} (6) P٨ 7P T, (3), (5) and I9 Here (6) P٨ 7P is a contradiction. Thus {1, 4} viz. 77(P٨ Q) and 7P٨ 7Q leads to a contradiction P ٨ 7P. Example 9Show that the following premises are inconsistent. 1. If Jack misses many classes through illness, then he fails high school. 2. If Jack fails high school, then he is uneducated. 3. If Jack reads a lot of books, then he is not uneducated. 4. Jack misses many classes through illness and reads a lot of books. Solution. P: Jack misses many classes. Q: Jack fails high school. R: Jack reads a lot of books. S: Jack is uneducated. The premises are P→ Q, Q → S, R→ 7S and P٨ R {1} (1) P→Q P {2} (2) Q→ S P {1, 2} (3) P → S T, (1), (2) and I13 {4} (4) R→ 7S P {4} (5) S → 7R T, (4), and E18 {1, 2, 4} (6) P→7R T, (3), (5) and I13 {1, 2, 4} (7) 7PV7R T, (6) and E16 {1, 2, 4} (8) 7(P٨R) T, (7) and E8 {9} (9) P٨ R P {1, 2, 4, 9) (10) (P٨ R) ٨ 7(P٨ R) T, (8), (9) and I9 The rules above can be summed up in the following table. The "Tautology" column shows how to interpret the notation of a given rule. Dept of CSE,RGMCET Page 30  Mathematical Foundation of Computer Science Rule of inference Tautology Name Addition Simplification Conjunction Modus ponens Modus tollens Hypothetical syllogism Disjunctive syllogism Resolution Proof of contradiction: The "Proof by Contradiction" is also known as reductio ad absurdum, which is probably Latin for "reduce it to something absurd". Here's the idea: 1. Assume that a given proposition is untrue. Dept of CSE,RGMCET Page 31  Mathematical Foundation of Computer Science 2. Based on that assumption reach two conclusions that contradict each other. This is based on a classical formal logic construction known as Modus Tollens: If P implies Q and Q is false, then P is false. In this case, Q is a proposition of the form (R and not R) which is always false. P is the negation of the fact that we are trying to prove and if the negation is not true then the original proposition must have been true. If computers are not "not stupid" then they are stupid. (I hear that "stupid computer!" phrase a lot around here.) Example: Lets prove that there is no largest prime number (this is the idea of Euclid's original proof). Prime numbers are integers with no exact integer divisors except 1 and themselves. 1. To prove: "There is no largest prime number" by contradiction. 2. Assume: There is a largest prime number, call it p. 3. Consider the number N that is one larger than the product of all of the primes smaller than or equal to p. N=1*2*3*5*7*11...*p + 1. Is it prime? 4. N is at least as big as p+1 and so is larger than p and so, by Step 2, cannot be prime. 5. On the other hand, N has no prime factors between 1 and p because they would all leave a remainder of 1. It has no prime factors larger than p because Step 2 says that there are no primes larger than p. So N has no prime factors and therefore must itself be prime (see note below). We have reached a contradiction (N is not prime by Step 4, and N is prime by Step 5) and therefore our original assumption that there is a largest prime must be false. Note: The conclusion in Step 5 makes implicit use of one other important theorem: The Fundamental Theorem of Arithmetic: Every integer can be uniquely represented as the product of primes. So if N had a composite (i.e. non-prime) factor, that factor would itself have prime factors which would also be factors of N. Dept of CSE,RGMCET Page 32  Mathematical Foundation of Computer Science Predicative logic: A predicate or propositional function is a statement containing variables. For instance ―x + 2 = 7‖, ―X is American‖, ―x < y‖, ―p is a prime number‖ are predicates. The truth value of the predicate depends on the value assigned to its variables. For instance if we replace x with 1 in the predicate ―x + 2 = 7‖ we obtain ―1 + 2 = 7‖, which is false, but if we replace it with 5 we get ―5 + 2 = 7‖, which is true. We represent a predicate by a letter followed by the variables enclosed between parenthesis: P (x), Q(x, y), etc. An example for P (x) is a value of x for which P (x) is true. A counterexample is a value of x for which P (x) is false. So, 5 is an example for ―x + 2 = 7‖, while 1 is a counterexample. Each variable in a predicate is assumed to belong to a universe (or domain) of discourse, for instance in the predicate ―n is an odd integer‖ ‘n‘ represents an integer, so the universe of discourse of n is the set of all integers. In ―X is American‖ we may assume that X is a human being, so in this case the universe of discourse is the set of all human beings. Free & Bound variables: Let's now turn to a rather important topic: the distinction between free variables and bound variables. Have a look at the following formula: The first occurrence of x is free, whereas the second and third occurrences of x are bound, namely by the first occurrence of the quantifier. The first and second occurrences of the variable y are also bound, namely by the second occurrence of the quantifier. Informally, the concept of a bound variable can be explained as follows: Recall that quantifications are generally of the form: or where may be any variable. Generally, all occurences of this variable within the quantification are bound. But we have to distinguish two cases. Look at the following formula to see why: Dept of CSE,RGMCET Page 33  Mathematical Foundation of Computer Science 1. may occur within another, embedded, quantification or , such as the in in our example. Then we say that it is bound by the quantifier of this embedded quantification (and so on, if there's another embedded quantification over within ). 2.Otherwise, we say that it is bound by the top-level quantifier (like all other occurences of in our example). Here's a full formal simultaneous definition of free and bound: 1.Any occurrence of any variable is free in any atomic formula. 2.No occurrence of any variable is bound in any atomic formula. 3.If an occurrence of any variable is free in or in , then that same occurrence is free in , , , and. 4. If an occurrence of any variable is bound in or in , then that same occurrence is bound in , , ,. Moreover, that same occurrence is bound in and as well, for any choice of variable y. 5.In any formula of the form or (where y can be any variable at all in this case) the occurrence of y that immediately follows the initial quantifier symbol is bound. 6.If an occurrence of a variable x is free in , then that same occurrence is free in and , for any variable y distinct from x. On the other hand, all occurrences of x that are free in , are bound in and in. If a formula contains no occurrences of free variables we call it a sentence Dept of CSE,RGMCET Page 34  Mathematical Foundation of Computer Science Quantifiers The variable of predicates is quantified by quantifiers. There are two types of quantifier in predicate logic − Universal Quantifier and Existential Quantifier. Universal Quantifier Universal quantifier states that the statements within its scope are true for every value of the specific variable. It is denoted by the symbol ∀ ∀xP(x) is read as for every value of x, P(x) is true.. Example − "Man is mortal" can be transformed into the propositional form ∀xP(x)∀xP(x) where P(x) is the predicate which denotes x is mortal and the universe of discourse is all men. Existential Quantifier Existential quantifier states that the statements within its scope are true for some values of the specific variable. It is denoted by the symbol ∃. ∃xP(x) is read as for some values of x, P(x) is true. Example − "Some people are dishonest" can be transformed into the propositional form ∃xP(x) where P(x) is the predicate which denotes x is dishonest and the universe of discourse is some people. Dept of CSE,RGMCET Page 35  Mathematical Foundation of Computer Science UNIT-III Relations Syllabus Relations: Relations, Properties of binary Relations, Types of relations: equivalence, compatibility and partial ordering relations, Hasse diagram. Lattices and its properties. Functions: introduction to Functions , types of functions. Introduction The elements of a set may be related to one another. For example, in the set of natural numbers there is the ‗less than‘ relation between the elements. The elements of one set may also be related to the elements another set. Binary Relation A binary relation between two sets A and B is a rule R which decides, for any elements, whether a is in relation R to b. If so,we write a R b.If a is not in relation R to b,then we shall write a /R b. We can also consider a R b as the ordered pair (a, b) in which case we can define a binary relation from A to B as a subset of A X B. This subset is denoted by the relation R. In general, any set of ordered pairs defines a binary relation. For example, the relation of father to his child is F = {(a, b) / a is the father of b} In this relation F, the first member is the name of the father and the second is the name of the child. The definition of relation permits any set of ordered pairs to define a relation. For example, the set S given by S = {(1, 2), (3, a), (b, a) ,(b, Joe)} Definition The domain D of a binary relation S is the set of all first elements of the ordered pairs in the relation.(i.e) D(S)= {a / $ b for which (a, b) Є S} Dept of CSE,RGMCET Page 36  Mathematical Foundation of Computer Science The range R of a binary relation S is the set of all second elements of the ordered pairs in the relation.(i.e) R(S) = {b / $ a for which (a, b) Є S}. For example For the relation S = {(1, 2), (3, a), (b, a) ,(b, Joe)} D(S) = {1, 3, b, b} and R(S) = {2, a, a, Joe} Let X and Y be any two sets. A subset of the Cartesian product X * Y defines a relation, say C. For any such relation C, we have D( C ) Í X and R( C) Í Y, and the relation C is said to from X to Y. If Y = X, then C is said to be a relation form X to X. In such case, c is called a relation in X. Thus any relation in X is a subset of X * X. The set X * X is called a universal relation in X, while the empty set which is also a subset of X * X is called a void relation in X. For example Let L denote the relation ―less than or equal to‖ and D denote the relation ―divides‖ where x D y means ― x divides y‖. Both L and D are defined on the set {1, 2, 3, 4} L = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)} D = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)} L Ç D = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)} =D Properties of Binary Relations: 1.reflexive Definition: A binary relation R in a set X is reflexive if, for every x Є X, x R x, That is (x, x) Є R, or R is reflexive in X ó (x) (x Є X ® x R x). For example  The relation £ is reflexive in the set of real numbers.  The set inclusion is reflexive in the family of all subsets of a universal set.  The relation equality of set is also reflexive.  The relation is parallel in the set lines in a plane. Dept of CSE,RGMCET Page 37  Mathematical Foundation of Computer Science  The relation of similarity in the set of triangles in a plane is reflexive. Examples: (i). If R1 = {(1, 1), (1, 2), (2, 2), (2, 3), (3, 3)} be a relation on A = {1, 2, 3}, then R1 is  a reflexive relation, since for every x ∈ A, (x, x) ∈ R1. (ii). If R2 = {(1, 1), (1, 2), (2, 3), (3, 3)} be a relation on A = {1, 2, 3}, then R2 is not a reflexive relation, since for every 2 ∈ A, (2, 2) R2. Symmetric Definition: A relation R in a set X is symmetric if for every x and y in X, whenever x R y, then y R x.(i.e) R is symmetric in X ó (x) (y) (x Є X ٨ y Є X ٨ x R y ® y R x} For example  The relation equality of set is symmetric.  The relation of similarity in the set of triangles in a plane is symmetric.  The relation of being a sister is not symmetric in the set of all people.  However, in the set females it is symmetric. Example. If R3 = {(1, 1), (1, 2), (1, 3), (2, 2), (2, 1), (3, 1)} be a relation on A = {1, 2, 3}, then R3 is a symmetric relation. Transitive Definition: A relation R in a set X is transitive if, for every x, y, and z are in X, whenever x R y and y R z , then x R z. (i.e) R is transitive in X ó (x) (y) (z) (x Є X٨ y Є X٨ z Є X ٨ x R y٨ y R z® x R z) For example  The relations , ³ and = are transitive in the set of real numbers  The relations Í, Ì, Ê, É and equality are also transitive in the family of sets.  The relation of similarity in the set of triangles in a plane is transitive.  Definition:A relation R in a set x is anti symmetric if , for every x and y in X, whenever x R y and y R x, then x = y. Symbolically,(x) (y) (x Є X ٨ y Є X ٨ x R y ٨ y R x ® x = y) Dept of CSE,RGMCET Page 38  Mathematical Foundation of Computer Science Example:If R4 = {(1, 2), (2, 2), (2, 3)} on A = {1, 2, 3} is an antisymmetric. Equivalence Relation: Definition:A relation R in a set A is called an equivalence relation if  a R a for every i.e. R is reflexive  a R b => b R a for every a, b Є A i.e. R is symmetric  a R b and b R c => a R c for every a, b, c Є A, i.e. R is transitive. For example  The relation equality of numbers on set of real numbers.  The relation being parallel on a set of lines in a plane. Problem1: Let us consider the set T of triangles in a plane. Let us define a relation R in T as R= {(a, b) / (a, b Є T and a is similar to b} We have to show that relation R is an equivalence relation Solution :  A triangle a is similar to itself. a R a  If the triangle a is similar to the triangle b, then triangle b is similar to the triangle a then a R b => b R a  If a is similar to b and b is similar to c, then a is similar to c (i.e) a R b and b R c => a R c. Hence R is an equivalence relation. Problem 2: Let x = {1, 2, 3, … 7} and R = {(x, y) / x – y is divisible by 3} Show that R is an equivalence relation. Solution: For any a Є X, a- a is divisible by 3, Hence a R a, R is reflexive For any a, b Є X, if a – b is divisible by 3, then b – a is also divisible by 3, Dept of CSE,RGMCET Page 39  Mathematical Foundation of Computer Science R is symmetric. For any a, b, c Є, if a R b and b R c, then a – b is divisible by 3 and b–c is divisible by 3. So that (a – b) + (b – c) is also divisible by 3, hence a – c is also divisible by 3. Thus R is transitive. Hence R is equivalence. Problem3 Let Z be the set of all integers. Let m be a fixed integer. Two integers a and b are said to be congruent modulo m if and only if m divides a-b, in which case we write a º b (mod m). This relation is called the relation of congruence modulo m and we can show that is an equivalence relation. Solution :  a - a=0 and m divides a – a (i.e) a R a, (a, a) Є R, R is reflexive.  a R b = m divides a-b m divides b - a b º a (mod m) bRa that is R is symmetric.  a R b and b R c => a ºb (mod m) and bº c (mod m) o m divides a – b and m divides b-c o a – b = km and b – c = lm for some k ,l Є z o (a – b) + (b – c) = km + lm o a – c = (k +l) m o aº c (mod m) o aRc o R is transitive Hence the congruence relation is an equivalence relation. Dept of CSE,RGMCET Page 40  Mathematical Foundation of Computer Science Equivalence Classes: Let R be an equivalence relation on a set A. For any a ЄA, the equivalence class generated by a is the set of all elements b Є A such a R b and is denoted [a]. It is also called the R – equivalence class and denoted by a Є A. i.e., [a] = {b Є A / b R a} Let Z be the set of integer and R be the relation called ―congruence modulo 3‖ defined by R = {(x, y)/ xÎ Z Ù yÎZ Ù (x-y) is divisible by 3} Then the equivalence classes are = {… -6, -3, 0, 3, 6, …} = {…, -5, -2, 1, 4, 7, …} = {…, -4, -1, 2, 5, 8, …} Composition of binary relations: Definition:Let R be a relation from X to Y and S be a relation from Y to Z. Then the relation R o S is given by R o S = {(x, z) / xÎX Ù z Î Z Ù y Î Y such that (x, y) Î R Ù (y, z) Î S)} is called the composite relation of R and S. The operation of obtaining R o S is called the composition of relations. Example: Let R = {(1, 2), (3, 4), (2, 2)} and S = {(4, 2), (2, 5), (3, 1),(1,3)} Then R o S = {(1, 5), (3, 2), (2, 5)} and S o R = {(4, 2), (3, 2), (1, 4)} It is to be noted that R o S ≠ S o R. Also Ro(S o T) = (R o S) o T = R o S o T Note: We write R o R as R2; R o R o R as R3 and so on. Definition Let R be a relation from X to Y, a relation R from Y to X is called the converse of R, where the ordered pairs of Ř are obtained by interchanging the numbers in each of the ordered pairs of R. This means for x Î X and y Î Y, that x R y ó y Ř x. Then the relation Ř is given by R = {(x, y) / (y, x) Î R} is called the converse of R Dept of CSE,RGMCET Page 41  Mathematical Foundation of Computer Science Example: Let R = {(1, 2),(3, 4),(2, 2)} Then Ř = {(2, 1),(4, 3),(2, 2)} Note: If R is an equivalence relation, then Ř is also an equivalence relation. Partial Ordering Relations: Definition A binary relation R in a set P is called a partial order relation or a partial ordering in P if R isreflexive, ant symmetric, and transitive. i.e., aRa for all a ∈ P aRb and bRa ⇒ a = b aRb and bRc ⇒ aRc A set P together with a partial ordering R is called a partial ordered set or poset. The relation R is often denoted by the symbol ≤ which is different from the usual less than equal to symbol. Thus, if ≤ is a partial order in P , then the ordered pair (P, ≤) is called a poset. Example: Show that the relation ‖greater than or equal to‖ is a partial ordering on the set of integers. Solution: Let Z be the set of all integers and the relation R =≥ (i). Since a ≥ a for every integer a, the relation ≥ is reflexive. (ii). Let a and b be any two integers. Let aRb and bRa ⇒ a ≥ b and b ≥ a ⇒a=b ∴ The relation≥ is antisymmetric. (iii).Let a, b and c be any three integers. Let aRb and bRc ⇒ a ≥ b and b ≥ c ⇒a≥c ∴ The relation Let aRb and bRc ⇒ a ≥ b and b ≥ c ⇒a≥c ∴ The relation≥ is transitive. Since the relation ≥ is reflexive, antisymmetric and transitive,≥ is partial ordering on the set of integers. Therefore, (Z, ≥) is a poset Dept of CSE,RGMCET Page 42  Mathematical Foundation of Computer Science Hasse Diagram: A Hasse diagram is a digraph for a poset which does not have loops and arcs implied by the transitivity. Example 10: For the relation {< a, a >, < a, b >, < a, c >, < b, b >, < b, c >, < c, c >} on set {a, b,c}, the Hasse diagram has the arcs {< a, b >, < b, c >} as shown below. Ex: Let A be a given finite set and r(A) its power set. Let Í be the subset relation on the elements of r(A). Draw Hasse diagram of (r(A), Í) for A = {a, b, c} Dept of CSE,RGMCET Page 43  Mathematical Foundation of Computer Science Functions: Introduction A function is a special type of relation. It may be considered as a relation in which each element of the domain belongs to only one ordered pair in the relation. Thus a function from A to B is a subset of A X B having the property that for each a ЄA, there is one and only one b Є B such that (a, b) Î G. Definition Let A and B be any two sets. A relation f from A to B is called a function if for every a Є A there is a unique b Є B such that (a, b) Є f. Note that the definition of function requires that a relation must satisfy two additional conditions in order to qualify as a function. The first condition is that every a Є A must be related to some b Є B, (i.e) the domain of f must be A and not merely subset of A. The second requirement of uniqueness can be expressed as (a, b) Є f ٨ (b, c) Є f => b = c Intuitively, a function from a set A to a set B is a rule which assigns to every element of A, a unique element of B. If a ЄA, then the unique element of B assigned to a under f is denoted by f (a).The usual notation for a function f from A to B is f: A® B defined by a ® f (a) where a Є A, f(a) is called the image of a under f and a is called pre image of f(a).  Let X = Y = R and f(x) = x2 + 2. Df = R and Rf Í R.  Let X be the set of all statements in logic and let Y = {True, False}. A mapping f: X®Y is a function.  A program written in high level language is mapped into a machine language by a compiler. Similarly, the output from a compiler is a function of its input.  Let X = Y = R and f(x) = x2 is a function from X ® Y,and g(x2) = x is not a function from X ® Y. Dept of CSE,RGMCET Page 44  Mathematical Foundation of Computer Science A mapping f: A ® B is called one-to-one (injective or 1 –1) if distinct elements of A are mapped into distinct elements of B. (i.e) f is one-to-one if a1 = a2 => f (a1) = f(a2) or equivalently f(a1) ¹ f(a2) => a1 ¹ a2 For example, f: N ® N given by f(x) = x is 1-1 where N is the set of a natural numbers. A mapping f: A® B is called onto (surjective) if for every b Є B there is an a Є A such that f (a) = B. i.e. if every element of B has a pre-image in A. Otherwise it is called into. For example, f: Z®Z given by f(x) = x + 1 is an onto mapping. A mapping is both 1-1 and onto is called bijective. For example f: R®R given by f(x) = X + 1 is bijective. Definition: A mapping f: R® b is called a constant mapping if, for all aÎA, f (a) = b, a fixed element. For example f: Z®Z given by f(x) = 0, for all x ÎZ is a constant mapping. Definition A mapping f: A®A is called the identity mapping of A if f (a) = a, for all aÎA. Usually it is denoted by IA or simply I. Composition of functions: If f: A®B and g: B®C are two functions, then the composition of functions f and g, denoted by g o f, is the function is given by g o f : A®C and is given by g o f = {(a, c) / a Є A ٨ c Є C ٨ $bÎ B ': f(a)= b ٨ g(b) = c} and (g of)(a) = ((f(a)) Example 1: Consider the sets A = {1, 2, 3},B={a, b} and C = {x, y}. Let f: A® B be defined by f (1) = a ; f(2) = b and f(3)=b and Let g: B® C be defined by g(a) = x and g(b) = y (i.e) f = {(1, a), (2, b), (3, b)} and g = {(a, x), (b, y)}. Then g o f: A®C is defined by (g of) (1) = g (f(1)) = g(a) = x Dept of CSE,RGMCET Page 45  Mathematical Foundation of Computer Science (g o f) (2) = g (f(2)) = g(b) = y (g o f) (3) = g (f(3)) = g(b) = y i.e., g o f = {(1, x), (2, y),(3, y)} If f: A® A and g: A®A, where A= {1, 2, 3}, are given by f = {(1, 2), (2, 3), (3, 1)} and g = {(1, 3), (2, 2), (3, 1)} Then g of = {(1, 2), (2, 1), (3, 3)}, fog= {(1, 1), (2, 3), (3, 2)} f of = {(1, 3), (2, 1), (3, 2)} and gog= {(1, 1), (2, 2), (3, 3)} Example 2: Let f(x) = x+2, g(x) = x – 2 and h(x) = 3x for x Î R, where R is the set of real numbers. Then f o f = {(x, x+4)/xÎ R} f o g = {(x, x)/ x Î X} g o f = {(x, x)/ xÎ X} g o g = {(x, x-4)/x Î X} h o g = {(x,3x-6)/ x Î X} h o f = {(x, 3x+6)/ x Î X} Inverse functions: Let f: A® B be a one-to-one and onto mapping. Then, its inverse, denoted by f -1 is given by f - 1 = {(b, a) / (a, b) Î f} Clearly f-1: B® A is one-to-one and onto. Also we observe that f o f -1 = IB and f -1o f = IA. If f -1 exists then f is called invertible. For example:Let f: R ®R be defined by f(x) = x + 2 Then f -1: R® R is defined by f -1(x) = x - 2 Dept of CSE,RGMCET Page 46  Mathematical Foundation of Computer Science Theorem: Let f: X ®Y and g: Y ® Z be two one to one and onto functions. Then gof is also one to one and onto function. Proof Let f:X ® Y g : Y ® Z be two one to one and onto functions. Let x1, x2 Î X  g o f (x1) = g o f(x2),  g (f(x1)) = g(f(x2)),  g(x1) = g(x2) since [f is 1-1] x1 = x2 since [ g is 1-1} so that gof is 1-1. By the definition of composition, gof : X ® Z is a function. We have to prove that every element of z Î Z an image element for some x Î X under gof. Since g is onto $ y ÎY ': g(y) = z and f is onto from X to Y, $ x ÎX ': f(x) = y. Now, gof (x) = g ( f ( x)) = g(y) [since f(x) = y] = z [since g(y) = z] which shows that gof is onto. Theorem (g o f) -1 = f -1 o g -1 (i.e) the inverse of a composite function can be expressed in terms of the composition of the inverses in the reverse order. Proof. f: A ® B is one to one and onto. g: B ® C is one to one and onto. gof: A ® C is also one to one and onto. Þ (gof) -1: C ® A is one to one and onto. Dept of CSE,RGMCET Page 47  Mathematical Foundation of Computer Science Let a Î A, then there exists an element b Î b such that f (a) = b Þ a = f-1 (b). Now b Î B Þ there exists an element c Î C such that g (b) = c Þ b = g -1(c). Then (gof)(a) = g[f(a)] = g(b) = c Þ a = (gof) -1(c). …….(1) (f -1 o g-1) (c) = f -1(g -1 (c)) = f -1(b) = a Þ a = (f -1 o g -1)( c ) ….(2) Combining (1) and (2), we have (gof) -1 = f -1 o g -1 Theorem: If f: A ® B is an invertible mapping , then f o f -1 = I B and f-1 o f = IA Proof: f is invertible, then f -1 is defined by f(a) = b ó f-1(b) = a where a Î A and bÎ B. Now we have to prove that f of -1 = IB. Let bÎ B and f -1(b) = a, a Î A then fof-1(b) = f(f-1(b)) = f(a) = b therefore f o f -1 (b) = b " b Î B => f o f -1 = IB Now f -1 o f(a) = f -1 (f(a)) = f -1 (b) = a therefore f -1 o f(a) = a " a Î A => f -1 o f = IA. Lattice and its Properties: Introduction: A lattice is partially ordered set (L, £) in which every pair of elements a, b ÎL has a greatest lower bound and a least upper bound. The glb of a subset, {a, b} Í L will be denoted by a * b and the lub by a Å b.. Usually, for any pair a, b Î L, GLB {a, b} = a * b, is called the meet or product and LUB{a, b} = a Å b, is called the join or sum of a and b. Example1 Consider a non-empty set S and let P(S) be its power set. The relation Í ―contained in‖ is a partial ordering on P(S). For any two subsets A, BÎ P(S) GLB {A, B} and LUB {A, B} are evidently A Ç B and A È B respectively. Dept of CSE,RGMCET Page 48  Mathematical Foundation of Computer Science Example2 Let I+ be the set of positive integers, and D denote the relation of ―division‖ in I+ such that for any a, b Î I+ , a D b iff a divides b. Then (I+, D) is a lattice in which the join of a and b is given by the least common multiple(LCM) of a and b, that is, a Å b = LCM of a and b, and the meet of a and b, that is , a * b is the greatest common divisor (GCD) of a and b. A lattice can be conveniently represented by a diagram. For example, let Sn be the set of all divisors of n, where n is a positive integer. Let D denote the relation ―division‖ such that for any a, b Î Sn, a D b iff a divides b. Then (Sn, D) is a lattice with a * b = gcd(a, b) and a Å b = lcm(a, b). Take n=6. Then S6 = {1, 2, 3, 6}. It can be represented by a diagram in Fig(1). Take n=8. Then S8 = {1, 2, 4, 8} Two lattices can have the same diagram. For example if S = {1, 2, 3} then (p(s), Í ) and (S6,D) have the same diagram viz. fig(1), but the nodes are differently labeled. We observe that for any partial ordering relation £ on a set S the converse relation ³ is also partial ordering relation on S. If (S, £) is a lattice With meet a * b and join a Å b , then (S, ³ ) is the also a lattice with meet a Å b and join a * b i.e., the GLB and LUB get interchanged. Thus we have the principle of duality of lattice as follows. Any statement about lattices involving the operations ^ and V and the relations £ and ³ remains true if ^, V, ³ and £ are replaced by V, ^, £ and ³ respectively. The operation ^ and V are called duals of each other as are the relations £ and ³.. Also, the lattice (L, £) and (L, ³) are called the duals of each other. Properties of lattices: Let (L, £) be a lattice with the binary operations * and Å then for any a, b, c Î L,  a*a=a aÅa =a (Idempotent)  a* b=b*a , aÅ b = bÅ a (Commutative)  (a * b) * c = a * (b * c) , (a Å ) Å c = a Å (b Å c) Dept of CSE,RGMCET Page 49  Mathematical Foundation of Computer Science o (Associative)  a * (a Å b) = a , a Å (a * b ) = a (absorption) For any a ÎL, a £ a, a £ LUB {a, b} => a £ a * (a Å b). On the other hand, GLB {a, a Å b} £ a i.e., (a Å b) Å a, hence a * (a Å b) = a Theorem 1 Let (L, £) be a lattice with the binary operations * and Å denote the operations of meet and join respectively For any a, b Î L, a£b óa*b=aóaÅb=b Proof Suppose that a £ b. we know that a £ a, a £ GLB {a, b}, i.e., a £ a * b. But from the definition of a * b, we get a * b £ a. Hence a £ b => a * b = a ………………………… (1) Now we assume that a * b = a; but is possible only if a £ b, that is a * b = a => a £ b ………………………… (2) From (1) and (2), we get a £ b ó a * b = a. Suppose a * b = a. then b Å (a * b) = b Å a = a Å b ……………………. (3) but b Å ( a * b) = b ( by iv) …………………….. (4) Hence a Å b = b, from (3) => (4) Suppose aÅ b = b, i.e., LUB {a, b} = b, this is possible only if a£ b, thus(3) => (1) (1) => (2) => (3) => (1). Hence these are equivalent. Let us assume a * b = a. Now (a * b) Å b = a Å b We know that by absorption law , (a * b) Å b = b so that a Å b = b, therefore a * b = a Þ a Å b = b (5) similarly, we can prove a Å b = b Þ a * b = a (6) From (5) and (6), we get Dept of CSE,RGMCET Page 50  Mathematical Foundation of Computer Science a*b=aÛaÅb =b Hence the theorem. Theorem2 For any a, b, c Î L, where (L, £) is a lattice. b £ c => { a * b £ a * c and { aÅb£ aÅc Proof Suppose b £ c. we have proved that b £ a ó b * c = b…….. (1) Now consider (a * b ) * (a * c) = (a * a) * (b * c) (by Idempotent) = a * (b * c) = a*b (by (1)) Thus (a * b) * (a * c ) = a * b which => (a * b ) £ (a * c) Similarly (a Å b) Å ( a Å c) = (a Å a) Å (b Å c) = a Å (b Å c) =aÅ c which => (a Å b ) £ (a Å c ) note:These properties are known as isotonicity. Dept of CSE,RGMCET Page 51  Mathematical Foundation of Computer Science Unit-IV: Algebraic Structures Syllabus: Algebraic structures: Algebraic systems with examples and general properties, semi groups and monoids, groups & its types, Introduction to homomorphism and Isomorphism (Proof of theorems are not required) Algebraic systems N = {1,2,3,4,….. } = Set of all natural numbers. Z = { 0, ± 1, ± 2, ± 3, ± 4 , ….. } = Set of all integers. Q = Set of all rational numbers. R = Set of all real numbers. Binary Operation: The binary operator * is said to be a binary operation (closed operation) on a non- empty set A, if a * b ∈ A for all a, b ∈ A (Closure property). Ex: The set N is closed with respect to addition and multiplication but not w.r.t subtraction and division. Algebraic System: A set A with one or more binary(closed) operations defined on it is called an algebraic system. Ex: (N, + ), (Z, +, – ), (R, +,. , – ) are algebraic systems. Properties Associativity: Let * be a binary operation on a set A. The operation * is said to be associative in A. if (a * b) * c = a *( b* c) for all a, b, c in A Dept of CSE,RGMCET Page 52  Mathematical Foundation of Computer Science Identity: For an algebraic system (A, *), an element ‗e‘ in A is said to be an identity element of A if a * e = e * a = a for all a ∈ A. Note: For an algebraic system (A, *), the identity element, if exists, is unique. Inverse: Let (A, *) be an algebraic system with identity ‗e‘. Let a be an element in A. An element b is said to be inverse of A. if a * b = b * a = e Dept of CSE,RGMCET Page 53  Mathematical Foundation of Computer Science Semi groups Semi Group: An algebraic system (A, *) is said to be a semi group if 1. * is closed operation on A. 2. * is an associative operation, for all a, b, c in A. Ex. (N, +) is a semi group. Ex. (N,.) is a semi group. Ex. (N, – ) is not a semi group. Monoid An algebraic system (A, *) is said to be a monoid if the following conditions are satisfied. 1) * is a closed operation in A. 2) * is an associative operation in A. 3) There is an identity in A. Ex. Show that the set ‗N‘ is a monoid with respect to multiplication. Solution: Here, N = {1,2,3,4,……} Closure property : 1We know that product of two natural numbers is again a natural number. i.e., a.b = b.a for all a,b ∈ N ∴ Multiplication is a closed operation. Associativity : Multiplication of natural numbers is associative. i.e., (a.b).c = a.(b.c) for all a,b,c ∈ N Identity : We have, 1 ∈ N such that Dept of CSE,RGMCET Page 54  Mathematical Foundation of Computer Science a.1 = 1.a = a for all a ∈ N. ∴ Identity element exists, and 1 is the identity element. Hence, N is a monoid with respect to multiplication Examples Ex. Let (Z, *) be an algebraic structure, where Z is the set of integers and the operation * is defined by n * m = maximum of (n, m). Show that (Z, *) is a semi group. Is (Z, *) a monoid ?. Justify your answer. Dept of CSE,RGMCET Page 55  Mathematical Foundation of Computer Science Solution: Let a , b and c are any three integers. Closure property: Now, a * b = maximum of (a, b) ∈ Z for all a,b ∈ Z Associativity : (a * b) * c = maximum of {a,b,c} = a * (b * c) ∴ (Z, *) is a semi group. Identity : There is no integer x such that a * x = maximum of (a, x) = a for all a ∈ Z ∴ Identity element does not exist. Hence, (Z, *) is not a monoid. Ex. Show that the set of all strings ‗S‘ is a monoid under the operation ‗concatenation of strings‘. Is S a group w.r.t the above operation? Justify your answer. Solution: Let us denote the operation ‗concatenation of strings‘ by +. Let s1, s2, s3 are three arbitrary strings in S. Closure property: Concatenation of two strings is again a string. i.e., s1+s2 ∈ S Associativity: Concatenation of strings is associative. (s1+ s2 ) + s3 = s1+ (s2 + s3 ) Identity: We have null string , l ∈ S such that s1 + l = S. ∴ S is a monoid. Note: S is not a group, because the inverse of a non empty string does not exist under concatenation of strings. 3.2 Groups Group: An algebraic system (G, *) is said to be a group if the following conditions are satisfied. 1) * is a closed operation. Dept of CSE,RGMCET Page 56  Mathematical Foundation of Computer Science 2) * is an associative operation. 3) There is an identity in G. 4) Every element in G has inverse in G. Dept of CSE,RGMCET Page 57  Mathematical Foundation of Computer Science Abelian group (Commutative group): A group (G, *) is said to be abelian (or commutative) if a * b = b * a "a, b ∈ G. Properties In a Group (G, * ) the following properties hold good 1. Identity element is unique. 2. Inverse of an element is unique. 3. Cancellation laws hold good a * b = a * c => b = c (left cancellation law) a * c = b * c => a = b (Right cancellation law) 4. (a * b) -1 = b-1 * a-1 In a group, the identity element is its own inverse. Order of a group : The number of elements in a group is called order of the group. Finite group: If the order of a group G is finite, then G is called a finite group. Ex1. Show that, the set of all integers is an abelian group with respect to addition. Solution: Let Z = set of all integers. Let a, b, c are any three elements of Z. 1. Closure property : We know that, Sum of two integers is again an integer. i.e., a + b ∈ Z for all a,b ∈ Z 2. Associativity: We know that addition of integers is Dept of CSE,RGMCET Page 58  Mathematical Foundation of Computer Science associative. i.e., (a+b)+c = a+(b+c) for all a,b,c ∈ Z. 3. Identity : We have 0 ∈ Z and a + 0 = a for all a ∈ Z. ∴ Identity element exists, and ‗0‘ is the identity element. 4. Inverse: To each a ∈ Z , we have – a ∈ Z such that a+(–a)=0 Each element in Z has an inverse. 5. Commutativity: We know that addition of integers is commutative. i.e., a + b = b +a for all a,b ∈ Z. Hence, ( Z , + ) is an abelian group. Dept of CSE,RGMCET Page 59  Mathematical Foundation of Computer Science Ex2. Show that set of all non zero real numbers is a group with respect to multiplication. Solution: Let R* = set of all non zero real numbers. Let a, b, c are any three elements of R*. 1. Closure property : We know that, product of two nonzero real numbers is again a nonzero real number. i.e., a. b ∈ R* for all a,b ∈ R*. 2. Associativity: We know that multiplication of real numbers is associative. i.e., (a.b).c = a.(b.c) for all a,b,c ∈ R*. 3. Identity : We have 1 ∈ R and a.1 = a for all a ∈ R. * * ∴ Identity element exists, and ‗1‘ is the identity element. 4. Inverse: To each a ∈ R* , we have 1/a ∈ R* such that a.(1/a) = 1 i.e., Each element in R* has an inverse. 5.Commutativity: We know that multiplication of real numbers is commutative. i.e., a. b = b. a for all a,b ∈ R*. Hence, ( R* ,. ) is an abelian group. Note: Show that set of all real numbers ‗R‘ is not a group with respect to multiplication. Solution: We have 0 ∈ R. The multiplicative inverse of 0 does not exist. Hence. R is not a group. Dept of CSE,RGMCET Page 60  Mathematical Foundation of Computer Science Example: Let S be a finite set, and let F(S) be the collection of all functions f: S → S under the operation of composition of functions, then show that F(S) is a monoid. Is S a group w.r.t the above operation? Justify your answer. Solution: Let f1, f2, f3 are three arbitrary functions on S. Closure property: Composition of two functions on S is again a function on S. i.e., f1o f2 ∈ F(S) Associativity: Composition of functions is associative. Dept of CSE,RGMCET Page 61  Mathematical Foundation of Computer Science i.e., (f1 o f2 ) o f3 = f1 o (f2 o f3 ) Identity: We have identity function I : S→S such that f1 o I = f1. ∴ F(S) is a monoid. Note: F(S) is not a group, because the inverse of a non bijective function on S does not exist. Ex. If M is set of all non singular matrices of order ‗n x n‘. then show that M is a group w.r.t. matrix multiplication. Is (M, *) an abelian group?. Justify your answer. Solution: Let A,B,C ∈ M. 1. Closure property : Product of two non singular matrices is again a non singular matrix, because ½AB½ = ½A½. ½B½ ¹ 0 ( Since, A and B are nonsingular) i.e., AB ∈ M for all A,B ∈ M. 2. Associativity: Marix multiplication is associative. i.e., (AB)C = A(BC) for all A,B,C ∈ M. 3. Identity : We have In ∈ M and A In = A for all A ∈ M. ∴ Identity element exists, and ‗In‘ is the identity element. 4. Inverse: To each A ∈ M, we have A-1 ∈ M such that A A-1 = In i.e., Each element in M has an inverse. ∴ M is a group w.r.t. matrix multiplication. We know that, matrix multiplication is not commutative. Hence, M is not an abelian group. Ex. Show that the set of all positive rational numbers forms an abelian group under the composition * defined by a * b = (ab)/2. Solution: Let A = set of all positive rational numbers. Let a,b,c be any three elements of A. 1. Closure property: We know that, Product of two positive rational numbers is again a Dept of CSE,RGMCET Page 62  Mathematical Foundation of Computer Science rational number. Dept of CSE,RGMCET Page 63  Mathematical Foundation of Computer Science i.e., a *b ∈ A for all a,b ∈ A. 2. Associativity: (a*b)*c = (ab/2) * c = (abc) / 4 a*(b*c) = a * (bc/2) = (abc) / 4 3. Identity : Let e be the identity element. We have a*e = (a e)/2 …(1) , By the definition of * again, a*e = a …..(2) , Since e is the identity. From (1)and (2), (a e)/2 = a ⇒ e = 2 and 2 ∈ A. ∴ Identity element exists, and ‗2‘ is the identity element in A. 4. Inverse: Let a ∈ A let us suppose b is inverse of a. Now, a * b = (a b)/2 ….(1) (By definition of inverse.) Again, a * b = e = 2 …..(2) (By definition of inverse) From (1) and (2), it follows that (a b)/2 = 2 => b = (4 / a) ∈ A ∴ (A ,*) is a group. Commutativity: a * b = (ab/2) = (ba/2) = b * a Hence, (A,*) is an abelian group. Finite groups Ex. Show that G = {1, -1} is an abelian group under multiplication. Solution: The composition table of G is * 1 -1 1 1 -1 -1 -1 1 Dept of CSE,RGMCET Page 64  Mathematical Foundation of Computer Science 1. Closure property: Since all the entries of the composition table are the elements of the given set, the set G is closed under multiplication. 2. Associativity: The elements of G are real numbers, and we know that multiplication of real numbers is associative. 3. Identity : Here, 1 is the identity element and 1∈ G. 4. Inverse: From the composition table, we see that the inverse elements of 1 and – 1 are 1 and – 1 respectively. Hence, G is a group w.r.t multiplication. 5. Commutativity: The corresponding rows and columns of the table are identical. Therefore the binary operation. is commutative. Hence, G is an abelian group w.r.t. multiplication.. Ex. Show that G = {1, w, w2} is an abelian group under multiplication. Where 1, w, w2 are cube roots of unity. Solution: The composition table of G is * 1 w w2 1 1 w w2 w w w2 1 w2 w2 1 w Dept of CSE,RGMCET Page 65  Mathematical Foundation of Computer Science 1. Closure property: Since all the entries of the composition table are the elements of the given set, the set G is closed under multiplication. 2. Associativity: The elements of G are complex numbers, and we know that multiplication of complex numbers is associative. 3. Identity : Here, 1 is the identity element and 1∈ G. 4. Inverse: From the composition table, we see that the inverse elements of 1 w, w2 are 1, w2, w respectively. Hence, G is a group w.r.t multiplication. 5. Commutativity: The corresponding rows and columns of the table are identical. Therefore the binary operation. is commutative. Hence, G is an abelian group w.r.t. multiplication. Dept of CSE,RGMCET Page 66  Mathematical Foundation of Computer Science Modulo systems. Addition modulo m ( +m ) let m is a positive integer. For any two positive integers a and b Dept of CSE,RGMCET Page 67  Mathematical Foundation of Computer Science a +m b = a + b if a + b < m a +m b = r if a + b ³ m where r is the remainder obtained by dividing (a+b) with m. Multiplication modulo p ( *m) let p is a positive integer. For any two positive integers a and b a *m b = ab if a b < p a *m b = r if a b ³ p where r is the remainder obtained by dividing (ab) with p. Ex. 3 *5 4 = 2 , 5 *5 4 = 0 , 2 *5 2 = 4 Example : The set G = {0,1,2,3,4,5} is a group with respect to addition modulo 6. Solution: The composition table of G is +6 0 1 2 3 4 5 0 0 1 2 3 4 5 1 1 2 3 4 5 0 2 2 3 4 5 0 1 3 3 4 5 0 1 2 4 4 5 0 1 2 3 5 5 0 1 2 3 4 1. Closure property: Since all the entries of the composition table are the elements of the given set, the set G is closed under +6. 2. Associativity: The binary operation +6 is associative in G. for ex. (2 +6 3) +6 4 = 5 +6 4 = 3 and 2 +6 ( 3 +6 4 ) = 2 +6 1 = 3 Dept of CSE,RGMCET Page 68  Mathematical Foundation of Computer Science 3. Identity : Here, The first row of the table coincides with the top row. The element heading that row , i.e., 0 is the identity element. 4.. Inverse: From the composition table, we see that the inverse elements of 0, 1, 2, 3, 4. 5 are 0, 5, 4, 3, 2, 1 respectively Dept of CSE,RGMCET Page 69  Mathematical Foundation of Computer Science 5.Commutativity: The corresponding rows and columns of the table are identical. Therefore the binary operation +6 is commutative. Hence, (G, +6 ) is an abelian group. Example : The set G = {1,2,3,4,5,6} is a group with respect to multiplication modulo 7. Solution: The composition table of G is *7 1 2 3 4 5 6 1 1 2 3 4 5 6 2 2 4 6 1 3 5 3 3 6 2 5 1 4 4 4 1 5 2 6 3 5 5 3 1 6 4 2 6 6 5 4 3 2 1 1. Closure property: Since all the entries of the composition table are the elements of the given set, the set G is closed under *7. 2. Associativity: The binary operation *7 is associative in G. for ex. (2 *7 3) *7 4 = 6 *7 4 = 3 and 2 *7 ( 3 *7 4 ) = 2 *7 5 = 3 3. Identity : Here, The first row of the table coincides with the top row. The element heading that row , i.e., 1 is the identity element. 4.. Inverse: From the composition table, we see that the inverse elements of 1, 2, 3, 4. 5 6 are 1, 4, 5, 2, 5, 6 respectively. 5. Commutativity: The corresponding rows and columns of the table are identical. Therefore the binary operation *7 is commutative. Hence, (G, *7 ) is an abelian group. More on finite groups In a group with 2 elements, each element is its own inverse Dept of CSE,RGMCET Page 70  Mathematical Foundation of Computer Science In a group of even order there will be at least one element (other than identity element) which is its own inverse The set G = {0,1,2,3,4,…..m-1} is a group with respect to addition modulo m. Dept of CSE,RGMCET