Foundations of Computing (COM1026)
https://www.cl.cam.ac.uk/teaching/1213/RLFA/reglfa-notes.pdf
(Regular Languages
and Finite Automata)
https://www.cl.cam.ac.uk/teaching/2122/DiscMath/materials.html]
(Discrete Mathematics)
https://www.cl.cam.ac.uk/teaching/2122/LogicProof/logic-notes.pdf
(Logic and Proof)
https://github.com/EasyCrypt/easycrypt
(EasyCrypt)
http://mfleck.cs.illinois.edu/building-blocks/version-1.0/proofs.pdf
(Direct Proofs)
https://courses.engr.illinois.edu/cs173/fa2009/lectures/lect_07.pdf
(Proofs by contrapositive and by contradiction)
http://mfleck.cs.illinois.edu/building-blocks/version-1.3/contradiction.pdf
http://www.oxfordmathcenter.com/drupal7/node/317
http://www.personal.kent.edu/~rmuhamma/Philosophy/Logic/ProofTheory/proo
f_by_contradictionExamples.htm
(Proofs by contradiction)
http://mfleck.cs.illinois.edu/building-blocks/version-1.3/induction.pdf
http://www.oxfordmathcenter.com/drupal7/node/114
http://www.oxfordmathcenter.com/drupal7/node/117
(Proofs by induction)
,1) What is a set? “A set is a collection of objects called
elements”
2) How do we describe a set in • An enumeration of elements
mathematics? A={1,2,3,4,5,6}
• Give a verbal description:
A is the set of all integers from 1 to 6,
inclusive
• Give a mathematical inclusion rule:
A={ Integers x | 1 ≤ x ≤ 6}
3) What is the Abstraction Axiom? Given a property P, there exists the set S of
objects that satisfy this property P.
(whatever property P, there exists a set S
containing the objects that satisfy P and only
these objects).
4) What is the empty set? The empty set is a set with no elements.
,5) What are the basic operations on sets? Membership:
– `x is in A’ 𝒙 ∈ 𝑨
– `x is not in A’ 𝒙 ∉ 𝑨
– `A is a subset of B, but A can be equal to
B’ 𝑨 ⊆ 𝑩
– `A is a proper subset of B, i.e., A cannot be equal
to B’ 𝑨 ⊂ 𝑩
or, specifically, 𝑨 ⊊ 𝑩
Operations:
– Union: putting sets together. 𝑨 ∪ 𝑩
– Intersection: what’s in both. 𝑨 ∩ 𝑩
– Set difference: what’s in the first but not in the
2nd. 𝑨 ∖ 𝑩
6) What are some examples of basic A = {alice, ben, cora}
operations on sets? B = {ben, dan, fran}
Membership:
Operations:
– Union:
– Intersection:
– Set difference:
, 7) How do we use Venn Diagrams in Set
Theory?
8) What are the basic operations of Venn
Diagrams?
9) What are subsets? Set A is a subset of set B if every element of A
is an element of B.
" A is a subset of B" is
denoted A ⊆ B
https://www.cl.cam.ac.uk/teaching/1213/RLFA/reglfa-notes.pdf
(Regular Languages
and Finite Automata)
https://www.cl.cam.ac.uk/teaching/2122/DiscMath/materials.html]
(Discrete Mathematics)
https://www.cl.cam.ac.uk/teaching/2122/LogicProof/logic-notes.pdf
(Logic and Proof)
https://github.com/EasyCrypt/easycrypt
(EasyCrypt)
http://mfleck.cs.illinois.edu/building-blocks/version-1.0/proofs.pdf
(Direct Proofs)
https://courses.engr.illinois.edu/cs173/fa2009/lectures/lect_07.pdf
(Proofs by contrapositive and by contradiction)
http://mfleck.cs.illinois.edu/building-blocks/version-1.3/contradiction.pdf
http://www.oxfordmathcenter.com/drupal7/node/317
http://www.personal.kent.edu/~rmuhamma/Philosophy/Logic/ProofTheory/proo
f_by_contradictionExamples.htm
(Proofs by contradiction)
http://mfleck.cs.illinois.edu/building-blocks/version-1.3/induction.pdf
http://www.oxfordmathcenter.com/drupal7/node/114
http://www.oxfordmathcenter.com/drupal7/node/117
(Proofs by induction)
,1) What is a set? “A set is a collection of objects called
elements”
2) How do we describe a set in • An enumeration of elements
mathematics? A={1,2,3,4,5,6}
• Give a verbal description:
A is the set of all integers from 1 to 6,
inclusive
• Give a mathematical inclusion rule:
A={ Integers x | 1 ≤ x ≤ 6}
3) What is the Abstraction Axiom? Given a property P, there exists the set S of
objects that satisfy this property P.
(whatever property P, there exists a set S
containing the objects that satisfy P and only
these objects).
4) What is the empty set? The empty set is a set with no elements.
,5) What are the basic operations on sets? Membership:
– `x is in A’ 𝒙 ∈ 𝑨
– `x is not in A’ 𝒙 ∉ 𝑨
– `A is a subset of B, but A can be equal to
B’ 𝑨 ⊆ 𝑩
– `A is a proper subset of B, i.e., A cannot be equal
to B’ 𝑨 ⊂ 𝑩
or, specifically, 𝑨 ⊊ 𝑩
Operations:
– Union: putting sets together. 𝑨 ∪ 𝑩
– Intersection: what’s in both. 𝑨 ∩ 𝑩
– Set difference: what’s in the first but not in the
2nd. 𝑨 ∖ 𝑩
6) What are some examples of basic A = {alice, ben, cora}
operations on sets? B = {ben, dan, fran}
Membership:
Operations:
– Union:
– Intersection:
– Set difference:
, 7) How do we use Venn Diagrams in Set
Theory?
8) What are the basic operations of Venn
Diagrams?
9) What are subsets? Set A is a subset of set B if every element of A
is an element of B.
" A is a subset of B" is
denoted A ⊆ B
