Diskretne strukture (FiM)

« nazaj

Diskretne strukture (FiM) - vaje 29.10.2020

---

Normalne oblike

Naloga 1

Poišči izjavni izraz, ki ima v resničnostni tabeli vrednosti:

1. $11001110$
2. $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

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 \lnot (\lnot p \lor r) \\ &\sim \lnot q \lor (p \land \lnot r) \\ &\sim q \Rightarrow p \land \lnot r \end{aligned}\]
2. \[\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 \land q) \lor r \end{aligned}\]

---

Polni nabori

• Nabor izjavnih veznikov je poln, če lahko z njimi izrazimo poljuben izjavni izraz.
• Primeri polnih naborov: $\lbrace \lnot, \land, \lor \rbrace$, $\lbrace \lnot, \land \rbrace$, $\lbrace \lnot, \lor \rbrace$
• Nabor $N$ je poln, če lahko vsak veznik znanega polnega nabora $Z$ izrazimo samo z vezniki nabora $N$.
  • Primer: $N = \lbrace \uparrow \rbrace$, $Z = \lbrace \lnot, \lor \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 sledečih lastnosti velja za vse veznike $\Delta \in N$:
  1. ohranjanje 0: $\Delta(0, 0, \dots, 0) \sim 0$
     • $\land, \lor$ ohranjata 0, $\lnot$ ne ohranja 0
  2. ohranjanje 1: $\Delta(1, 1, \dots, 1) \sim 1$
     • $\land, \lor$ ohranjata 1, $\lnot$ ne ohranja 1
  3. afinost:
     • veznik lahko izrazimo z naborom $\lbrace \oplus, 1 \rbrace$
     • vsak vhod bodisi vedno vpliva na izhod, bodisi nikoli ne vpliva
     • $\lnot p \sim 1 \oplus p$ je afina
     • $0 \land 1 \not\sim 1 \land 1$, $0 \land 0 \sim 1 \land 0$, $\land$ ni afin veznik
     • $\lor$ ni afin veznik
  4. monotonost: $\Delta(p_1, p_2, \dots, 0, \dots, p_n) \le \Delta(p_1, p_2, \dots, 1, \dots, p_n)$
     • $\land, \lor$ sta monotona, $\lnot$ ni monotona
  5. sebi dualnost: $\lnot \Delta(p_1, p_2, \dots, p_n) \sim \Delta(\lnot p_1, \lnot p_2, \dots, \lnot p_n)$
     • $\land, \lor$ nista sebi dualna, $\lnot$ je sebi dualna

---

Naloga 2

Pokaži, da so naslednji nabori izjavnih povezav polni.

1. $\lbrace \land, \oplus, 1 \rbrace$
2. $\lbrace \Rightarrow, \lnot \rbrace$
3. $\lbrace \Rightarrow, 0 \rbrace$

---

1. • $Z = \lbrace \lnot, \land \rbrace$
   • $\lnot p \sim 1 \oplus p$
   • $p \land q \sim p \land q$
2. • $Z = \lbrace \lnot, \lor \rbrace$
   • $\lnot p \sim \lnot p$
   • $p \lor q \sim \lnot p \Rightarrow q$
3. • $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 1 \oplus p \oplus 0 \sim \Delta(1, p, 0)$
• $p \land q \sim p \land q$

---

Naloga 4

Pokaži, da naslednji nabori izjavnih veznikov niso polni.

1. $\lbrace \land, \Leftrightarrow \rbrace$
2. $\lbrace \land, \oplus \rbrace$
3. $\lbrace \lnot, \oplus \rbrace$

---

1. • 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
     • $0 \sim 0 \land 1 \not\sim 1 \land 1 \sim 1$, $0 \sim 0 \land 0 \sim 1 \land 0 \sim 0$ ni afina
     • $p \iff q \sim p \oplus q \oplus 1$ je afina
   • monotonost NE VELJA
     • $\land$ je monotona
     • $0 \iff 0 \sim 1 > 0 \sim 0 \iff 1$
   • sebi dualnost NE VELJA
     • $\land$ ni sebi dualna
     • $\lnot (p \iff q) \not\sim (\lnot p \iff \lnot q)$ ni sebi dualna
2. • ohranjanje 0 VELJA, nabor ni poln
     • $0 \land 0 \sim 0$
     • $0 \oplus 0 \sim 0$
3. • afinost VELJA, nabor ni poln
     • $\lnot p \sim 1 \oplus p$
     • $p \oplus q \sim p \oplus q$

---

Naloga 5

Ali izjavni veznik $\Lambda(p,q,r) \equiv p \Rightarrow (q \lor r)$ sestavlja poln nabor?

---

• $\Lambda(0, 0, 0) \sim 0 \Rightarrow (0 \lor 0) \sim 1$
• $\Lambda(1, 1, 1) \sim 1 \Rightarrow (1 \lor 1) \sim 1$, nabor $\lbrace \Lambda \rbrace$ ni poln

Ta stran je odprtokodna. Izboljšaj to stran.

Ta zapisek je dostopen tudi na HackMD.