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