RAH Flashcards
An example that proves a statement false is often called a
counterexample
direct approach to proving a conditional of the form “if A then B” starts with the assumption that the antecedent ______________
A is true.
is a false statement
contradiction
starts out by assuming that the statement to be proved is
false
proof by contradiction
another name for proof by contradiction
indirect proof
a smallest number for which a case is false
minimal counterexample
construct an instance of
the object
Constructive approach
where we check that each thing has the stated property.
Exhaustive checking
That if the premise is true, then the conclusion must also be true.
conditional proof
We’ll simply say that a set is a collection of things called its
elements,
members, or objects.
A set with one element is called a
singleton
Sets can have other sets as elements
T or F
T
The set with no elements is called the
empty set or null set
The empty set is denoted by
∅ or {}
is a set or not?
x = {1,2,3,4,5,…}
yes
is a set or not?
x = {1,2,3,…, 35, 37}
yes
equal or not
{u,g,h} = {h,u,g}
equal
equal or not
{h,g, u,h} = {h, g, u}
not
are repeated occurences allowed in sets
no
What are natural numbers?
N={0,1,2,3,4,5,…}
What are integers?
Z = {…,-2,-1,0,1,2,…}
What are rational numbers?
Q={…, -1/2, 0, .08,…}
What are real numbers?
R={…,-2, -1/2, 0, .08, 3, √3, π(22/7),…}
If A ⊆ B and there is some element in B that does not occur in A,
proper subset
A ⊂ B
The collection of all subsets of a set is called the
power set
what is the powerset of S = {a, b, c}
S = {∅, {a}, {b}, {c}, {a,b}, {a,c},…, {a,b,c}}
consists of one or more closed curves in which the interior of each
curve represents a set.
Venn Diagram
who created the Venn Diagram
John Venn
___________ of two sets A and B is the set of all elements that are either in A
or in B or in both A and B
union
A U B
The _________ of two sets A and B is the set of all elements that are in
both A and B
intersection
A ∩ B
If A ∩ B = ∅, then A and B are said to be
disjoint
is the set of elements in A that are not in B
Difference (relative complement)
A-B
is the set of elements in A that are not in B, and in B but not in A
symmetric difference
the difference U − A is
called the
complement
A’
The
size of a set S is called its
cardinality
) is a collection of objects that may contain repeated
occurrences of elements
bag (or multiset
T or F
there is order and arrangement in bags or multisets
F
equal or not? Bag ed.
[h,u,g,h] = [h,u,g]
NOT
is the first one a subbag of the second?
[a, b,a] ⊆ [a, b]
NOPE
T OR F
|
There is no order in sets
T
What is the Inclusion-Exclusion principle
|A ∪ B| = |A| + |B| − |A ∩ B|
is a collection
of things, called its elements, where there is a first element, a second
element, and so on.
Tuple
What are the things inside tuples called?
members
The 0-tuple is denoted by ___________
( ), and we call it the empty tuple
2-tuple is
often called an
ordered pair
equal or not.
(3,7) = (7,3)
NOT IT IS TUPLE STUPIT
Characteristic of tuple?
Yes repeat is good
YES ARRANGEMENT MATTERS
is
denoted by A × B, is the set of all ordered pairs (a, b)
Cartesian product
can be thought of as a
table of objects that are indexed by rows and columns
Matrix
finite ordered sequence of zero or more elements that can be
repeated.
List
what’s the difference
between tuples and lists?
tuples, we can
randomly access any component in a constant amount of time.
lists, we can randomly access only two things in a constant amount of
time. (Heads and tails)
number of elements in a list is called its
length
Whyat is the heads and tails of
<w, x, y, z>
heads = <w></w>
tails = <x,y,z>
will be used to denote this construction operation
cons
A = <A,v,c,d,g>
B = <N, r,t,y,j>
What is cons(head(A), head(B)) ?
<A, N>
A = <A,v,c,d,g>
B = <N, r,t,y,j>
What is cons(A, B) ?
«A,v,c,d,g> ,N, r,t,y,j>
he block of memory contains the
element together with an address
(called a pointer or link
is a finite ordered sequence of zero or more elements that are
placed next to each other in juxtaposition
string
make up a string are taken from a finite set called
Alphabet
string over of {a,b,c}
a, bc, abba, bbcba
string with no element is called the
empty string
is a set of strings
language
is a written number.
numeral
represent the set of positive integers by using the alphabe
Roman numerals
set of natural numbers using the alphabet
decimal numerals
represent the natural numbers using the alphabet
Binary numbers
We can combine two languages L and M to obtain the set of all
concatenations of strings in L with strings in M
Product of languages
L = {ab, ac}
M = {a, bc, abc}
LM = ?
{aba, abbc, ababc, aca, acbc, acabc}
is a set of n-tuples, where the
elements in each tuple are related in some way.
Relation
Another term for 1-ary, 2-ary, and 3-ary,
unary, binary,
and ternary
is a collection of facts that are represented by tuples
such that the tuples can be accessed in various ways to answer queries about
the facts.
relational database
What is product rle?
|A × B| = |A||B|
informal proof is a demonstration that some statement
is true
informal proof
