Diskretne strukture (FiM) - vaje 28.10.2020

Normalne oblike

Naloga 1

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

1. \(11001110\)
2. \(01110101\)

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

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 \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\):
  1. ohranjanje 0: \(\Delta(0, 0, \dots, 0) \sim 0\)
  2. ohranjanje 1: \(\Delta(1, 1, \dots, 1) \sim 1\)
  3. afinost:
     • \(\Delta\) lahko izrazimo z naborom \(\lbrace \oplus, 1 \rbrace\)
     • vsak vhod bodisi vedno vpliva na rezultat ali pa nikoli ne vpliva
     4. monotonost: \(\Delta(p_1, p_2, \dots, 0, \dots, p_n) \le \Delta(p_1, p_2, \dots, 1, \dots, p_n)\)
     5. 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.

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 p \oplus 1\)
   • \(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 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.

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
     • \(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
2. • ohranjanje 0 VELJA, nabor ni poln
     • \(\land\) ohranja 0
     • \(0 \oplus 0 \sim 0\)
3. • ohranjanje 0 NE VELJA
     • \(\lnot 0 \not\sim 0\)
   • ohranjanje 1 NE VELJA
     • \(\lnot 1 \not\sim 1\)
   • afinost VELJA, nabor ni poln
     • \(\lnot p \sim p \oplus 1\)
     • \(p \oplus q \sim p \oplus q\)