Příklady VPL ZS 2017/18

Náhradní příklady 2017/18.

Jeden (správně vyřešený) příklad za 3 body.
  1. Dokažte tablo-metodou pro formule $\varphi(x)$ a $\psi(x)$ s volnou proměnnou $x$:
    • a) $(\exists x)(\varphi(x) \lor \psi(x)) \leftrightarrow (\exists x)\varphi(x) \lor (\exists x)\psi(x)$
  2. (G7.4var) Uvažme teorii $T$ (teorie grup) nad jazykem $L=\langle +_2, -_1, 0_0 \rangle$ pouze s funkčními symboly a s rovností, s axiomy $$ x+ (y+z) = (x+y)+z$$ $$ 0+x=x=x+0$$ $$x+(-x) = 0 = (-x) + x$$ Rozhodněte, zda následující formule jsou pravdivé / lživé / nezávislé v $T$.
    • a) $ -(-x) = x$
  3. (G7.5var) Nechť $L = \langle F_2 \rangle$ je jazyk s funkčním symbolem $F$ a s rovností. Napište formule definující v následujících strukturách následující množiny:
    • a) interval $\langle 0, \infty )$ v ${\cal A} = \langle \mathbb{R}, \cdot \rangle$ bez parametrů, kde $\cdot$ je standardní násobení reálných čísel,
    • b) množinu všech nejvýše jednoprvkových podmnožin $\mathbb N$ v ${\cal B} = \langle {\cal P}(\mathbb{N}), \cup \rangle$,
    • Dále $L = \langle \cdot_2, +_2 \rangle$ s rovností a funkčními symboly v obvyklém významu násobení a sčítání reálných čísel:
    • c) interval $( 0, d)$ v ${\cal A} = \langle \mathbb{R}, \cdot, + \rangle$ s parametrem $d$.
  4. Pro teorii $T=\{P(0), (\forall x)(P(x) \to P(s(x)))\}$ nad jazykem $L =\langle P_1,s_1,0_0 \rangle$ dokažte rezolucí $T \vdash P(s(s(0)))$
  5. (G9.6) Nechť $T$ je teorie s axiomy rovnosti. Tablo metodou dokažte:
    • a) $T \models (x=y \wedge y=z ) \to x=z $
    Nápověda: Pro a) v axiomu rovnosti (iii) vezměte $x_1=x$, $x_2=y$, $y_1=x$ a $y_2=z$.
  6. (G9.8) Dokažte větu o dedukci pomocí transformací tabel.
    Věta. Pro každou teorii $T$ (v uzavřeném tvaru) a sentence $\varphi$, $\psi$,
    $T \vdash \varphi \to \psi$     právě když     $T,\varphi \vdash \psi$

Cvičení 1.

  1. Sestrojte pravdivostní tabulky pro následující formule:
    • a) $((p \to q ) \to p) \to p$
    • b) $\neg (p \vee q) \leftrightarrow \neg p \wedge \neg q$
    • c) $(p \to q \to r) \to (p \to q) \to (p \to r)$
  2. Navrhněte relace a teorie pro
    • a) obyčejné orientované grafy bez násobných hran
    • b) grafy bez smyček
    • c) neorienované grafy
  3. Vyjádřete formulí 1. řádu v grafu
    • a) v grafu existuje cesta délky 4
    • b) v grafu existuje kružnice délky 4
    • ...
    • ...
  4. Formalizujte s relací dělitelnosti $m|n$ ($m$ dělí $n$) v teorii množin:
    • a) $z$ je společný dělitel $x$ a $y$
    • b) $z$ je největší společný dělitel $x$ a $y$
    • c) $z$ je největší společný dělitel všech čísel z množiny $X$
  5. Formalizujte v jazyce s relacemi $P(x)$ - "$x$ je prvočíslo" a $R(x,y)$
    • a) pro nějaké prvočíslo $x$ máme prvek $y$, že platí $R(x,y)$
    • b) pro každé prvočíslo $x$ máme prvek $y$, že platí $R(x,y)$
  6. Formalizujte v jazyce s $\le$ a rovností
    • a) $x$ je minimální prvek
    • b) $x$ je nejmenší prvek
    • c) $x$ má bezprostředního předchůdce
  7. Formalizujte v jazyce s rovností pro dané $n$
    • a) existuje nejvýš $n$ prvků
    • b) existuje aspoň $n$ prvků
    • c) existuje právě $n$ prvků
    • d) Lze vyjádřit "existuje nekonečně mnoho prvků"? (proč ne, případně jak ano)
  8. Hra dvou hráčů. Mějme konečnou hru dvou (střídajících se) hráčů. Hra končí po $n$ kolech výhrou jednoho ze dvou hráčů označených $X$ a $Y$, přičem $X$ začíná. Hra je zadána formulí $\varphi(x_1, y_1, ... , x_n, y_n)$ vyjadřující, že ve hře s tahy $x_1, y_1, ... , x_n, y_n$ vyhrává $X$. Pomocí kvantifikátorů sestrojte formuli vyjadřující
    • a) "$X$ nemůže prohrát",
    • b) "$Y$ nemůže prohrát",
    • c) "$X$ má vyhrávající strategii",
    • d) "$Y$ má vyhrávající strategii".
  9. Navrhněte pro daný graf $G$ výrokovou formuli, která je pravdivá právě když
    • a) graf je bipartitní
    • b) graf je obarvitelný 3 barvami
    • c) graf má cestu délky 4
    • d) ...

Cvičeni 2

    • Zapište a/nebo zakreslete vytvořující strom formule $\neg(p \to \neg q) \to (q \vee \neg r) $.
    • Jaké jiné zápisy struktury výrazů (termů) znáte, např. z programování? Použijte je.
  1. Zapište v CNF a DNF formuli $f(p,q,r)$ nad $\{p, q, r\}$:
    • a) parita , tj. lichý počet pravdivých prvovýroků
    • b) majorita, tj. aspoň polovina pravdivých prvovýroků
  2. Univerzální množiny spojek.
    • a) Určete, které z následujících množin spojek jsou univerzální: 1: $\{\vee,\wedge,\neg\}$, 2: $\{\vee,\wedge\}$, 3: $\{\vee, \neg\}$, 4: $\{\to,\neg\}$, 5: $\{\to,\neg,\vee,\wedge\}$, 6: $\{\downarrow \}$, 7: $\{\uparrow \}$.
      Pozn.: šipka dolu: Peirceova spojka, NOR (TeX: downarrow); šipka nahoru: Shefferova spojka, NAND (TeX: uparrow)
    • b) Pokud je nějaká množina spojek $S$ univerzální, je každá její nadmnožina $S'$, $S \subseteq S'$, univerzální?
  3. Převeďte na CNF

Nástroje

    Pro kopirovani
  1. test, $\tt OK$ Příliš žluťoučký kůň úpěl ďábelské ódy. áäčďéěíĺľňóö_o_řŕšťúůýž