Příklady VPL ZS 2018/19

Cvičení 1.

  1. Sestrojte pravdivostní tabulky pro následující formule:
    • a) $((p \to q ) \to p) \to p$ *CV2*
    • 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 jazyk, relace a teorie pro
    • a) obyčejné orientované grafy bez násobných hran *CV1*
    • b) grafy bez smyček *CV1*
    • c) neorientované grafy *CV1*
    • d) spojitost na grafech (tj. relaci pro pojem cesty)
  3. Vyjádřete formulí 1. řádu (v jazyce teorie grafů)
    • a) v grafu existuje cesta délky 4
    • b) v grafu existuje kružnice délky 4
    • c) $u$ a $v$ mají aspoň jednoho společného souseda
    • d) existují tři nezávislé hrany
    • e) existuje cesta mezi $u$ a $v$ délky $n$, kde $n>0$ je předem dané
    • e1) existuje cesta mezi $u$ a $v$ délky nejvýše $n$, kde $n>0$ je předem dané
    • f) v grafu existuje vrchol stupně 1
    • g) graf je regulární stupně 3
    • h) existuje vrcholové pokrytí velikosti $n$, kde $n>0$ je předem dané
    • i) ... klika, nezávislá množina ... , dané velikosti $n$
  4. Sestrojte formule 2. řádu (v jazyce teorie grafů) vyjadřující
    • a) existuje bipartitní rozklad *CV1/DU*
    • b) existuje perfektní párování *CV1*
    • c) existuje cesta mezi $u$ a $v$
    • d) existuje obarvení grafu třemi barvami *CV1*
    • e) existuje obarvení grafu $n$ barvami, kde $n>0$ je předem dané
    • f) graf má tvar vrstveného grafu s $n$ vrstvami, kde $n>0$ je předem dané (tj. všechny hrany vedou z vrstvy $i$ do vrstvy $i+1$)
    • g) ...
  5. Je dán (neorientovaný) graf $G$ a dva jeho vrcholy $u$ a $v$. Sestrojte výrokovou formuli (algoritmicky, v závislosti na $G$), která je splnitelná, právě když
    • a) $G$ je bipartitní *CV2*
    • b) $G$ má perfektní párování
    • c) v $G$ existuje cesta mezi $u$ a $v$
    • d) graf je obarvitelný 3 barvami *CV2*
    • e) graf má cestu délky 4
    • (f) v $G$ existuje f.1) klika velikosti $n$, f.2) nezávislá množina velikosti $n$, f.3) vrcholové pokrytí velikosti $n$, f.4) obarvení grafu $n$ barvami, kde $n>0$ je předem dané
    • Poznámky:
    • i) Předbíháme, bude ještě na ADS. Většinou chceme formuli v CNF a polynomiálně velkou k $G$.
    • ii) Pro podobné grafové úlohy v minulých úlohách chceme 3 odlišné věci: 1) navrhnout jazyk a teorii; 2) vyjádřit formulí; 3) převést na výrokovou formuli.
  6. 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$
  7. Formalizujte v jazyce s relacemi $P(x)$ vyjadřující "$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)$
    Pozn.: V PL nemáme sorty (druhy/typy prvků), proto pokud chceme charakterizovat nebo vybírat pouze z nějakých prvků, potřebujeme je určit a vhodně spojit se zbytkem formule. *CV2*
  8. Formalizujte v jazyce s $\le$ a rovností *CV2*
    • a) $x$ je minimální prvek,
    • b) $x$ je nejmenší prvek,
    • c) $x$ má bezprostředního předchůdce,
    • d) každé dva prvky mají nejmenšího společného následníka.
  9. Formalizujte v jazyce s rovností pro dané $n$ *CV2*
    • 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)
  10. Hra dvou hráčů. *CV2* 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".

  11. a) Navrhněte jazyk pro posloupnosti, tj. řetězce. *CV3*
    b) Definujte teorie pro relace předpona $P_2$ (\(P(x,y)\) pro "\(x\) má předponu \(y\)") , přípona $S_2$, (spojitý) podřetězec $U_2$, (nespojitá) podposloupnost $W_2$ a obrácení řetězce $R_2$.
    Pozn.: Algebraická struktura monoid: asociativní, s neutrálním prvkem.

Cvičení 2

  1. Zapište a/nebo zakreslete vytvořující strom formule $\neg(p \to \neg q) \to (q \vee \neg r) $. *CV3*
    • p) Jaké jiné zápisy struktury výrazů (termů) znáte, např. z programování? Použijte je.
  2. 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ů, *CV2*
    • b) majorita, tj. aspoň polovina pravdivých prvovýroků,
    • (a.1) pro paritu (i majoritu) vycházejí velké formule. Víte zdůvodnit proč?
    • (a.2) Máte spojku xor (vylučovací nebo, $\otimes$). Dokážete zapsat paritu malou formulí? *CV2*
    • (a.3) Najdete jinou formuli, která bude mít dlouhý zápis?
  3. Univerzální množiny spojek. *CV3*
    • 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í? *CV3*
    • (c) Jakým způsobem lze dokázat, že nějaká množina spojek není univerzální?
  4. Převeďte dané formule do CNF a DNF i) tabulkou (tj určením modelů) a ii) ekvivalentními úpravami
    • a) $(p \lor \neg q) \to (q \vee \neg r)$ *CV3*
    • b) $(\neg p \to (\neg q \to r)) \to p $
    • c) $((p \to \neg q) \to r) \to q $
    • d) $(\neg p \wedge q) \to (\neg q \leftrightarrow r)$
  5. Pomocí implikačního grafu rozhodněte o splnitelnosti formule.
    • a) $(x_1 \lor \neg x_2) \wedge (x_2 \lor x_3) \wedge (\neg x_3 \lor \neg x_1) \wedge (\neg x_3 \lor \neg x_4) \wedge (x_4 \lor x_5) \wedge (\neg x_5 \lor \neg x_1)$
    • b) $(x_1 \lor \neg x_2) \wedge (x_2 \lor x_3) \wedge (\neg x_3 \lor x_1) \wedge (\neg x_3 \lor \neg x_4) \wedge (x_4 \lor x_5) \wedge (\neg x_5 \lor x_1)$
    • c) $(x_1 \lor x_2) \wedge (\neg x_2 \lor x_3) \wedge (\neg x_3 \lor x_1) \wedge (\neg x_3 \lor \neg x_4) \wedge (x_4 \lor x_5) \wedge (\neg x_5 \lor x_2)$
  6. Pomocí jednotkové propagace zjednodušte a rozhodněte o splnitelnosti formule:
    • a) $x_1 \wedge (\neg x_1 \lor x_2) \wedge (\neg x_1 \lor \neg x_3) \wedge (\neg x_2 \lor x_3 \lor x_4) \wedge (\neg x_4 \lor x_5 \lor \neg x_6)$
    • b) $x_1 \wedge (\neg x_1 \lor x_2) \wedge (\neg x_1 \lor \neg x_3) \wedge (\neg x_1 \lor x_3 \lor x_4) \wedge (x_3 \lor \neg x_4)$
  7. Pro testování splnitelnosti máte formule zjednodušit a případně popsat použitou úvahu/pravidlo obecně: ("ekvisplnitelnost")
    • a) $(x_1 \lor \neg x_2) \wedge (x_2 \lor x_3) \wedge (\neg x_3 \lor x_1)$
    • b) $(x_1 \lor \neg x_3) \wedge (x_1 \lor x_2 \lor \neg x_3)$
  8. Uvažme teorii $T=\{\neg q \to (\neg p \vee q), \neg p \to q, r \to q \}$. Které výroky jsou pravdivé / lživé / nezávislé / splnitelné / ekvivalentní v $T$?
    • $p,q,r,s$
    • $p \to \neg q, \neg q \to p, \neg q \to \neg p, \neg q \to q$
  9. Uvažme teorii $T=\{p_i \to p_{i+1} | i \in \mathbb{N}\}$ nad var($T$).
    • a) Které výroky ve tvaru $p_i \to p_{j} $ jsou důsledkem $T$?
    • b) Určete všechny modely teorie $T$.
  10. Uvažme teorii $T=\{p_i \to p_{i+1} \vee q_{i+1}, q_i \to p_{i+1} \vee q_{i+1}| i \in \mathbb{N}\}$ nad var($T$).
    • a) Které výroky ve tvaru $p_i \to p_{j} $ jsou důsledkem $T$?
    • b) Které výroky ve tvaru $p_i \to (p_{i+1} \vee q_{i+1})$ jsou důsledkem $T$?
    • c) Určete všechny modely teorie $T$.
  11. Pro formuli nad $n$ proměnnými a $k$ spojkami odhadněte
    • a) počet výskytů proměnných, označme $m$
    • b) počet podformulí
    • c) časovou složitost tabulkové metody, v závislosti na $n$, $m$ a $k$ (pro určení tautologie a/nebo splnitelnosti)
    • d) paměťovou složitost;
    • Pozn.: případně optimalizujte (výběr proměnných, výběr hodnot)

  12. DU2: Pro formuli $\neg(p \to \neg q) \to (q \vee \neg r) $ určete modely (nad $\{p,q,r\}$) a použitím pravidel převeďte do CNF a DNF. *CV3/DU2*
  13. Které všechny pravidla potřebujete, abyste mohli převést lib. formuli do CNF, resp. DNF? *CV3*
  14. (QBF, Kvantifikované Boolovské Formule) QBF dovolují pro výrokové proměnné kvantifikátory ve formuli, tj. $(\forall p)\phi$ (A) a $(\exists p) \phi$ (B) jsou formule pro libovolnou QBF $\phi$, s významem A, resp. B, je pravdivá, pokud $\phi$ je pravdivá pro obě hodnoty $p$, resp. pro aspoň jednu hodnotu $p$. (Splnitelnost definujeme analogicky.)
    • a) Navrhnout algoritmus a/nebo upravit tabulkovou metodu pro a.1) pravdivost a.2) splnitelnost
    • b) odhadnout složitost algoritmu, časovou i paměťovou
    • c) navrhnout převod na nekvantifikované formule VL, když c.1) máme $\top$ a $\bot$ (True a False); c.2) nemáme výrokové konstanty; c.3) a dokázat správnost převodu,
    • d) analyzovat složitost převodu; je polynomiální?

Cvičení 3

  1. Kolik neekvivalentních výroků lze sestavit z $n$ prvovýroků?
  2. Nechť $T$ je teorie $\{(p \land q) \to r \}$ nad ${\mathbb P} =\{ p,q,r,s\} $
    • a) Kolik má T modelů?
    • b)
  3. Nechť T je teorie

-konec VPL

Slovníček
(Řecká písmena: ...)