Дигитална логика
Задатак 1 Изразити формулу \(p \Rightarrow q\) само помоћу Шеферове функције \(\uparrow\).
\[ p \Rightarrow q \equiv \neg p \lor q \equiv \neg(p \land \neg q) \equiv p \uparrow \neg q \equiv p \uparrow (q \uparrow q). \]
Задатак 2 Остварити негацију, конјункцију и дисјункцију само помоћу NAND кола.
Означимо NAND коло са \(\uparrow\). Тада је \[ \neg A \equiv A \uparrow A, \qquad A \land B \equiv (A \uparrow B) \uparrow (A \uparrow B), \qquad A \lor B \equiv (A \uparrow A) \uparrow (B \uparrow B). \] Последња једнакост важи јер је \((A \uparrow A) \uparrow (B \uparrow B) = \neg(\neg A \land \neg B) \equiv A \lor B\) (Де Морганов закон). За негацију је потребно једно, за конјункцију два, а за дисјункцију три NAND кола.
Задатак 3 Одредити исказну формулу \(F\) коју реализује логичко коло на слици 1.
(а) Испитати да ли је \(F\) таутологија.
(б) Да ли је \(F\) записана у СДНФ, СКНФ, ДНФ или КНФ?
(в) Представити \(F\) у СДНФ и СКНФ, као и у једној ДНФ и једној КНФ.
Читајући коло од улаза ка излазу, горње AND коло даје \(\neg p \land q\), а доње \(p \land \neg r\), које NOT коло затим негира. Излазно OR коло их спаја: \[ F = (\neg p \land q) \lor \neg(p \land \neg r). \]
| \(p\) | \(q\) | \(r\) | \(\neg p \land q\) | \(p \land \neg r\) | \(\neg(p \land \neg r)\) | \(F\) |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 | 1 |
(а) У колони \(F\) има нула, па \(F\) није таутологија (на пример, за \(p = 1\), \(q = r = 0\)).
(б) \(F\) није ни у једној од ових форми. Није у СДНФ ни у СКНФ, јер у њима сваки члан садржи све три променљиве. Није у КНФ, јер су чланови спојени са \(\lor\), а не са \(\land\). Није ни у ДНФ, јер \(\neg(p \land \neg r)\) није конјункција литерала: негација стоји испред заграде.
(в) Свака од две врсте са \(F = 0\) даје по један дисјункт, па је СКНФ \[ F = (\neg p \lor q \lor r) \land (\neg p \lor \neg q \lor r). \] Ова два дисјункта разликују се само по \(q\), па се спајају у \(\neg p \lor r\). Свака од шест врста са \(F = 1\) даје по један конјункт, па је СДНФ \[ \begin{aligned} F = {} & (\neg p \land \neg q \land \neg r) \lor (\neg p \land \neg q \land r) \lor (\neg p \land q \land \neg r) \\ & \lor (\neg p \land q \land r) \lor (p \land \neg q \land r) \lor (p \land q \land r). \end{aligned} \] Прва четири члана дају \(\neg p\), а други, четврти, пети и шести (сви у којима је \(r = 1\)) дају \(r\). Тако је \(F \equiv \neg p \lor r\), формула која је истовремено и КНФ (један дисјункт) и ДНФ (два једночлана конјункта). Још једну ДНФ добијамо директно из \(F\) Де Моргановим законом: \(F \equiv (\neg p \land q) \lor \neg p \lor r\).
Провера у алату за исказне формуле: (¬p ∧ q) ∨ ¬(p ∧ ¬r)
Задатак 4 Одредити исказну формулу \(F\) коју реализује логичко коло на слици 2. Испитати да ли је \(F\) таутологија и представити је у једној ДНФ и једној КНФ.
Три AND кола дају \(a \land b \land \neg c\), \(\neg b \land c\) и \(\neg a \land b\), а излазно OR коло их спаја: \[ F = (a \land b \land \neg c) \lor (\neg b \land c) \lor (\neg a \land b). \] Формула није таутологија, јер је за \(a = b = c = 0\) сваки конјункт нетачан, па је \(F = 0\). Записана је као дисјункција конјункција литерала, па је то већ једна ДНФ.
| \(a\) | \(b\) | \(c\) | \(F\) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
Из три врсте са \(F = 0\) добијамо СКНФ, која је уједно и КНФ: \[ F = (a \lor b \lor c) \land (\neg a \lor b \lor c) \land (\neg a \lor \neg b \lor \neg c). \] Прва два дисјункта разликују се само по \(a\), па је краћа КНФ \(F = (b \lor c) \land (\neg a \lor \neg b \lor \neg c)\).
Провера у алату за исказне формуле: (a ∧ b ∧ ¬c) ∨ (¬b ∧ c) ∨ (¬a ∧ b)