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:

• Peter: "Rok je kriv, Simon pa ne."
• Rok: "Če je kriv Peter, je kriv tudi Simon."
• Simon: "Jaz nisem kriv, toda vsaj eden od drugih dveh je kriv."

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?

• \(p\) … Peter je kriv
• \(r\) … Rok je kriv
• \(s\) … Simon je kriv

1. • \(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\) … smo v Butalah
• \(q\) … govorimo z Butalcem

• govorimo z domačinom: \(p \iff q\)
• sogovornikov odgovor: \((p \iff q) \iff q \sim p\)

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:

• Če mi je všeč Analiza, mi Algebra gotovo ni.
• Če v prejšnji povedi nisem lagal, potem to počnem zdaj in všeč mi je Algebra.

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

• \(p\) … všeč mu je Analiza
• \(q\) … všeč mu je Algebra
• \(r\) … prva izjava je resnična
• \(s\) … druga izjava je resnična

• \((p \Rightarrow \lnot q) \iff r\)
• \((r \Rightarrow \lnot s \land q) \iff s\)
• \(p \lor q\)

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

• \(\lnot \lnot p \sim p\)
• \(p\Rightarrow q \sim \lnot q\Rightarrow \lnot p \sim \lnot p\vee q\)
• \(p \land (q \lor r) \sim (p \land q) \lor (p \land r)\)
• \(p \lor (q \land r) \sim (p \lor q) \land (p \lor r)\)

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} \]