Diskretne strukture (FiM)

« nazaj

Diskretne strukture (FiM) - vaje 16.10.2020

Enakovrednost in poenostavljanje izrazov

Naloga 1

Peter, Rok in Simon so bili obdolženi, da so razbili šipo. Ko so jih vprašali, kdo je kriv, so podali naslednje izjave:

  1. Določi izjavne izraze.
  2. Ali so lahko vse izjave resnične?
  3. Kdo je lagal, če so vsi nedolžni?
  4. Kdo je lagal, če krivi lažejo, nedolžni pa govorijo resnico?
    • $r \land \lnot s$
    • $p \Rightarrow s$
    • $\lnot s \land (p \lor r)$
  2. $p$ $r$ $s$ $r \land \lnot s$ $p \Rightarrow s$ $\lnot s \land (p \lor r)$
    0 0 0 0 1 0
    0 0 1 0 1 0
    0 1 0 1 1 1
    0 1 1 0 1 0
    1 0 0 0 0 1
    1 0 1 0 1 0
    1 1 0 1 0 1
    1 1 1 0 1 0

    Vse tri izjave so resnične natanko tedaj, ko je Rok kriv, Peter in Simon pa ne.

  3. Če so vsi nedolžni, sta se Peter in Simon zlagala.

  4. $p$ $r$ $s$ $(r \land \lnot s) \oplus p$ $(p \Rightarrow s) \oplus r$ $(\lnot s \land (p \lor r)) \oplus s$
    0 0 0 0 1 0
    0 0 1 0 1 1
    0 1 0 1 0 1
    0 1 1 0 0 1
    1 0 0 1 0 1
    1 0 1 1 1 1
    1 1 0 0 1 1
    1 1 1 1 0 1

    Če nedolžni govorijo resnico in krivi lažejo, potem sta kriva Peter in Simon, Rok pa je nedolžen.

Naloga 2

Butale in Tepanje sta sosedni vasi. Butalci vedno govorijo resnico, Tepanjci pa vedno lažejo. Med seboj se obiskujejo. Znajdeš se v eni od teh vasi, a ne veš, v kateri. Kako bi z enim samim odločitvenim vprašanjem prvemu mimoidočemu ugotovil, kje si? Poskusi vprašanje oblikovati v treh (ali dveh) besedah.

“Ali si domačin?”

$p$ $q$ $(p \iff q)$ $\iff q$
0 0 1 0
0 1 0 0
1 0 0 1
1 1 1 1

Naloga 3

Študent Svit je zvit, včasih govori po resnici in včasih laže. Ko ga povprašamo po predmetih v prvem letniku, pove:

Svitu je seveda všeč vsaj eden od obeh predmetov. Kateri?

$p$ $q$ $r$ $s$ $(p \Rightarrow \lnot q) \iff r$ $(r \Rightarrow \lnot s \land q) \iff s$ $p \lor q$
0 0         0
0 1 0 0 0    
0 1 0 1 0    
0 1 1 0 1 0  
0 1 1 1 1 0  
1 0 0 0 0    
1 0 0 1 0    
1 0 1 0 1 1 1
1 0 1 1 1 0  
1 1 0 0 1 0  
1 1 0 1 1 1 1
1 1 1 0 0    
1 1 1 1 0    

Svitu je zagotovo všeč Analiza, za Algebro pa ne vemo.

Naloga 4

Ali so naslednji pari izjavnih izrazov enakovredni?

  1. $p\Rightarrow q$ in $\lnot q\Rightarrow \lnot p$
  2. $p\Rightarrow q$ in $\lnot p\vee q$
  3. $(p \Rightarrow q) \wedge (\lnot p \Rightarrow r)$ in $(p \wedge q) \vee (\lnot p \wedge r)$
  4. $(p\Rightarrow q) \Rightarrow r$ in $p\Rightarrow (q \Rightarrow r)$ in $(p\Rightarrow q) \wedge (q \Rightarrow r)$
  1. in
  2. $p$ $q$ $p\Rightarrow q$ $\lnot q\Rightarrow \lnot p$ $\lnot p\vee q$
    0 0 1 1 1
    0 1 1 1 1
    1 0 0 0 0
    1 1 1 1 1

    $p\Rightarrow q \sim \lnot q\Rightarrow \lnot p \sim \lnot p\vee q$

  3. $p$ $q$ $r$ $(p \Rightarrow q) \wedge (\lnot p \Rightarrow r)$ $(p \wedge q) \vee (\lnot p \wedge r)$
    0 0 0 0 0
    0 0 1 1 1
    0 1 0 0 0
    0 1 1 1 1
    1 0 0 0 0
    1 0 1 0 0
    1 1 0 1 1
    1 1 1 1 1

    $(p \Rightarrow q) \wedge (\lnot p \Rightarrow r) \sim (p \wedge q) \vee (\lnot p \wedge r)$

  4. $p$ $q$ $r$ $(p\Rightarrow q) \Rightarrow r$ $p\Rightarrow (q \Rightarrow r)$ $(p\Rightarrow q) \wedge (q \Rightarrow r)$
    0 0 0 0 1 1
    0 0 1 1 1 1
    0 1 0 0 1 0
    0 1 1 1 1 1
    1 0 0 1 1 0
    1 0 1 1 1 0
    1 1 0 0 0 0
    1 1 1 1 1 1

    Izrazi $(p\Rightarrow q) \Rightarrow r$, $p\Rightarrow (q \Rightarrow r)$ in $(p\Rightarrow q) \wedge (q \Rightarrow r)$ so paroma neenakovredni.

Enakovrednosti izjavnih izrazov

Naloga 5

Poenostavi izjavna izraza:

  1. $(\lnot p \Rightarrow q) \wedge (p \Rightarrow \lnot q)$,
  2. $\lnot (p \wedge q) \Rightarrow (p \wedge r)$,
  1. \[\begin{aligned} (\lnot p \Rightarrow q) \wedge (p \Rightarrow \lnot q) &\sim (p \lor q) \land (\lnot p \lor \lnot q) \\ &\sim (p \land \lnot q) \lor (\lnot p \land q) \\ &\sim \lnot p \iff q \\ &\sim p \oplus q \end{aligned}\]
  2. \[\begin{aligned} \lnot (p \wedge q) \Rightarrow (p \wedge r) &\sim (p \land q) \lor (p \land r) \\ &\sim p \land (q \lor r) \end{aligned}\]
Ta stran je odprtokodna. Izboljšaj to stran.
Ta zapisek je dostopen tudi na HackMD.