程序代做CS代考 ECS 20 — Lecture 7 — Fall 2013 —18 Oct 2013

ECS 20 — Lecture 7 — Fall 2013 —18 Oct 2013
Phil Rogaway
Today: o Sets and
o Writing sets
o Some operations on sets
o Some important sets for math and CS
S = {dog, cat}. Order we write elements (points) in a set doesn’t matter. = {cat, dog}. Repetitions don’t matter, either:
= {cat, dog, cat}.
S = 

Often many ways to write a set
A = {2i+1: i  Z}
= {…,-5,-3,-1, 1, 3, 5,…}
= {x: x is an odd integer}
= {n: n Z and  (jZ)(2j=n)}
Or
Let P be the set of prime numbers. P = {n: n is a prime number}
P = {n N : i | n  i  {-n,-1,1,n}} P = {2,3,5,7,11,…}
Can a set contain a set? Sure.
Can a set contain the emptyset? Sure
S = {N, {2,3}, [0,1]}.
S = { 

Naïve set theory, where we describe sets with natural language, can sometime run into trouble. Can a set contain itself? No
Can a set contain “everything”? No
Russell’s paradox: Let R = { x | x x}


Def: S = T iff xS  xT
Def: ST if xS  xT
{a, b} {a,b,c} YES {a, b} {a,b} YES
Problem:
is R R iff R R?
1

{a b} {a,d,e}
{a,b,c}
{} {a,b,c}
{} {{}}
T/F: for all S, S: True
Some important sets for math and computer science N = {1, 2, 3, …} // some books include 0, some don’t R = {x: x is a real number}
Z = {…,-2,-1, 0, 1, 2, ,…}
Q = {m/n: m, n\in Z, n 0}
[ a.. b] integers between a and b, inclusive.
[ a, b] reals between a and b, inclusive [1..N] = {1, 2, …, N}
[N] = ZN = {0, 1, …, N-1}
Sometimes sets come with operations on them, these operations satisfying simple algebraic
properties.
Example:
Group This is a set A and an operation * where:
1) (x*y)*z = x*(y*z);
2) there exists an element 1 in A such that x*1=1*x = x;
3) for every element x there is an element y such that x*y = 1 = y*x]
But let me emphasize that a set, all by itself, does not have operations defined on its elements.
 Ask questions about making N, R, Z into groups.
 Later: ask questions about making BITS, BYTES, WORDS32 into a group, by either XOR and
Modular addition operation
For computers, important sets correspond to those things that our architectures natively manipulate:
BITS = {0,1}
BYTES = {0,1}8 Signed, unsigned
WORDS32 = {0,1}32 Signed, unsigned
WORDS64 = {0,1}64 Signed, unsigned
IEEEFLOAT64 = {0,1}64 = representing exponents -1022 .. 1023
NO
YES (explain)
NO YES
(about 16 digits of accuracy) sign, significand (=coefficient), exponent (-1)sign  signficand 2exponentEEF
Weirder than you may think
   
+
∞ and −∞
NaN (of various kinds)
Zero can be +0 or 0
2

. A primary architect of the IEEE 754 floating-point standard
Or particular language:
The set of all valid C programs The set of valid URLs
The set of valid http programs
|S| = the number of element in S if S is finite, otherwise A= {{a}, b,}. |A| = 3
A = {, {}, {{}}} |A|=3.
UNION
A B = {x: xA or xB} // not really very rigorous:
{x : blah} before the colon, the universe should be clear, with
what comes after a narrowing of that. Books don’t all stick to this, but that’s what learned! {dog, cat}  {cat, fish}
{a,b} {,a} = {a,b,} A  = A
Can union up infinitely many things  nNn] = R
_{iI} A_i eg, \cup{iN} {2i1} = the set of odd positive number _{aN} {ai: iN}
“powers of integers”
INTERSECTION
{1,2,3} {2,5,8} = {2}
{1,2,3} {4,5,8} = 
{1,2,3} = True/False
S = True/False
Can intersect infinitely many things, too:
3

 nNn] = {0}
Set Difference
A\B or A–B
Symmetric Difference
AB
Algebra of sets
Commutative laws:
 
Associative laws:
 
Distributive laws:


Proof: x  A  (BC) means
(x  A) = ((x  A) = (A  B)
(x  B)  (x  C))
x  B))  (x  A) (x  C))
 (A  C) Identity laws:
But P QR) = (P Q)
P R). So
 
Complement laws:
4


 
idempotent laws:
 
domination laws:
 
absorption laws:
 
double complement or Involution law:

complement laws for the universal set and the empty set:
 
De Morgan’s laws:
Proof (of first claim): x  (A  B) c
iff iff iff iff
 x  (A  B)) xA x B)
xA)  xB) xAc  xBc
Be careful!!
 
? (A\B)\CA\(B\C)
5

Cartesian Product (= Cross product)  Did get here, continue next time A  B = {(a,b): AA, B B}
R2 points in the plane
An array of chessmen might be represented by BYTES64
Power Set
P (X) = {A: A  X} Example: X = {a, b, c}
Example:
Variant notation: P (X) = 2X
Notation is suggestive of size – For X finite, |P (X) |= 2|X|
…
P – Power set operator, unary operator (takes 1 input). P(x) is the “set of all subsets of x”
6