COMP 1002 Unit 4 overview

In unit 4, we will expand our reasoning rules to predicate logic, and will show how to apply these rules to do actual proofs like ones you see in your computer science and mathematics textbooks. First, we will discuss what logic rules can let us reason with quantifiers. Then, we will move into actual proofs. We will start with the simplest proofs (and most algorithmic in practice): proofs where you show that an object with some properties exists by constructing an example of such an object. These kinds of proofs can be used to prove existentially quantified statements (and disprove universally quantified statements). Then we will move into proving universal statements, and cover a number of classic techniques for doing that. Definitions also play a big role in this unit. It is a crucial skill for a computer scientist to be able to read a new definition (of a data structure, a type of object, etc) and understand what it is saying, give examples of objects satisfying the definitions and others that do not satisfy it, and use the definition in proofs. As introductory examples of definitions (and proofs using those definitions), we will use modular arithmetic and congruence, as well as rational and irrational numbers. Even though I would expect you to learn what an irrational number is, or what it means for two integers to be congruent mod a number, the focus here is on understanding new definitions, rather than memorizing given ones. As you are reading proofs and working out proofs of your own, remember that there is no fixed strict way of doing proofs. Two people would write different proofs for any statement that needs more than one-two lines of proofs; if you explain the same proof twice to somebody, you will notice that you did not explain it in exactly the same way. This is OK, as long as you give enough details to check that your reasoning is valid. It is very helpful to explain your proofs to somebody, preferably at your own level: from their questions you will see much more clearly which steps you do need to elaborate, and what does not need to be made explicit. It is also helpful to read extra examples of proofs; the textbook is a good source for that; however, don't just read the proofs: after you read a proof, close the textbook and try to write a proof yourself, and/or explain it to somebody.

Readings

Most of the material in this unit is covered in the rest of section 1.6 (from p.76), sections 4.1, 1.7, and section 1.8 (except Tilings pp. 103-105)

Learning objectives

This unit introduces reasoning in predicate logic, with the focus on proofs from logic perspective. The main skill you would acquire after working through the material in this unit is understanding proofs (their structure, steps of the proofs, using definitions, etc), as well as ability to construct simple proofs using the methods and proof techniques we cover here. As always, for each concept (proof technique, rule of inference, etc), be able to give an example of this concept.

Prove an existential statement by giving a witness. Disprove a universal statement by giving a counterexample. Here, you may need to specify a domain, or an interpretation of the predicates, or both, or just give an element of an already given domain. Note that universal statements with empty domain are vacuously true.
Know what are universal/existential generalization/instantiation
Use universal modus ponens (and be able to identify invalid usage).
When reading a proof, first note what is given and what needs to be proven. Then, identify which type of proof it is (direct, by cases, by contraposition, by contradiction; there may be multiple parts of multiple types in a proof).
Say which rules used at every step of the proof (and where there might be skipped steps). In particular, identify usage of universal/existential generalization/instantiation, and where the next step follows by definition or an application of a theorem vs. calculations.
Construct simple proofs with similar structure to the given examples.
Given a definition, be able to come up with examples of objects that satisfy it, and examples that don't, as well as use it in proofs.

Vocabulary

You need to know the meaning of the following terminology:

Existential instantiation, existential generalization, universal instantiation, universal generalization
Universal modus ponens
Definition, theory, axiom, theorem, proof, disproof.
Counterexample, witness, constructive proof. Vacuously true.
Rational and irrational numbers, congruence, quotient, remainder, Pythagoras' theorem, Pythagorean triple.
Direct proof, proof by cases, proof by contraposition, proof by contradiction.