test

antara97

Chapter11.ppt

Home >Computer Science homework help >test

Elementary Notions and Notations

Section 1.1 A Proof Primer

A proof is a demonstration that some statement is true. We normally demonstrate proofs

by writing English sentences mixed with symbols.

We’ll consider statements that are either true or false. If A and B be are statements, then

“not A,” “A and B,” and “A or B,” are called negation, conjunction, and disjunction,

respectively. “not A” is opposite in truth value from A. “A and B” is true exactly when

both A and B are true “A or B” is true except when both A and B are false.

Conditionals: “if A then B” (or “A implies B”) is a

conditional statement with antecedent A and consequent B. It’s contrapositive is “if not B then not A” and it’s converse is “if B then A”. Statements with the same truth table are said to be equivalent. The table shows that a conditional and it’s contrapositive are equivalent.

A conditional is vacuously true if its antecedent is false.

A conditional is trivially true if its consequent is true.

Proof Techniques: We’ll give sample proofs about numbers. Here are some definitions.

integers: …, -2, -1, 0, 1, 2, …
odd integers: …, -3, -1, 1, 3, … (have the form 2k + 1 for some integer k).
even integers:…, -4, -2, 0, 2, 4, … (have the form 2k for some integer k).
m | n (read m divides n) if m ≠ 0 and n = km for some integer k.
p is prime if p > 1 and its only divisors are 1 and p.

Notice that the converse of “if A then B” is “if B then A” and they have DIFFERENT truth tables.

Exhaustive Checking

Some statements can be proven by exhaustively checking a finite number of cases.

Example 1. There is a prime number between 200 and 220.

Proof: Check exhaustively and find that 211 is prime. QED.

Example 2. Each of the numbers 288, 198, and 387 is divisible by 9.

Proof: Check that 9 divides each of the numbers. QED.

Conditional Proof

Most statements we prove are conditionals. We start by assuming the antecedent is true.

Then we try to find a statement that follows from the assumption and/or known facts. We

continue in this manner until we reach the consequent.

Example 3. If x is odd and y is even then x – y is odd.

Proof: Assume x is odd and y is even. Then x = 2k + 1 and y = 2m for some

integers k and m. So we have

x – y = 2k + 1 – 2m = 2(k – m) + 1,

which is an odd integer since k – m is an integer. QED.

Example 4. If x is odd then x2 is odd.

Proof: Assume x is odd. Then x = 2k + 1 for some integer k. So we have

x2 = (2k + 1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1,

which is an odd integer since 2k2 + 2k is an integer. QED.

Example 5. If x is even then x2 is even.

Proof: Class do as one minute quiz.

Example 6. If x2 is odd then x is odd.

Proof: The contrapositive of this statement is “if x is even, then x2 is even,” which is

true by Example 5. QED.

Example 7. If x2 is even then x is even.

Proof: This is the contrapositive of Example 4, which has been shown to be true. QED.

If And Only If (Iff) Proofs

A statement of the form “A if and only if B” means “A implies B” and “B implies A.” So

there are actually two proofs to give. Sometimes the proofs can be written as a single

proof of the form “A iff C iff D iff … iff B,” where each iff statement is clear from

previous information.

Example 8. x is even if and only if x2 – 2x + 1 is odd.

Proof: x is even iff x = 2k for some integer k (definition)

iff x – 1 = 2k – 1 for some integer k (algebra)

iff x – 1 = 2(k – 1) + 1 for some integer k – 1 (algebra)

iff x – 1 is odd (definition)

iff (x – 1)2 is odd (Examples 4 and 6)

iff x2 – 2x + 1 is odd (algebra). QED.

Proof By Contradiction

A false statement is called a contradiction. For example, “S and not S” is a

contradiction for any statement S. A truth table will show us that “if A then B,” is

equivalent to “A and not B implies false.” So to prove “if A then B,” it suffices to

assume A and also to assume not B, and then argue toward a false statement. This

technique is called proof by contradiction or reductio ad absurdum.

Example 9. If x2 is odd then x is odd.

Proof: Assume, BWOC, that x2 is odd and x is even. Then x = 2k for some integer k.

So we have

x2= (2k)2 = 4k2 = 2(2k2),

which is even since 2k2 is an integer. So we have

x2 is odd and x2 is even, a contradiction. So the statement is true. QED.

Example 10. If 2 | 5n then n is even.

Proof: Assume, BWOC, that 2 | 5n and n is odd. Since 2 | 5n, we have 5n = 2d for some

integer d. Since n is odd, we have n = 2k + 1 for some integer k. Then we have

2d = 5n = 5(2k + 1) = 10k + 5.

So 2d = 10k + 5. Solve for 5 to get

5 = 2d – 10k = 2(d – 5k).

But this says that 5 is an even number, a contradiction. So the statement is true. QED.

Section 1.2 Sets

A set is a collection of things.

If S is a set and x is a member or element of S we write x  S. Othewise we write x  S.
The set with elements x1, …, xn is denoted {x1, …, xn}.
The empty set with no elements is denoted { } or .
A set with one element is called a singleton. e.g., {a} is a singleton.
The set of integers is denoted by Z, the natural numbers {0, 1, …} by N, the rational

numbers by Q, and the real numbers by R.

Equal Sets

Two sets A and B are equal, denoted A = B if they have the same elements.

e.g., {a, b, c} = {c, b, a} (no ordering).

e.g., {a, a, b, c} = {a, b, c} (no repetitions)

Sets can be described by properties that the elements satisfy. If P is a property, then the

expression {x | P} denotes the set of all x that satisfy P.

e.g., The set of odd natural numbers can be represented by the following equal sets.

{x | x = 2k + 1 for some k  N} = {1, 3, 5, …}.

Subsets

The set A is a subset of B, denoted A  B, means every element of A is an element of B.

e.g., N  Z  Q  R.

e.g., S  S for any set S.

e.g.,   S for any set S.

The power set of a set S, denoted power(S) is the set of all subsets of S.

e.g., power({a, b}) = {, {a}, {b}, {a, b}}.

Example(Comparing sets). Let A = {2k + 7 | k  Z} and B = {4k + 3 | k  Z}.

Quiz. Is A  B?

Answer: No. For example, 9  A but 9  B.

Quiz. Is B  A?

Answer: Yes. Let x  B. Then x = 4k + 3 for some k  Z. But we can write

x = 4k + 3 = 4k – 4 + 7 = 2(2k – 2) + 7.

Since 2k – 2  Z, it follows that x  A. Therefore B  A. QED.

Equality in terms of subsets: A = B iff A  B and B  A.

Example. Let A = {2k + 5 | k  Z} and B = {2k + 3 | k  Z}.

Show that A = B.

Proof: First show A  B. Let x  A. Then x = 2k + 5 for some k  Z. So we have

x = 2k + 5 = 2k + 2 + 3 = 2(k + 1) + 3.

Since k + 1  Z, it follows that x  B. Therefore A  B.

Now show the other direction B  A.

…….Class fill in the proof (2 minute quiz).

Since A  B and B  A it follows that A = B. QED.

Operations on Sets

Union: A  B = {x | x  A or x  B}.

Intersection: A  B = {x | x  A and x  B}.

Difference: A – B = {x | x  A and x  B}.

Symmetric Difference: A  B = {x | x  A or x  B but not both}

Note: A  B = (A – B)  (B – A) = (A  B) – (A  B ) .

Universal Complement: Given a universe U and A  U, we write

A' = U – A.

Example. For each n  N let Dn = {x  N | x divides n}. So Dn is the set of positive

divisors of n. Here are some expressions involving these sets.

D0 = {1, 2, 3, … } = N – {0}, D5 = {1, 5}, D6 = {1, 2, 3, 6}, and D9 = {1, 3, 9}.
D5  D6 = {1, 2, 3, 5, 6}
D5  D6 = {1}
D9 – D6 = {9}
D5  D6 = {2, 3, 5, 6}
Let N be the universe. Then D0' = N – D0 = {0}, and {0}' = D0.

Quiz (2 minutes). Draw a Venn diagram for three sets A, B, C with some areas shaded.

Then find an expression to represent the shaded area.

Properties of Set Operations

Union and intersection are commutative, associative, and distribute over each other. There

are many other properties too. For example,

Absorption: A  (A  B) = A and A  (A  B) = A.
De Morgan’s Laws: (A  B)' = A'  B' and (A  B)' = A'  B'.

Counting Sets

The cardinality of a set S is denoted by | S |. Two useful rules for counting finite sets are:

Inclusion-Exclusion principle: | A  B | = | A | + | B | – | A  B |.
Difference Rule: | A – B | = | A | – | A  B |.

Quiz (2 minutes). Find a rule for the union of three sets: | A  B  C | = ?

Quiz (3 minutes). Three programs use a collection of processors in the following way,

where A, B, and C represent the sets of processors used by the three programs:

| A | = 20, | B | = 40, | C | = 60, | A  B | = 10, | A  C | = 8, | B  C | = 6.

If there are 100 processors available, what could | A  B  C | be?

Answer: 100 ≥ | A  B  C | = 20 + 40 + 60 – 10 – 8 – 6 + | A  B  C | . So

| A  B  C | ≤ 4.

Bags (Multisets) are like sets but can contain repeated elements. e.g., [t, o, o, t] = [o, t, t, o].

Union and intersection can be defined by taking the maximum and minimum occurrences of

each element, respectively.

Quiz (2 minutes). Let A = [m, i, s, s, i, s, s, i, p, p, i] and B = [s, i, p, p, i, n, g].

What are A  B and A  B?

Answer: A  B = [m, i, s, s, i, s, s, i, p, p, i, n, g] and A  B = [s, i, p, p, i].

Section 1.3 Ordered Structures

Tuples: Have order and can have repetitions. For example, (6, 7, 6) is a 3-tuple and ( ) is

the empty tuple. We write (x1, …, xn) = (y1, …, yn) to mean xi = yi for 1 ≤ i ≤ n.

Cartesian Product: A  B = {(x, y) | x  A and y  B}. The definition extends to more than

two sets. For example, A  B  C = {(x, y, z) | x  A, y  B, z  C}.

Notation: A0 = {( )}, A1 = {(x) | x  A}, and in general, An = {(x1, …, xn) | xi  A}.

Quiz (1 minute). Does (A  B)  C = A  (B  C)?

Lists: Are like tuples but there is no random access. For example, a, b, a, c is a list with 4

elements and   is the empty list.

The operations on lists are head, tail, and cons. For example,

head(a, b, a, c) = a, tail(a, b, a, c) = b, a, c, cons(a, b, a, c) = a, b, a, c.

The set of lists whose elements are in A is denoted by lists(A).

Quiz (1 minute). For L =  a, b, c, d , find head(L) and tail(L).

Strings: Are like lists, but are represented as juxtaposed elements from a given alphabet.

For example, if A = {a, b}, then some strings over A are: a, b, aa, ab, ba, bb, aaa, bbb.

The empty string is denoted by L.
The concatenation of two strings is their juxtaposition. For example, the concatenation of

ab and bab is abbab.

For any string s we have sL = Ls = s.
If s is a string, sn denotes the concatenation of s with itself n times. Also s0 = L. For

example, (ab)3 = ababab.

Languages

A language is a set of strings, usually taken over some alphabet.

Notation: If A is an alphabet, then the set of all strings over A is denoted by A*.

Example. Some languages over A are: , {L}, A, and A*.

Example. {abna | n  N} = {aa, aba, abba, abbba, … } is a language over {a, b}.

Language Operations

Let L and M be languages. The product of L and M, denoted LM, is the language

LM = {st | s  L and t  M}.

Notation: L0 = {L}; and Ln = {s1…sn | si  L}.

Quiz (1 minute). What are the products L and L{L}?

Quiz (1 minute). Solve for L in the equation {L, a, b}L = {L, a, b, aa, ba, aba, bba}.

The closure L* is the set of all possible concatenations of strings in L. So

L* = L0  L1  …  Ln  …

Quiz (1 minute). What are {L}* and *?

Example. Examine the structure of an arbitrary string x  L*(ML)*.

A solution: Use the definitions to write x in terms of strings in L and M.

1. Since x  L*(ML)*, it follows that x = uv where u  L* and v  (ML)*.

2. Since u  L*, either u = L or u = s1…sn for some n where si  L.

3. Since v  (ML)*, either v = L or v = r1t1 …rktk for some k where ri  M and ti  L.

So x has one of four forms: L, s1…sn, r1t1 …rktk, or s1…snr1t1 …rktk.

Relations.

A relation is a set of tuples. If R is a relation and (x1, …, xn)  R, we write R(x1, …, xn).

We can usually represent a relation as a subset of some cartesian product.

Example. Let R = {(0, 0), (1, 1), (4, 2), (9, 3), …, (n2, n), …} = {(n2, n) | n  N}. We might

call R the “is square of” relation on N. Notice also that R  N  N.

Notation: If R is binary, we can use infix to represent pairs in R. For example, from the

previous example, we have (9, 3)  R. So we can also write

R(9, 3) or 9 R 3 or 9 is square of 3.

Relational Databases

A relational database is a relation where the indexes of a tuple have associated names

called attributes.

Example. Let Students = {(x, y, z) | x is a Name, y is a Major, and z is Credits}.

Who are the people majoring in CS?

{x | (x, CS, z)  Students, for some z}.

Note: We need “for some z” to indicate that z is a variable.

How many math majors are upper division students?

| {x | (x, math, z)  Students and z ≥ 90} |.

What is the major of AbeLincoln?

{y | (AbeLincoln, y, z)  Students, for some z}.

What is the history department database of names and their credits?

{(x, z) | (x, history, z)  Students}.

Counting Tuples (or strings or lists)

Product Rule: | A  B | = | A | | B | and | An | = | A |n.

Example. If A = {a, b} and B = {1, 2, 3}, then

A  B = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)}.

So | A  B | = 6 = (2)(3) = | A | | B |.

Example. Count the number of strings of length 8 over A = {a, b, c} that begin with either

a or c and have at least one b.

It is easy to calculate the cardinality of U – B:

| U – B | = | U | – | U  B | = | U | – | B | (since B is a subset of U)

It is also easy to count U because it has the same cardinality as the set {a, c}  A7, which is

| {a, c}  A7 | = | {a, c} | | A7 | = | {a, c} | | A |7 = (2)37.

It is also easy to count B because it has the same cardinality as the set {a, c}8, which is

| {a, c}8 | = | {a, c} |8 = 28.

So we have the answer:

| U – B | = | U | – | U  B | = | U | – | B | = (2)37 – 28, which is 4118.

A Solution: Split the problem up into easier problems and combine

the results (divide and conquer). Let U be the universe consisting

of the strings over A of length 8 that begin with either a or c. Let B

be the subset of U consisting of strings with no b’s. Then the set of

strings to count is U – B, as pictured.

U – B

Section 1.4 Graphs and Trees

A graph is set of objects called vertices or nodes where some pairs of objects may be

connected by edges. (A directed graph has edges that point in one direction.)

Example. Draw a graph of the South American countries that touch the Pacific Ocean and

their neighbors, where the vertices are countries and an edge indicates a common border.

Vertices = {Co, V, E, Br, P, Bo, Ch, A}

Edges = {{Co, V}, {Co, E}, ….}.

A path from vertex x0 to xn is a sequence of edges

that we denote by (x0, x1, …, xn) where

there is an edge from xi–1 to xi for 1≤ i ≤ n.

The length of a path is the number of edges.

A cycle is a path with distinct edges that begins

and ends at the same vertex.

Example. (A, Bo, A) is not a cycle since the edge

{A, Bo} occurs twice. (A, Bo, Br, A) is a cycle.

Quiz (1 minute). What is a longest path from A to V with distinct edges and no cycles?

Answer: The length is 6. For example, (A, Bo, Br, P, E, Co, V).

A graph is connected if there is a path between every pair of vertices. The example graph is connected. A graph of the United States is not connected. Hawaii and Alaska are isolated vertices.

Trees

A tree is a connected graph (a path between any two points) with no

cycles. Most trees are oriented so that they look like upside-down

trees, such as the tree pictured.

The top node is the root, the nodes directly below a node are its

children, the node directly above a node is the parent, the bottom

nodes are leaves, and the height or depth of the tree is the length of

the longest path of distinct edges from root to a leaf.

Any algebraic expression can be represented as a tree. For

example, the tree for the expression (x – y) + log(z + w) is

pictured to the right.

Quiz (1 minute). Do a depth-first (left to right) traversal.

Answer: + – x y log + z w. This is the prefix form of the

expression.

Example. For this tree the root is A. The children of A are B, C, D. D is the

parent of G. The height or depth of the tree is 3. The leaves are E, F, C, H, I.

Any node of a tree is the root of a subtree. One way to represent a tree is as a

list whose head is the root of the tree and whose tail is the list of subtrees, where

each subtree is represented in the same way.

Example. The pictured tree can be represented by the list

 A,  B,  E ,  F  ,  C ,  D,  G,  H ,  I    .

log

Binary Trees

A binary tree is either empty, denoted by  , or each node has two subtrees that are binary

trees and are called the left and right subtrees of the node. If a binary tree is not empty,

we’ll represent it as a list of the form L, x, R, where x is the root and L and R are the left

and right subtrees, respectively.

Spanning Trees

A spanning tree for a connected graph is a tree whose nodes are the nodes of the graph and

whose edges are a subset of the edges of the graph. A minimal spanning tree minimizes the

sum of weights on the edges of all spanning trees.

Example. The binary tree with a single node x is denoted by  , x,  .

A binary search tree represents ordered information, where the predecessors

and successors of a node are in its left and right subtrees, respectively.

Example. A binary search tree for the first six prime numbers is pictured.

Example. Use Prim’s algorithm to construct a minimal spanning tree

for the pictured graph, starting with node D.

Solution: A minimal spanning tree is constructed in 4 steps: