COMP 1002 Unit 1 overview
In Unit 1, you will learn about the language of propositional logic. We will see how logic formulas are constructed, how to read them, and how to translate from English to logic and back. We will spend a fair bit of time talking about the meaning of these formulas, and how to determine when (if ever) a given formula is true or false, and when two formulas are equivalent. We will also study basic manipulations with formulas, in particular negating and simplifying them.
This unit has a number of puzzles, to help you play around with the concepts. Try to solve the puzzles yourself before moving on to the next video, and try to do the relevant exercises from the labs, online exercises and practice problems as soon as you are done watching the corresponding videos.
Readings
The material in this unit loosely corresponds to section 1.1-1.3 in the textbook. For the syntax trees, you might find examples example 5 on page 779 and example 10 on page 782 helpful.
Learning objectives
- After completing this unit, you should be able to translate between English and propositional logic sentences; in particular, you need to learn the meaning of symbols ∧ (and), ∨ (or), &neg; (not), → (implies) and ↔ (biconditional), and know how to construct a well-formed formula using these symbols and propositional variables.
- You should be able to draw a syntax tree for a given formula and fully parenthesize the formula to make the order of operations unambiguous.
- Given a formula, you should be able to evaluate it on a specific assignment and write a truth table for it. In particular, you should know how to label rows and columns of a truth table, and be able to determine if a formula is a tautology, a contradiction or neither using a truth table.
- Given a formula, you need to know how to simplify it using the table of logical equivalences given in Lab 1. 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.
- Putting it all together, you should be able to do problems similar to Knight and Knave puzzles, from the statement of the puzzle through representing it in logic form, solving using a truth table, and finally producing an answer (i.e., saying who is a knight and who is a knave).
- 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).