---
# System prepended metadata

title: Untitled

---

:::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ń:
:::
![image alt](https://i.imgur.com/V9Opuik.jpg =250x250 )
$\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$
