Discrete Structure Week 4

Question 1

theorem

Answer 1

a statement that is shown to be true

Question 2

what is used to prove theorems

Answer 2

rules of inferences
(ex modus ponens)

Question 3

axioms

Answer 3

arguments are based on statements that are said to be true

Question 4

proposition

Answer 4

minor result compared to theorems that are major/important results

Question 5

proof

Answer 5

the series of arguments used to prove a theorem

Question 6

| meaning and the definition

definition

Answer 6

let m and n be integers
if there exists an integer k, such that m = k times n we say that n divides m

n|m

Question 7

definition of even

Answer 7

an integer is even if it is divisible by 2. it is odd otherwise

Question 8

theorem of n

Answer 8

let n be an integer
then n is even if and only if n^2 is even

Question 9

paradox

Answer 9

contradicsts itself

Question 10

circular reasoning

Answer 10

assumes what it tries to prove

Question 11

induction

Answer 11

idea: consider a predicate p(n) where n is any integer n>= 0
the inductive principle allows to give a proof of
V-, p(n) = T

Question 12

weak induction/induction theorem

Answer 12

consider a predicate p(n) for all integers n>=0 assume
1. p(0) =T
2. V- k>=0, p(k) -> p(k+1)
then p(n) = T for all n>= 0 that is V-n,p(n)

Question 13

induction steps

Answer 13

1. base case, assumption of 0
2. V- k, P(k) ->P(k+1)
3. P(k) means… plug k into P
4. want to show P(k+1) = “plugging in k+1 in this case”
5. plug in whatever you may see
6. convert it into P(k+1) when k+1 is plugged in
7. state P(k+1) =T
   …so by the theorem of induction, P(n) = T for all n>=0