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 look a a generalization of formulas, Boolean circuits, which are the basis of computer hardware.
Additionally, we will look at other connection of propositional model with computation, namely at computing functions which output 0/1 values with formulas and circuits. Finally, we will discuss what variants of propositional logic have the same expressive power, more specifically what logical connectives do we need to express all possile Boolean functions.
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.2 in the textbook. For the syntax trees, you might find examples example 5 on page 779 and example 10 on page 782 helpful. Logic circuits appear at the end of section 1.2. Representing Boolean functions as DNFs/CNFs (sums of products / product of sums expansions) is in section 12.2.
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), ¬ (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 explain how it describes the order of operations in evaluating the formula.
- Given a formula, you should be able to evaluate it on a specific assignment (using a syntax tree) 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.
- Know the definition of logical equivalence, and be able to give an example (DeMorgan's law).
- 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).
- Given an implication, you should know what its contrapositive, converse and inverse are, and which of them are equivalent.
- You need to know what a Boolean function is and how to build a canonical CNF and canonical DNF for a Boolean function given its truth table.
- You will need to be able to evaluate a given Boolean circuit, and also construct a Boolean circuit given a description of a simple Boolean function.
- Finally, given a collection of logic connectives you need to be able to determine if this collection is functionally complete.
Vocabulary
You need to know the meaning of the following terminology:
- Proposition, propositional statement, logic connectives (NOT ¬, AND ∧, OR ∨, IMPLIES →, IFF (biconditional) ↔), syntax tree.
- Truth assignment, satisfying/falsifying assignment, tautology, contradiction, statisfiable/unsatisfiable formula, truth table.
- Logical equivalence.
- Contrapositive, converse and inverse to an implication.
- Boolean function and its canonical CNF (ProductOfSums) and DNF (SumOfProducts), Boolean circuit,
- Functionally complete set of logic connectives. Sheffer stroke. NAND.