« nazaj
Diskretne strukture (FiM) - vaje 28.10.2020
Normalne oblike
Naloga 1
Poišči izjavni izraz, ki ima v resničnostni tabeli vrednosti:
- $11001110$
- $01110101$
| $p$ |
$q$ |
$r$ |
1. |
2. |
| 0 |
0 |
0 |
1 |
0 |
| 0 |
0 |
1 |
1 |
1 |
| 0 |
1 |
0 |
0 |
1 |
| 0 |
1 |
1 |
0 |
1 |
| 1 |
0 |
0 |
1 |
0 |
| 1 |
0 |
1 |
1 |
1 |
| 1 |
1 |
0 |
1 |
0 |
| 1 |
1 |
1 |
0 |
1 |
-
\[\begin{aligned}
(p \lor \lnot q \lor r) \land (p \lor \lnot q \lor \lnot r) \land (\lnot p \lor \lnot q \lor \lnot r)
&\sim \lnot q \lor ((p \lor r) \land (p \lor \lnot r) \land (\lnot p \lor \lnot r)) \\
&\sim \lnot q \lor (p \land \lnot r) \\
&\sim q \Rightarrow p \land \lnot r
\end{aligned}\]
-
\[\begin{aligned}
(p \lor q \lor r) \land (\lnot p \lor q \lor r) \land (\lnot p \lor \lnot q \lor r)
&\sim ((p \lor q) \land (\lnot p \lor q) \land (\lnot p \lor \lnot q)) \lor r \\
&\sim \lnot (p \lor \lnot q) \lor r \\
&\sim (\lnot p \land q) \lor r
\end{aligned}\]
Polni nabori
- Nabor izjavnih veznikov je poln, če lahko z njim izrazimo poljuben izjavni izraz.
- Primeri polnih naborov: $\lbrace \land, \lor, \lnot \rbrace$, $\lbrace \land, \lnot \rbrace$, $\lbrace \lor, \lnot \rbrace$
- Nabor $N$ je poln, če lahko vsak veznik znanega polnega nabora $Z$ izrazimo samo z vezniki nabora $N$.
- Primer: $N = \lbrace \uparrow \rbrace$
- Vzamemo npr. $Z = \lbrace \lor, \lnot \rbrace$
- $\lnot p \sim \lnot (p \land p) \sim p \uparrow p$
- $p \lor q \sim \lnot (\lnot p \land \lnot q) \sim \lnot p \uparrow \lnot q \sim (p \uparrow p) \uparrow (q \uparrow q)$
- Nabor $N$ ni poln, če vsaj ena od naslednjih lastnosti velja za vse veznike $\Delta \in N$:
- ohranjanje 0: $\Delta(0, 0, \dots, 0) \sim 0$
- ohranjanje 1: $\Delta(1, 1, \dots, 1) \sim 1$
- afinost:
- $\Delta$ lahko izrazimo z naborom $\lbrace \oplus, 1 \rbrace$
- vsak vhod bodisi vedno vpliva na rezultat ali pa nikoli ne vpliva
- monotonost: $\Delta(p_1, p_2, \dots, 0, \dots, p_n) \le \Delta(p_1, p_2, \dots, 1, \dots, p_n)$
- sebi dualnost: $\lnot \Delta(p_1, p_2, \dots, p_n) \sim \Delta(\lnot p_1, \lnot p_2, \dots, \lnot p_n)$
Naloga 2
Pokaži, da so naslednji nabori izjavnih povezav polni.
- $\lbrace \land, \oplus, 1 \rbrace$
- $\lbrace \Rightarrow, \lnot \rbrace$
- $\lbrace \Rightarrow, 0 \rbrace$
-
- $Z = \lbrace \lnot, \land \rbrace$
- $\lnot p \sim p \oplus 1$
- $p \land q \sim p \land q$
-
- $Z = \lbrace \lnot, \lor \rbrace$
- $\lnot p \sim \lnot p$
- $p \lor q \sim \lnot p \Rightarrow q$
-
- $Z = \lbrace \lnot, \lor \rbrace$
- $\lnot p \sim p \Rightarrow 0$
- $p \lor q \sim (p \Rightarrow 0) \Rightarrow q$
Naloga 3
Pokaži, da je nabor $\lbrace \land, 0, 1, \Delta \rbrace$ poln, pri čemer je $\Delta(p,q,r) \equiv p \oplus q \oplus r$.
- $Z = \lbrace \lnot, \land \rbrace$
- $\lnot p \sim p \oplus 1 \oplus 0 \sim \Delta(p, 1, 0)$
- $p \land q \sim q \land p$
Naloga 4
Pokaži, da naslednji nabori izjavnih veznikov niso polni.
- $\lbrace \land, \Leftrightarrow \rbrace$
- $\lbrace \land, \oplus \rbrace$
- $\lbrace \lnot, \oplus \rbrace$
-
- ohranjanje 0 NE VELJA
- $0 \land 0 \sim 0$
- $0 \iff 0 \not\sim 0$
- ohranjanje 1 VELJA, nabor ni poln
- $1 \land 1 \sim 1$
- $1 \iff 1 \sim 1$
- afinost NE VELJA
- $1 \land 0 \sim 0 \not\sim 1 \land 1 \sim 1$, $0 \land 0 \sim 0 \sim 0 \land 1 \sim 0$, veznik ni afin
- $p \iff q \sim p \oplus q \oplus 1$, veznik je afin
- monotonost NE VELJA
- $p \land q \sim 1$, samo če $p \sim q \sim 1$, veznik je monoton
- $0 \iff 0 \sim 1 > 0 \iff 1 \sim 0$, veznik ni monoton
- sebi dualnost NE VELJA
- $\lnot (p \land q) \not\sim (\lnot p \land \lnot q)$, veznik ni sebi dualen
- $\lnot (p \iff q) \not\sim (\lnot p \iff \lnot q)$, veznik ni sebi dualen
-
- ohranjanje 0 VELJA, nabor ni poln
- $\land$ ohranja 0
- $0 \oplus 0 \sim 0$
-
- ohranjanje 0 NE VELJA
- ohranjanje 1 NE VELJA
- afinost VELJA, nabor ni poln
- $\lnot p \sim p \oplus 1$
- $p \oplus q \sim p \oplus q$