# CMPUT272 Lecture Notes - Lecture 17: Halting Problem, Idempotence, Knuth'S Algorithm X

For unlimited access to Class Notes, a Class+ subscription is required.

November 4 2014

ETLC 2-001

Sets

Element Methods

Venn Diagrams

Algebraic Rules

Associative

(P ∩ Q) ∩ R = P ∩ (Q ∩ R)

(P Q) R = P (Q R)∪ ∪ ∪ ∪

Distributive

P ∩ (Q R) = (P ∩ Q) (P ∩ R)∪ ∪

P (Q ∩ R) = (P Q) ∩ (P R)∪ ∪ ∪

Idempotent

P ∩ P = P

P P = P∪

Double Negation

P = P∼∼

DeMorgan

(P ∩ Q) = P Q∼ ∼ ∪ ∼

(P Q) = P ∩ Q∼ ∪ ∼ ∼

Absorption

P (P ∩ Q) = P∪

P ∩ (P Q) = P∪

Commutative

P ∩ Q = Q ∩ P

P Q = Q P∪ ∪

Bound

P ∩ = ∅ ∅

P ∩ U = P

P = P∪ ∅

P U = U∪

Negation

P ∩ ( P) = ∼ ∅

P ( P) = U∪ ∼

Tabular Method

Example

Simplify ( ((A B) ∩ C) B)∼ ∼ ∪ ∪ ∼