---
# System prepended metadata

title: Introduction of Discrete Mathematics
tags: [Discrete Mathematics, 必修, NTNU, CSIE]

---

---
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)
