Diskretne strukture (FiM)

« nazaj

Diskretne strukture (FiM) - vaje 15.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?
  1. Izjave:
    • Peter: $r \land \lnot s$
    • Rok: $p \Rightarrow s$
    • Simon: $\lnot s \land (p \lor r)$
    $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

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

  3. Če so vsi nedolžni, Peter in Simon lažeta.

  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 ne.

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 ste 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 moremo povedati.

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 \lor 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 \oplus q \end{aligned}\]
  2. \[\begin{aligned} \lnot (p \wedge q) \Rightarrow (p \wedge r) &\sim (p \wedge q) \lor (p \wedge r) \\ &\sim p \land (q \lor r) \end{aligned}\]
Ta stran je odprtokodna. Izboljšaj to stran.
Ta zapisek je dostopen tudi na HackMD.