Discrete Mathematics T Veerarajan Pdf
Discrete Mathematics
T. Veerarajan
यह पुस्तक आपको कितनी अच्छी लगी?
फ़ाइल की गुणवत्ता क्या है?
पुस्तक की गुणवत्ता का मूल्यांकन करने के लिए यह पुस्तक डाउनलोड करें
डाउनलोड की गई फ़ाइलों की गुणवत्ता क्या है?
प्रकाशन:
McGraw-Hill Education
फ़ाइल 1-5 मिनट के भीतर आपके ईमेल पते पर भेजी जाएगी.
फ़ाइल 1-5 मिनट के भीतर आपकी Kindle पर डिलीवर हो जाएगी.
ध्यान रखें:आप जो भी पुस्तक Kindle को भेजना चाहें, उसे सत्यापित करना होगा. अपना मेलबॉक्स देखें कि इसमें Amazon Kindle Support की तरफ़ से सत्यापन ईमेल है या नहीं.
Discrete Mathematics About the Author T Veerarajan is Dean (Retd), Department of Mathematics, Velammal College of Engineering and Technology, Viraganoor, Madurai, Tamil Nadu. A Gold Medalist from Madras University, he has had a brilliant academic career all through. He has 53 years of teaching experience at undergraduate and postgraduate levels in various established engineering colleges in Tamil Nadu including Anna University, Chennai. Discrete Mathematics T Veerarajan Dean (Retd) Department of Mathematics Velammal College of Engineering and Technology Viraganoor, Madurai Tamil Nadu McGraw Hill Education (India) Private Limited CHENNAI McGraw Hill Education Offices Chennai New York St Louis San Francisco Auckland Bogotá Caracas Kuala Lumpur Lisbon London Madrid Mexico City Milan Montreal San Juan Santiago Singapore Sydney Tokyo Toronto McGraw Hill Education (India) Private Limited Published by McGraw Hill Education (India) Private Limited 444/1, Sri Ekambara Naicker Industrial Estate, Alapakkam, Porur, Chennai 600 116 Discrete Mathematics Copyright © 2019 by McGraw Hill Education (India) Private Limited. No part of this publication may be reproduced or distributed in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise or stored in a database or retrieval system without the prior written permission of the publishers. The program listings (if any) may be entered, stored and executed in a computer system, but they may not be reproduced for publication. This edition can be exported from India only by the publishers, McGraw Hill Education (India) Private Limited. 1 2 3 4 5 6 7 8 9 D102739 22 21 20 19 18 Printed and bound in India. Print-Book Edition ISBN (13): 978-93-5316-160-6 ISBN (10): 93-5316-160-6 E-Book Edition ISBN (13): 978-93-5316-161-3 ISBN (10): 93-5316-161-4 Director—Science & Engineering Portfolio: Vibha Mahajan Senior Portfolio Manager—Science & Engineering: Hemant K Jha Associate Portfolio Manager—Science & Engineering: Tushar Mishra Prod; uction Head: Satinder S Baveja Copy Editor: Taranpreet Kaur Assistant Manager—Production: Anuj K Shriwastava General Manager—Production: Rajender P Ghansela Manager—Production: Reji Kumar Information contained in this work has been obtained by McGraw Hill Education (India), from sources believed to be reliable. However, neither McGraw Hill Education (India) nor its authors guarantee the accuracy or completeness of any information published herein, and neither McGraw Hill Education (India) nor its authors shall be responsible for any errors, omissions, or damages arising out of use of this information. This work is published with the understanding that McGraw Hill Education (India) and its authors are supplying information but are not attempting to render engineering or other professional services. If such services are required, the assistance of an appropriate professional should be sought. Typeset at SaiTech Global, 1/575, Sector-1, Vaishali, Ghaziabad (UP) 201 010, and printed at Cover Designer: APS Compugraphics Cover Image Source: Shutterstock Cover Printer: Visit us at: www.mheducation.co.in Write to us at: info.india@mheducation.com CIN: U22200TN1970PTC111531 Toll Free Number: 1800 103 5875 Preface This book conforms to the latest syllabus in 'Discrete Mathematics' prescribed not only to the students of Engineering at the graduate and postgraduate levels by Anna University but also to the students of BCA, MCA and other IT related professional courses in most colleges in various universities throughout India. This book has been designed to provide an introduction to some fundamental concepts in Discrete Mathematics in a precise and readable manner and most of the mathematical foundations required for further studies. Many students taking this course are used to express that this subject is quite abstract and vague and that they need more examples and exercises to understand and develop an interest in the subject. To motivate such students, the book contains an extensive collection of examples and exercises with answers, so as to enable them to relate the mathematical techniques to computer applications in a sufficient manner. I have maintained my style of presentation as in my other books. I am sure that the students and the faculty will find this book very useful. Critical evaluation and suggestions for improvement of the book will be highly appreciated and gratefully acknowledged. I wish to express my thanks to Prof. M Jegan Mohan, Principal, SSCE, Aruppukottai for the appreciative interest shown and constant encouragement given to me while writing this book. I am thankful to my publishers, McGraw Hill Education (India) for their painstaking efforts and cooperation in bringing out this book in a short span of time. vi Preface I am grateful to the following reviewers for their feedback: Dr. B. Pushpa Panimalar Engineering College, Chennai Dr. D. Iranian Panimalar Institute of Technology, Chennai M.S. Muthuraman PSNA College of Engineering & Technology, Dindigul I have great pleasure in dedicating this book to my beloved students, past and present. T Veerarajan Contents Preface v Roadmap to the Syllabus 1. MaTheMaTIcal logIc Introduction 1 Propositions 1 Connectives 2 Order of Precedence for Logical Connectives 3 Conditional and Biconditional Propositions 3 Tautology and Contradiction 4 Equivalence of Propositions 4 Duality Law 5 Duality Theorem 5 Algebra of Propositions 6 Tautological Implication 7 Normal Forms 8 Disjunctive and Conjunctive Normal Forms 8 Principal Disjunctive and Principal Conjunctive Normal Forms Worked Examples 1(A) 10 Exercise 1(A) 24 Theory of Inference 27 Truth Table Technique 27 Rules of Inference 27 Form of Argument 28 xiii 1 9 viii Contents Rule CP or Rule of Conditional Proof 28 Inconsistent Premises 29 Indirect Method of Proof 29 Predicate Calculus or Predicate Logic 29 Introduction 29 Quantifiers 30 Existential Quantifier 31 Negation of a Quantified Expression 31 Nested (More than One) Quantifiers 32 Free and Bound Variables 32 Valid Formulas and Equivalences 32 Inference Theory of Predicate Calculus 33 Worked Examples 1(B) 35 Exercise 1(B) 46 Answers 49 2. coMBInaTorIcS Introduction 51 Permutations and Combinations 51 Pascal's Identity 52 Vandermonde's Identity 53 Permutations with Repetition 54 Circular Permutation 55 Pigeonhole Principle 55 Generalisation of the Pigeonhole Principle 56 Principle of Inclusion-Exclusion 56 Worked Examples 2(A) 57 Exercise 2(A) 74 Mathematical Induction 79 Recurrence Relations 80 Particular Solutions 82 Solution of Recurrence Relations by using Generating Functions Worked Examples 2(B) 83 Exercise 2(B) 99 Answers 101 3. graPh Theory Introduction 103 Basic Definitions 103 Degree of a Vertex 104 Some Special Simple Graphs 106 Matrix Representation of Graphs 110 Worked Examples 3(A) 112 Exercise 3(A) 119 51 82 103 Contents ix Paths, Cycles and Connectivity 124 Eulerian and Hamiltonian Graphs 129 Connectedness in Directed Graphs 130 Shortest Path Algorithms 131 Worked Examples 3(B) 135 Exercise 3(B) 146 Trees 152 Spanning Trees 153 Minimum Spanning Tree 153 Rooted and Binary Trees 155 Binary Tree 155 Tree Traversal 157 Expression Trees 158 Worked Examples 3(C) 159 Exercise 3(C) 171 Answers 175 4. grouP Theory Introduction 185 Algebraic Systems 185 Semigroups and Monoids 188 Homomorphism of Semigroups and Monoids 189 Subsemigroups and Submonoids 191 Groups 192 Permutation 194 Permutation Group 195 Dihedral Group 196 Cyclic Group 197 Worked Examples 4(A) 199 Exercise 4(A) 211 Subgroups 214 Group Homomorphism 215 Kernel of a Homomorphism 216 Cosets 216 Normal Subgroup 218 Quotient Group (or) Factor Group 219 Algebraic Systems with Two Binary Operations 221 Ring 221 Worked Examples 4(B) 227 Exercise 4(B) 240 Coding Theory 243 Encoders and Decoders 243 Group Code 243 Hamming Codes 244 232 x Contents Error Correction in Group Codes 249 Step by Step Procedure for Decoding Group Codes 251 Worked Examples 4(C) 253 Exercise 4(C) 260 Answers 264 5. SeT Theory Introduction 267 Basic Concepts and Notations 267 Ordered Pairs and Cartesian Product 269 Set Operations 270 Worked Examples 5(A) 274 Exercise 5(A) 280 Relations 282 Types of Relations 283 Some Operations on Relations 284 Composition of Relations 284 Properties of Relations 285 Equivalence Classes 286 Partition of a Set 287 Partitioning of a Set Induced by an Equivalence Relation 288 Matrix Representation of a Relation 288 Representation of Relations by Graphs 290 Hasse Diagrams for Partial Orderings 291 Terminology Related to Posets 292 Worked Examples 5(B) 293 Exercise 5(B) 306 Lattices 312 Principle of Duality 312 Properties of Lattices 313 Lattice as Algebraic System 315 Sublattices 316 Lattice Homomorphism 317 Some Special Lattices 317 Boolean Algebra 319 Additional Properties of Boolean Algebra 319 Dual and Principle of Duality 322 Principle of Duality 322 Subalgebra 322 Boolean Homomorphism 322 Isomorphic Boolean Algebras 322 Boolean Expressions and Boolean Functions 322 Expression of a Boolean Function in Canonical Form 324 Logic Gates 326 267 Contents Combination of Gates 326 Adders 327 Karnaugh Map Method 330 Don't Care Terms 334 Quine-McCluskey's Tabulation Method Worked Examples 5(C) 336 Exercise 5(C) 360 Answers 365 xi 334 Roadmap to the Syllabus Discrete Mathematics Semester III Unit-I: Logic and Proofs Propositional logic – Propositional equivalences – Predicates and quantifiers – Nested quantifiers – Rules of inference – Introduction to proofs – Proof methods and strategy Go To Chapter 1: Mathematical Logic Unit-II: Combinatorics Mathematical induction – Strong induction and well ordering – The basics of counting – The pigeonhole principle – Permutations and combinations – Recurrence relations – Solving linear recurrence relations – Generating functions – Inclusion and exclusion principle and its applications Go To Chapter 2: Combinatorics Unit-III: Graphs Graphs and graph models – Graph terminology and special types of graphs – Matrix representation of graphs and graph isomorphism – Connectivity – Euler and Hamilton paths Go To Chapter 3: Graph Theory Roadmap to the Syllabus xiv Unit-IV: Algebraic Structures Algebraic systems – Semi groups and monoids - Groups – Subgroups – Homomorphism's – Normal subgroup and cosets – Lagrange's theorem – Definitions and examples of Rings and Fields Go To Chapter 4: Group Theory Unit-V: Lattices and Boolean Algebra Partial ordering – Posets – Lattices as posets – Properties of lattices - Lattices as algebraic systems – Sub lattices – Direct product and homomorphism – Some special lattices – Boolean algebra Go To Chapter 5: Set Theory Mathematical Logic INTRODUCTION Logic is the discipline that deals with the methods of reasoning. One of the aims of logic is to provide rules by which we can determine whether a particular reasoning or argument is valid. Logical reasoning is used in many disciplines to establish valid results. Rules of logic are used to provide proofs of theorems in mathematics, to verify the correctness of computer programs and to draw conclusions from scientific experiments. In this chapter, we shall introduce certain logical symbols using which we shall state and apply rules of valid inference and hence understand how to construct correct mathematical arguments. PROPOSITIONS A declarative sentence (or assertion) which is true or false, but not both, is called a proposition (or statement). Sentences which are exclamatory, interrogative or imperative in nature are not propositions. Lower case letters such as p, q, r … are used to denote propositions. For example, we consider the following sentences: 1. New Delhi is the capital city of India. 2. How beautiful is Rose? 3. 2 + 2 = 3 4. What time is it? 5. x + y = z 6. Take a cup of coffee. In the given statements, (2), (4) and (6) are obviously not propositions as they are not declarative in nature. (1) and (3) are propositions, but (5) is not, 2 Discrete Mathematics since (1) is true, (3) is false and (5) is neither true nor false as the values of x, y and z are not assigned. If a proposition is true, we say that the truth value of that proposition is true, denoted by T or 1. If a proposition is false, the truth value is said to be false, denoted by F or 0. Propositions which do not contain any of the logical operators or connectives (to be introduced in the next section) are called atomic (primary or primitive) propositions. Many mathematical statements which can be constructed by combining one or more atomic statements using connectives are called molecular or compound propositions. The truth value of a compound proposition depends on those of subpropositions and the way in which they are combined using connectives. The area of logic that deals with propositions is called propositional logic or propositional calculus. CONNECTIVES Definition When p and q are any two propositions, the proposition "p and q" denoted by p � q and called the conjunction of p and q is defined as the compound proposition that is true when both p and q are true and is false otherwise. (� is the connective used) A truth table is a table that displays the relationships between the truth values of sub-propositions and that of compound proposition constructed from them. Table 1.1 is the truth table for the conjunction of two Table 1.1 propositions p and q viz., "p and q". Definition When p and q are any two propositions, the propositions "p or q" denoted by p � q and called the disjunction of p and q is defined as the compound proposition that is false when both p and q are false and is true otherwise. (� is the connective used) Table 1.2 is the truth table for the disjunction of two propositions p and q, viz., "p � q". Definition Given any proposition p, another proposition formed by writing "It is not the case that" or "It is false that" before p or by inserting the word 'not' suitably in p is called the negation of p and denoted by p (read as 'not p'). p is also denoted as p�, p and ~ p. It p is true, then p is false and if p is false, then p is true. Table 1.3 is the truth table for the negation of p. For example, if p is the statement "New Delhi is in India", the p is any one of the following statements. p q T T F F T F T F p q T F F F Table 1.2 p q T T F F T F T F p q T T T F Table 1.3 p 7p T F F T Mathematical Logic 3 (a) It is not the case that New Delhi is in India (b) It is false that New Delhi is in India (c) New Delhi is not in India The truth value of p is T and that of p is F. ORDER OF PRECEDENCE FOR LOGICAL CONNECTIVES We will generally use parentheses to specify the order in which logical operators in a compound proposition are to be applied. For example, (p � q) � ( r) is the conjunction of p � q and r. However to avoid the use of an excessive number of parentheses, we adopt an order of precedence for the logical operators, given as follows: (i) The negation operator has precedence over all other logical operators. Thus p � q means ( p) � q, not (p � q). (ii) The conjunction operator has precedence over the disjunction operator. Thus p � q � r means (p � q) � r, but not p � (q � r). (iii) The conditional and biconditional operators � and � (to be introduced subsequently) have lower precedence than other operators. Among them, � has precedence over �. CONDITIONAL AND BICONDITIONAL PROPOSITIONS Definition If p and q are propositions, the compound proposition "if p, then q", that is denoted by p � q is called a conditional proposition, which is false when p is true and q is false and true otherwise. In this conditional proposition, p is called the hypothesis or premise and q is called the conclusion or consequence. Note Some authors call p � q as an implication. For example, let us consider the statement. "If I get up at 5 A.M., I will go for a walk", which may be represented as p � q and considered as a contract. If p is true and q is also true, the contract is not violated and so 'p � q' is true. If p is true and q is false (viz., I get up at 5 A.M., but I do not go for a walk), the contract is violated and so 'p � q' is false. Table 1.4 If p is false and whether q is true or false (viz., when I have not got up at 5 A.M; I may or may not go for a p q p q walk), the contract is not violated and so 'p � q' is true. T T T Accordingly, the truth table for the conditional T F F proposition p � q will be as given in Table 1.4. F T T F F T The alternative terminologies used to express p � q (if p, then q) are the following: Discrete Mathematics 4 (i) p implies q, (ii) p only if q ["If p, then q" formulation emphasizes the hypothesis, whereas "p only if q" formulation emphasizes the conclusion; the difference is only stylistic], (iii) q if p or q when p, (iv) q follows from p, (v) p is sufficient for q or a sufficient condition for q is p and (vi) q is necessary for p or a necessary conditions for p is q. Definition If p and q are propositions, the compound proposition "p if and only if q", that is denoted by p � q, is called a biconditional proposition, which is true when p and q have the same truth values and is false otherwise. It is easily verified that 'p � q' is true when both the conditionals p � q and q � p are true. This is the reason for the symbol � which is a combination of � and �. Table 1.5 Alternatively, 'p � q' is also expressed as 'p iff q' and 'p is necessary and sufficient for q'. p q p q The truth table for 'p � q' is given in Table 1.5. T T T Note The notation p � q is also used instead of p � q. T F F TAUTOLOGY AND CONTRADICTION F T F F F T A compound proposition P = P(p1, p2, …, pn), where p1, p2, …, pn are variables (elemental propositions), is called a tautology, if it is true for every truth assignment for p1, p2, …, pn. P is called a contradiction, if it is false for every truth assignment for p1, p2, …, pn. For example, p � p is a tautology, whereas p � p is a contradiction, as seen from the Table 1.6 given below. Table 1.6 p T F p F T p p T T p p F F Note 1. The negation of a tautology is a contradiction and the negation of a contradiction is a tautology. 2. If P(p1, p2, …, pn) is a tautology, then P(q1, q2, …, qn) is also a tautology, where q1, q2, …, qn are any set of propositions. This is known as the principle of substitution. For example, since p � p is a tautology, ((p � q) � r) � ((p � q) � r) is also a tautology. 3. If a proposition is neither a tautology nor a contradiction, it is called a contingency. EQUIVALENCE OF PROPOSITIONS Two compound propositions A(p1, p2, …, pn) and B(p1, p2, …, pn) are said to be logically equivalent or simply equivalent, if they have identical truth tables, viz. if the truth value of A is equal to the truth value of B for every one of the 2n possible sets of truth values assigned to p1, p2, …, pn. Mathematical Logic 5 The equivalence of two propositions A and B is denoted as A � B or A � B (which is read as 'A is equivalent to B'). � or � is not a connective. For example, let us consider the truth tables of (p � q) and p � q (see Table 1.7). The final columns in the truth tables for (p � q) and p � q are identical. Hence (p � q) � p � q. Table 1.7 p q p�q T T F F T F T F T T T F (p � q) p F F F T q F F T T p� F T F T q F F F T Note We have already noted that the biconditional proposition A � B is true whenever both A and B have the same truth value, viz. A � B is a tautology, when A and B are equivalent. Conversely, A � B, when A � B is a tautology. For example, (p � q) � ( p � q), since (p � q) � ( p � q) is a tautology, as seen from the truth Table 1.8 given below: Table 1.8 p q p�q T T F F T F T F T F T T p p�q F F T T (p � q) � T F T T p � q) T T T T DUALITY LAW The dual of a compound proposition that contains only the logical operators �, � and is the proposition obtained by replacing each � by �, each � by �, each T by F and each F by T, where T and F are special variables representing compound propositions that are tautologies and contradictions respectively. The dual of a proposition A is denoted by A*. DUALITY THEOREM If A(p1, p2, …, pn) � B(p1, p2, …, pn), where A and B are compound propositions, then A*(p1, p2, …, pn) � B* (p1, p2, …, pn). Proof In Table (1.7), we have proved that (p � q) � p � q or p � q � ( p � Similarly we can prove that p � q � ( p � q) Note q) (1) (2) (1) and (2) are known as De Morgan's laws. Using (1) and (2), we can show that A(p1, p2, …, pn) � A*( p1, p2, …, pn) (3) Discrete Mathematics 6 Equation (3) means that the negation of a proposition is equivalent to its dual in which every variable (primary proposition) is replaced by its negation. From Eq. (3), it follows that A(p1, p2, …, pn) � A*( p1, p2, …, pn) (4) Now since A(p1, p2, …, pn) � B(p1, p2, …, pn), we have A(p1, p2, …, pn) � B(p1, p2, …, pn) is tautology � A( p1, p2, …, pn) � B( p1, p2, …, pn) is also a tautology (5) Using (4) in (5), we get A*(p1, p2, …, pn) � B*(p1, p2, …, pn) is a tautology. � A* � B* is a tautology. � A* � B* ALGEBRA OF PROPOSITIONS A proposition in a compound proposition can be replaced by one that is equivalent to it without changing the truth value of the compound proposition. By this way, we can construct new equivalences (or laws). For example, we have proved that p � q � p � q (Table 1.8). Using this equivalence, we get another equivalence p � (q � r) � p � ( q � r). Some of the basic equivalences (laws) and their duals which will be of use later are given in Tables 1.9, 1.10 and 1.11. They can be easily established by using truth tables. Table 1.9 Sl. No. Name of the law 1. 2. 3. 4. 5. 6. 7. 8. 9. Laws of Algebra of Propositions Primal form p�p�p p�F�p p�T�T p� p�T p�q�q�p (p � q) � r � p � (q � r) p � (q � r) � (p � q) � (p � r) � (p � q) � (p � q) � p � q Idempotent law Identity law Dominant law Complement law Commutative law Associative law Distributive law Absorption law De Morgan's law Table 1.10 1. 2. 3. 4. 5. 6. 7. 8. 9. Dual form p�p�p p�T�p p�F�F p� p�F p�q�q�p (p � q) � r � p � (q � r) p � (q � r) � (p � q) � (p � r) � (p � q) � (p � q) � p � q Equivalences Involving Conditionals p�q� � p�q� q� p p�q� � � q � (p � ) (p � q) � p � q (p � q) � (p � r) � p � (q � r) (p � r) � (q � r) � (p � q) � r (p � q) � (p � r) � p � (q � r) (p � r) � (q � r) � (p � q) � r Mathematical Logic Table 1.11 7 Equivalences Involving Biconditionals 1. p � q � � q � q � p) 2. p � q � p � 3. � q � (p � q) � p � q) 4. (p � q) � p � q TAUTOLOGICAL IMPLICATION A compound proposition A(p1, p2, …, pn) is said to tautologically imply or simply imply the compound proposition B(p1, p2, …, pn), if B is true whenever A is true or equivalently if and only if A � B is a tautology. This is denoted by A � B, read as "A implies B". Note � is not a connective and A � B is not a proposition). For example, p � p � q, as seen from the following truth Table 1.12. We note that p � q is true, whenever p is true and that p � (p � q) is a tautology. Table 1.12 p q T T F F T F T F p q p � (p � q) T T T F Similarly we note that (p � q) � ( q � Table 1.13. T T T T p) from the following truth Table 1.13 p q T T F F T F T F p q F F T T F T F T p�q T F T T q� p (p � q) � T F T T q� p) T T T T Some important implications which can be proved by truth tables are given in Table 1.14. Table 1.14 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. Implications p�q�p p�q�q �p�q p�p�q �p�q (p � q) � (p � q) � q � (p � q) � q q � (p � q) � p p � (p � q) � q (p � q) � (q � r) � p � r (p � q) � (p � r) � (q � r) � r Discrete Mathematics 8 Note We can easily verify that if A � B and B � A, then A � B. Hence to prove the equivalence of two propositions, it is enough to prove that each implies the other. NORMAL FORMS To determine whether a given compound proposition A(p1, p2, …, pn) is a tautology or a contradictor or at least satisfiable and whether two given compound propositions A(p1, p2, …, pn) and B(p1, p2, …, pn) are equivalent, we have to construct the truth tables and compare them. Note A(p1, p2, …, pn) is said to be satisfiable, if it has the truth value T for at least one combination of the truth values of p 1 , p 2 , …, p n . But the construction of truth tables may not be practical, when the number of primary propositions (variables) p1, p2, …, pn increases. A better method is to reduce A and B to some standard forms, called normal forms and use them for deciding the nature of A or B and for comparing A and B. There are two types of normal form—disjunctive normal form and conjunctive normal form. We shall use the word 'product' in place of 'conjunction' and 'sum' in place 'disjunction' hereafter in this section for convenience. DISJUNCTIVE AND CONJUNCTIVE NORMAL FORMS A product of the variables and their negations (a conjunction of primary statements and their negations) is called an elementary product. Similarly, a sum of the variables and their negations is called an elementary sum. For example, p, p, p � p, p � q, p � q and p � q are some elementary products in 2 variables q, q, p � q, p � q and p � q are some elementary sums is 2 variables. A compound proposition (or a formula) which consists of a sum of elementary products and which is equivalent to a given proposition is called a disjunctive normal form (DNF) of the given proposition. A formula which consists of a product of elementary sums and which is equivalent to a given formula is called a conjunctive normal form (CNF) of the given formula. Procedure to Obtain the DNF or CNF of a Given Formula Step 1 If the connectives � and � are present in the given formula they are replaced by �, � and viz. p � q is replaced by p � q and p � q is replaced by either (p � q) � ( p � q) or ( p � q) � ( q � p). Step 2 If the negation is present before the given formula or a part of the given formula (not a variable), De Morgan's laws are applied so that the negation is brought before the variables only. Mathematical Logic 9 Step 3 If necessary, the distributive law and the idempotent law are applied. Step 4 If there is an elementary product which is equivalent to the truth value F in the DNF, it is omitted. Similarly if there is an elementary sum which is equivalent to the truth value T in the CNF, it is omitted. For example, the DNF of q � (q � p) is given by q � (q � p) � q � (q � p) � q � ( q � p) � ( q � q) � p, by associative law � q � p, by idempotent law. The CNF of (p � q) � (p � q) is given by (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) � F � F � (p � q) � ( p � q) � (p � q) � ( p � q) PRINCIPAL DISJUNCTIVE AND PRINCIPAL CONJUNCTIVE NORMAL FORMS Given a number of variables, the products (or conjunctions) in which each variable or its negation, but not both, occurs only once are called the minterms. For two variable p and q, the possible minterms are p � q, p � q, p � q and p � q. For three variables p, q and r, the possible minterms 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. We note that there are 2n minterms for n variables. Given a number of variables, the sums (or disjunctions) in which each variable or its negation, but not both, occurs only once are called the maxterms. For the two variables p and q, the possible maxterms are p � q, p � q, p � q and p � q. The maxterms are simply the duals of minterms. A formula (compound proposition) consisting of disjunctions of minterms in the variables only and equivalent to a given formula is known as its principal disjunctive normal form (PDNF) or its sum of products canonical form of the given formula. Similarly, a formula consisting of conjunctions of maxterms in the variables only and equivalent to given formula is known as its principal conjunctive normal form (PCNF) or its product of sums canonical form. In order to obtain the PDNF of a formula, we first obtain a DNF of the formula by using the procedure given above. To get the minterms in the disjunctions, the missing factors are introduced through the complement law (viz. P � P = T) and then applying the distributive law. Identical minterms Discrete Mathematics 10 appearing in the disjunctions are then deleted, as P � P = P. A similar procedure with necessary modifications is adopted to get the PCNF of a formula. In order to verify whether two given formulas are equivalent, we may obtain either PDNF or PCNF of both the formulas and compare them. If the PDNF of a formula A is known, the PDNF of A will consist of the disjunctions of the remaining minterms which are not included in the PDNF of A. Note To obtain the PCNF of A, we use the fact that A = De Morgan's laws to the PDNF of A repeatedly. ( A) and apply Examples (a) The PDNF of (p � q) is given by p � q � p � (q � q) � q � (p � p), by complement law � (p � q) � (p � q) � ( q � p) � ( q � p), by distributive law q), by commutative and idempotent laws. (b) To get the PCNF of p � q, we proceed as follows: The PDNF of p � q � (p � q) � ( p � q) [assumed from Table (1.11)] � PDNF of (p � q) � ( p � q) � (p � q) (remaining minterms) (1) (p � q) � (p � q) � � (( p � q) � (p � q), form (1) � ( p � q) � (p � q), by De Morgan's law � (p � q) � ( p � q), by De Morgan's law, which is the same as p � q � (p � q) � (q � p). � (p � q) � (p � q) � ( p � WORKED EXAMPLES 1(A) Example 1.1 Construct a truth table for each of the following compound propositions: (a) (p � q) � (p � q); (b) (p � q) � (q � p); (c) (q � p) � (p � q); (d) (p � q) � ((p � q) � ( p � q)); (e) ( p � q) � (p � q). Table 1.15 (a) Truth Table for (p � q) � (p � q) p q p�q p�q (p � q) � (p � q) T T F F T F T F T T T F T F F F T F F T Mathematical Logic Truth Table for (p � q) � (q � p) Table 1.16 (b) p q p�q q�p (p � q) � (q � p) T T F F T F T F T F T T T T F T T T F T Table 1.17 (c) p q T T F F T F T F p q T T F F T F T F p F F T T p q T T F F T F T F q� F F T T q p) � (p � q) p�q F T T T (q � T F F T p) � (p � q) F F F T Truth Table for (p � q) � ((p � q) � ( p � q p�q p�q F T F T T F F T Table 1.19 (e) Truth Table for (q � p Table 1.18 (d) 11 q(p � q) � F F F T F T F T p� q) given formula T F F T Truth Table for ( p � p F F T T p� T F F F p� q) (p � T F F T T F F T q)) T T T T q) � (p � q) p� q) � (p � q) T T T T Formulas given in (d) and (e) are tautologies. Note Example 1.2 Construct the truth table for each of the compound proposi- tions (a) (b) (c) (d) (e) given as follows: ((p � (q � r)) � ((p � q) � (p � r)) (p � (q � r)) � ((p � q) � (p � r)) ( p � q) � (q � r) (p � (q � s)) � ( r � p) � q ((p � q) � r) � s If there are n distinct components (sub-propositions) in a statement (compound proposition), the corresponding truth table will consist of 2n rows corresponding to 2n possible combinations. In order not to miss any of the combinations, we adopt the following procedure: In the first column of the truth table corre- Note sponding to the first component, we will write 1 � 2n entries each equal to T, followed 2 Discrete Mathematics 12 by 1 1 � 2n T's will be first � 2n entries each equal to F. In the second column, 4 2 written, then 1 1 � 2n F's will be written followed again by � 2n T's. Finally 4 4 1 1 1 � 2 n T's and � 2 n F's will � 2n F's will be written. In the third column 8 8 4 be alternately written starting with T's and so on. (a) Table 1.20 Truth Table for (p � (q � r)) � ((p � q) � (p – r)) p q r p�q p�r q�r T T T T F F F F T T F F T T F F T F T F T F T F T T F F T T T T T F T F T T T T T F T T T F T T Note p � (q � r) (p � q) � (p � r) a � b �a �b T F T T T T T T T F T T T T T T T T T T T T T T The given compound proposition is a tautology. (b) Table 1.21 Truth Table for p q r q�r T T T T F F F F T T F F T T F F T F T F T F T F T F F F T F F F p� � r) a a T T T T T F F F F F F F F T T T (p � (q � r) � ((p � q) � (p � r)) p � q p � r (p � q) � (p � r) b T T T T T T F F T F T F T T T T Table 1.22 Truth Table for ( p � p q r p T T T T F F F F T T F F T T F F T F T F T F T F (c) F F F F T T T T p� F F T T F F T T T T F F F F T T q) � a a�b T F T F T T F F F T F T F T F F q) � (q � r) q�r�b T F F T T F F T a�b T F T F F T F T Mathematical Logic Table 1.23 (d) p q r s T T T T T T T T F F F F F F F F T T T T F F F F T T T T F F F F T T F F T T F F T T F F T T F F T F T F T F T F T F T F T F T F Truth Table for (p � (q � s)) � ( r � p) � q q�s�a T F T F T T T T T F T F T T T T p�a�b T F T F T T T T T T T T T T T T r � p) � c b � c b � c � q F F T T F F T T F F T T F F T T T T T T T T T T F F T T F F T T T F T F T T T T F F T T F F T T T F T F F F F F F F T T F F F F Truth Table for ((p � q) � r) � s Table 1.24 (e) 13 p q r s T T T T T T T T F F F F F F F F T T T T F F F F T T T T F F F F T T F F T T F F T T F F T T F F T F T F T F T F T F T F T F T F p�q T T T T F F F F T T T T T T T T (p � q) � r ((p � q) � r) � s T T F F T T T T T T F F T T F F T F T T T F T F T F T T T F T T Example 1.3 Determine which of the following compound propositions are tautologies and which of them are contradictions, using truth tables: (a) ( q � (p � q) � p (b) ((p � q) � (q � r)) � (p � r) (c) (q � r) � r � (p � q) (d) ((p � q) � (p � r) � (q � r)) � r. Discrete Mathematics 14 Table 1.25 Truth Table for ( q � (p � q)) � p q q T T F F T F T F (a) p F F T T F T F T (p � q) T F T T q � (p � p q � (p � q)) � F F F T p T T T T Since the truth value of the given compound proposition is T for all combinations of p and q, it is a tautology. Truth Table for ((p � q) � (q � r)) � (p � r) Table 1.26 (b) p q r p�q p�r T T T T F F F F T T F F T T F F T F T F T F T F T T F F T T T T T F T F T T T T q � r (p � q) � (q � r) ((p � q) � (q – r)) � (p – r) T F T T T F T T T F F F T F T T T T T T T T T T Since the truth value of the given statement is T for all combinations of truth values of p, q and r, it is a tautology. Table 1.27 (c) Truth Tables for (q � r) � r � (p � q) p q r p�q q�r (q � r) (q � r) � T T T T F F F F T T F F T T F F T F T F T F T F T T F F T T T T T F T T T F T T F T F F F T F F F F F F F F F F (q � r) � r � (p � q) F F F F F F F F The last column contains only F as the truth values of the given statement. Hence it is a contradiction. (d) Truth Table for ((p � q) � (p � r)� (q � r)) � r Table 1.28 p q r p�q �a p�r �b T T T T T T F F T F T F T T T T T F T F a�b T F T F q�r �c T F T T a � b � c (a T F T F b � c) r T T T T (Contd.) Mathematical Logic (Contd.) F T F T F F F F T F T F T T F F T T T T T T F F T F T T 15 T F F F T T T T Since all the entries in the last column are T's, the given statement is a tautology Example 1.4 (i) (ii) (iii) (i) (ii) (iii) Without using truth tables, prove the following: ( p � q) � (p � (p � q) � p � q p � (q � p) � p � (p � q) (p � q) � (p � q) � (p � q) � (p � q) � ( p � q) ( p � q) � (p � (p � q)) � ( p � q) � (p � p) � q, by associative law � ( p � q) � (p � q), by idempotent law � (p � q) � ( p � q), by commutative law � ((p � q) � p) � ((p � q) � q), by distributive law � ( p � (p � q)) � ((p � q) � q), by commutative law � (( p � p) � q) � (p � (q � q), by associative law � (F � q) � (p � q), by complement and idempotent law � F � (p � q), by dominant law � p � q, by dominant law. p � (q � p) � p � (q � p) [Refer to Table 1.10] [Refer to Table 1.10] � p � ( q � p) � q � (p � p), by commutative and associative laws � p � T, by complement law � T, by dominant law (1) p � (p � q) � p � (p � q), by (1) of Table 1.10 � p � ( p � q), by (1) of Table 1.10 � (p � p)�� q, by associative law � T � q, by complement law � T, by dominant law, (2) From (1) and (2), the result follows. (p � q) � ((p � q) � (q � p)), from Table 1.11 � (( p � q) � ( q � q)), from Table 1.10 � [(( p � q) � q) � (( p � q) � p], by distributive law � [(( p � q) � (q � q)) � (( p � p)) � (q � p))], by distributive law � [(( p � q) � F) � ((F � (q � p))], by complement law � [( p � q) � (q � p)], by identity law � [ (p � q) � (q � p)], by De Morgan's law � (p � q) � (q � p), by De Morgan's law (1) � (p � q) � ( q � p), by De Morgan's law � ((p � q) � q)) � ((p � q) � p)), by distributive law � ((p � q) � (q � q)) � ((p � p) � (q � p)), by distributive law 16 Discrete Mathematics � ((p � q) � F) � ((F � (q � p)), by complement law � (p � q) � (q � p), by identity law � (p � q) � ( p � q), by commutative law From (1) and (2), the result follows. (2) Example 1.5 Without constructing the truth tables, prove the following: (i) p � (q � r) � q � (p � r) (ii) p � (q � r) � p � ( q � r) � (p � q) � r (iii) ((p � q) � ( p � ( q � r))) � ( p � q) � ( p � r) is a tautology. (i) p � (q � r) � p � (q � r), from Table 1.10 � p � ( q � r), from Table 1.10 � (p � q) � r, by associative law � ( q � p)�� r, by commutative law � q � (p � r), by associative law � q � (p � r), from Table 1.10. (ii) p � (q � r) � p � ( q � r), from Table 1.10 (1) Now p � ( q � r) � p � ( q � r), from Table 1.10 � ( p � q) � r, by associative law � (p � q) � r, by De Morgan's law � (p � q) � r (2) (iii) ((p � q) � ( p � ( q � r))) � ( p � q) � ( p � r) � ((p � q) � (p � (q � r))) � (p � q) � (p � r), by De Morgan's law � ((p � q) � [(p � q) � (p � r)]) � [ (p � q) � (p � r)], by distributive law � [(p � q) � (p � r)] � [(p � q) � (p � r)], by idempotent and De Morgan's laws The final statement is in the form of p � p. � L.H.S. � T Hence the given statement is tautology. Example 1.6 Prove the following equivalences by proving the equivalences of the duals: (i) (( p � q) � ( p � q)) � (p � q) � p (ii) (p � q)� r � (p � r) ��(q � r) (iii) (p � (p � q)) � q � T (i) The dual of the given equivalence is (( p � q) � ( p � q)) � (p � q) � p Let us now prove the dual equivalence. L.H.S. � ( p � (q � q)) � (p � q), by distribution law � ( p � F) � (p � q), by complement law � ( p) � (p � q), by identity law � p � (p � q) � p, by absorption law Mathematical Logic 17 (ii) (p � q) � r � (p � r) � (q � r) i.e., (p � q) � r � ( p � r) � ( q � r) Dual of this equivalence is (p � q) � r � ( p � r) � ( q � r) L.H.S � ( p � q) � r, by De Morgan's law � ( p � r) � ( q � r), by distributive law � R.H.S. (iii) (p � (p � q)) � q � T i.e. p � ((p � q) � (q � p)) � q � T, from Table 1.11 i.e. p � (( p � q) � ( q � p)) � q � T i.e. (p � (( p � q) � ( q � p))) � q � T Dual of this equivalence is (p � (( p � q) � ( q � p))) � q � F L.H.S. � [(p � ( p � q)) � ( q � p)]�� q, by associative law � [(T � (p � q)) � ( q � p)] � q, by distributive and complement laws � [(p � q) � ( q � p)] � q, by identity law � [((p � q) � q) � ((p � q)�� p)] � q, by distributive law � [(p � T) � (p � q)] � q, by idempotent and complement laws. � [T � (p � q)] � q, by dominant law � [p � q] � q, by identity law � ( p � q) � q, by De Morgan's law � ( p � F), by complement law � F, by dominant law. Example 1.7 Prove the following implications by using truth tables: (i) p � ((p � r) � (p � q) � (p � r) (ii) (p � (q � s)) � ( r � p) � q � r � s (i) We have defined that A � B, if and only if A� B is a tautology (i) Table 1.29 p q r p�q (a) q�r (b) p�r (c) p�b (d) a�c (e) d�e T T T T F F F F T T F F T T F F T F T F T F T F T T F F T T T T T F T T T F T T T F T F T T T T T F T T T T T T T F T T T T T T T T T T T T T T Since d � e, viz., [p � (q � r)] � [(p � q) � (p � r)] is a tautology, the required implication follows. 18 Discrete Mathematics (ii) Table 1.30 p q r s q�s (a) p�a (b) r � p) b � c (c) (d) d�q (e) r�s e�f (f) T T T T T T T T F F F F F F F T T T T F F F F T T T T F F F T T F F T T F F T T F F T T F T F T F T F T F T F T F T F T T F T F T T T T T F T F T T T T F T F T T T T T T T T T T T F F T T F F T T F F T T F F T T T T T T T T T F F T T F F T T F T F T T T T F F T T F F T T F T F F F F F F F T T F F F T F T T T F T T T F T T T F T T T T T T T T T T T T T T T T F F F F T T T T T F T T Since e � f is a tautology, e � f. Example 1.8 (i) (ii) (i) (ii) Prove the following implications without using truth tables: (p � q) � (p � r) � (q � r) � r ((p � p) � q) � ((p � p) � r) � q � r [(p � q) � (p � r) � (q � r)] � r � (p � q) � ((p � q) � r) � r, from Table 1.10 � (p � q) � ( (p � q) � r) � r � (F � (p � q) � r) � r � ((p � q) � r) � r � ((p � q) � r) � r � ((p � r) � (q � r)) � r � ( (p � r) � (q � r)) � r � ( (p � r) � r) � ( (q � r) � r) � ( p � r � r) � ( q � r � r) � ( p � T) � ( q � T) �T�T �T [((p � p) � q) � ((p � p) � r)] � (q � r) � [(T � q) � (T � r)] � (q � r) � [(F � q) � (F � r)] � (q � r) � (q � r) � (q � r) �T Mathematical Logic 19 Example 1.9 Find the disjunctive normal forms of the following statements: (i) ( (p � q) � r) (ii) p � ( p � (q � (q � r))) (iii) p � (q � r) � (p � q) (iv) (p � (q � r)) � (((p � q) � r) � p) (i) ( (p � q) � r) � ( ((p � q) � ( p � q)) � r) � [( (p � q) � ( p � q)) � r] � [(( p � q) � (p � q)) � r] � [(( p � p) � ( p � q) � ( q � p) � ( q � q)) � r], by extended distributive law � [(( p � q) � ( q � p)) � r) � [(( p � q) � ( p � p) � (q � q) � (q � p)) � r] � [((p � q) � ( p � q)) � r] � (p � q) � ( p � q) � r � ( p � q) � (p � q) � r (ii) p � ( p � (q � (q � r))) � p � ( p � (q � ( q � r))) � p � (p � (q � ( q � r))) �p�p�q� q� r �p�q� q� r Note The given statement is a tautology, as p � (q � q) � r�P�T� r�T (iii) p � (q � r) � (p � q) � p � (q � r) � ( p � q) � (p � ( q � r)) � ( p � q) � (p � q) � (p � r) � ( p � q) � (p � q) � (p � r) � p � q (iv) (p � (q � r)) � (((p � q) � r) � p) � (p � ( q � r)) � ((p � q) � q) � ( r � p) � (p � q � r) � (p � q) � (p � r) Example 1.10 Find the conjunction normal forms of the following statements: (i) (p (ii) (q (iii) (p (i) (p � (q � r)) � (p � q) � (p � q)) � ((p � r) � q) � (q � r)) � (((p � q) � r) � p � (q � r)) � (p � q) � (p � ( q � r)) � ( p � q) � (p � q) � (p � r) � ( p � q) � (p � p) � (p � r) � ( q � p) � ( q � r) � ( p � q) � (p � p) � (p � r) � (p � q) � ( p � q � q � r) � (p � p) � (p � r) � (p � q) � ( p � T � r) � (p � (p � r) � (p � q) (ii) [q � (p � q)] � [(p � r) � q] � q � [(p � r) � q], by absorption law � q � [ (p � r) � q] Discrete Mathematics 20 (iii) (p � � q � [( p � r) � q] � q � ( p � q) � ( q � r) (q � r)) � (((p � q) � r) � p) � (p � ( q � r)) � ((p � r) � (q � r) � p) � (p � q � r) � (p � (p � r) � q � r)) � (p � q � r) � (p � (q � r)), by absorption law � [(p � ( q � r)) � p] � [(p � q � r) � (q � r)] � p � [((p � q � r) � r) � q], by absorption law � p � ( r � q), by absorption law � p � (q � r) Example 1.11 Obtain the principal disjunctive normal forms and the principal conjunctive normal forms of the following statements using truth tables: (i) ( p � q) � (p � q) (ii) p � ( p � (q � ( q � r))) (iii) (p � (q � r)) � ( p � ( q � r)) Procedure If the given statement is not a contradiction, then the disjunction (sum) of the minterms corresponding to the rows of the truth table having truth value T is the required PDNF, as it is equivalent to the given statement. For example, if the truth value T of the statement corresponds to the truth values T, T and F for the variables p, q and r respectively, then the corresponding minterm is taken as (p � q � r). If the given statement A is not a tautology, we can find the equivalent PCNF as follows: We write down the PDNF of A, which is the disjunction of the minterms corresponding to the rows of the truth table having the truth value F. Then if A(=A), we will get the required PCNF of A. Equivalently the we find PCNF is the conjunction of maxterms corresponding to the F values of A. But the maxterm corresponding to T, T, F value of p, q, r is [( p � q � r)] (i) Table 1.31 p q T T F F T F T F p� p F F T T F T F T PDNF of ( p � q) � (p � since the minterms q) F T T T a p� q�b F T T F q) � (p � q) � (p � a�b T T T F q) � ( p � q), Mathematical Logic (ii) 21 Table 1.32 p q r T T T T F F F F T T F F T T F F T F T F T F T F p q�r�a q F F F F T T T T F F T T F F T T q�a�b T T T F T T T F p�b�c p�c T T T F T T T F T T T T T T T F T T T T T T T F PDNF of the given statement = (p � q � r) � (p � q � r) � (p � q � r) � (p � q � � ( p � q � r) � ( p � q � r) � ( p � q � r). Now PCNF of the given statement = ( p � q � r) =p�q�r (iii) r) Table 1.33 p q r T T T T F F F F T T F F T T F F T F T F T F T F p F F F F T T T T q F F T T F F T T r q�r �a F T F T F T F T T F F F T F F F p�a �b T F F F T T T T q� r �c F F F T F F F T p�c b�d �d T T T T F F F T T F F F F F F T PDNF of the given statement � (p � q � r) � ( p � q � r) PDNF of (b � d) � (p � q � r) � (p � q � r) � (p � q � r) p � q � r) � ( p � q � r) � ( p � q � r) � PCNF of (b � d) � ( p � q � r) � ( p � q � r) � ( p � q � r) � (p � q � r) � (p � q � r) � (p � q � r) Example 1.12 Without constructing the truth tables, find the principal disjunctive normal forms of the following statements: (i) ( p � q) � (q � p) (ii) (p � q) � ( p � q) � (q � r) (iii) p � (q � r) � (p � q) (iv) (q � (p � r)) � ((p � r) � q) (i) ( p � q) � (q � p) � (p � q) � ((q � p) � ( q � p)) � (p � q) ��((p � q) � (p � q)) � ((p � q) � (p � q)) � ((p � q) � (p � q)) � ((p � q) � (p � q)) � F � (p � (p � q)) � ((q � (p � q)) Discrete Mathematics 22 � (p � q) � (p � q) �p�q (ii) (p � q) � ( p � q) � (q � r) � � (� Already the given statement is in the DNF, but not in PDNF) � (p � q � r) � (p � q � r) � ( p � q � r) � ( p � q � r) � (p � q � r) � ( p � q � r) � (p � q � r) � (p � q � r) � ( p � q � r) � ( p � q � r) (Deleting repetition of identical minterms) (iii) p � (q � r) � (p � q) � (p � ( q � r)) � ( p � q) � (p � q) � (p � r) � p � q � (p � q) � (p � r) � ( p � (q � q)) � (q � (p � p)) � (p � q) � (p � r) p � q) p � q) � (p � q) p � q) � (p � q) � (p � r) � ( p � q) � ( p � q) � (p � q) [Omitting the repletion of ( p � q)] � ((p � q) � (r � r)) � ((p � r) � (q � q)) � (( p � q) � (r � r)) � (( p � q) � (r � r)) � ((p � q) � (r � r)) � (p � q � r) � (p � q � r) � (p � q � r) � (p � q � r) � ( p � q � r) � ( p � q � r) � ( p � q � r) � ( p � q � r) ��(p � q � r) � (p � q � r) � (p � q � r) � (p � q � r) � (p � q � r) � ( p � q � r) p � q � r) p � q � r) p � q � r) � (p � q � r) (Omitting repetitions) Note Since all possible minterms are present in the PDNF, we infer that the given statement is a tautology. (iv) (q � (p � r)) � ((p � r) � q) � (q � (p � r)) � ( (p � r) � q) � (q � (p � r)) � (( p � r) � q) � (q � p � r) � (q � q) � (p � r � p � r) � (p � r � q) (By extended distribution law) � ( p � q � r) � F � F � (p � q � r) � ( p � q � r) � (p � q � r), deleting F's Example 1.13 Without constructing the truth tables, find the principal conjunctive normal forms of the following statements: (i) (p � q) � ( p � q � r) (ii) (p � q) � (r � p) � (q � r) (iii) (p � (q � r)) � (((p � q) � r) � p) (iv) (p � (q � r)) � ( p �( q � r) (i) (p � q) � ( p � q � r) � ((p � q) � p) � ((p � q) � q) � ((p � q) � r) � (p � p) � (q � p) � (p � q) � (q � q) � (p � r) � (q � r) � T � ( p � q) � (p � q) � q � (p � r) � (q � r) � (( p � q) � (r � r)) � ((p � q) � (r � r)) � q � (p � p) � (p � r) � (q � q) � (q � r) � (p � p) (� A � F = A) Mathematical Logic 23 � ( p � q � r)� ( p � q � r) � (p � q � r) � (p � q � r) � (q � p) � (q � p) � (p � r � q) � (p � r � q) � (q � r � p) � (q � r � p) � ( p � q � r) � ( p � q � r) � (p � q � r) � (p � q � r) � (p � q � r) � ((q � p) � (r � r)) � ((q � p) � (r � r)) (Omitting repetitions) � ( p � q � r) � ( p � q � r) � (p � q � r) � (p � q � r) � (p � q � r) (1) (Deleting repetitions) In this process, we have directly found out the PCNF of the given statement Note S. Alternatively we can first find the PDNF of S, write down the PDNF of S and hence get the PCNF of S given as follows: Aliter S � (p � q) � (r � r) � ( p � q � r) � (p � q � r) � (p � q � r) ��( p � q � r) � S � (p � q � r) p � q � r) p � q � r) � (p � q � r) � ( p � q � r) � S= S � (p � q � r) � ( p � q � r) � ( p � q � r) � (p � q � r) � ( p � q � r) � ( p � q � r) � (p � q � r) � (p � q � r) � ( p � q � r) � (p � q � r) (2) We see that PCNF's of S in (1) and (2) are one and the same. (ii) Let S ��(p � q) � (r � p) � (q � r) Already S is in the CNF. Hence we can get the PCNF directly quickly. S � ((p � q) � (r � r) p � r) � (q � q)) � ((q � r) � (p � p)) � (p � q � r) � (p � q � r) � ( p � q � r) � ( p � q � r) � (p � q � r) � ( p � q � r) � (p � q � r) � (p � q � r) � ( p � q � r) � ( p � q � r) � ( p � q � r) (iii) Let S � (p � (q � r)) � ((p � q) � r) � p � (p � ( q � r)) � (p � q � r � p) � p � (q � q) � ( q � r) � (p � q � r) � (p � q) � (p � q) � ( q � r) � (p � q � r) � ((p � q) � (r � r)) � ((p � q) � (r � r)) � (( q � r) � (p � p)) � (p � q � r) � (p � q � r) � (p � q � r) � (p � q � r) � (p � q � r) � (p � q � r) � ( p � q � r) � (p � q � r) � (p � q � r) � (p � q � r) � (p � q � r) � (p � q � r) � ( p � q � r) (1) In (1), we have got the PDNF of S. Now S � ( p � q � r) � ( p � q � r) � ( p � q � r) � S� S � (p � q � r) � (p � q � r) � (p � q � r) (2) (2) is the required PCNF of S. (iv) Let S � (p � (q � r)) � ( p � ( q � r)) � ( p � (q � r)) � (p � ( q � r)) � ( p � q) � ( p � r)) � (p � q) � (p � r) Discrete Mathematics 24 � (( p � q) � (r � r)) � (( p � r) � (q � q)) � ((p � q) � (r � r)) � ((p � r) � (q � q)) � ( p � q � r) � ( p � q � r) � ( p � q � r) � ( p � q � r) � (p � q � r) � (p � q � r) � (p � q � r) � (p � q � r) � (p � q � r) � (p � q � r) � (p � q � r) � ( p � q � r) � ( p � q � r) � ( p � q � r) EXERCISE 1(A) Part A: (Short answer questions) 1. Define the connectives conjunction and disjunction and give the truth tables for p � q and p � q. 2. Define conditional and biconditional propositions and also give the truth tables for p � q and p � q. 3. Define tautology and contradiction with simple examples. 4. When do you say that two compound propositions are equivalent? 5. Define the dual of compound proposition with an example. 6. What is the law of duality? 7. Give the primal and dual forms of the distributive law, absorption law and De Morgan's law. 8. Define tautological implication with an example. 9. When is a statement said to be satisfiable? 10. Define disjunctive and conjunctive normal forms of a statement. 11. Define PDNF and PCNF of a statement. 12. Construct the truth table for each of the following compound propositions: (a) (p � q) � (p � q) (b) (p � q) � ( q � p) (c) (p � q) � ( p � q) (d) (p � q) � ( p � q) (e) (p � q) � ( p � q) 13. Determine which of the following statements are tautologies or contradictions. (a) (p � p) � p (b) p � (p ��q) (c) ( q � p) � q (d) (q � p) � ( p � q) 14. Prove the following equivalences: (a) (p � q) � p � q (b) (p � q) � (p � q) � p (c) (p � q) � (p � q) � p (d) (p � q) � (p � q) � ( p � q) Mathematical Logic 25 15. Write down the duals of the following statements: (a) (p � q) � [( p) � q]�� p (b) p � (p � q) (c) (p � q) � (p � q) (d) (p � q) � ( q � 7p) 16. Prove the following implications, using truth tables: (a) (p � q) � (p � q) (b) (q � p) � p � q (c) p � q � p � (p � q) (d) (p � q) � q � p � q 17. Find a DNF or a CNF of the following: (a) (p � (p � q) (b) (p � q) (c) (p � q) (d) q � (p � q) 18. Find the PDNF of the following statements using truth tables: (a) p � (p � q) (b) (p � q) � p � q (c) q � (p � q) (d) (q � p) � ( p � q) 19. Find the PCNF of the following statements using truth tables: (a) p � q (b) (p � q) � (p � q) (c) ( (p � q)) � (p � q) (d) (q � p) � ( p � q) (e) p � (p � (q � p) Part B 20. Construct the truth table for each of the following compound propositions: (a) ( p � ( q � r)) � (q � r) � (p � r) (b) (p � q) � (q � r) � (p � r) (c) ((p � q) � ((p � r) � (q � r))) � r (d) (p � q) � ( q � r) (e) (p � q) � (r � s) 21. Determine which of the following statements are tautologies or contradictions: (a) (p � q) � (p � q) (b) q � (p � q) � ( p � q) (c) (p � q) � ( p � r) � (q � r) (d) ((p � (q � r)) � ((p � q) � (p � r)) (e) ((p � q) � ( p � ( q � r))) � ( p � q) � ( p � r) 22. By constructing truth tables, prove the following equivalences: (a) (p � q) � (p � r) � p � (q � r) 26 23. 24. 25. 26. 27. 28. 29. 30. 31. Discrete Mathematics (b) q � (p � q) � ( p � q) � F (c) (p � q) � (r � q) � (p � r) � q Without using truth tables, prove the following equivalences: (a) (p � q) � ( p � ( p � q)) � ( p � q) (b) ( p � ( q � r)) � (q � r) � (p � r) � r (c) p � (q � r) � (p � q) � (p � r) (d) (p � q) � r � (p � r) � (q � r) (e) ( p � q) � (q � p) � T Write down the duals of the following equivalences and prove the duals without using truth tables: (a) (p � q) � ( p � ( p � q)) � ( p � q) (b) ( p � ( p � ( p � q))) � p � q (c) p � q � (p � q) � (p � q) (d) (p � r) � (q � r) � (p � q) � r (e) p � (q � r) � q � (p � r) Prove the following implications, using truth tables: (a) ((p � (q � r)) � p) � ( q � r) (b) (p � q) � (p � r) � (q � s) � (s � r) Prove the following implications, without using truth tables: (a) (p � q) � (q � r) � (p � r) (b) (q � (p � p)) � (r � (p � p)) � (r � q) Find the DNF of the following statements: (a) (p � (q � r)) (b) ( p � r)�� (p � q) (c) (q � (p � r)) � ((p � r) � q) Find the CNF of the following statements: (a) (p � q) � (p � q) (b) ((p � q) � r) (c) q � (p � r) � ((p � r) � q) Find the PDNF and PCNF of the following statements using truth tables: (a) p � (p � (q � p)) (b) (q � p) � ( p � q) (c) (p � q) � (p � r) � (q � r) (d) (p � q) � ( p � q) � (q � r) Without using truth tables, find the PDNF of the following statements: (a) (p � q) � ( p � r) � (q � r) (b) p � ((p � q) � ( q � p)) (c) ( ((p � q) � r)) � (p � r) (d) (p � q) � (q � p) � (r � p) Without using truth tables, find the PCNF of the following statements: (a) ( p � r) � (q � p) (b) p � (p � q) � p � ( p � q) (c) p � ( p � q � r) (d) p � ( p � (q � ( q � r))) Mathematical Logic 27 THEORY OF INFERENCE Introduction Inference theory is concerned with the inferring of a conclusion from certain hypotheses or basic assumptions, called premises, by applying certain principles of reasoning, called rules of inference. When a conclusion derived from a set of premises by using rules of inference, the process of such derivation is called a formal proof. The rules of inference are only means used to draw a conclusion from a set of premises in a finite sequence of steps, called argument. These rules will be given in terms of statement formulas rather than in terms of any specific statements or their truth values. In this section we deal with the rules of inference by which conclusions are derived from premises. Any conclusion which is arrived at by following these rules is called a valid conclusion and the argument is called a valid argument. The actual truth values of the premises and that of the conclusion do not play any part in the determination of the validity of the argument. However, if the premises are believed to be true and if proper rules of inference are used, then the conclusion may be expected to be true. TRUTH TABLE TECHNIQUE When A and B are two statement formulas, then B is said to (logically) follow A or B is a valid conclusion of the premise A, if A � B is a tautology, viz., A � B. Extending, a conclusion C is said to follow from a set of premises H1, H2, … Hn, if (H1 � H2 � … � Hn) � C. If a set of premises and a conclusion are given, it is possible to determine whether the conclusion follows from the premises by constructing relevant truth tables, as explained in the following example. This method is known as truth table technique. For example, let us consider (i) H1: p, H2: p � q, C : q (ii) H1: p � q, H2: q, C : p Table 1.34 (i) H1 and H2 are true only in the third row, p q p p�q p�q in which case C is also true. Hence (i) is T T F T T valid T F F T F (ii) H1 and H2 are true in the first and third F T T T T rows, but C is not true in the third row. F F T F T Hence (ii) is not a valid conclusion. Note The truth table technique becomes tedious, if the premises contain a large number of variables. RULES OF INFERENCE Before we give the frequently used rules of inference in the form of tautologies in a table, we state two basic rules of inference called rules P and T. Rule P A premise may be introduced at any step in the derivation. Discrete Mathematics 28 Rule T A formula S may be introduced in the derivation, if S is tautologically implied by one or more preceding formulas in the derivation. Table 1.35 Rules of Inference Rule in tautological form Name of the rule (p � q) � p (viz., p � q � p) � (p � q) � q (viz., p � q � q) � � p � (p � q) � � q � (p � q) � ((p) � (q)) � (p � q) [p � (p � q)] � q [ q � (p � q)] � p [(p � q) � (q � r)] � (p � r) [(p � q) � p] � q [(p � q) � ( p � r)] � (q � r) [(p � q) � (p � r) � (q � r)] � r Simplification Addition Conjunction Modus ponens Modus tollens Hypothetical syllogism Disjunctive syllogism Resolution Dilemma FORM OF ARGUMENT When a set of given statements constitute a valid argument, the argument form will be presented as in the following example: "If it rains heavily, then travelling will be difficult. If students arrive on time, then travelling was not difficult. They arrived on time. Therefore, it did not rain heavily." Let the statements be defined as follows: p: It rains heavily q: Travelling is difficult r: Students arrived on time Now we have to show that the premises p � q, r � q and r lead to the conclusion p. The form of argument given as follows shows that the premises lead to the conclusion. Step No. 1. 2. 3. 4. 5. 6. Statement p�q q� p r� q r� p r p Reason Rule P T, Contrapositive of 1 Rule P T, Steps 2, 3 and hypothetical syllogism Rule P T, steps 4, 5 and Modus ponen RULE CP OR RULE OF CONDITIONAL PROOF In addition to the two basic rules of inference P and T, we have one more basic rule called Rule CP, which is stated below: If a formula s can be derived from another formula r and a set of premises, then the statement (r � s) can be derived from the set of premises alone. Mathematical Logic 29 The rule CP follows from the equivalence (p � r) � s � p � (r � s) Note If the conclusion is of the form r � s, we will take r as an additional premise and derive s using the given premises and r. INCONSISTENT PREMISES A set of premises (formulas) H1, H2, … Hn is said to be inconsistent, if their conjunction implies a contradiction. viz. if H1 � H2 � … � Hn � R � R, for some formula R. A set of premises is said to be consistent, if it is not inconsistent. INDIRECT METHOD OF PROOF The notion of inconsistency is used to derive a proof at times. This procedure is called the indirect method of proof or proof by contradiction or reduction and absurdum. In order to show that a conclusion C follows from the premises H1, H2, … Hn by this method, we assume that C is false and include C as an additional premise. If the new set of premises is inconsistent leading to a contradiction, then the assumption that C is true does not hold good. Hence C is true whenever H1 � H2 � … � Hn is true. Thus C follows from H1, H2, … Hn. For example, we prove that the premises q, p � q result in the conclusion p by the indirect method of proof. We now include p as an additional premise. The argument form is given below: Step No. 1. 2. 3. 4. 5. 6. 7. Thus the inclusion of Statement Reason p C p T, double negation, 1 p�q C q� p T, Contrapositive, 3 q C p T, Modus ponens, 4, 5 p� p T, Conjunction, 2, 6 C leads to a contradiction. Hence q, p � q � p. PREDICATE CALCULUS OR PREDICATE LOGIC Introduction In mathematics and computer programs, we encounter statements involving variables such as "x > 10", "x = y + 5" and "x + y = z". These statements are neither true nor false, when the values of the variables are not specified. The statement "x is greater than 10" has 2 parts. The first part, the variable x, is the subject of the statement. The second part "is greater than 10", which Discrete Mathematics 30 refers to a property that the subject can have, is called the predicate. We can denote the statement "x is greater than 10" by the notation P(x), where P denotes the predicate "is greater than 10" and x is the variable. P(x) is called the propositional function at x. Once a value has been assigned to the variable x, the statement P(x) becomes a proposition and has a truth value. For example, the truth values of P(15){� 15 > 10} and P(5){� 5 > 10} are T and F respectively. The statements "x = y + 5" and "x + y = z" will be denoted by P(x, y) and P(x, y, z) respectively. The logic based on the analysis of predicates in any statement is called predicate logic or predicate calculus. QUANTIFIERS Many mathematical statements assert that a property is true for all values of a variable in a particular domain, called the universe of discourse. Such a statement is expressed using a universal quantification. The universal quantification of P(x) is the statement. "P(x) is true for all values of x in the universe of discourse" and is denoted by the notation (x)P(x) or � xP(x). The proposition (x)P(x) or � xP(x) is read as "for all x, P(x)" or "for every x, P(x)". The symbol � is called the universal quantifier. Let us consider �x P(x) � �x, (x2 – 1) = (x – 1)(x + 1) (1) (1) is a proposition and not a propositional function, even though a variable x appears in it. We need not replace x by a number to obtain a statement. The truth value of �x P(x) is T.] Note Examples 1. If P(x) � {(–x)2 = x}, where the universe consists of all integers, then the truth value of �x((–x)2 = x2) is T. 2. If Q(x) � "2x > x", where the universe consists of all real numbers, then the truth value of �x Q(x) is F. 3. If P(x) � "x2 <10", where the universe consists of the positive integers 1, 2, 3 and 4, then �x P(x) = P(1) � P(2) � P(3) � P(4) and so the truth value of �x P(x) = T � T � T � F = F. We have so far applied universal quantification to propositional functions of a single variable only. Universal quantification (and also existential quantification, that is discussed below) can be applied to compound propositional functions such as P(x) � Q(x), P(x) � Q(x), P(x), P(x) � Q(x) etc. and to propositional functions of many variables, as given in the following examples.] Note 4. Let P(x) � x is an integer and Q(x) � x is either positive or negative. Then P(x) � Q(x) is a compound propositional function. Obviously �x(P(x) � Q(x)), where the universe of discourse consists of integers. 5. Let P(x, y): x is taller than y. If x is taller than y, then y is not taller than x. viz. P(x, y) � P(y, x) Mathematical Logic 31 As this assertion is true for all x and y, it can be symbolically represented as �x � y (P(x, y) � P(y, x)) EXISTENTIAL QUANTIFIER The existential quantification of P(x) is the proposition. "There exists at least one x (or an x) such that P(x) is true" and is denoted by the notation �xP(x). The symbol � is called the existential quantifier. The proposition �xP(x) is read as "For some x, P(x)". Examples 1. When P(x) denotes the propositional function "x > 3", the truth value of �xP(x) is T, where the universe of discourse consists of all real numbers, since "x > 3" is true for x = 4. When the elements of the universe of discourse is finitely many, viz., consists of x1, x2, … xn, then �xP(x) is the same as the disjunction P(x1) � P(x2) � … � P(xn), since this disjunction is true if and only if at least one of P(x1), P(x2), …, P(xn) is true. Note 2. When P(x) denotes "x2 > 10", where the universe of discourse consists of the positive integers not exceeding 4, then the truth value of �xP(x) is T, since P(1) � P(2) � P(3) � P(4) is true as P(4) [viz., 42 > 10] is true. NEGATION OF A QUANTIFIED EXPRESSION If P(x) is the statement "x has studied computer programming", then � xP(x) means that "every student (in the class) has studied computer programming". The negation of this statement is "It is not the case that every student in the class has studied computer programming" or equivalently "There is a student in the class who has not studied computer programming" which is denoted by �x P(x). Thus we see that �xP(x) � �x P(x). Similarly, �xP(x) means that "there is a student in the class who has studied computer programming "The negation of this statement is "Every student in this class has not studied computer programming", which is denoted by � x P(x). Thus we get �xP(x) � � x P(x) � xP(x) is true, when there is an x for which P(x) is Further we note that false and false when P(x) is true for every x, since � xP(x) � �x P(x) � P(x1) � P(x2) … � P(xn) �xP(x) is true, when P(x) is false for every x and false when there is an x for which P(x) is true, � xP(x) � � x P(x) since � P(x1) � P(x2) … � P(xn) Discrete Mathematics 32 NESTED (MORE THAN ONE) QUANTIFIERS There are situations when quantifiers occur in combinations in respect of 1-place or n-place predicate formulas (i.e., propositional functions containing 1 or n variables). For example let us consider a 2-place predicate formula P(x, y). Now �x �y P(x, y) � �x[�y P(x, y)] � �y[�x P(x, y)] (1) and � x �y P(x, y) � �x[�y P(x, y)] � �y[�x P(x, y)] (2) From the meaning of quantifiers and by (1) and (2) the following simplifications hold good: �x �y P(x, y) � (�y) � x P(x, y) � � x �y P(x, y) �y �x P(x, y) � (�x) � y P(x, y) � � y �x P(x, y) Note Thus The negation of multiply quantified predicate formulas may be obtained by applying the rules for negation (given earlier) from left to right. [�x �y P(x, y)] � �x[ �y P(x, y)] � �x �y[ P(x, y)] FREE AND BOUND VARIABLES When a quantifier is used on a variable x or when we have to assign a value to this variable to get a proposition, the occurrence of the variable is said to be bound or the variable is said to be a bound variable. An occurrence of a variable that is not bound by a quantifier or that is set equal to a particular value is said to be free. The part of the logical expression or predicate formula to which a quantifier is applied is called the scope of the quantifier. Examples Table 1.36 Predicate formula 1. � x P(x, y) 2. � x (P(x) �Q(x)) 3. � x (P(x) � E(y)Q(x, y)) 4. � x (P(x) � Q(x)) � � y R(y) 5. � x P(x) � Q(x) Bound variable and scope x; P(x, y) x; P(x) �Q(x) x; P(x) � E(y)Q(x, y) y; Q(x, y) x; P(x) � Q(x) y; R(y) First x; P(x) Free variable y — — — Second x VALID FORMULAS AND EQUIVALENCES Let A and B be any two predicate formulas defined over a common universe of discourse E. When each of the variables appearing in A and B is replaced by any element (object name) of the universe E, if the resulting statements have the same truth values, then A and B are said to be equivalent to each other over Mathematical Logic 33 E and denoted as A � B or A � B over E. If E is arbitrary, we simply say that A and B are equivalent and denote it as A � B or A � B. Generally, logically valid formulas in predicate calculus can be obtained from tautologies of propositional calculus by replacing primary propositions (elementary statements) such as p, q, r by propositional functions. For example, p � p � T and (p � q) � ( p � q) � T are tautologies in statement calculus. If we replace p by � R(x) and q by �x S(x) in the above, we get the following valid formulas in predicate calculus. (�x R(x)) � ( �x R(x)) � T (� x R(x) � �x S(x)) � (( � x R(x)) � �x S(x)) � T More generally, all the implications and equivalences of the statement calculus can also be considered as implications and equivalences of the predicate calculus if we replace elementary statements by primary predicate formulas. For example, from p � p, we get P(x) � P(x) (1) from p � q � q � p, we get P(x) � Q(x, y) � Q(x, y) � P(x) (2) from p � q � p � q, we get P(x) � Q(x) � P(x) � Q(x) (3) (1), (2) and (3) are some examples for valid formulas in predicate calculus. Apart from the types of valid formulas given above, there are other valid formulas also which involve quantifiers. Such valid formulas are obtained by using the inference theory of predicate logic, discussed below: INFERENCE THEORY OF PREDICATE CALCULUS Derivations of formal proof in predicate calculus are done mostly in the same way as in statement calculus, using implications and equivalences, provided that the statement formulas are replaced by predicate formulas. Also the three basic rules P, T and CP of Inference theory used in statement calculus can also be used in predicate calculus. Moreover, the indirect method of proof can also be used in predicate calculus. Apart from the above rules of inference, we require certain additional rules to deal with predicate formulas involving quantifiers. If it becomes necessary to eliminate quantifiers during the course of derivation, we require two rules of specification, called US and ES rules. Once the quantifiers are eliminated, the derivation is similar to that in statement calculus. If it becomes necessary to quantify the desired conclusion, we require two rules of generalisation, called UG and EG rules. Rule US Universal Specification is the rule of inference which states that one can conclude that P(c) is true, if � x P(x) is true, where c is an arbitrary member of the universe of discourse. This rule is also called the universal instantiation. Rule ES Existential Specification is the rule which allows us to conclude that P(c) is true, if �x P(x) is true, where c is not an arbitrary member of the Discrete Mathematics 34 universe, but one for which P(c) is true. Usually we will not know what c is but know that it exists. Since it exists, we may call it c. This rule is also called the existential instantiation. Rule UG Universal Generalisation is the rule which states that � x P(x) is true, if P(c) is true, where c is an arbitrary member (not a specific member) of the universe of discourse. Rule EG Existential Generalisation is the rule that is used to conclude that �x P(x) is true when P(c) is true, where c is a particular member of the universe of discourse. Examples 1. Let us consider the following "Famous Socrates argument" which is given by: All men are mortal. Socrates is a man. Therefore Socrates is a mortal. Let us use the notations H(x): x is a man M(x): x is a mortal s: Socrates With these symbolic notations, the problem becomes � x(H(x) � M(x)) � H(s) � M(s) The derivation of the proof is as follows: Step No. Statement Reason 1. � x (H(x) � M(x)) P 2. H(s) � M(s) US, 2 3. H(s) P 4. M(s) T, 2, 3, Modus ponens 2. Application of any of US, ES, UG and EG rules wrongly may lead to a false conclusion from a true premise as in the following example Let D(u, v): u is divisible by v, where the universe of discourse is (5, 6, 10, 11). Then �u D(u, 5) is true, since D(5, 5) and D(10, 5) are true. But � u D(u, 5) is false, since D(6, 5) and D(11, 5) are false. We now give the following derivation: Step No. 1. 2. 3. Note Statement � u D(u, 5) D(c, 5) � x D(x, 5) Reason P ES, 1 UG, 2 In step (3), UG has been applied wrongly, since c is not an arbitrary member in step (2), as c(= 5 or 10) is only a specific member of the given universe of discourse. Mathematical Logic 35 WORKED EXAMPLES 1(B) Example 1.1 Find whether the conclusion C follows from the premises H1, H2, H3 in the following cases, using truth table technique: (i) H1: p, H2: p � q, C: p � q (ii) H1: p � q, H2: p � r, H3: q � r, C: r Table 1.37 (i) p q H1 � T T F F T F T F F F T T H2 � p p q T T T F H1 � H2 C�p�q F F T F T F F F H1 and H2 and hence H1 � H2 are true in the third row, in which C is false. Hence C does no follow from H1 and H2. Table 1.38 (ii) p q r T T T T F F F F T T F F T T F F T F T F T F T F H1(p � q) H2(p � r) T T T T T T F F T F T F T T T T H3(q � r) H1 � H2 � H3 T F T T T F T T T F T F T F F F H1, H2, H3 and hence H1� H2 � H3 are true in the first, third and fifth rows in which r is also true. Hence C follows from H1, H2 and H3. Example 1.2 q� Show that (t � s) can be derived from the premises p � q, r, r, p � (t � s). Step No. 1. 2. 3. 4. 5. 6. 7. 8. Statement p�q q� r p� r r� p r p p � (t � s) t�s Reason P P T, T, P T, P T, 1, 2 and Hypothetical syllogism 3 and p � q � q � p 4, 5 and Modus ponens 6, 7 and Disjunctive syllogism Discrete Mathematics 36 Example 1.3 p � q, (p � q) � Step No. 1. 2. 3. 4. 5. 6. 7. Show that (a � b) follows logically from the premises r, r � (s � t) and (s � t) � (a � b). Statement (p � q) � r r � (s � t) (p � q) � (s � t) p�q s� t (s � t) � (a � b) a�b Example 1.4 and (p � r) � Step No. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. Example 1.5 Step No. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. Reason P P T, 1, 2 and hypothetical syllogism P T, 3, 4 and modus ponens P T, 5, 6 and Modus ponens Show that (p � q) � (r � s), (q � t) � (s � u), (t � u) p. Statement (p � q) � (r � s) p�q r�s (q � t) � (s � u) q�t s�u p�t r�u p�r p�u t� p u� p ( t � u) � p (t � u) � (t � u) p p Reason P T, 1 and simplification T, 1 and simplification P T, 4 and simplification T, 4 and simplification T, 2, 5 and hypothetical syllogism T, 3, 6 and hypothetical syllogism P T, 8, 9 and hypothetical syllogism T and 7 T and 10 T, 11, 12, and (a � b), (c � b) � (a � c) � b T, 13 and De Morgan's law P T, 14, 15 and modus ponens. Show that (a � b) � (a � c), Statement (a � b) � (a � c) a�b a�c b� a c� a ( b � c) � a (b � c) � a (b � c) a d�a (b � c), (d � a) � d Reason P T, 1 and simplification T, 1 and simplification T, 2 and contrapositive T, 3 and contrapositive T, 4 and 5 T and De Morgan's law P T, 7, 8 and modus ponens P Mathematical Logic (d � a) � a (d � a) � (a � (d � a) � F d� a d 11. 12. 13. 14. 15. Example 1.6 a) T, T, T, T, T, 37 9, 10 and conjunction 11 and distributive law 12 and negation law 13 and identity law 14 and simplification Give a direct proof for the implication p � (q � s), ( r � p), q � (r � s). Step No. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. Statement r�p r�p p � (q � s) r � (q � s) r � ( q � s) q q � ( r � q � s) q � ( r � s) r�s r�s Reason P T, 1 and equivalence of (1) P T, 2, 3 and hypothetical syllogism. T, 4 and equivalence of (4) P T, 5, 6 and conjunction T, 7, 8 and negation and domination laws T, 8 and simplification T, 9 and equivalence of (9) Example 1.7 Derive p � (q � s) using the CP-rule (if necessary) from the premises p � (q � r) and q � (r � s). We shall assume p as an additional premise. Using p and the two given premises, we will derive (q � s). Then, by CP-rule, p � (q � s) is deemed to have been derived from the two given premises. Step No. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. Statement p p � (q � r) q�r q�r q � (r � s) q � (r � s) q � (r � (r � s)) q�s q�s p � (q � s) Reason P(additional) P T, 1, 2 and modus ponens T, 3 and equivalence of (3) P T, 5 and equivalence of (5) T, 4, 6 and distributive law T, 7 and modus ponens T, 8 and equivalence of (8) T, 9 and CP-rule Example 1.8 Use the indirect method to show that r � q, r � s, s � q, p � q � p. p � p as an additional To use the indirect method, we will include premise and prove a contradiction. Step No. 1. 2. Statement p p�q Reason P (additional) P Discrete Mathematics 38 3. 4. 5. 6. 7. 8. 9. 10. q r� q s� q (r � s) � 7q r�s q q� q F T, P P T, P T, T, T, 1, 2 and modus ponens 4, 5 and equivalence 6, 7 and modus ponens 3, 8 and conjunction 9 and negation law Example 1.9 Show that b can be derived from the premises a � b, c � b, d � (a � c), d, by the indirect method. Let us include b as an additional premise and prove a contradiction. Step No. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. Statement a�b c�b (a � c) � b d � (a � c) d�b d b b b� b F Reason P P T, 1, 2 and equivalence P T, 3, 4 and hypothetical syllogism P T, 5, 6 and modus ponens P (additional) T, 7, 8 and conjunction T, 9 and negation law. Example 1.10 Using indirect method of proof, derive p � s from the premises p � (q � r), q � p, s � r, p. Let us include (p � s) as an additional premise and prove a contradiction. Now (p � s) = ( p � s) = p � s Hence the additional premise to be introduced may be taken as p � s. Step No. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. Statement q � (q � r) p q�r p�s s s� r r q q� p p p� p F Reason P P T, 1, 2 and modus ponens P (additional) T, 4 and simplification P T, 5, 6 and modus ponens T, 3, 7 and disjunctive syllogism P T, 8, 9 and modus ponens T, 2, 10 and conjunction T, 11 and negation law Mathematical Logic 39 Example 1.11 Prove that the premises p � q, q � r, s � r and p � s are inconsistent. If we derive a contradiction by using the given premises, it means that they are inconsistent. Step No. Statement Reason 1. p�q P 2. q�r P 3. p�r T, 1, 2 and hypothetical syllogism P 4. s� r 5. r� s T, 4 and contrapositive 6. q� s T, 2, 5 and hypothetical syllogism 7. q� s T, 6 and equivalence of (6) 8. (q � s) T, 7 and De Morgan's law 9. q�s P 10. (q � s) � (q � s) T, 8, 9 and conjunction 11. F T, 10 and negation law Hence the given premises are inconsistent Example 1.12 Prove that the premises a � (b � c), d � (b � (a � d) are inconsistent. Step No. Statement 1. a�d 2. a 3. d 4. a � (b � c) 5. b�c b�c 6. 7. d � (b � c) (b � c) � d 8. 9. b�c� d d 10. 11. d� d 12. F Hence the given premises are inconsistent. Example 1.13 c) and Reason P T, T, P T, T, P T, T, T, T, T, 1 and simplification 1 and simplification 2, 4 and modus ponens 5 and equivalence of (5) 7 and contrapositive 8 and equivalence 6, 9 and modus ponens 3, 10 and conjunction 11 and negation law Construct an argument to show that the following premises imply the conclusion " it rained". "If it does not rain or if there is no traffic dislocation, then the sports day will be held and the cultural programme will go on"; "If the sports day is held, the trophy will be awarded" and "the trophy was not awarded". Let us symbolise the statement as follows: p: It rains. q: There is traffic dislocation. Discrete Mathematics 40 r: Sports day will be held. s: Cultural programme will go on. t: The trophy will be awarded. Then we have to prove that p � q � r � s, r � t, Step No. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. t�p Statement Reason p� q�r�s P ( p � (r � s)) � ( q � (r � s)) T, 1 and the equivalence (a � b) � c � (a � c) � (b � c) (r � s) � p T, 2 and contrapositive of (2) r�t P t� r T, 4 and contrapositive of (4) t P r T, 5, 6 and modus ponens r� s T, 7 and addition (r � s) T, 8 and De Morgan's law p T, 3, 9 and modus ponens Example 1.14 Show that the following set of premises is inconsistent: If Rama gets his degree, he will go for a job. If he goes for a job, he will get married soon. If he goes for higher study, he will not get married. Rama gets his degree and goes for higher study. Let the statements be symbolised as follows: p: Rama gets his degree. q: He will go for a job. r: He will get married soon. s: He goes for higher study. Then we have to prove that p � q, q � r, s � r, p � s are inconsistent Step No. Statement Reason 1. p�q P 2. q�r P 3. p�r T, 1, 2 and hypothetical syllogism 4. p�s P 5. p T, 4 and simplification 6. s T, 4 and simplification 7. s� r P 8. r T, 6, 7 and modus ponens 9. r T., 3, 5 and modus ponens 10. r� r T, 8, 9 and conjunction 11. F T, 10 and negation law Hence the set of given premises is inconsistent. Mathematical Logic 41 Example 1.15 If L(x, y) symbolises the statement "x loves y", where the universe of discourse for both x and y consists of all people in the world, translate the following English sentences into logical expressions: (a) Every body loves z. (b) Every body loves somebody. (c) There is somebody whom everybody loves. (d) Nobody loves everybody. (e) There is somebody whom no one loves. (a) L(x, z) for all x. Hence � x L(x, z) (b) L(x, y) is true for all x and some y. Hence � �y L(x, y) (c) Eventhough, (c) is the same as (b), the stress is on the existence of somebody (y) whom all x love. Hence ��y � x L(x, y) (d) Nobody loves every body i.e., There is not one who loves everybody �x �y L(x, y) Hence � �x � y L(x, y) � �x �y L(x, y) (e) The sentence means that there is somebody whom every one does not love. �x �y L(x, y) Hence � �x �y L(x, y) � �x �y L (x, y) and logical operations, predicates and quantifiers, where the universe of discourse consists of all computer science students/mathematics courses. (a) Every computer science student needs a course in mathematics. (b) There is a student in this class who owns a personal computer. (c) Every student in this class has taken at least one mathematics course. (d) There is a student in this class who has taken at least one mathematics course. (a) Let M(x) � 'x needs a course in mathematics', where the universe of discourse consists of all computer science students. Then �x M(x). (b) Let P(x) � 'x owns a personal computer', where the universe consists of all students in this class. Then �x P(x) (c) Let Q(x, y) � 'x has taken y', where the universe of x consists of all students in this class and that of y consists of all mathematics courses. Then �x �y Q(x, y) (d) Using the same assumptions as in (c), we have �x �y Q(x, y). 42 Example 1.17 Discrete Mathematics Express the negations of the following statements using quantifiers and in English: (a) If the teacher is absent, then some students do not keep quiet. (b) All the students keep quiet and the teacher is present. (c) Some of the students do not keep quiet or the teacher is absent. (d) No one has done every problem in the exercise. (a) Let T represent the presence of the teacher and Q(x) represent "x keeps quiet". Then the given statement is: T � �x Q(x) � T � �x Q(x) � T � �x Q(x) � Negation of the given statement is (T � �x Q(x)) � T � �x Q(x) i.e., the teacher is absent and all the students keep quiet. (b) The given statement is: �x Q(x) � T � The negation of the given statement is (�x Q(x) � T) � �x Q(x) � T � �x Q(x) � T i.e., some students do not keep quiet or the teacher is absent. (c) The given statement is: �x Q(x) � T � �x Q(x) � T � The negation of the given statement is ( �x Q(x) � T) � �x Q(x) � T i.e., All the students keep quiet and the teacher is present. (d) Let D(x, y) represent "x has done problem y". The given statement is ( �x)(�y D(x, y)) (1) � The negation of the given statement is ( � (x))(�y D(x, y)) � �x �y D(x, y) (2) i.e., some one has done every problem in the exercise. Aliter: (1) can be re-written as �x �y D(x, y) � �x �y D(x, y) � The negative of this statement is �x �y D(x, y) � �x �y D(x, y) � �x �y D(x, y), which is the same as (2). Mathematical Logic 43 Example 1.18 Show that the premises "one student in this class knows how to write programs in JAVA" and "Everyone who knows how to write programs in JAVA can get a high-paying job" imply the conclusion "Someone in this class can get a high-paying job". Let C(x) represent "x is in this class" J(x) represent "x knows JAVA programming" and H(x) represent "x can get a high paying job". Then the given premises are �x (C(x) � J(x)) and �x (J(x) � H(x)). The conclusion is � x(C(x) � H(x)). Step No. 1. 2. 3. 4. 5. 6. 7. 8. 9. Statement �x(C (x) � J(x)) C(a) � J(a) C(a) J(a) �x (J(x) � H(x)) J(a) � H(a) H(a) C(a) � H(a) �x (C(x) � H(x)) Reason P ES and 1 T, 2 and simplification T, 2 and simplification P US and 5 T, 4, 6 and modus ponens T, 3, 7 and conjunction EG and 8. Example 1.19 Show, by indirect method of proof, that �x (p(x) � q(x)) � (�x p(x)) � (�x q(x)). Let us assume that [(�x p(x)) � (�x q(x))] as an additional premise and prove a contradiction. Step No. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. Statement [(�x p(x)) � (�x q(x))] (�x p(x)) � (�x q(x)) (�x p(x)) (�x q(x)) �x p(x) �x q(x) p(a) q(a) p(a) � q(a) (p(a) � q(a) �x (p(x) � q(x)) p(a) � q(a) (p(a) � q(a)) � (p(a) � q(a)) F Example 1.20 Reason P(additional) T, 1, De Morgan's law T, 2, simplification T, 2, simplification T, 3 and negation T, 4 and negation ES and 5 US and 6 T, 7, 8 and conjunction T, 9 and De Morgan's law P US and 11 T, 10, 12 and conjunction T, 13 Prove that �x (P(x) � (Q(y) � R(x))), �x P(x) � Q(y) � �x (P(x) � R(x)). Step No. 1. 2. Statement �x (P(x) � (Q(y) � R(x))) P(z) � (Q(y) � R(z)) Reason P US and 1 Discrete Mathematics 44 3. 4. 5. 6. 7. 8. 9. 10. �x P(x) P(z) Q(y) � R(z) Q(y) R(z) P(z) � R(z) �x (P(x) � R(x)) Q(y) � �x (P(x) � R(x) P ES and 3 T, 2, 4 and modus ponens T, 5 and simplification T, 5 and simplification T, 4, 7 and conjunction EG and 8 T, 6, 10 and conjunction Example 1.21 Show that the conclusion �x(P(x) � Q(x)) follows from the premises �x (P(x) � Q(x)) � �y (R(y) � S(y)) and �y (R(y) � S(y)). Step No. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. Statement �y (R(y) � S(y)) R(a) � S(a) (R(a) � S(a)) �y ( (R(y) � S(y))) 7�y (R(y) � S(y)) �x (P(x) � Q(x))� �y (R(y) � S(y)) �x (P(x) � Q(x)) �x (P(x) � Q(x)) (P(b) � Q(b)) P(b) � Q(b) P(b) � Q(b) �x (P(x) � Q(x)) Example 1.22 Step No. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. Reason P ES and 1 T, 2 and equivalence EG and 3 T, 4 and negation equivalence P T, 5, 6 and modus tollens T, 7 and negative equivalence US and 8 T, 9 and De Morgan's law T, 10 and equivalence UG and 11. Prove the derivation �x P(x) � �x ((P(x) � Q(x)) � R(x)), �x P(x), �x Q(x) � �x �y (R(x) � R(y)) Statement �x P(x) � �x((P(x) ��Q(x)) � R(x) P(a) � (P(b) � Q(b) � R(b)) �x P(x) P(a) (P(b) � Q(b)) � R(b) �x Q(x) Q(b) P(b) � Q(b) R(b) �x R(x) R(a) Reason P ES, US and 1 P ES and 3 T, 2, 4 and modus ponens P ES and 6 T, 7 and addition T, 5, 8 and modus ponens EG and 9 ES and 9 Mathematical Logic R(a) � R(b) �y (R(a) � R(y)) �x �y (R(x) � R(y)) 12. 13. 14. 45 T, 9, 11 and conjunction EG and 12 EG and 13. Example 1.23 Prove the implication �x (P(x) � Q(x)), �x (R(x)� Q(x)) � �x (R(x) � Step No. 1. 2. 3. 4. 5. 6. 7. 8. Statement �x (P(x) � Q(x)) P(a) � Q(a) �x (R(x) � Q(x)) R(a) � Q(a) Q(a) � R(a) P(a) � R(a) R(a) � P(a) �x R(x) � P(x)) P(x)). Reason P US and 1 P US and 2 T, 4 and equivalence T, 2, 5 and hypothetical syllogism T, 6 and equivalence UG and 7 Example 1.24 Use the indirect method to prove that the conclusion �z Q(z) follows from the premises �x (P(x) � Q(x)) and �y P(y). Let us assume the additional premise (�z Q(z)) and prove a contradiction Step No. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. Statement (�z Q(z)) �z ( Q(z)) Q(a) �y P(y) P(a) P(a) � Q(a) ( P(a) � Q(a) (P(a) � Q(a)) �x (P(x) � Q(x)) P(a) � Q(a) (P(a) � Q(a)) � (P(a) � Q(a)) F Example 1.25 Reason P (additional) T, 1 and negation equivalence US and 2 P ES and 4 T, 3, 5 and conjunction T, 6 and equivalence T, 7 and equivalence P US and 9 T, 8, 10 and conjunction T, 11 and negative law Show that �x (P(x) � Q(x)) � �x P(x) � �x Q(x), using the indirect method Step No. 1. 2. 3. 4. 5. 6. 7. Statement (�x P(x) � �x Q(x)) (�x P(x) � (�x Q(x)) �x ( P(x)) � �x ( Q(x)) �x ( P(x)) �x ( Q(x)) P(a) Q(a) Reason P (additional) T, 1 and De Morgan's law T, 2 and negation equivalence T, 3 and simplification T, 3 and simplification ES and 4 US and 5 Discrete Mathematics 46 8. 9. 10. 11. 12. 13. P(a) � Q(a) T, 6, 7 and conjunction (P(a) � Q(a)) T, 8 and De Morgan's law �x (P(x) � Q(x)) P P(a) � Q(a) US and 10 (P(a) � Q(a)) � (P(a) � Q(a)) T, 9, 11 and conjunction F T, 12 and negation law. EXERCISE 1(B) Part A: (Short answer questions) 1. What is meant by 'formal proof' in the context of mathematical logic? Show that the conclusion C follows from the premises H1, H2, H3 in the following cases, using truth table technique. 2. H1 : q, H2 : p � q, C : p 3. H1 : p � q, H2 : q � r, C : p � r 4. H1 : p � q, H2 : (p � q), C : p 5. H1 : p, H2 : p � q, C : (p � q) 6. State the P, T and CP rules of inference. 7. State the inference rules of modus ponens and modus tollens. 8. State the inference rules of hypothetical syllogism and disjunction syllogism 9. When is a set of premises said to be inconsistent? 10. What do you mean by indirect method of proof? 11. Prove that p, p � q, q � r � r 12. Prove that q, p � q � p 13. Prove that p, p � q � q 14. Prove that (p � q) � p � (p � q) 15. Using indirect method, prove that p � q � (p � q). 16. Show that the hypotheses "x works hard", "If x works hard, then he is a dull boy" and " If x is a dull boy, then he will not get a job" imply the conclusion "x will not get a job". 17. "If you help me, then I will do my home work". "If you do not help me, then I will go to sleep early". "If I go to bed early, the teacher will punish me". Show that the above hypotheses lead to the conclusion "If I do not do my home-work, then the teacher will punish me". 18. What do you mean be predicate and predicate logic? 19. Define universal and existential quantifiers. 20. Prove or disprove: [�x �y P(x, y)] = [�x �y P(x, y)] 21. What are free and bound variables in predicate logic? 22. What are the ways by which we can get valid formulas and equivalences in predicate logic? 23. Define the rules of specification and generalisation in predicate logic. Mathematical Logic 47 24. If A(x): x is an animal, B(x): x is black and C(x): x is a cat, translate the following in words: (a) �x[C(x)� A(x)]; (b) �x[C(x) � B(x)] 25. Show that �x P(x) � �x P(x) is a logically valid statement. 26. Show that �x (P(x) � Q(x)) � �x P(x) � �x Q(x) is a logically valid statement. 27. Show that � x (P(x) � Q(x)) � �x P(x) � �x Q(x) is a logically valid statement. 28. Show that �x P(x) � �x Q(x) � �x (P(x) � Q(x)) is a valid statement. Is the statement �x (P(x) � Q(x)) � �x P(x) � �x Q(x) valid? 29. Show that the premises " Everyone in the Computer Science branch has studied Discrete Mathematics" and "Ram is in Computer Science branch" imply that "Ram has studied Discrete Mathematics". 30. Show that [�x P(x) � Q(a)) � �x P(x) � Q(a) 31. Show that P(a, b) follow logically from �x �y (P(x, y) � Q(x, y)) and Q(a, b). 32. Negate the statements "Every student in this class is intelligent" in two different ways. Part B 33. Show that the conclusion C follows from the premises H1, H2, H3 in the following cases using truth table technique: (a) H1 : p � (q � r), H2 : p � q, C : r (b) H1 : p � q, H2 : (q � r), H3 : r; C : p 34. Prove the following by using direct method: (a) p � q, p � r, q � s � s � r. (b) a � b, (a � b) � (c � d) � d � c. (c) (p � q) � r, r � s, s � p � q. (d) p � q, q � r, p � s, s � r � (p � q). (e) (p � q), q � r, r � p. (f) p � q, ( q � r) � r, ( p � s) � s. (g) (p � q) � r, p � s, q � t � r. (h) j � (m � n), (h � g) � j, h � g � m � n 35. Prove the following by using indirect method: (a) p � q, q � r, (p � r), p � r � r. (b) q, p � q, p � r � r. (c) s � q, s � r, r, r � q � p. (d) (p � q) � (r � s), (q � p) � r, r � p � q. 36. Prove the following by using the CP rule. (a) (p � q) � r � (p � q) � r. (b) p � q, q � r, r � s � p � s. (c) p, p � (q � (r � s)) � q � s. (d) p �(q � s), r � p, q � r � s. 48 Discrete Mathematics 37. Prove that each of the following sets of premises is inconsistent: (a) p � q, p � r, q � r, p. (b) p � q, (q � r) � s, s � p, p � r. (c) p � (q � r), q � (r � s), p � q � 7s. Show that the following premises are inconsistent. 38. (i) If Raja misses many classes, then he fails in the final examination. (ii) If Raja fails in the final examination, then he is uneducated. (iii) If Raja reads a lot of books, then he is not uneducated. (iv) Raja misses many classes and reads a lot of books. 39. "It is not sunny this afternoon and it is colder than yesterday"; "We will go to the playground only if it is sunny". "If we do not go to the ground, then we will go to a movie" and "If we go to a movie, then we will return home by sunset" lead to the conclusion "We will return home by sunset". 40. Construct an argument using rules of inference to show that the hypotheses "Radha works hard", "If Radha works hard, then she is a dull girl" and "If Radha is a dull girl, then she will not get the job" imply the conclusion" "Radha will not get the job". 41. "If I eat spicy food, then I have strange dreams". "I have strange dreams, if there is thunder while I sleep". "I did not have strange dreams". What relevant conclusion can be drawn from the above premises? Construct an argument to obtain your conclusion. 42. Show that the following set of premises is inconsistent: John will get his degree, if and only if he passes all the examinations. He will pass all the examinations, if and only if he works hard. He will be unemployed, if and only if he does not get his degree. John works hard if and only if he is employed. 43. If A works hard, then B or C will enjoy themselves. If B enjoys himself, then A will not work hard. If D enjoys himself, then C will not. Therefore, if A works hard, D will not enjoy himself. Translate the above into statements and prove the conclusion by using the CP-rule. 44. Symbolise the following expressions: (a) x is the father of the mother of y. (b) Everybody loves a lover. 45. Prove the following implications (a) �x (P(x) � Q(x)) � �x (Q(x)� R(x)) � �x (P(x) � R(x)). (b) �x P(x), �x (P(x) � Q(x)) � �x Q(x). (c) �x (P(x) � Q(x)) � �x P(x)�� �x Q(x). (d) �x P(x) � �x Q(x) � �x (P(x)� Q(x)) (e) �x (P(x) � Q(x)) � �x P(x)� �x Q(x) (f) �x (C(x) � A(x)) � �x (�y (C(y)�� B(x, y)) � �y (A(y) � B(x, y))). 46. Show that the premises "A student in this class has not read the book" and "Everyone in this class passed the first examination" imply the conclusion "Someone who passed the first examination has not read the book." Mathematical Logic 49 47. Establish the validity of the following argument: Everyone who takes some fruit daily is healthy. X is not healthy. Therefore X does not take fruit daily. 48. Verify the validity of the following argument: Every living thing is a plant or an animal. Rama's dog is alive and it is not a plant. All animals have hearts. Therefore Rama's dog has a heart. 49. Establish the validity of the following argument: All integers are rational numbers. Some integers are powers of 2. Therefore some rational numbers are powers of 2. ANSWERS Exercise 1(A) Part (A) 12. (a) T, T, T, T (b) T, T, T, T (c) T, T, T, T (d) T, F, T, F (e) T, T, T, T (for the conventional order of truth values of p and q) 13. (a) tautology (b) Tautology (c) contradiction (d) contradiction. 15. (a) (p � q) � [( p) � q] � p (b) p � p � q (c) ( (p � q)) � ( p � q) (d) ( p � q) � (q � p) 17. (a) p � q (b) p � q (d) p � q (c) (p � q) � (q � p) 18. (a) p � q (b) (p � q) � ( p � q) (c) p � q (d) PDNF cannot be found out as the given statement is a contradiction. 19. (a) ( p � q) � (p � q) (b) ( p � q) � (p � q) (c) ( p � q) � (p � q) (d) ( p � q) � ( p � q) � (p � q) � (p � q) (e) PCNF cannot be found out, as the given statement is tautology. 20. (a) T, F, T, F, T, F, T, T (b) Given statement is a tautology (c) A tautology (d) T, T, T, F, F, T, T, T (e) T, F, F, T, F, T, T, F, F, T, T, F, T, F, F, T 21. (a) to (e)—all contradictions 27. (a) (p � q) � (p � r) (b) (p � q) � (p � q � r) � ( p � q � r) (c) (p � q � r) � ( p � q � r) 28. (a) (p � q) � ( p � q) (b) ( p � r) � (q � r) (c) (p � q) � (q � r) � ( p � q) � ( q � r). 29. (a) (p � q) � (p � q) � ( p � q) � ( p � q); PCNF is not possible. (b) PDNF is not possible; PCNF � ( p � q) � ( p � q) � (p � q) � (p � q) 50 Discrete Mathematics (c) PDNF � (p � q � r) � (p � q � r) � (p � q � r) � ( p � q � r) PCNF � ( p � q � r) � (p � q � r) � (p � q � r) � (p � q � r) (d) PDNF � (p � q � r) � (p � q � r) � ( p � q � r) � ( p � q � r) PCNF � ( p � q � r) � ( p � q � r) � (p � q � r) � (p � q � r) 30. (a) (p � q � r) � (p � q � r) � ( p � q � r) � ( p � q � r) (b) (p � q) � ( p � q) � ( p � q) (c) (p � q � r) � (p � q � r) � ( p � q � r) 31. (a) ( p � q � r) � ( p � q � r) � (p � q � (p � q � r) (b) S is a tautology (c) (p � q � r) � (p � q � r) � (p � q � r) (d) (p � q � r) r) � (p � q � r) � Exercise 1(B) 24. (a) All cats are animals (b) Some cats are black. 28. No. 32. (i) Not every student in this class is intelligent (ii) Some student in this class is not intelligent. 41. I did not eat spicy food or there was no thunder. 44. (a) P(x): x is a person; F(x, y): x is the father of y; M(x, y): x is the mother of y. � x (P(z) � F(x, z) � M(z, y)) (b) P(x): x is a person; L(x): x is a lover; R(x, y): x loves y �x (P(x) � �y (P(y) � L(y) � R(x, y))). 48. Valid. Combinatorics INTRODUCTION Combinatorics is an important part of discrete mathematics that solves counting problems without actually enumerating all possible cases. More specifically, combinatorics deals with counting the number of ways of arranging or choosing objects from a finite set according to certain specified rules. In other words, combinatorics is concerned with problems of permutations and combinations, which the students have studied in some detail in lower classes. As combinatorics has wide applications in Computer Science, especially in such areas as coding theory, analysis of algorithms and probability theory, we shall briefly first review the notions of permutations and combinations and then deal with other related concepts. PERMUTATIONS AND COMBINATIONS Definitions An ordered arrangement of r elements of a set containing n distinct elements is called an r-permutation of n elements and is denoted by P(n, r) or nPr, where r � n. An unordered selection of r elements of a set containing n distinct elements is called an r-Combination of n elements and is denoted by C(n, r) or � n� n Cr or �� r �� . Note A permutation of objects involves ordering whereas a combination does not take ordering into account. Values of P(n, r) and C(n, r) The first element of the permutation can be selected from a set having n elements in n ways. Having selected the first element for the first position of Discrete Mathematics 52 the permutation, the second element can be selected in (n – 1) ways, as there are (n – 1) elements left in the set. Similarly, there are (n – 2) ways of selecting the third element and so on. Finally there are n – (r – 1) = n – r + 1 ways of selecting the r th element. Consequently, by the product rule (stated as follows), there are n(n – 1) (n – 2) … (n – r + 1) ways of ordered arrangement of r elements of the given set. Thus, P(n, r) = n(n – 1) (n – 2) … (n – r + 1) n! = ( n � r )! In particular, P(n, n) = n! Product Rule If an activity can be performed in r successive steps and step 1 can be done in n1 ways, step 2 can be done in n2 ways, …, step r can be done in nr ways, then the activity can be done in (n1 � n2 … nr) ways. The r-permutations of the set can be obtained by first forming the C(n, r) r-combinations of the set and then arranging (ordering) the elements in each r-combination, which can be done in P(r, r) ways. Thus P(n, r) = C(n, r) � P(r, r) P(n, r ) n !/(n � r )! � P(r , r ) r !/(r � r )! � C(n, r) = In particular, n! r !(n � r )! C(n, n) = 1. = Since the number of ways of selecting out r elements from a set of n elements is the same as the number of ways of leaving (n – r) elements in the set, it follows that C(n, r) = C(n, n – r) This is obvious otherwise, as n! C(n, n – r) = ( n � r )!{n � (n � r )}! n! = (n � r )! r ! = C(n, r) Note PASCAL'S IDENTITY � n � � n� � n � 1� If n and r are positive integers, where n � r, then � � � . � r � 1�� �� r �� �� r �� Proof Let S be a set containing (n + 1) elements, one of which is 'a'. Let S� � S – {a}. � n � 1� The number of subsets of S containing r elements is � . � r �� Combinatorics 53 Now a subset of S with r elements either contains 'a' together with (r – 1) elements of S� or contains r elements of S� which do not include 'a'. � n � The number of subsets of (r – 1) elements of S� = � . � r � 1�� � n � � The number of subsets of r elements of S that contain 'a' = � . � r � 1�� Also the number of subsets of r elements of S that do not contain 'a' = that � n� � n � � n� � n � 1� of S � = � � . Consequently, � � � � r� � r � 1�� �� r �� �� r �� Note � n � � n� This result can also be proved by using the values of � and , � r � 1�� �� r �� � n � 1� �� r �� . Corollary n C(n + 1, r + 1) = � C(i, r) i�r Proof Changing n to i and r to r + 1 in Pascal's identity, we get C(i, r) + C(i, r + 1) = C(i + 1, r + 1) i.e., C(i, r) = C(i + 1, r + 1) – C(i, r + 1) Putting i = r, r + 1, …, n in (1) and adding, we get (1) n � C(i, r) = C(n + 1, r + 1) – C(r, r + 1) i�r = C(n + 1, r + 1) [� C(r, r + 1) = 0] VANDERMONDE'S IDENTITY If m, n, r are non-negative integers where r � m or n, then r C(m + n, r) = � C(m, r – i) � C(n, i) i �0 Proof Let m and n be the number of elements in sets 1 and 2 respectively. Then the total number of ways of selecting r elements from the union of sets 1 and 2 = C(m + n, r) The r elements can also be selected by selecting i elements from set 2 and (n – i) elements from set 1, where i = 0, 1, 2, …, r. This selection can be done in C(m r – i). C(n, i) ways, by the product rule. The (r + 1) selections corresponding to i = 0, 1, 2, …, r are disjoint. Hence, by the sum rule (stated as follows), we get r C(m + n, r) = � C(m, r – i) � C(n, i) or i �0 r � C(m, i) � C(n, r – i) i �0 Discrete Mathematics 54 Sum rule If r activities can be performed in n1, n2, …, nr ways and if they are disjoint, viz., cannot be performed simultaneously, then any one of the r activities can be performed in (n1 + n2 + … + nr) ways. PERMUTATIONS WITH REPETITION Theorem When repetition of n elements contained in a set is permitted in r-permutations, then the number of r-permutations is nr. Proof The number of r-permutations of n elements can be considered as the same as the number of ways in which the n elements can be placed in r positions. The first position can be occupied in n ways, as any one of the n elements can be used Similarly, the second position can also be occupied in n ways, as any one of the n elements can be used, since repetition of elements is allowed. Hence, the first two positions can be occupied in n � n = n2 ways, by the product rule. Proceeding like this, we see that the 'r' positions can be occupied by 'n' elements (with repetition) in nr ways. i.e., the number of r-permutations of n elements with repetition = nr. Theorem The number of different permutations of n objects which i Discrete Mathematics T Veerarajan Pdf
Source: https://in.b-ok.as/book/5472549/390c37
Posted by: ellisardeculd.blogspot.com
0 Response to "Discrete Mathematics T Veerarajan Pdf"
Post a Comment