Исказни рачун
Задатак 1 Које од следећих реченица су искази? За исказе одредити истинитосну вредност.
(а) „Број 7 је прост.“
(б) „Затвори прозор!“
(в) „\(x > 3\).“
(г) „Ако је \(2 > 3\), онда је Месец од сира.“
(а) Исказ, тачан.
(б) Није исказ — заповест.
(в) Није исказ — истинитост зависи од вредности \(x\).
(г) Исказ, и то тачан: импликација са нетачном претпоставком (\(2 > 3\)) увек има вредност 1.
Задатак 2 Одредити вредност формуле \((p \Rightarrow q) \Leftrightarrow (\neg q \lor r)\) при валуацији \(v(p) = 1\), \(v(q) = 0\), \(v(r) = 0\).
\(v(p \Rightarrow q) = 1 \Rightarrow 0 = 0\) и \(v(\neg q \lor r) = 1 \lor 0 = 1\), па је вредност формуле \(0 \Leftrightarrow 1 = 0\).
Провера у алату за исказне формуле: (p ⇒ q) ⇔ (¬q ∨ r)
Задатак 3 Направити таблицу истинитости формуле \(\neg(p \land q) \Rightarrow (\neg p \lor q)\) и утврдити да ли је таутологија, контрадикција или контингенција.
| \(p\) | \(q\) | \(p \land q\) | \(\neg(p \land q)\) | \(\neg p \lor q\) | \(F\) |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 | 1 |
Формула је нетачна при валуацији \(v(p) = 1,\ v(q) = 0\), а тачна при осталим — контингенција.
Провера у алату за исказне формуле: ¬(p ∧ q) ⇒ (¬p ∨ q)
Задатак 4 Трансформацијама доказати да је \(p \land (\neg p \lor q) \equiv p \land q\).
\[ p \land (\neg p \lor q) \equiv (p \land \neg p) \lor (p \land q) \equiv 0 \lor (p \land q) \equiv p \land q \] (дистрибутивност, закон непротивречности, закон за 0).
Провера у алату за исказне формуле: (p ∧ (¬p ∨ q)) ⇔ (p ∧ q)
Задатак 5 Свођењем на противречност доказати да је формула \(\big(p \land (p \Rightarrow q)\big) \Rightarrow q\) таутологија.
Ако би формула била нетачна при некој валуацији \(v\), морало би бити \(v(p \land (p \Rightarrow q)) = 1\) и \(v(q) = 0\). Тада је \(v(p) = 1\) и \(v(p \Rightarrow q) = 1\), али \(v(p \Rightarrow q) = 1 \Rightarrow 0 = 0\) — противречност.
Провера у алату за исказне формуле: (p ∧ (p ⇒ q)) ⇒ q
Задатак 6 Да ли је формула \(q\) семантичка последица скупа \(\{p \lor q,\ \neg p\}\)? Образложити.
Јесте (дисјунктивни силогизам). Ако су обе премисе тачне, из \(v(\neg p) = 1\) следи \(v(p) = 0\), па из \(v(p \lor q) = 1\) мора бити \(v(q) = 1\).
Провера у алату за исказне формуле: ((p ∨ q) ∧ ¬p) ⇒ q
Задатак 7 Показати да \(p \Rightarrow q,\ q \models p\) не важи.
При валуацији \(v(p) = 0,\ v(q) = 1\) обе премисе \(p \Rightarrow q\) и \(q\) су тачне, а закључак \(p\) нетачан (грешка „потврђивање последице“).
Провера у алату за исказне формуле: ((p ⇒ q) ∧ q) ⇒ p
Задатак 8 Свести формулу \((p \Rightarrow q) \land \neg(q \land r)\) на КНФ и на ДНФ.
Уклањањем импликације и применом Де Моргановог закона добијамо КНФ: \[ (p \Rightarrow q) \land \neg(q \land r) \equiv (\neg p \lor q) \land (\neg q \lor \neg r). \] Дистрибутивношћу добијамо ДНФ (конјункт \(q \land \neg q \equiv 0\) изостављамо): \[ (\neg p \land \neg q) \lor (\neg p \land \neg r) \lor (q \land \neg r). \]
Провера у алату за исказне формуле: (p ⇒ q) ∧ ¬(q ∧ r)
Задатак 9 Колико има Булових функција од три променљиве?
\(2^{2^3} = 2^8 = 256\).
Задатак 10 Булова функција \(f(p, q, r)\) има вредност 1 тачно када су бар два аргумента једнака 1 (функција већине). Одредити њену СДНФ и СКНФ.
Функција има вредност 1 у редовима 011, 101, 110 и 111, а вредност 0 у редовима 000, 001, 010 и 100. Зато је СДНФ \[ (\neg p \land q \land r) \lor (p \land \neg q \land r) \lor (p \land q \land \neg r) \lor (p \land q \land r), \] а СКНФ \[ (p \lor q \lor r) \land (p \lor q \lor \neg r) \land (p \lor \neg q \lor r) \land (\neg p \lor q \lor r). \] Функција се може записати и краће: \((p \land q) \lor (p \land r) \lor (q \land r)\).
Провера у алату за исказне формуле: T(3,5,6,7)
Задатак 11 Помоћу Карноове мапе одредити минималну ДНФ функције \(f(p, q, r, s)\) која има вредност 1 у врстама 0, 1, 2, 5, 8, 9 и 10 таблице.
Јединице су у пољима \(0, 1, 2, 5, 8, 9, 10\). Група од четири поља \(0, 1, 8, 9\) (врсте \(pq = 00\) и \(10\), колоне \(rs = 00\) и \(01\)) даје \(\neg q \land \neg r\); група од четири угла \(0, 2, 8, 10\) даје \(\neg q \land \neg s\); остаје поље \(5\), које са пољем \(1\) чини групу \(\neg p \land \neg r \land s\). Минимална ДНФ је \[ f = (\neg q \land \neg r) \lor (\neg q \land \neg s) \lor (\neg p \land \neg r \land s). \]
Провера у алату за исказне формуле: T(0,1,2,5,8,9,10)
Задатак 12 У Буловој алгебри делилаца броја 30 из примера 3.23 израчунати \(G = \overline{10 \cdot 15} + 3\). Показати затим да делиоци броја 12 са истим операцијама (НЗС, НЗД, \(\overline{a} = 12/a\)) не чине Булову алгебру.
\(10 \cdot 15 = \text{НЗД}(10, 15) = 5\), \(\overline{5} = 30/5 = 6\), па је \(G = 6 + 3 = \text{НЗС}(6, 3) = 6\). За делиоце броја \(12 = 2^2 \cdot 3\) не важи аксиома комплемента: \(\overline{2} = 6\), али \(2 \cdot \overline{2} = \text{НЗД}(2, 6) = 2 \neq 1\) (и \(2 + \overline{2} = 6 \neq 12\)). Проблем је што се прост чинилац 2 у броју 12 понавља.
Задатак 13 Из аксиома Булове алгебре извести законе \(a + 1 = 1\) и \(a + ab = a\). Шта ови закони значе у исказном, а шта у скуповном рачуну? Који су им дуални закони?
Користимо аксиоме неутралног елемента, комплемента и дистрибутивности: \[ a + 1 = (a + 1) \cdot 1 = (a + 1)(a + \overline{a}) = a + 1 \cdot \overline{a} = a + \overline{a} = 1. \] Помоћу тог закона је \[ a + ab = a \cdot 1 + a b = a(1 + b) = a(b + 1) = a \cdot 1 = a. \] У исказном рачуну то су закони \(p \lor 1 \equiv 1\) и \(p \lor (p \land q) \equiv p\) (апсорпција), а у скуповном \(A \cup U = U\) и \(A \cup (A \cap B) = A\). Дуални закони су \(a \cdot 0 = 0\) и \(a(a + b) = a\).
Следећи задаци су сложенији и повезују целу причу: реченице преводимо у исказне формуле, таблицом проверавамо непротивречност и закључке, а формуле записујемо у нормалним формама и минимизујемо Карноовим мапама. Задатак са логичким колом решите после поглавља о дигиталној логици.
Задатак 14 Аца, Браца, Пера и Жика су студенти ФОН-а и сваки од њих је или информатичар или менаџер. О њима су дати следећи искази:
- \(I\): Ако је Аца менаџер, онда су Браца и Пера или обојица информатичари или обојица менаџери.
- \(II\): Ако је Браца менаџер, онда Пера и Жика нису обојица менаџери.
- \(III\): Пера је информатичар ако и само ако је бар један од Жике и Аце информатичар.
- \(IV\): Тачно један од Жике и Браце је информатичар.
(а) Да ли су ови искази непротивречни? Да ли међу њима има логички еквивалентних?
(б) За кога од студената се са сигурношћу може утврдити да ли је информатичар или менаџер?
(в) За формулу \(F\) која одговара конјункцији свих исказа одредити СДНФ, минималну ДНФ и једну КНФ, а за формулу која одговара исказу \(I\) одредити СКНФ, минималну КНФ и једну ДНФ.
Уведимо исказна слова: \(a\) — „Аца је информатичар“, \(b\) — „Браца је информатичар“, \(c\) — „Пера је информатичар“, \(d\) — „Жика је информатичар“. Менаџер је онда онај за кога је одговарајуће слово нетачно, па искази гласе: \[ I\colon \neg a \Rightarrow (b \Leftrightarrow c), \quad II\colon \neg b \Rightarrow (c \lor d), \quad III\colon c \Leftrightarrow (a \lor d), \quad IV\colon b \veebar d, \] а \(F = I \land II \land III \land IV\). У исказу \(II\) смо „Пера и Жика нису обојица менаџери“, тј. \(\neg(\neg c \land \neg d)\), по Де Моргановом закону записали као \(c \lor d\).
| \(a\) | \(b\) | \(c\) | \(d\) | \(I\) | \(II\) | \(III\) | \(IV\) | \(F\) |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
(а) Искази су непротивречни, јер постоји валуација при којој су сви тачни (\(F\) није контрадикција). Међу колонама \(I\)–\(IV\) нема две једнаке, па међу исказима нема логички еквивалентних.
(б) \(F\) је тачна у две валуације, \(1011\) и \(1110\). У обе је \(a = c = 1\), па су Аца и Пера сигурно информатичари. За Брацу и Жику се то не може утврдити — зна се само да је тачно један од њих информатичар.
(в) За \(F\): СДНФ је \((a \land \neg b \land c \land d) \lor (a \land b \land c \land \neg d)\) и то је уједно минимална ДНФ (две јединице мапе нису суседне). Једна КНФ је \(a \land c \land (b \lor d) \land (\neg b \lor \neg d)\); последња два дисјункта заједно кажу \(b \veebar d\).
За \(I\): формула је нетачна у валуацијама \(0010\), \(0011\), \(0100\) и \(0101\), па је СКНФ \[ (a \lor b \lor \neg c \lor d) \land (a \lor b \lor \neg c \lor \neg d) \land (a \lor \neg b \lor c \lor d) \land (a \lor \neg b \lor c \lor \neg d). \] Нуле се групишу у два пара у којима се мења само \(d\), па је минимална КНФ \((a \lor b \lor \neg c) \land (a \lor \neg b \lor c)\). Једна ДНФ је \(a \lor (b \land c) \lor (\neg b \land \neg c)\), јер је \(\neg a \Rightarrow (b \Leftrightarrow c) \equiv a \lor (b \Leftrightarrow c)\).
Провера у алату за исказне формуле: (¬a ⇒ (b ⇔ c)) ∧ (¬b ⇒ (c ∨ d)) ∧ (c ⇔ (a ∨ d)) ∧ (b ⊻ d), ¬a ⇒ (b ⇔ c)
Задатак 15 Одредити исказну формулу \(F\) коју реализује логичко коло на слици 1. Упоредити је са формулом из задатка 14.
Читајући коло од улаза ка излазу добијамо \[ F = \big(a \lor \neg(b \veebar c)\big) \land \big(\neg(c \veebar (a \lor d))\big) \land (b \lor c \lor d) \land (b \veebar d). \] Како је \(\neg(p \veebar q) \equiv p \Leftrightarrow q\), ово је \[ F = \big(a \lor (b \Leftrightarrow c)\big) \land \big(c \Leftrightarrow (a \lor d)\big) \land (b \lor c \lor d) \land (b \veebar d), \] што је иста формула као у задатку 14: \(a \lor (b \Leftrightarrow c) \equiv \neg a \Rightarrow (b \Leftrightarrow c)\) и \(b \lor c \lor d \equiv \neg b \Rightarrow (c \lor d)\). Коло, дакле, на излазу \(F\) даје 1 тачно у две валуације, \(1011\) и \(1110\).
Провера у алату за исказне формуле: (a ∨ ¬(b ⊻ c)) ∧ ¬(c ⊻ (a ∨ d)) ∧ (b ∨ c ∨ d) ∧ (b ⊻ d)
Задатак 16 Декан бира продекане међу наставницима Ацом, Бошком, Цецом и Душком. О томе су дати следећи искази:
- \(I\): Ако декан изабере Ацу, изабраће и Бошка.
- \(II\): Декан ће изабрати Бошка или Цецу ако и само ако не изабере Ацу.
- \(III\): Декан ће изабрати Бошка или ће од Душка и Аце изабрати тачно једног.
- \(IV\): Ако декан изабере Цецу и Душка, изабраће и Бошка.
(а) Да ли су ови искази непротивречни? Да ли међу њима има логички еквивалентних?
(б) За кога од наставника се са сигурношћу може утврдити да ли ће бити изабран? Колико ће продекана бити изабрано?
(в) За формулу \(F\) која одговара конјункцији свих исказа одредити СДНФ, минималну ДНФ и једну КНФ, а за формулу која одговара исказу \(IV\) одредити СКНФ, минималну КНФ и једну ДНФ.
Нека је \(a\) — „декан ће изабрати Ацу“, и слично \(b\) за Бошка, \(c\) за Цецу и \(d\) за Душка. Тада је \[ I\colon a \Rightarrow b, \quad II\colon (b \lor c) \Leftrightarrow \neg a, \quad III\colon b \lor (d \veebar a), \quad IV\colon (c \land d) \Rightarrow b, \] и \(F = I \land II \land III \land IV\).
| \(a\) | \(b\) | \(c\) | \(d\) | \(I\) | \(II\) | \(III\) | \(IV\) | \(F\) |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 |
(а) Искази су непротивречни (\(F\) је тачна у четири валуације), а међу колонама \(I\)–\(IV\) нема једнаких, па нема ни логички еквивалентних исказа.
(б) У свим валуацијама у којима је \(F\) тачна је \(a = 0\) и \(b = 1\): Бошко ће сигурно бити изабран, а Аца сигурно неће. За Цецу и Душка се не може утврдити, па ће бити изабрано најмање један, а највише три продекана.
(в) За \(F\): СДНФ је \[ (\neg a \land b \land \neg c \land \neg d) \lor (\neg a \land b \land \neg c \land d) \lor (\neg a \land b \land c \land \neg d) \lor (\neg a \land b \land c \land d), \] а четири јединице чине једну групу, па је минимална ДНФ \(\neg a \land b\), што је уједно и КНФ.
За \(IV\): формула је нетачна само када је \(c = d = 1\) и \(b = 0\), тј. у валуацијама \(0011\) и \(1011\), па је СКНФ \((a \lor b \lor \neg c \lor \neg d) \land (\neg a \lor b \lor \neg c \lor \neg d)\). Минимална КНФ је \(b \lor \neg c \lor \neg d\), што је уједно и ДНФ.
Провера у алату за исказне формуле: (a ⇒ b) ∧ ((b ∨ c) ⇔ ¬a) ∧ (b ∨ (d ⊻ a)) ∧ ((c ∧ d) ⇒ b), (c ∧ d) ⇒ b
Задатак 17 Дата је скуповна формула \[ \big((A \cup B) \setminus C\big) \cap D \subseteq (A \triangle C) \cap (B \triangle D). \]
(а) Записати је као исказну формулу \(F\).
(б) Да ли скуповна формула важи за све скупове \(A\), \(B\), \(C\) и \(D\)?
(в) За формулу \(F\) одредити СКНФ, минималну КНФ и једну ДНФ, а за формулу која одговара левој страни инклузије одредити СДНФ, минималну ДНФ и једну КНФ.
(а) За произвољан елемент \(x\) уведимо \(a\) — „\(x \in A\)“, и слично \(b\), \(c\), \(d\) за \(B\), \(C\), \(D\). Разлици одговара \(p \land \neg q\), симетричној разлици \(p \veebar q\), а инклузији импликација, па је \[ F\colon \underbrace{(a \lor b) \land \neg c \land d}_{L} \Rightarrow \underbrace{(a \veebar c) \land (b \veebar d)}_{D}. \]
| \(a\) | \(b\) | \(c\) | \(d\) | \(L\) | \(D\) | \(F\) |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 1 |
(б) Не важи увек: \(F\) није таутологија. Нуле у валуацијама \(0101\) и \(1101\) говоре да проблем праве елементи који су у \(B\) и \(D\), а нису у \(C\). На пример, за \(A = C = \emptyset\) и \(B = D = \{1\}\) лева страна је \(\{1\}\), а десна \(\emptyset\).
(в) За \(F\): СКНФ је \((a \lor \neg b \lor c \lor \neg d) \land (\neg a \lor \neg b \lor c \lor \neg d)\), а пошто се две нуле разликују само у \(a\), минимална КНФ је \(\neg b \lor c \lor \neg d\), што је уједно и ДНФ.
За \(L\): формула је тачна у валуацијама \(0101\), \(1001\) и \(1101\), па је СДНФ \[ (\neg a \land b \land \neg c \land d) \lor (a \land \neg b \land \neg c \land d) \lor (a \land b \land \neg c \land d), \] минимална ДНФ је \((b \land \neg c \land d) \lor (a \land \neg c \land d)\), а једна КНФ \((a \lor b) \land \neg c \land d\) — то је сама формула \(L\).
Провера у алату за исказне формуле: ((a ∨ b) ∧ ¬c ∧ d) ⇒ ((a ⊻ c) ∧ (b ⊻ d)), (a ∨ b) ∧ ¬c ∧ d
Задатак 18 За формулу дату у СКНФ \[ F = (a \lor \neg b \lor \neg c \lor d) \land (a \lor \neg b \lor \neg c \lor \neg d) \land (\neg a \lor b \lor \neg c \lor d) \land (\neg a \lor b \lor \neg c \lor \neg d) \] одредити минималну КНФ и једну ДНФ.
Дисјункти се групишу у два пара који се разликују само у \(d\), па је минимална КНФ \[ (a \lor \neg b \lor \neg c) \land (\neg a \lor b \lor \neg c). \] Извлачењем заједничког \(\neg c\) добијамо \(\neg c \lor \big((a \lor \neg b) \land (\neg a \lor b)\big) \equiv \neg c \lor (a \Leftrightarrow b)\), што даје ДНФ \((a \land b) \lor (\neg a \land \neg b) \lor \neg c\).
Провера у алату за исказне формуле: (a ∨ ¬b ∨ ¬c ∨ d) ∧ (a ∨ ¬b ∨ ¬c ∨ ¬d) ∧ (¬a ∨ b ∨ ¬c ∨ d) ∧ (¬a ∨ b ∨ ¬c ∨ ¬d)
Задатак 19 За формулу дату у СДНФ \[ F = (\neg a \land \neg b \land \neg c) \lor (\neg a \land \neg b \land c) \lor (\neg a \land b \land \neg c) \lor (\neg a \land b \land c) \lor (a \land \neg b \land c) \lor (a \land b \land c) \] одредити минималну ДНФ и једну КНФ.
СДНФ садржи шест од осам могућих конјуната; недостају \(a \land \neg b \land \neg c\) и \(a \land b \land \neg c\), па је \(F\) нетачна тачно када је \(a = 1\) и \(c = 0\). Зато је \(F \equiv \neg(a \land \neg c) \equiv \neg a \lor c\). То је минимална ДНФ, а уједно и КНФ (један дисјункт).
Провера у алату за исказне формуле: (¬a ∧ ¬b ∧ ¬c) ∨ (¬a ∧ ¬b ∧ c) ∨ (¬a ∧ b ∧ ¬c) ∨ (¬a ∧ b ∧ c) ∨ (a ∧ ¬b ∧ c) ∨ (a ∧ b ∧ c)
Задатак 20 Да ли је исправно закључивање:
- Ако је Милан добио добру оцену, онда није грешио или су били лаки задаци и знао је све формуле.
- Милан је добио добру оцену.
- Било је тешких задатака.
- Дакле, Милан није грешио.
Задатак решити на три начина: таблицом истинитости, дискусијом по слову и свођењем на противречност.
Означимо исказе: \(p\) — „Милан је добио добру оцену“, \(q\) — „Милан је грешио“, \(r\) — „били су лаки задаци“ и \(s\) — „Милан је знао све формуле“. Претпоставке су \[ a = p \Rightarrow \neg q \lor (r \land s), \qquad b = p, \qquad c = \neg r, \] а закључак је \(\neg q\). Закључивање је исправно ако је формула \[ d = a \land b \land c \Rightarrow \neg q = \Big(\big(p \Rightarrow \neg q \lor (r \land s)\big) \land p \land \neg r\Big) \Rightarrow \neg q \] таутологија.
I начин (таблица истинитости).
| \(p\) | \(q\) | \(r\) | \(s\) | \(\neg q \lor (r \land s)\) | \(a\) | \(a \land p \land \neg r\) | \(d\) |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
У последњој колони су све јединице, па је \(d\) таутологија.
II начин (дискусија по слову). Редом разматрамо случајеве када је нека променљива једнака 0, односно 1, почев од оне која се најчешће јавља. У формули \(d\) слова \(p\), \(q\) и \(r\) јављају се по два пута, а \(s\) једном. Почнимо од \(q\).
1° \(q = 0\): закључак је \(\neg 0 = 1\), а импликација са тачним закључком је тачна, \(d = 1\).
2° \(q = 1\): тада је \(\neg q = 0\), па \(d = \big((p \Rightarrow r \land s) \land p \land \neg r\big) \Rightarrow 0 = \neg\big((p \Rightarrow r \land s) \land p \land \neg r\big)\). Настављамо по слову \(p\):
- 2°а) \(p = 0\): \(d = \neg\big((0 \Rightarrow r \land s) \land 0 \land \neg r\big) = \neg 0 = 1\);
- 2°б) \(p = 1\): \(d = \neg\big((1 \Rightarrow r \land s) \land \neg r\big) = \neg(r \land s \land \neg r) = \neg 0 = 1\).
У свим случајевима је \(d = 1\), па је \(d\) таутологија.
III начин (свођење на противречност). Претпоставимо супротно, да је \(v(d) = 0\). Импликација је нетачна само ако је претпоставка тачна, а закључак нетачан:
- из \(v(a \land p \land \neg r) = 1\) следи \(v(a) = 1\), \(v(p) = 1\) и \(v(r) = 0\);
- из \(v(\neg q) = 0\) следи \(v(q) = 1\).
Заменом \(p = 1\), \(q = 1\), \(r = 0\) у \(a\) добијамо \(1 \Rightarrow \neg 1 \lor (0 \land s) = 1 \Rightarrow 0 = 0\), тј. \(v(a) = 0\), што је противречно са \(v(a) = 1\). Претпоставка \(v(d) = 0\) не важи, па је \(d\) таутологија.
Закључивање је, дакле, исправно.
Провера у алату за исказне формуле: ((p ⇒ ¬q ∨ (r ∧ s)) ∧ p ∧ ¬r) ⇒ ¬q
Задатак 21 Одредити СДНФ и минималну ДНФ, као и СКНФ и минималну КНФ, Булове функције \[ f(p, q, r, s) = \Big(p \downarrow \big(q \Rightarrow (r \downarrow p)\big)\Big) \Leftrightarrow (s \land \neg q). \]
Означимо \(\varphi = q \Rightarrow (r \downarrow p)\), \(L = p \downarrow \varphi\) и \(D = s \land \neg q\), тако да је \(f = L \Leftrightarrow D\).
| \(p\) | \(q\) | \(r\) | \(s\) | \(r \downarrow p\) | \(\varphi\) | \(L\) | \(D\) | \(f\) |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
СДНФ. Свака врста са \(f = 1\) даје по један конјункт: \[ \begin{aligned} f = {} & (\neg p \land \neg q \land \neg r \land \neg s) \lor (\neg p \land \neg q \land r \land \neg s) \lor (\neg p \land q \land \neg r \land \neg s) \\ & \lor (\neg p \land q \land \neg r \land s) \lor (p \land \neg q \land \neg r \land \neg s) \lor (p \land \neg q \land r \land \neg s) \\ & \lor (p \land q \land \neg r \land \neg s) \lor (p \land q \land \neg r \land s) \lor (p \land q \land r \land \neg s) \\ & \lor (p \land q \land r \land s). \end{aligned} \]
Минимална ДНФ. Последња четири члана имају заједничко \(p \land q\), а за \(r\) и \(s\) јављају се све четири комбинације. Вишеструком применом дистрибутивности добијамо \[ \begin{aligned} & (p \land q \land \neg r \land \neg s) \lor (p \land q \land \neg r \land s) \lor (p \land q \land r \land \neg s) \lor (p \land q \land r \land s) \\ &= \big((p \land q \land \neg r) \land (\neg s \lor s)\big) \lor \big((p \land q \land r) \land (\neg s \lor s)\big) \\ &= (p \land q \land \neg r) \lor (p \land q \land r) = (p \land q) \land (\neg r \lor r) = p \land q. \end{aligned} \] На исти начин први, други, пети и шести члан дају \(\neg q \land \neg s\), а трећи, четврти, седми и осми \(q \land \neg r\). Зато је минимална ДНФ \[ f = (p \land q) \lor (\neg q \land \neg s) \lor (q \land \neg r). \] Седми и осми члан смо искористили двапут. То је дозвољено због идемпотентности, \(x \equiv x \lor x\): члан \(x\) заменимо са \(x \lor x\), па један примерак употребимо у првом, а други у другом спајању. Исти резултат даје Карноова мапа: три групе од по четири јединице.
СКНФ. Свака врста са \(f = 0\) даје по један дисјункт (променљива са вредношћу 1 улази негирана): \[ \begin{aligned} f = {} & (p \lor q \lor r \lor \neg s) \land (p \lor q \lor \neg r \lor \neg s) \land (p \lor \neg q \lor \neg r \lor s) \\ & \land (p \lor \neg q \lor \neg r \lor \neg s) \land (\neg p \lor q \lor r \lor \neg s) \land (\neg p \lor q \lor \neg r \lor \neg s). \end{aligned} \]
Минимална КНФ. Први, други, пети и шести дисјункт дају \(q \lor \neg s\), а трећи и четврти \(p \lor \neg q \lor \neg r\), па је \[ f = (q \lor \neg s) \land (p \lor \neg q \lor \neg r). \]
Провера у алату за исказне формуле: (p ↓ (q ⇒ (r ↓ p))) ⇔ (s ∧ ¬q)