COMP 1002 Unit 3 overview

In Unit 3, we expand our language of logic to be able to talk about scenarios involving numbers, people and other domains. We start with the notion of a predicate (hence the name "predicate logic", which is a "proposition with parameters" such as Even(x) which may be true or false depending on the value of the number x from some domain of numbers. In predicate logic, in addition to logical connectives such as ∧ ∨ ¬, we introduce quantifiers, which would allow us to say whether the formula is true no matter what values from the domain its parameters (free variables) tak (universal quantifier), as well as whether there is some value of the parameters which makes the formula true (existential quantifier). We then discuss at length how to construct such formulas to express, in particular, database queries, how to evaluate them, and how to negate them. We will also review basic concepts about sets.

Readings

Section 2.1 (up to p.118), Sections 1.4, 1.5

Learning objectives

The focus of this unit is the language of predicate logic. Thus, you will learn to

Describe a set by listing elements as well as set builder notation with a formula.
Take union, intersection, difference and symmetric difference of given sets, as well as a complement of a set.
Draw Venn diagrams indicating relationships among given sets.
Translate between English and predicate logic (including creating database queries).
State types of symbols and operations occurring in a predicate logic formula.
Evaluate predicate logic formulas, in particular on finite domains and domains of numbers (integers, reals, etc).
Determine whether given predicate logic formulas are equivalent or not; if not, show a counterexample.
Negate a predicate logic formula, simplifying until all negations are on predicates.

Vocabulary

You need to know the meaning of the following terminology:

Set (including $\emptyset, \mathbb{N, Z, Q, R}, universe$ , subset, proper subset, Venn diagram
Set intersection, union, complement, difference, symmetric difference
Predicate (binary, ternary, n-ary), domain of a predicate, arity
Universal and existential quantifiers.
Type checking.
Prenex normal form.