Bhavanari Satyanarayana - Mathematical Foundations of Computer Science

Dr. Bhavanari Satyanarayana
Dr. Tumurukota Venkata Pradeep Kumar
Dr. Shaik Mohiddin Shaw CRC Press Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 2020 by Bhavanari Satyanarayana, Tumurukota Venkata Pradeep Kumar, Shaik Mohiddin Shaw and BSP Publications CRC Press is an imprint of the Taylor & Francis Group, an informa business No claim to original U.S. Government works Printed on acid-free paper International Standard Book Number-13: 978-0-367-3681-0 (Hardback) This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use.

The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint. Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, please access www.copyright.com (http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400.

CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged. Trademark notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe. Print edition not for sale in South Asia (India, Sri Lanka, Nepal, Bangladesh, Pakistan or Bhutan) Library of Congress Cataloging-in-Publication Data A catalog record has been requested Visit the Taylor & Francis Web site at http://www.taylorandfrancis.com and the CRC Press Web site at http://www.crcpress.com

When something can be read without effort, great effort has gone into its writing. By- Enrique Jardiel Poncela We have great pleasure in presenting this book Mathematical Foundation of Computer Science for B.Tech students. Book has been written in a simple, lucid and easy to understandable style.

Number of problems have been worked out as examples. Hints and answers are given for the problems in the exercise to help the students for self-learning. Each chapter has been planned as independent unit so that various topics connected which can also be read separately. Suggestions for further improvement of the book are most welcome and will be gratefully acknowledged. No originality of the subject was claimed by the authors. The authors presented the subject in their own way for the better understanding of the target group of the readers.

The authors referred several existing books. Some of them were listed in the book. -Authors

The Authors are pleased to express their thanks to the following for their constant encouragement in each of their endeavors: *Dr. P. V. *Dr. D. D.

Ramakotaiah, Former Vice Chancellor of Acharya Nagarjuna University, A.P. *Dr. A. Radhakrishna former Professor of Mathematics, Kakatiya University, Warangal, Telangana, India. *Dr. L.

Radha Krishna, Visiting Professor, Mathematics, Bangalore University, Bangalore, Karnataka, India. *Dr. Kuncham Syamprasad, Manipal University, Manipal. *Dr. Kedukodi Babushri Srinivas, Manipal University, Manipal. P. P.

Trimurthy and Dr. Y. Venkateswara Reddy of Acharya Nagarjuna University. Dr. Bhavanari Satyanarayana places on record his deep sense of gratitude to his parents: Bhavanari Ramakotaiah (a teacher in an elementary school in the village Madugula, Guntur(dt), A.P., India) and Bhavanari Anasuyamma, without whose constant encouragement and help it would not have been possible for him to pursue higher studies in Mathematics. -Authors

LEARNING OBJECTIVES to Construct compound statements by using the connectivesto identify the Tautologies and Contradictionsto Construct the Truth Tables for the given expressionsto find the Equivalent statements for a given expressionto formulate DNF and CNF for the given expressions Logic means reasoning. -Authors LEARNING OBJECTIVES to Construct compound statements by using the connectivesto identify the Tautologies and Contradictionsto Construct the Truth Tables for the given expressionsto find the Equivalent statements for a given expressionto formulate DNF and CNF for the given expressions Logic means reasoning.

One of the important aims of logic is to provide rules through which one can determine the validity of any particular argument. Logic concern with all types of reasonings such as legal arguments, mathematical proofs, conclusions in a scientific theory based upon a set of given hypothesis. The rules are called as rules of inference. The rules should be independent of any particular argument or discipline or language used in the argument. We shall mean, by formal logic, a system of rules and procedures used to decide whether or not a statement follows from some given set of statements. In order to avoid ambiguity, we use symbols.

The symbols are easy to write and easy to manipulate. Hence, the logic that we study is named as Symbolic logic. For example, observe the following statements. (i) All men are mortal (ii) Socrates is a man Therefore (iii) Socrates is mortal According to the logic, if any three statements have the following form (i) All M are P (ii) S is M Therefore (iii) S is P then (iii) follows from (i) and (ii). The argument is correct, no matter whether the meanings of statements (i), (ii), and (iii) are correct. All that required is that they have the forms (i), (ii), and (iii).

In Aristotelian logic, an argument of this type is called syllogism. The formulation of the syllogism is contained in Aristotles organon. It had a great fascination for medieval logicians, for almost all their work centered about ascertaining its valid moods. The three characteristic properties of a syllogism are as follows: (i) It consists of three statements. The first two statements are called as premises, and the third statement is called as conclusion. (ii) Each of the three sentences has one of the four forms given in the Table.

Classification	Examples