2019 First Edition DDDiiissscccrrreeettteee MMMaaattthhheeemmmaaatttiiicccsss engineering handbook Arjun Singh GRAB YOUR COPY NOW !!! CONTENTS 1 THE FOUNDATIONS : LOGIC AND CH APTER . . METHOD OF PROOFS 1.1 PROPOSITIONAL LOGIC 1 SOLVED EXERCISE - 1.1 8 1.2 PROPOSITIONAL EQUIVALENCE 27 SOLVED EXERCISE - 1.2 28 1.3 PREDICATES AND QUANTIFIER 38 SOLVED EXERCISE - 1.3 43 1.4 NESTED QUANTIFIERS 58 SOLVED EXERCISE - 1.4 61 1.5 RULES OF INFERENCE 76 SOLVED EXERCISE - 1.5 78 1.6 INTRODUCTION TO PROOF 88 SOLVED EXERCISE-1.6 91 1.7 PROOF METHOD AND STRATEGY 96 SOLVED EXERCISE-1.7 98 2 SEQUENCE, INDUCTION AND RECURSION CH APTER . . 2.1 SEQUENCES AND SUMMATIONS 103 SOLVED EXERCISE -2.1 (2.4) 108 2.2 MATHEMATICAL INDUCTION 117 SOLVED EXERCISE - 2.2. (4.1) 120 2.3 STRONG INDUCTION 136 SOLVED EXERCISE -2.3 (4.2) 140 2.4 RECURSIVELY DEFINED FUNCTION 146 SOLVED EXERCISE- 2.4(4.3) 156 2.5 RECURSIVE ALGORITHMS 164 SOLVED EXERCISE- 2.5 (4.4) 167 2.6 PROGRAM CORRECTNESS 169 SOLVED EXERCISE-2.6 (4.5) 173 3 ADVANCE COUNTING TECHNIQUES CH APTER . . 3.1 RECURRENCE RELATION 177 SOLVED EXERCISE-3.1(6.1) 181 3.2 SOLVING RECURRENCE RELATION 190 SOLVED EXERCISE - 3.2 (6.2) 197 3.3 GENERATING FUNCTION 201 SOLVED EXERCISE-3.3(6.4) 209 3.4 INCLUSION AND EXCLUSION PRINCIPLE 221 SOLVED EXERCISE - 3.4 (6.5) 223 3.5 APPLICATION OF INCLUSION-EXCLUSION PRINCIPLE 227 SOLVED EXERCISE -3.5 (6.6) 229 4 RELATIONS CH APTER . . 4.1 RELATION AND THEIR PROPERTIES 232 SOLVED EXERCISE-4.1 (7.1) 241 4.2 n-ary RELATION 249 SOLVED EXERCISE-4.2(7.2) 251 4.3 REPRESENTATION OF RELATIONS 253 SOLVED EXERCISE-4.3 (7.3) 258 4.4 CLOSURE OF RELATIONS 265 SOLVED EXERCISE-4.4 (7.4) 276 4.5 EQUIVALENCE RELATIONS 283 SOLVED EXERCISE - 4.5 (7.5) 290 4.6 PARTIAL ORDERING RELATIONS 293 SOLVED EXERCISE - 4.6 (7.6) 294 5 GRAPH THEORY CH APTER . . 5.1 INTRODUCTION TO GRAPHS 301 SOLVED EXERCISE - 5.1 (8.1) 304 5.2 GRAPH TERMINOLOGY 308 SOLVED EXERCISE - 5.2 (8.2) 319 5.3 MATRIX REPRESENTATION OF GRAPHS 323 SOLVED EXERCISE - 5.3 (8.3) 328 5.4 PATHS AND CONNECTIVITY 334 SOLVED EXERCISE - 5.4 (8.4) 341 5.5 EULERIAN AND HAMILTONIAN GRAPH 345 SOLVED EXERCISE - 5.5 (8.5) 353 5.6 SHORTEST PATH PROBLEMS 357 SOLVED EXERCISE - 5.6 (8.6) 364 5.7 PLANAR GRAPHS 368 SOLVED EXERCISE - 5.7 (8.7) 373 5.8 GRAPH COLORING 377 SOLVED EXERCISE - 5.8 (8.8) 386 6 TREES CH APTER . . 6.1 INTRODUCTION TO TREES 390 SOLVED EXERCISE - 6.1 (9.1) 397 6.2 APPLICATION OF TREES 400 SOLVED EXERCISE-6.2(9.2) 404 6.3 TREE TRAVERSAL 413 SOLVED EXERCISE - 6.3 (9.3) 415 6.4 SPANNING TREES 419 SOLVED EXERCISE - 6.4 (9.4) 421 6.5 MINIMAL SPANNING TREE 425 7 ALGEBRAIC STRUCTURE CH APTER . . 7.1 INTRODUCTION TO GROUP 429 7.2 SUB GROUPS 434 7.3 COSETS AND LAGRANGE’S THEOREM 435 7.4 PERMUTATION GROUP 440 7.5 GROUP CODES 443 7.6 HOMOMORPHISM AND ISOMORPHISM OF GROUPS 445 7.7 NORMAL SUB GROUPS 446 7.8 RINGS, INTEGRAL DOMAINS, AND FIELDS 447 7.9 RING HOMOMORPHISM 450 SOLVED EXERCISE - 7(10) 453 8 LATTICES & BOOLEAN ALGEBRA CH APTER . . 8.1 LATTICE & ALGEBRAIC SYSTEMS 469 8.2 PRINCIPLE OF DUALITY 472 8.3 BASIC PROPERTIES OF ALGEBRAIC SYSTEMS DEFINED BY LATTICES 472 8.4 BOOLEAN LATTICES AND BOOLEAN ALGEBRAS 474 8.5 BOOLEAN FUNCTION AND BOOLEAN EXPRESSIONS 475 SOLVED EXERCISE - 8 (11) 477 ppp THE FOUNDATIONS : LOGIC AND METHOD OF PROOFS 1.1 PROPOSITIONAL LOGIC In this chapter we shall study mathematical logic, which is the basics of all kinds of reasoning. Mathematical logic has two aspects. On one hand it is analytical theory of art of reasoning whose goal is to systematize and codify principles of valid reasoning. It may be used to judge the correctness of statements which make up the chain. In this aspect logic may be called 'classical' mathematical logic. The other aspect of mathematical logic is inter-related with problems relating the foundation of Mathematics. G. Frege (1884- 1925) developed the idea, regarding a mathematical theory as applied system of logic. Principles of logic are valuable to problem analysis, programming and logic design. Proposition A number of words making a complete grammatical structure having a sense and meaning in logic or mathematics is called as entence. This assertion may be of two types - declarative and non-declarative. A Proposition or Statement is a declarative sentence that is either true of false, For example, “Three plus four equals seven” and “Three plus four equals eight” are both statements, the first because it is true and the second because it is false. Similarly “x + y > 2” is not a statement because for some values of x and y the sentence is true, whereas for others it is false. For instance, if x = 1 and y = 2, the sentence is true, if x = –3 and y = 1, this is false. The truth or falsity of a statement is called tirtsu th value. Since only two possible truth values are admitted this logic is sometimes called two - valued logic. Questions, exclamations and commands are not propositions. For examples, consider the following sentences. (a) The sun rises in the north. (b) 12 + 4 = 16 (c) {5,6}(cid:204){7,6,5} (d) Do you speak Hindi? (e) 4 – x = 8 (f) Close the door, (g) What a hot day! (h) We shall have chicken for dinner. The sentences (a), (b) and (c) are statements, the first is false and second and third are 2 Discrete Mathematical Structure true. (d) is a question, not a declarative sentence, hence it is not a statement. (e) is a declarative sentence, but not a statement, since it is true or false depends on the value of x. (f) is not a statement, it is a command. (g) is not a statement, it is exclamation. (h) is a statement since it is either true or false but not both, although one has to wait until dinner to find out if it is true or false. It is necessary to represent simple statements by letter p, q, r........... known as proposition variables (Note that usually a real variable is represented by the symbol x. This means that x is not a real number but can take a real value. Similarly, a propositional variable is not a proposition but can be replaced by a proposition) Propositional variables can only assume two values, true or false. There are also twop ropositional constants, T and F, that represent true and false, respectively. If p denotes the proposition “The sun sets in the west”, then instead of saying the proposition “ The sun sets in the west:” is false, one can simply say the value of p is F. Compound Proposition A proposition consisting of only a single propositional variable or a single propositional constant is called anp rimary, (primitive)p roposition or simply proposition; that is they can not be further subdivided. A proposition obtained from the combinations of two or more propositions by means of logical operators or connectives of two or more propositions or by negating a single proposition is referred tom olecular or composite or compound proposition. Connectives The words and phrases (or symbols) used to form compound propositions are called connectives. There are five basic connectives called Negation, Conjunction, Disjunction, Implication or Conditional and Equivalence or Biconditional. The following symbols are used to represent connectives. Symbol Connective Nature of the compound Symbolic Negation used word statement formed by the from connective ~, (cid:216) not Negation ~p ~(~p) = p (cid:217) and Conjuction p (cid:217) q (-p) (cid:218) (~q) (cid:218) or Disjunction p (cid:218) q (-p) (cid:217) (~q) (cid:222), fi if... ...... .then Implication (or Conditional) p (cid:222) q p (cid:217) (~q) (cid:219),<--> if and only if Equivalence (or Bi- p (cid:219) q [p (cid:217) (~q)] (cid:218) conditional) [ q (cid:217) (~p)] Discrete Mathematical Structure 3 Negation If p is any proposition, the negation of p, denoted by ~p or(cid:216) p and read as not p, is a proposition which is false when p is true and true when p is false. Consider the statement p: Paris is in England. Then the negation of p is the statement , ~p: It is not the case that Paris is in England. Usually it is written as ~p: Paris is not in England. Strictly speaking, not is not connective, since it does not join two statements and ~p is not really a compound statement. However, not is a unary operation for the collection of statements, and ~p is a statement if p is considered a statement. Note: 1. The following propositions all have the same meaning: p: All people are intelligent. q: Every person is intelligent. r: Each person is intelligent. s: Any person is intelligent. 2. The negation of the proposition is p: All students are intelligent. ~p: Some students are not intelligent. ~p: There exists a student who is not intelligent. ~p: There exist students who are not intelligent. ~p: At least are student is not intelligent. The negation of q: No student is intelligent, is ~q: Some students are intelligent. Note that “No student is intelligent” is not the negation of p; “All students are intelligent” is not the negation of q. Example -1 Find the negation of the following statements. Solution : Statement Negation a) p : You are my brother, ~p : You are not my brother. b) q : Think twice before doing this, ~q : Don’t think twice before doing this. c) r : There are many hurdles in this way. ~r : There is no hurdles in this way. d) s : He slaps me very hard, ~s : He doesn’t slaps me hard.