COMP 1002 Unit 2 overview
In Unit 2, we will focus on reasoning in the language of logic. We will look at rules of inference which let us build valid arguments. In particular, we will see how to do reasoning using natural deduction method, commonly taught in logic classes, and resolution method, which is the basis for many automated theorem provers. We will also study basic manipulations with formulas, in particular negating and simplifying them.
Readings
Most of the material in this unit is covered in sections 1.3 and 1.6 (up to example 11, p.76). Exercises 43-56 in section 1.6 cover complete sets of connectives. See section 6.2 for the Pigeonhole Principle.
Learning objectives
- Given a formula, you need to know how to simplify it using the table of logical equivalences. You do not need to memorize the table, but you should at least remember what De Morgan's laws are, and know how to express A → B as &neg; A ∨ B.
- You should be able to write a negation of a given formula in a form where all negation symbols are on variables, using definition of implication, De Morgan's laws and double negation law.
- Given an implication, you should know what its contrapositive, converse and inverse are, and which of them are equivalent.
- Given a collection of logic connectives you need to be able to determine if this collection is functionally complete.
- You should know what an argument is, what are its premises and conclusion, and be able to determine if an argument presented to you is valid or invalid.
- From a list of premises you should be able to derive conclusions using rules of inference, in particular Modus Ponens (natural deduction).
- From a description of a situation in English you need to be able to build a list of premises, then derive conclusions using natural deduction. Similarly, you need to be able to show that a given list of statements is inconsistent by deriving a contradiction using either natural deduction or resolution.
- Given a formula you should be able to convert it to CNF (sum of products) form by using logical equivalences.
- Starting from a CNF formula, you should be able to show what can be derived from it using resolution, and in particular prove that a formula is a contradiction by writing a resolution refutation for it.
- Combining it with the previous items, you should be able to take an argument and show that its conclusion follows from premises by writing a resolution refutation for "AND of premises AND NOT conclusion" formula.
- You should be able to apply Pigeonhole Principle to solve simple problems (like the pens puzzle).
- You should be able to answer questions about computational complexity of determining if a formula is a tautology (ie., know that truth tables are not efficient, and that it is an open problem with a million dollar prize attached to find if there is a significantly faster way).
- Finally, you should be able to answer questions about computational complexity of determining if a formula is a tautology (ie., know that truth tables are not efficient, and that it is an open problem with a million dollar prize attached to find if there is a significantly faster way).
- From the computational complexity perspective, you need to know that resolution refutations can be up to exponentially larger than the original formula (with the pigeonhole principle an example where it happens), and that it is unknown whether natural deduction is always faster than resolution.
Vocabulary
You need to know the meaning of the following terminology:
- Logical equivalence. Logical identities (laws), including De Morgan's law and double negation rule.
- Negation (of a formula).
- Complete set of connectives, NAND, Sheffer's stroke.
- Argument, valid/invalid argument, natural deduction, rules of inference, modus ponens, premises, conclusion.
- Resolution rule, resolution proof/refutation, empty clause.