Discrete-math 20

Pigeonhole principle variations #theorem

\begin{matrix} There is m pigeons and k pigeonholes \\ Then there is a pigeonhole with at least ⌈ \frac{m}{k} ⌉ pigeons \\ Proof: \\ Let c_{i} be the number of pigeons in each pigeonhole \\ Let \forall i \in [1, n] : c_{i} < ⌈ \frac{m}{k} ⌉ ⟹ c_{i} \leq ⌈ \frac{m}{k} ⌉ - 1 \\ Then m = \sum_{i = 1}^{k} c_{i} \leq \sum_{i = 1}^{k} ⌈ \frac{m}{k} ⌉ - 1 < \sum_{i = 1}^{k} (\frac{m}{k} + 1 - 1) = m - Contradiction! \end{matrix}

\begin{matrix} In any group of 6 people \\ there is a group of 3 people who are all friends of each other \\ or there is a group of 3 people who are all not friends of each other \\ Proof: \\ Let A be one of the 6 people \\ Let’s consider two groups: \\ 1. Friends of A \\ 2. Not friend of A \\ By the pigeonhole principle, at least one of the groups has ⌈ \frac{5}{2} ⌉ = 3 people \\ Case 1. There are at least 3 friends of A \\ Case 1.1 There are two people in this group that are friends \\ Then A and these 2 people make a group of 3 people who are all friends of each other \\ Case 1.2 There are no two people in this group that are friends \\ Then this group is a group of at least 3 people that are all not friends of each other \\ Case 2. There are at least 3 people who are not friends of A \\ Case 2.1 There are two people who are not friends in this group \\ Then A and these two people make a group where all are not friends of each other \\ Case 2.2 There are no such pair \\ Then this group is at least 3 people who are all friends of each other \end{matrix}

\begin{matrix} Literal: logical variable or it’s negation \\ \land (AND) clause/term: \land of literals \\ \lor (OR) clause/term: \lor of literals \\ Proposition P is a disjuncitve normal form (DNF) \\ if it is \lor of AND clauses \\ DNF is complete if in any AND clause, any variable appears exactly once \\ For example: x_{1}, x_{2}, x_{3} : (x_{1} \land x_{2} \land x_{3}) \lor (\neg x_{1} \land \neg x_{2} \land \neg x_{3}) \\ Proposition P is a conjunctive normal form (CNF) \\ if it is \land of OR clauses \\ CNF is complete if in any OR clause, any variable appears exactly once \\ For example: x_{1}, x_{2}, x_{3} : (x_{1} \lor x_{2} \lor x_{3}) \land (\neg x_{1} \lor \neg x_{2} \lor \neg x_{3}) \end{matrix}

\begin{matrix} For any proposition P which is not a contradiction \\ There is an equivalent proposition in complete DNF \\ Proof: \\ Process of building the DNF: \\ 1. Compute the truth table \\ 2. Choose all substitutions that yield True. Each substitution will be an AND clause \\ 3. Each variable will appear in the clause as is if it’s value is True \\ 4. Each variable will appear in the clause as a negation if it’s value is False \\ 5. Connect all chosen clauses with \lor \\ For example: \\ (\begin{matrix} p & q & p \oplus q \\ 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{matrix}) \to {\begin{matrix} \neg p \land q \\ p \land \neg q \end{matrix} \to (\neg p \land q) \lor (p \land \neg q) \end{matrix}

\begin{matrix} For any proposition P which is not a tautology \\ There is an equivalent proposition in complete C N F \\ Proof: \\ P is not a tautology ⟹ \neg P is not a contradiction \\ ⟹ \exists a complete D N F of \neg P \\ \neg (complete D N F of \neg P) is a complete C N F of P \\ ⟹ \exists a complete C N F of P \end{matrix}

\begin{matrix} Set of logical connectives is complete if we can express any proposition \\ using only this set \end{matrix}

\begin{matrix} Connective N A N D (↑) \\ p ↑ q = \neg (p \land q) \\ Connective N O R (↓) \\ p ↓ q = \neg (p \lor q) \end{matrix}

\begin{matrix} The following sets are complete: \\ 1. {\lor, \land, \neg} \\ 2. {\lor, \neg} \\ 3. {\land, \neg} \\ 4. {\to, \neg} \\ 5. {↑} \\ 6. {↓} \\ Proof for 1 \\ {\lor, \land, \neg} is complete because any proposition has an equivalent in D N F \\ Proof for 2 \\ p \land q = \neg (\neg p \lor \neg q) \\ ⟹ By 1: {\lor, \neg} is complete \\ Proof for 3 \\ p \lor q = \neg (\neg p \land \neg q) \\ ⟹ By 2: {\land, \neg} is complete \\ Proof for 4 \\ p \lor q = \neg p \to q \\ ⟹ By 2: {\to, \neg} is complete \\ Proof for 5 \\ \neg p = p ↑ p \\ p \land q = \neg (p ↑ q) = (p ↑ q) ↑ (p ↑ q) \\ ⟹ By 3: {↑} is complete \\ Proof for 6 \\ \neg p = p ↓ p \\ p \lor q = \neg (p ↓ q) = (p ↓ q) ↓ (p ↓ q) \\ ⟹ By 2: {↓} is complete \end{matrix}