Diskretne strukture (FiM)

« nazaj

Diskretne strukture (FiM) - vaje 22.10.2020

---

Enakovrednost in poenostavljanje izrazov

Naloga 1

Poenostavi izjavna izraza:

1. $\lnot (p \vee q \Rightarrow p) \vee \lnot p \wedge q$,
2. $\lnot(\lnot(p \Leftrightarrow \lnot r \Leftrightarrow (q \Leftrightarrow r)) \Leftrightarrow p)$.

---

1. \[\begin{aligned} \lnot (p \vee q \Rightarrow p) \vee \lnot p \wedge q &\sim \lnot (\lnot (p \lor q) \lor p) \lor (\lnot p \land q) \\ &\sim ((p \lor q) \land \lnot p) \lor (\lnot p \land q) \\ &\sim (\lnot p \land q) \lor (\lnot p \land q) \\ &\sim \lnot p \land q \end{aligned}\]
2. \[\begin{aligned} \lnot(\lnot(p \Leftrightarrow \lnot r \Leftrightarrow (q \Leftrightarrow r)) \Leftrightarrow p) &\sim p \Leftrightarrow \lnot r \Leftrightarrow q \Leftrightarrow r \Leftrightarrow p \\ &\sim p \iff p \iff q \iff r \iff \lnot r \\ &\sim 1 \iff q \iff 0 \\ &\sim \lnot q \end{aligned}\]

---

Naloga 2

Poenostavi izraz $A_k \equiv a \uparrow a \uparrow \ldots \uparrow a$ ($k$ veznikov) za vsak $k \geq 1$.

---

• $A_{k+1} \sim A_k \uparrow a$
• $A_0 \sim a$
• $A_1 \sim a \uparrow a \sim \lnot (a \land a) \sim \lnot a$
• $A_2 \sim \lnot a \uparrow a \sim \lnot (\lnot a \land a) \sim 1$
• $A_3 \sim 1 \uparrow a \sim \lnot (1 \land a) \sim \lnot a$
• $A_4 \sim 1$
• $A_k \sim \begin{cases} \lnot a & k \text{ lih} \newline 1 & k \text{ sod} \end{cases}$ ($k \ge 1$)

---

Naloga 3

S pomočjo izpeljevanja pokaži, da so naslednji pari izjavnih izrazov enakovredni:

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

---

1. \[\begin{aligned} (p\Rightarrow q)\wedge(p\Rightarrow r) &\sim (\lnot p \lor q) \land (\lnot p \lor r) \\ &\sim \lnot p \lor (q \land r) \\ &\sim p \Rightarrow q \land r \end{aligned}\]
2. \[\begin{aligned} (p\Rightarrow q)\lor(p\Rightarrow r) &\sim (\lnot p \lor q) \lor (\lnot p \lor r) \\ &\sim \lnot p \lor q \lor r \\ &\sim p \Rightarrow q \lor r \end{aligned}\]
3. \[\begin{aligned} (p\Rightarrow r)\wedge(q\Rightarrow r) &\sim (\lnot p \lor r) \land (\lnot q \lor r) \\ &\sim (\lnot p \land \lnot q) \lor r \\ &\sim \lnot (p \lor q) \lor r \\ &\sim p \lor q \Rightarrow r \end{aligned}\]
4. \[\begin{aligned} (p\Rightarrow r)\vee(q\Rightarrow r) &\sim (\lnot p \lor r) \lor (\lnot q \lor r) \\ &\sim \lnot p \lor \lnot q \lor r &&\sim \lnot (p \land q) \lor r \\ &\sim \lnot p \lor (q \Rightarrow r) &&\sim p \land q \Rightarrow r\\ &\sim p \Rightarrow (q \Rightarrow r) \end{aligned}\]

---

Normalne oblike

• konjunktivna normalna oblika (KNO): $(p \lor \lnot q \lor r) \land (\lnot p \lor \lnot q \lor \lnot r) \land \dots$
• disjunktivna normalna oblika (DNO): $(p \land \lnot q \land \lnot r) \lor (p \land q \land r) \lor \dots$

---

Naloga 4

S pomočjo izpeljevanja zapiši izraz v konjunktivni normalni obliki ali v disjunktivni normalni obliki.

1. $\lnot (p \vee q) \wedge (p \Rightarrow r)$
2. $(p \uparrow q) \downarrow r$
3. $((p \Rightarrow q) \vee \lnot r) \uparrow p$

---

1. \[\begin{aligned} \lnot (p \vee q) \wedge (p \Rightarrow r) &\sim (\lnot p \land \lnot q) \land (\lnot p \lor r) \\ &\sim \lnot p \land \lnot q \land (\lnot p \lor r) \\ &\sim \lnot p \land \lnot q \\ &\sim (\lnot p \land \lnot q \land r) \lor (\lnot p \land \lnot q \land \lnot r) \end{aligned}\]
   • disjunktivna normalna oblika
2. \[\begin{aligned} (p \uparrow q) \downarrow r &\sim \lnot (\lnot (p \land q) \lor r) \\ &\sim p \land q \land \lnot r \end{aligned}\]
   • disjunktivna normalna oblika
3. \[\begin{aligned} ((p \Rightarrow q) \vee \lnot r) \uparrow p &\sim \lnot ((\lnot p \lor q \lor \lnot r) \land p) \\ &\sim \lnot ((q \lor \lnot r) \land p) \\ &\sim \lnot (q \lor \lnot r) \lor \lnot p \\ &\sim (\lnot q \land r) \lor \lnot p \\ &\sim (p \land \lnot q \land r) \lor (\lnot p \land \lnot q \land r) \lor (\lnot p \land q \land r) \lor (\lnot p \land q \land \lnot r) \lor (\lnot p \land \lnot q \land \lnot r) \end{aligned}\]
   • disjunktivna normalna oblika

   \(\begin{aligned} (\lnot q \land r) \lor \lnot p &\sim (\lnot p \lor \lnot q) \land (\lnot p \lor r) \\ &\sim (\lnot p \lor \lnot q \lor r) \land (\lnot p \lor \lnot q \lor \lnot r) \land (\lnot p \lor q \lor r) \end{aligned}\)

   • konjunktivna normalna oblika

Ta stran je odprtokodna. Izboljšaj to stran.

Ta zapisek je dostopen tudi na HackMD.