Logic, Sets, and Functions

This book is intended as an introduction to symbolic logic and elementary set theory, including mathematical induction. It is designed to meet the needs of a semester-long course, with the needs and interests of computer science majors and others requiring a foundation in the construction of proofs and in the use of discrete mathematics. The text is accompanied by a software application, Plato, available in both Windows and Macintosh versions. Plato can be used by students in producing derivations that employ the proof styles and rules introduced in this text. The use of Plato provides the student with immediate feedback, since it will not allow any logical errors to be committed. Plato is quite flexible, capable of being used to generate a derivation of any valid argument in first-order logic. In addition, Plato greatly eases the burden of grading homework. We would like to express our appreciation to the College of Liberal Arts at the University of Texas-Austin, and to the Multimedia Task Force of the UT System, for their financial support for the development of Plato. 1 Basic Concepts of Logic 1.1 Arguments 1.2 Validity 1.3 Implication and Equivalence 1.4 Logical Properties of Sentences 1.5 Satisfiability 2 Sentences 2.1 The Language of Sentential Logic 2.2 Truth Functions 2.3 A Sentential Language 2.4 Translation 2.5 Validity 2.6 Truth Tables 2.7 Truth Tables for Formulas 2.8 Examples 2.9 Truth Tables for Argument Forms 2.10 Implication, Equivalence and Satisfiability 3 Natural Deduction 3.1 Natural Deduction Systems 3.2 Rules for Negation and Conjunction 3.3 Rules for the Conditional and Biconditional '3_4 Rules for Disjunction 3.5 Derivable Rules 4 Quantifiers 4.1 Constants and Quantifiers 4.2 Categorical Sentence Forms 4.3 Polyadic Predicates 4.4 The Language Q 4.5 Translation 4.5.1 Noun Phrases 4.5.2 Verb Phrases 4.5.3 Connectives 4.6 Interpretations 5 Quantified Natural Deduction 5.1 Deduction Rules for Quantifiers 5.2 Universal Proof 5.3 Derived Rules for Quantifiers 6 Identity and Function Symbols 6.1 Identity 6.2 Deduction Rules for Identity 6.3 Function Symbols 7 Sets 7.1 Extensionality 7.2 Abstraction 7.3 Pair Sets, Unit Sets and Enumeration 7.4 The Null Set 7.5 Binary Unions, Intersections and Complements 7.6 Unions and Intersections of Single Sets 7.7 Power Sets 7.8 Complex Abstraction 8 Relations 8.1 Sequences and Ordered Pairs 8.2 Cartesian Products 8.3 Relations 8.4 Properties of Relations 8.5 Ordering Relations 8.6 Relations between Relations 8.7 Restrictions and Images 8.8 Equivalence Relations and Partitions 9 Functions 9.1 Functions and Relations 9.2 Properties of Functions 10 Induction 10.1 The Natural Numbers and Definition by Recursion 10.2 Weak Induction on the Natural Numbers 10.3 Strong Induction on Natural Numbers 10.4 Induction on Sets other than the Natural Numbers 10.5 Graphs, Trees and Lists 10.6 Formal Languages A Plato's Users' Guide A.I Introduction A.2 Getting Started A.3 Starting Plato on the Macintosh A.3.1 The Menus: An Overview A.3.2 The File Menu A.3.3 The Edit Menu A.3.4 The Annotations Menu A.3.5 The Font and Size Menus A.4 Homework Mode the Windows Version A.5 The Windows Menu A.6 Languages of Logic A.6.1 The Language of Sentential Logic A.6.2 The Language of Quantificational Logic A. 7 Systems of Proof A.7.1 Proof Formats A.7.2 Derivation Rules A.7.3 The Proofs Menu A.7.4 Imported Rules A.7.5 The Quantification Rule Set A.8 Macintosh Keyboard Shortcuts A.8.1 Mackintosh Keyboard Equivalents for Logical Symbols B Answers to Selected Problems Index