:::info
Zadanie 93. Udowodnij, ze dla każdej formuły zdaniowej φ istnieje formuła ψ równowazna z φ i mająca koniunkcyjną postac normalną.
:::
**Dowód**:
Weźmy dowolną formułę $\phi$ oraz niech $p_1...p_n$ będą zmiennymi zdaniowymi występującymi w $\phi$. Rozważmy tabelkę zerojedynkową.

| $p_1$ | ... | $p_n$ | $\phi$ |
| ----- | ---- | ----- | ------ |
| F |... | T| T |
| ... | ... | ... | |
| ... | ... | ...| |
| T | ... | F | F |

Rozważmy dwa przypadki:
Przypadek I:
W kolumnie $\phi$ nie ma ani jednego wystąpienia F. Wtedy $\phi$ jest tautologią i w związku z tym $\phi\equiv$ T, a T jest w CNF
Przypadek II:
W kolumnie $\phi$ jest co najmniej jedno wystąpienie F. Ten wiersz odpowiada jakiemuś wartościowaniu $\sigma$, dla którego oznaczmy formułę $\phi_\sigma$:
Niech $\phi_\sigma$ oznacza formułę
$\bigvee_{i:\sigma(p_{i})=F} p_i \wedge \bigvee_{i:\sigma(p_{i})=T} \neg p_i$
Zauważmy, że $\sigma$ jest jedynym wartościowaniem dla którego $\phi_\sigma$ jest fałszem. Dla innych dowolnych wartościowań różnych od $\sigma$ formuła $\phi_\sigma$ będzie prawdą.
Niech $\psi$ będzie formułą $\bigwedge_{\sigma:\sigma(\phi) = F}\phi_\sigma$, wtedy $\psi$ jest formułą w CNF oraz $\phi = \psi$, bo mają taką samą tabelkę zerojedynkową.

:::info
Zadanie 87. Znajdź formuły zdaniowe φ1, φ2, φ3 mające dysjunkcyjną postac normalną, zawierające zmienne p, q i r i spełnione dla podanych nizej wartościowań:
:::
$\phi = (T \wedge T \wedge \neg F) \vee (\neg F \wedge \neg F \wedge T)$

$\phi_1 = (p\wedge q\wedge r) \vee (p\wedge \neg q\wedge r) \vee (\neg p\wedge q\wedge r)$
$\phi_2 = (p\wedge \neg q\wedge r) \vee (p\wedge \neg q\wedge \neg r)$
$\phi_3 = (p\wedge \neg q\wedge \neg r) \vee (\neg p\wedge q\wedge r) \vee (\neg p\wedge q\wedge \neg r) \vee (\neg p\wedge \neg q\wedge r)$

$\lim_{x\rarr \infty}{\Big|\frac{n^2}{2^n}\Big|}=\lim_{x\rarr \infty}{\frac{n^2}{2^n}}=\lim_{x\rarr \infty}{\frac{2n}{2^nln(2)}}=\lim_{x\rarr \infty}{\frac{2}{2^nln^{2}(2)}}=\lim_{x\rarr \infty}{\frac{0}{2^nln^{3}(2)}}=0<\infty$