Discrete Structures Lecture 10 Segment

Basic terminology pertaining to proofs 00:19 Definition: proof & theorem 02:07 Definition: lemma 02:58 Definition: corollary 03:22 ...

Basic number theory terminology 00:50 definition: even integer 01:36 definition: odd integer 01:51 definition: perfect square 02:29 ...

Proof technique: Universal generalization 00:00 Definition: arbitrary element of the domain 01:13 Proof of theorem in previous ...

Proof technique: Trivial proof Prove p → q by proving that q is always true.

Proof technique: Direct proof Prove p → q by proving that, assuming p is true, q must also be true.

Proving the same set equality as in the previous video using two other proof techniques, namely: + proof by equational reasoning ...

Proof technique: Direct proof for quantified conditionals Prove ∀x (P(x) → Q(x)) by combining a universal generalization proof ...

Proof technique: Vacuous proof Prove p → q by proving that p is always false.

More set operations 0:00 Union of two sets 6:15 Intersection of two sets

More terminology in basic set theory 0:00 Set cardinality; finite vs infinite sets 2:39 Power set 9:24 Cardinality of the power set.

Welcome back in this

Nested quantifiers The order of the quantifiers (sometimes) matters.

Functions 0:00 Definition: function, domain, co-domain 1:44 Definition: image, pre-image 3:46 Definition: arrow diagram 4:29 ...

10

Important functions 0:00 Factorial function 0:38 Modulus function 2:42 CS application: hash function 6:32 CS application: ...

Proving set equalities using proofs by mutual containment.

Cartesian product 0:00 Definition: n-tuple 1:18 Definition: pair 2:44 Definition: Cartesian product 8:20 Definition: relation