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\)
    • \(Z = \lbrace \lnot, \land \rbrace\)
    • \(\lnot p \sim 1 \oplus p\)
    • \(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 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\)
    • 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
    • ohranjanje 0 VELJA, nabor ni poln
      • \(0 \land 0 \sim 0\)
      • \(0 \oplus 0 \sim 0\)
    • 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
Select a repo