離散数学まとめ

コンピューターサイエンス学科の授業の離散数学の授業のまとめ。（随時更新）

論理記号

AND

$\land$

\land

$\begin{array}{|c |c|c|}p & q & p \land q\\ \hline T & T & T\\T & F & F\\F & T & F\\F & F & F\\\end{array}$

OR

$\lor$

\lor

$\begin{array}{|c |c|c|}p & q & p \lor q\\ \hline T & T & T\\T & F & T\\F & T & T\\F & F & F\\\end{array}$

Negation

$\neg$

\neg

$\begin{array}{|c |c|}p &\neg p\\ \hline T & F\\T & F \\F & T \\F & T\\\end{array}$

XOR

$\oplus$

\oplus

$\begin{array}{|c |c|c|}p & q & p \oplus q\\ \hline T & T & F\\T & F & T\\F & T & T\\F & F & F\\\end{array}$

Implies

$\to$

\to

$\begin{array}{|c |c|c|}p & q & p \to q\\ \hline T & T & T\\T & F & F\\F & T & T\\F & F & T\\\end{array}$

IFF

$\leftrightarrow$

\leftrightarrow

In / Not in

$\in$

$\notin$

\in
\notin

Subset

$\subseteq$

\subseteq

Logical distributivity

OR

$P \lor (Q\land R) \equiv (P\lor Q) \land (P\lor R)　$

AND

$P \land (Q\lor R) \equiv (P\land Q) \lor (P\land R)　$

Simpler compound statement

例1

$P \land (P\lor Q) \equiv P$

$\begin{array}{|c |c|c|}p & q & p \land (p \lor q) \\ \hline T & T & T\\T & F & T\\F & T & F\\F & F & F\\\end{array}$

$P \lor (P\land Q) \equiv P$

$\begin{array}{|c |c|c|}p & q & p \lor (p\land q) \\ \hline T & T & T\\T & F & T\\F & T & F\\F & F & F\\\end{array}$

$\therefore P \land (P\lor Q) \equiv P \lor (P\land Q)$

例2

$\neg (p\land q) \equiv (\neg p) \lor (\neg q)$

$\neg (p\lor q) \equiv (\neg p) \land (\neg q)$

Roster notation

$A = \{2n \mid n \in \mathbb{Z} \}$

Operators

Union

$P\cup Q$

\cup

$\forall x\in U; x\in P\cup Q \iff x\in P \lor x\in Q$

Intersection

$P\cap Q$

\cap

$\forall x\in U; x\in P\cap Q \iff x\in P\land x\in Q$

Complement

$P^c$

P^c

$\forall x\in U; x\in P^c \iff \neg (x\in P) \quad or\quad x\notin P $

Symmetric difference

$P\oplus Q$

\oplus

$\forall x\in U; x\in P \oplus Q \iff x\in P \oplus x\in Q$

Subset

A is a subset of B

\subseteq

$A\subseteq B\quad (\forall x \in U, x\in A \to x\in B$)

Empty set

$\varnothing$

\varnothing

$\varnothing = U^c,\quad \varnothing = \{\}$

Operator exercise

例１

$1\in \mathbb{N} \to True$

例２

$1\in \varnothing \to False$

例３

$\varnothing \subseteq \mathbb{N}\to True $

例４

$\varnothing \in \mathbb{N} \to False$

例５

$\{1,2\} \in \{\{1,2\},3\} \to True$

例６

$\{1,2\} \subseteq \{\{1,2\},3\} \to False$

例７

$\varnothing　\in \{1,2,\varnothing\} \to True$

例８

$\varnothing \subseteq \{\varnothing\}\to True$

Cardinality

$|\{1,2,3\}| = 3$

$|\{\{1,2\},\varnothing,3\}| = 3$

$P\subseteq Q$ then $|P| \subseteq |Q|$

$P\nsubseteq Q$ then $|P| \nsubseteq |Q|$

Power set

$P(A)$:the set of subsets of A

・$\varnothing\in P(A)$

・$P(\{1,2\})=\{\varnothing,\{1\},\{2\},\{1,2\}\}$

・$|P(A)|=2^{|A|}$