CSci 271 Lecture Notes

Week One, Wednesday: Propositional Equivalences, Predicates, and Quantifiers

Propositional Equivalences

Definition: a compound proposition that is always true is a tautology. ("p or not p" is always true) One that is always false is a contradiction. ("p and not p" is always false)

A pair of compound propositions that always have the same truth value are logically equivalent. Equivalently, we can say that p and q are logically equivalent if "p if and only if q" is a tautology.

Predicates

A predicate is a function that has a value of true or false. A predicate is also called a propositional function.

Quantifiers

The universal quantifier asserts that the value of a proposition is true for all values of its variable in the universe of discourse.

Think of the universal quantifier as a conjunction: all values in the universe of discourse must give true evaluations for the quantifier to give a true evaluation.

The existential quantifier is a disjunction: there must only be one of its values in the universe of discourse resulting in a true evaluation of its predicate in order for the quantifier to have a true evaluation.

It is often helpful, when working with nested quantifiers, as thinking of them as looping through all the values in the universe of discourse.

Homework Assignment

Assigned Wednesday, September 9, due Wednesday, September 16, at beginning of class.

Chapter 1.2: 6, 18. Chapter 1.3: problems 10, 14, 20.


This page established September 8, 1998; last updated September 8, 1998.