❦ LOGIC AS A TOOL ❦ ❦ ❦ ❦ ❦ ❦ ❦ ❦ LOGIC AS A TOOL AGUIDE TO FORMAL LOGICAL REASONING Valentin Goranko Stockholm University, Sweden ❦ ❦ ❦ ❦ This edition frst published 2016 © 2016 by John Wiley & Sons, Ltd Registered offce John Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex, PO19 8SQ, United Kingdom For details of our global editorial offces, for customer services and for information about how to apply for permission to reuse the copyright material in this book please see our website at www.wiley.com. The right of the author to be identifed as the author of this work has been asserted in accordance with the Copyright, Designs and Patents Act 1988. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, except as permitted by the UK Copyright, Designs and Patents Act 1988, without the prior permission of the publisher. Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic books. Designations used by companies to distinguish their products are often claimed as trademarks. All brand names and product names used in this book are trade names, service marks, trademarks or registered trademarks of their respective owners. The publisher is not associated with any product or vendor mentioned in this book. Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifcally disclaim any implied warranties of merchantability or ftness for a particular purpose. It is sold on the understanding that the publisher is not engaged in rendering professional services and neither the publisher nor the author shall be liable ❦ ❦ for damages arising herefrom. If professional advice or other expert assistance is required, the services of a competent professional should be sought. Library of Congress Cataloging-in-Publication Data Names: Goranko, Valentin, author. Title: Logic as a tool : a guide to formal logical reasoning / Valentin Goranko. Description: Chichester, UK ; Hoboken, NJ : John Wiley & Sons, 2016. | Includes bibliographical references and index. Identifers: LCCN 2016010458 (print) | LCCN 2016014532 (ebook) | ISBN 9781118880005 (cloth) | ISBN 9781118880050 (pdf) | ISBN 9781118880043 (epub) Subjects: LCSH: Logic–Textbooks. Classifcation: LCC BC71 .G67 2016 (print) | LCC BC71 (ebook) | DDC 511.3–dc23 LC record available at http://lccn.loc.gov/2016010458 A catalogue record for this book is available from the British Library. Set in 10.5/12pt, TimesLTStd by SPi Global, Chennai, India. 1 2016 ❦ ❦ This book is dedicated to those from whom I have learned and to those who will learn from it. ❦ ❦ ❦ ❦ ❦ ❦ ❦ ❦ Contents Preface xi Acknowledgements xv Introduction xvii An Appetizer: Logical Paradoxes and Self-Reference xxi 1 Understanding Propositional Logic 1 1.1 Propositions and logical connectives: truth tables and tautologies 1 ❦ 1.1.1 Propositions 1 ❦ 1.1.2 Propositional logical connectives 2 1.1.3 Truth tables 3 1.1.4 The meaning of the connectives in natural language and in logic 4 1.1.5 Computing truth values of propositions 5 1.1.6 Propositional formulae and their truth tables 6 1.1.7 Tautologies 11 1.2 Propositional logical consequence: logically correct inferences 18 1.2.1 Propositional logical consequence 18 1.2.2 Logically sound rules of propositional inference and logically correct propositional arguments 21 1.2.3 Fallacies of the implication 23 1.3 Logical equivalence: negation normal form of propositional formulae 28 1.3.1 Logically equivalent propositional formulae 28 1.3.2 Basic properties of logical equivalence 29 1.3.3 Some important logical equivalences 29 1.4 Supplementary: Inductive defnitions and structural induction and recursion 34 1.4.1 Inductive defnitions 34 1.4.2 Induction principles and proofs by induction 36 1.4.3 Basics of the general theory of inductive defnitions and principles 37 1.4.4 Inductive defnitions and proofs in well-founded sets 39 1.4.5 Recursive defnitions on inductively defnable sets 40 ❦ ❦ viii Contents 2 Deductive Reasoning in Propositional Logic 47 2.1 Deductive systems: an overview 47 2.1.1 The concept and purpose of deductive systems 47 2.1.2 Brief historical remarks on deductive systems 48 2.1.3 Soundness, completeness and adequacy of deductive systems 50 2.2 Axiomatic systems for propositional logic 52 2.2.1 Description 52 2.2.2 Derivations in the axiomatic system H 54 2.3 Semantic Tableaux 58 2.3.1 Description of the deductive system ST of Semantic Tableaux 59 2.3.2 Some derivations in ST 61 2.3.3 Unsigned version of the system of Semantic Tableaux 64 2.4 Natural Deduction 68 2.4.1 Description 69 2.4.2 Examples of derivations in Natural Deduction 71 2.5 Normal forms and Propositional Resolution 77 2.5.1 Conjunctive and disjunctive normal forms of propositional formulae 77 2.5.2 Clausal Resolution 79 2.5.3 Resolution-based derivations 80 2.5.4 Optimizing the method of resolution 82 2.6 Supplementary: The Boolean satisfability problem and NP-completeness 86 2.7 Supplementary: Completeness of the propositional deductive systems 88 ❦ ❦ 3 Understanding First-order Logic 96 3.1 First-order structures and languages: terms and formulae of frst-order logic 97 3.1.1 First-order structures 97 3.1.2 First-order languages 99 3.1.3 Terms and formulae 100 3.2 Semantics of frst-order logic 108 3.2.1 The semantics of frst-order logic: an informal outline 108 3.2.2 Interpretations of frst-order languages 111 3.2.3 Variable assignment and evaluation of terms 112 3.2.4 Truth of frst-order formulae 112 3.2.5 Evaluation games 114 3.2.6 Translating frst-order formulae to natural language 117 3.3 Basic grammar and use of frst-order languages 123 3.3.1 Translation from natural language to frst-order languages: warm-up 123 3.3.2 Restricted quantifcation 124 3.3.3 Free and bound variables, and scope of a quantifer 125 3.3.4 Renaming of a bound variable in a formula and clean formulae 127 3.3.5 Substitution of a term for a variable in a formula, and capture of a variable 128 3.3.6 A note on renamings and substitutions in a formula 130 ❦