Symbolic logic and proofs propositional logic

An Open Introduction

Oscar Levin

This work is licensed under the CreativeCommonsAttribution-ShareAlike 4.0 International License. To view a copy of this license, visit
.

Cover image: Tiling with Fibonacci and Pascal.

For Madeline and Teagan

The book is now available in an interactive online format, and this is entirely thanks to the work of Rob Beezer, David Farmer, and Alex Jordan along with the rest of the participants of the .

Finally, a thank you to the numerous stud out typos and made suggestions over the years and a thanks in advance to those who will do so in the future.

Another difference between this text and most other discrete math books is that this book is intended to be used in a class taught using problem oriented or inquiry based methods. When I teach the class, I will assign sections for reading after first introducing them in class by using a mix of group work and class discussion on a few interesting problems. The text is meant to consolidate what we discover in class and serve as a reference for students as they master the concepts and techniques covered in the unit. None-the-less, every attempt has been made to make the text sufficient for self study as well, in a way that hopefully mimics an inquiry based classroom.

The topics covered in this text were chosen to match the needs of the students I teach at UNC. The main areas of study are combinatorics, sequences, logic and proofs, and graph theory, in that order. Induction is covered at the end of the chapter on sequences. Most discrete books put logic first as a preliminary, which certainly has its advantages. However, I wanted to discuss logic and proofs together, and found that doing both of these before anything else was overwhelming for my students given that they didn’t yet have context of other problems in the subject. Also, after spending a couple weeks on proofs, we would hardly use that at all when covering combinatorics, so much of the progress we made was quickly lost. Instead, there is a short introduction section on mathematical statements, which should provide enough common language to discuss the logical content of combinatorics and sequences.

While I (currently) believe this selection and order of topics is optimal, you should feel free to skip around to what interests you. There are occasionally examples and exercises that rely on earlier material, but I have tried to keep these to a minimum and usually can either be skipped or understood without too much additional study. If you are an instructor, feel free to edit the LATEX or PreTeXt source to fit your needs.

Improvements to the 3rd Edition.

• The interactive online version of the book has added interactivity. Currently, many of the exercises are displayed as WeBWorK prob-lems, allowing readers to enter answers to verify they are correct.

The previous editions (2nd edition, released in August 2016, and the Fall 2015 edition) will still be available for instructors who wish to use those versions due to familiarity.

In addition to expository text, this book has a few features designed to encourage you to interact with the mathematics.

Investigate! activities.

You get good at math through practice. Each section concludes with a small number of exercises meant to solidify concepts and basic skills presented in that section. At the end of each chapter, a larger collection of similar exercises is included (as a sort of “chapter review”) which might bridge material of different sections in that chapter. Many exercise have a hint or solution (which in the pdf version of the text can be found by clicking on the exercises number—clicking on the solution number will

ix

For those of you reading this in a pdf or in print, I encourage you to also check out the interactive online version, which makes navigating the book a little easier. Additionally, some of the exercises are implemented as WeBWorK problems, which allow you to check your work without see-ing the correct answer immediately. Additional interactivity is planned, including instructional videos for examples and additional exercises at the end of sections. These “bonus” features will be added on a rolling basis, so keep an eye out!

You can view the interactive version for free at or by scanning the QR code below

xi

Index 389

Chapter 0

Adjective: Individually separate and distinct.

Synonyms: separate - detached - distinct - abstract.

One way to get a feel for the subject is to consider the types of problems you solve in discrete math. Here are a few simple examples:

1

0.1. What is Discrete Mathematics? 3

this course we will study four main topics: combinatorics (the theory of ways things combine; in particular, how to count these ways), sequences, symbolic logic, and graph theory. However, there are other topics that belong under the discrete umbrella, including computer science, abstract algebra, number theory, game theory, probability, and geometry (some of these, particularly the last two, have both discrete and non-discrete variants).

While walking through a fictional forest, you encounter three trolls guarding a bridge. Each is either a knight, who always tells the truth, or a knave, who always lies. The trolls will not let you pass until you correctly identify each as either a knight or a knave.

Each troll makes a single statement:

A statement is any declarative sentence which is either true or false. A statement is atomic if it cannot be divided into smaller statements, otherwise it is called molecular.

These are statements (in fact, atomic statements):

You can build more complicated (molecular) statements out of simpler (atomic or molecular) ones using logical connectives. For example, this is a molecular statement:

Telephone numbers in the USA have 10 digits and 42 is a perfect square.

for the logical connectives: ∧, ∨, →, ↔︎, ¬.