Study Guides (390,000)
CA (150,000)
UW (7,000)
CS (400)
CS245 (20)
Final

# Final Exam Help Sheet Winter 2009

Department
Computer Science
Course Code
CS245
Professor
Nancy Day
Study Guide
Final

This preview shows half of the first page. to view the full 2 pages of the document.
CS 245 Winter 2009 Final Exam
Potentially Useful Information
Propositional Logic Transformational Proof Logical Laws
Commutativity
Associativity
Law of Excluded Middle (LEM)
Implication
Contrapositive
Distributivity
De Morgan’s (DM)
Negation
Equivalence
Idempotence
Simpliﬁcation I
Simp II
p(pq)p
p(pq)p
Predicate Logic Transformationl Proof Logical Laws
• ∀—Distr—
(xp(x)q(x)) ((xp(x)) (xq(x)))
De Morgan’s
(¬(xp(x))) (x• ¬p(x))
(¬(xp(x))) (x• ¬p(x))
Swap Vars
(x, y p(x, y)) (y, x p(x, y))
(x, y p(x, y)) (y, x p(x, y))
• ∃—Distr—
(xp(x)q(x)) ((xp(x)) (xq(x)))
Move—(xnot free in p(y))
(xq(x)p(y)) ((xq(x)) p(y))
(xq(x)p(y)) ((xq(x)) p(y))
Move—(xnot free in p(y))
(xq(x)p(y)) ((xq(x)) p(y))
(xq(x)p(y)) ((xq(x)) p(y))
Sets, Relations, Functions, and Z Notation (R:AB, S :BC, Q A, P B)
Set Comprehension
x∈ {aa:A|P(a)}xAP(x)
x∈ {t(a)a:A|P(a)}
zzAx=t(z)P(z)
Domain
dom R={a| ∃b(a, b)R}
Range
ran R={b| ∃a(a, b)R}
Inverse
R={(b, a)|(a, b)R}
Iteration (V:AA)
V0= id A
Vn=V;Vn1
Relational Image
R(|Q|) = {b| ∃a(a, b)RaQ}
Domain Restriction
Q ⊳ R ={(a, b)|(a, b)RaQ}
Domain Subtraction
Q⊳ R ={(a, b)|(a, b)R∧ ¬(aQ)}
Range Restriction
R ⊲ P ={(a, b)|(a, b)RbP}
Range Subtraction
R ⊲ P ={(a, b)|(a, b)R∧ ¬(bP)}
Relational Overriding
RS= ((dom S)⊳ R)S
Relational Composition
SR=R;S={(a, c)| ∃b(a, b)R(b, c)S}
Name Notation Name Notation
Relation R:AB
Total Fcn f:ABNon-total Fcn f:A7B
Total Injective (1-to-1) Fcn f:A֌BNon-total Injective (1-to-1) Fcn f:A7֌B
Total Surjective (onto) Fcn f:ABNon-total Surjective (onto) Fcn f:A7B
Total Bijective Fcn f:A֌BNon-total Bijective Fcn f:A7֌B