---
tags: NTNU,CSIE,必修,Discrete Mathematics
title : Introduction of Discrete Mathematics
description:

---
{%hackmd @NTNUCSIE112/S1VbPN1HU %}
# Introduction
### Information on Moodle
- Reading assignment: 
- Ch01: 1.1, 1.3.1-1.3.4, 1.4.1-1.4.10, 1.5, 1.7, 1.8 
- Ch02: 2.1-2.4, 2.6

---
### Logic and Proofs
> 1800s G.Boole & de Morgan

- Propositional Logic
- Proposition -> true or false sentence

#### Propositional Logic
- variable (symbol) for sentence
- e.g. $P$、$Q$
- Operations
- and($\land$)
- or($\lor$)
- not($\lnot$)
- Conditional Operator
- $\implies$
- If... then...
- $P \implies Q$ (if $P$ then $Q$)
- $P$ is precondition
- $Q$ is conclusion
- $(P \implies Q)$ $\iff$ $(\lnot P \land Q)$
- $\iff$
- If and only if
- $P \iff Q$
- $(P \implies Q)$ $\land$ $(Q\implies P)$
- Truth Table
| $P$ | $Q$ | $P \implies Q$ | $P \iff Q$ | $\lnot\ Q \implies \lnot\ P$ |
|:---:| --- |:--------------:|:----------:|:--------------------------:|
| $T$ | $T$ | $T$ | $T$ | $T$ |
| $T$ | $F$ | $F$ | $F$ | $F$ |
| $F$ | $T$ | $T$ | $F$ | $T$ |
| $F$ | $F$ | $T$ | $T$ | $T$ |
* $(P \rightarrow Q) \iff (\neg P \lor Q)$ : 為等價
- Quantifier
- If sentence has variables, true or false value change by variables.
- Predicate Logic(First-order logic)
- e.g.
- $x \in \mathbb{N}$
- $P(x)$： $x$ is prime (表 $x$ 和 $P$ 關係)
- Universsal quentifer $(\forall)$
- for all
- Existential quentifer $(\exists)$
- there exist
#### Sample
- If n is an odd number, then $n^2$ is also odd.
- $pf.$
$\because n$ is odd, $n = 2k + 1$, for some $k \in \mathbb Z$
$\therefore n^2 = (2k + 1)(2k + 1)$
$=4 k^2 + 4k + 1$
$=2(2k^2 + 2k) + 1$

- If n^2^ is an odd number, then n is also odd.
- $pf.$
$\lnot P$：$n^2$ is even
$\lnot Q$：$n$ is even
$(P \implies Q)$ $\iff$ $(\lnot Q \implies \lnot P)$
$\because$ $n$ is even
$\therefore$ $n =2k$ for some $k$ $\in \mathbb{Z}$
$\therefore$ $n^2 = 4k^2 = 2(2k^2)$, which is even

> Proof by [contraposition](https://en.wikipedia.org/wiki/Contraposition)

- Show that $\sqrt{2}$ is irrational
- $pf.$
(rational number ： $\cfrac{b}{a},\ a,b \in \mathbb{Z},\ a \neq$ 0)
suppose to the contrary that $\sqrt{2}$ = $\cfrac{b}{a}$,$b$$\in \mathbb{Z}$,$a \neq 0,\ gcd(a,b)=1$
$\sqrt{2} a = b$
$\rightarrow 2a^2 = b^2$
$\rightarrow b^2$ is even, $b = 2k,\ k \in \mathbb{Z}$
$\rightarrow 代入 \sqrt{2} a = b$
$\ \ \ \ \ \ \ \ \ \ 2a^2 = 4k^2$
$\ \ \ \ \ \ \ \ \ \ a$ is even
$\ \ \ \ \ \ \ \ \ \ gcd(a,b)\geq 2$
> Proof by contradiction
>

### Set
> Derive from 1874 by [Cantor](####Cantor)

- Set theory
- Primitive Concept
- Axiom
- Representation Method
- Roster Method
- E.g. : $\{a,\ b,\ c\}$
- Set comprehension
- E.g. : $\{x|x$ has property $P\}$
- The set of all $x$ such that $x$ has property $P$

#### [Frege](https://en.wikipedia.org/wiki/Gottlob_Frege)
> "The set of all sets $X$ s.t. $X \notin X$."
> [time=1903] [name=Russell]

- [Bertrand_Russell Wikipedia](https://en.wikipedia.org/wiki/Bertrand_Russell)
- i.e. $S=\{X|X \notin X\}$
- Russell's paradox
- Q : $S \in S$ ? $S \notin S$ ?

#### [Cantor](https://en.wikipedia.org/wiki/Georg_Cantor)
- Halting problem

<!--
終於真的進下章了
-->
<!-- 所以要開新的頁面了嗎 -->

[Modular Arithmetic](https://hackmd.io/tWVrN1MKQBCoyON5hOxmjQ?both)