Discrete Structures Week 5

Question 1

Theorem of Induction

Answer 1

given a predicate P(n), domain n >= 0 then if

p(0) = T
For all K, p(K) -> p(k+1)

then p(n) = T for all n >= 0

Question 2

Steps for Induction Professor way

Answer 2

find base
(rhs and lhs are equal)

show p(k) -> p(k+1)
assume P(k) = T

do p(k+1)
staring turning the lhs of p(k+1) into rhs of p(k+1)

make rhs look like rhs of the claim

Question 3

steps for induction TA way

Answer 3

prove base case

state inductive hypothesis
for induction we may assume p(n-1) is true that is we may assume
plug into n

inductive step to show p(n) convert p(n-1) into p(n) by manipulating

Question 4

set

Answer 4

an unordered list of elements without repetitions

Question 5

set of all integers

Answer 5

Z

Question 6

set of all natural numbers

Answer 6

N

Question 7

set of rational numbers

Answer 7

Q

Question 8

{x E U | p(x)}

Answer 8

for any x contained in domain U, P(x) is true

Question 9

look at examples on notes lecture 12 for more of set examples

Answer 9

:)

Question 10

subset

Answer 10

we say set A is a subset of set B if every element of A is also an element of B

Question 11

A c_ B

Answer 11

A is contained in B

Question 12

A = B

Answer 12

A c_ B
B c_ A

Question 13

definition of tautology in sets

Answer 13

given set A in U, define Pa(x) = “x C- A”

U = the set for which Pu(x) is a tautology

Question 14

empty set

Answer 14

set for which Po/(x) is a contradiction V-x, Po/(x) = F

how to prove on notes

Question 15

theorem for empty set

Answer 15

For any set S, o/ c_ S and Sc_ S
proof in notes

Question 16

theorem of two sets

Answer 16

long proof
on notes

Let
A = { x C- U | P(x) }
B = {x C- U | Q(x) }
then A = B if and only if P(x) =_ Q(x), V- X C- U

Question 17

intersection and venn diagram

Answer 17

A n B
= { x C- U | x C- A and x C- B}
= {x C- U | P(x) ^ Q(x) }

Question 18

disjoint and venn diagram

Answer 18

A n B = o/

Question 19

union and venn diagram

Answer 19

A U B
= {x C- U | x C- A or x C- B}
= {x C- U | P(x) v Q(x) }

Question 20

compliment and venn diagram

Answer 20

A ^c = A - (bar on top)
= { x C- U | ! P(x) }

Question 21

symmetric difference and venn diagram

Answer 21

only one true
exclusive or sign means symmetric difference here

A o+ B
= {x C- U | P(x) o+ Q(X) }

with venn diagrams can see
A o+ B = (A - B) U (B - A)

Question 22

set difference and venn diagram

Answer 22

A - B
= {x C- U | x C- A ^ x C- B}
= {x C- u | P(x) ^ !Q(x)}