3  Исказни рачун

Логика проучава правила исправног закључивања. У овом поглављу почињемо од реченица свакодневног говора, издвајамо из њих оно што је битно за закључивање и градимо прецизан математички језик — исказни рачун. Научићемо да рачунамо вредност формуле, да препознамо и докажемо таутологију, да проверимо исправност закључка и да формулу запишемо у нормалној форми.

Интуитивна логика

Дефиниција 3.1 (Исказ) Исказ је свака реченица која је или тачна (истинита) или нетачна (неистинита), али не и оба истовремено.

Пример 3.1 Реченице које су искази:

  • „Београд је главни град Србије.“ — тачан исказ.
  • „5 је непаран број.“ — тачан исказ.
  • „2 + 2 = 5.“ — нетачан исказ.
  • „Сунце је звезда.“ — тачан исказ.
  • „Ако данас пада киша, онда је улица мокра.“ — ово је сложен исказ, настао повезивањем два једноставна исказа („данас пада киша“ и „улица је мокра“) везником „ако … онда“. Када је такав исказ тачан, видећемо у наставку.

Реченице које нису искази:

  • „Отвори врата.“ — заповест; нема истинитосну вредност.
  • „Како се осећаш данас?“ — питање; не може бити тачно или нетачно.
  • „Ова реченица је нетачна.“ — парадокс: ако је тачна, онда је нетачна, и обрнуто, па јој се не може доделити истинитосна вредност.
  • „\(x + y = z\).“ — истинитост зависи од вредности \(x\), \(y\) и \(z\); оваквим реченицама бави се предикатски рачун у следећем поглављу.

Логички везници у свакодневном говору

У говору ретко изговарамо само једноставне исказе. Сложене исказе градимо помоћу малог броја речи: „није“, „и“, „или“, „или … или“, „ако … онда“ и „ако и само ако“. Управо зато исказни рачун уводи баш ове операције — оне формализују начин на који свакодневно говоримо и закључујемо.

Кључна особина ових везника јесте да истинитост сложеног исказа зависи само од истинитости његових делова, а не од њиховог значења. Погледајмо како се сваки везник понаша у говору:

  • Негација — „Није тачно да данас пада киша.“ Исказ је тачан тачно онда када је исказ „данас пада киша“ нетачан.
  • Конјункција — „Данас је понедељак и пада киша.“ Тачна је само ако су оба дела тачна.
  • Дисјункција — „Одмарам се читајући књигу или слушајући музику.“ Тачна је ако је тачан бар један део, па и ако су тачна оба — могу истовремено да читам и слушам музику.
  • Ексклузивна дисјункција — „Вечерас ћу или гледати утакмицу или ићи у биоскоп.“ Овде „или“ значи „тачно једно од два“: исказ је тачан ако је тачан тачно један део, а нетачан ако су тачна оба или ниједан. Исти смисао има и питање „Кафа или чај?“ — не очекује се да изаберемо оба.
  • Импликација — „Ако положиш колоквијум, онда добијаш 15 поена.“ Ово обећање је прекршено само у једном случају: положио си колоквијум, а ниси добио поене. Ако колоквијум ниси положио, обећање није прекршено шта год да се деси са поенима — зато импликација са нетачном претпоставком има вредност „тачно“.
  • Еквиваленција — „Излазиш на испит ако и само ако си положио оба колоквијума.“ Тачна је када су оба дела истовремено тачна или истовремено нетачна.

Дакле, сложене исказе градимо од једноставних на следећи начин:

  • Негација исказа A је исказ „није A“.
  • Конјункција исказа A и B је исказ „A и B“.
  • Дисјункција исказа A и B је исказ „A или B“.
  • Ексклузивна дисјункција исказа A и B је исказ „или A или B“.
  • Импликација исказа A и B је исказ „ако A онда B“. 1
  • Еквиваленција исказа A и B је исказ „A ако и само ако B“. 2

Исказна алгебра

Исказна алгебра даје прецизан, формални оквир за рад са сложеним исказима. Исказе записујемо помоћу исказних слова (\(p, q, r, \dots\)) и симбола логичких операција, а уместо „тачно“ и „нетачно“ користимо две логичке вредности:

  • \(1\) представља тачно (истинито),
  • \(0\) представља нетачно (неистинито).

Операције исказне алгебре тачно преносе значење везника из говора. Свака операција задата је таблицом која за све комбинације вредности исказа даје вредност резултата:

  1. Негација (\(\neg\), NOT)

    Резултат је 1 ако исказ има вредност 0, и обрнуто.

    \(p\) \(\neg p\)
    1 0
    0 1

  2. Конјункција (\(\land\), AND)

    Резултат је 1 само ако оба исказа имају вредност 1.

    \(p\) \(q\) \(p \land q\)
    1 1 1
    1 0 0
    0 1 0
    0 0 0

  3. Дисјункција (\(\lor\), OR)

    Резултат је 1 ако бар један од исказа има вредност 1.

    \(p\) \(q\) \(p \lor q\)
    1 1 1
    1 0 1
    0 1 1
    0 0 0

  4. Импликација (\(\Rightarrow\), IF … THEN)

    Резултат је 0 само ако први исказ има вредност 1, а други 0.

    \(p\) \(q\) \(p \Rightarrow q\)
    1 1 1
    1 0 0
    0 1 1
    0 0 1

  5. Еквиваленција (\(\Leftrightarrow\), IFF)

    Резултат је 1 ако оба исказа имају исту вредност.

    \(p\) \(q\) \(p \Leftrightarrow q\)
    1 1 1
    1 0 0
    0 1 0
    0 0 1

  6. Ексклузивна дисјункција (\(\veebar\), XOR)

    Резултат је 1 само ако искази имају различите вредности.

    \(p\) \(q\) \(p \veebar q\)
    1 1 0
    1 0 1
    0 1 1
    0 0 0

    У литератури, посебно у дигиталној логици, за ексклузивну дисјункцију користи се и ознака \(\oplus\).

Логичке операције у Пајтону. Логичким операцијама одговарају оператори not, and и or. Пајтон при рачунању логичких израза користи скраћено израчунавање (енгл. short-circuit evaluation): израз се рачуна слева надесно само до тачке у којој је резултат одређен. Ако је у изразу A and B вредност A једнака False, резултат је сигурно False и B се уопште не рачуна; слично, у изразу A or B део B се не рачуна ако је A једнако True.

def neka_provera(x):
    # Исписујемо информацију о позиву функције за дати аргумент x.
    print(f"Poziv funkcije za vrednost argumenta {x}")
    return True  # Функција увек враћа True, симулирајући успешну проверу.

# Прва петља: пролазимо кроз бројеве од 1 до 10.
for i in range(1, 11):
    # Проверавамо да ли функција neka_provera враћа True за тренутни број i.
    if neka_provera(i):
        # Ако је резултат True, исписујемо да је број прошао проверу.
        print(f"{i} - uspešna provera")

print("-" * 50)  # Исписујемо линију ради прегледности између два дела излаза.

# Друга петља: пролазимо кроз бројеве од 1 до 10.
for i in range(1, 11):
    # Проверавамо да ли је број i паран (i % 2 == 0) и да ли пролази проверу описану функцијом neka_provera.
    if i % 2 == 0 and neka_provera(i):
        # Ако је провера успешна, исписујемо да је паран број прошао проверу.
        print(f"{i} - uspešna provera")
Poziv funkcije za vrednost argumenta 1
1 - uspešna provera
Poziv funkcije za vrednost argumenta 2
2 - uspešna provera
Poziv funkcije za vrednost argumenta 3
3 - uspešna provera
Poziv funkcije za vrednost argumenta 4
4 - uspešna provera
Poziv funkcije za vrednost argumenta 5
5 - uspešna provera
Poziv funkcije za vrednost argumenta 6
6 - uspešna provera
Poziv funkcije za vrednost argumenta 7
7 - uspešna provera
Poziv funkcije za vrednost argumenta 8
8 - uspešna provera
Poziv funkcije za vrednost argumenta 9
9 - uspešna provera
Poziv funkcije za vrednost argumenta 10
10 - uspešna provera
--------------------------------------------------
Poziv funkcije za vrednost argumenta 2
2 - uspešna provera
Poziv funkcije za vrednost argumenta 4
4 - uspešna provera
Poziv funkcije za vrednost argumenta 6
6 - uspešna provera
Poziv funkcije za vrednost argumenta 8
8 - uspešna provera
Poziv funkcije za vrednost argumenta 10
10 - uspešna provera

У првој петљи функцију neka_provera позивамо за сваки број. У другој петљи користимо израз i % 2 == 0 and neka_provera(i), па се функција позива само када је први услов испуњен, односно само за парне бројеве: за непаран број први део има вредност False, резултат конјункције је одређен и функција се не позива. Тако се избегавају непотребна израчунавања, а често и грешке (нпр. у услову x != 0 and 1 / x > 2 дељење се не извршава када је x једнако 0).

Исказне формуле

Дефиниција 3.2 (Исказна формула) Исказна формула је израз састављен од исказних слова, логичких операција и заграда, који је формиран коначном применом следећих правила:

  1. Свако исказно слово је исказна формула.
  2. Ако су \(A\) и \(B\) исказне формуле, онда су и изрази \(\neg A\), \((A \land B)\), \((A \lor B)\), \((A \Rightarrow B)\), \((A \Leftrightarrow B)\) и \((A \veebar B)\) исказне формуле.

Пример 3.2 Исказне формуле добијене применом наведених правила:

  • \((((\neg p \lor q) \land (r \Rightarrow s)) \Leftrightarrow t)\)
  • \(((p \land q) \Rightarrow r)\)

Изрази који нису исказне формуле, јер се не могу добити наведеним правилима:

  • \(p \neg q\)
  • \(p \lor \Rightarrow q\)
  • \(p \land q p\neg\)

Изостављање заграда

Да формуле не би биле претрпане заградама, усвајамо следећа два договора:

  • спољне заграде се изостављају, па уместо \(((p \land q) \Rightarrow r)\) пишемо \((p \land q) \Rightarrow r\);
  • операције имају приоритет (од највишег ка најнижем): \[\neg, \quad \land, \quad \lor, \quad \Rightarrow, \quad \Leftrightarrow,\] па заграде око операције вишег приоритета можемо изоставити.

Пример 3.3 Формула \(\neg p \land q \lor r \Rightarrow s\) је скраћени запис формуле \(((\neg p \land q) \lor r) \Rightarrow s\), а формула \(p \lor q \Rightarrow \neg r\) скраћени запис формуле \((p \lor q) \Rightarrow \neg r\).

Код узастопних импликација заграде увек пишемо, јер формуле \((p \Rightarrow q) \Rightarrow r\) и \(p \Rightarrow (q \Rightarrow r)\) нису исте (за \(v(p)=v(q)=v(r)=0\) прва има вредност 0, а друга 1).

Подформуле и главни везник

Формула која се појављује као део друге формуле назива се њена подформула. Операција која је у правилима из дефиниције 3.2 примењена последња назива се главни везник формуле — она одређује да ли је формула негација, конјункција, импликација итд.

Пример 3.4 Формула \(F = (p \lor q) \land \neg r\) је конјункција (главни везник је \(\land\)) формула \(p \lor q\) и \(\neg r\). Њене подформуле су \[p, \quad q, \quad r, \quad p \lor q, \quad \neg r, \quad (p \lor q) \land \neg r.\] Управо ове подформуле чине колоне таблице истинитости у наредном одељку.

Валуација и таблица истинитости

Дефиниција 3.3 (Валуација) Валуација је пресликавање које свакој исказној променљивој додељује вредност 0 или 1, тј. \[ v: \{ \text{исказне променљиве} \} \to \{0, 1\}. \]

Дефиниција 3.4 (Вредност формуле) Вредност исказне формуле \(F\) при валуацији \(v\) је логичка вредност \(v(F) \in \{0, 1\}\) која се одређује рекурзивно, према грађи формуле:

  • ако је \(F\) исказна променљива \(p\), онда је \(v(F) = v(p)\);
  • ако су \(F\) и \(G\) исказне формуле, онда је
    • \(v(\neg F) = \neg v(F)\),
    • \(v(F \land G) = v(F) \land v(G)\),
    • \(v(F \lor G) = v(F) \lor v(G)\),
    • \(v(F \Rightarrow G) = v(F) \Rightarrow v(G)\),
    • \(v(F \Leftrightarrow G) = v(F) \Leftrightarrow v(G)\),
    • \(v(F \veebar G) = v(F) \veebar v(G)\).

Пример 3.5 Нека је дата исказна формула \(F = (p \lor q) \land \neg r\) и валуација \(v\) за коју је \[v(p) = 1, \quad v(q) = 0, \quad v(r) = 1.\]

Вредност формуле рачунамо од најмањих подформула ка већим:

  • дисјункција: \(v(p \lor q) = v(p) \lor v(q) = 1 \lor 0 = 1\),
  • негација: \(v(\neg r) = \neg v(r) = \neg 1 = 0\),
  • цела формула: \(v(F) = v(p \lor q) \land v(\neg r) = 1 \land 0 = 0\).

Дакле, \(v(F) = 0\), односно формула је нетачна при датој валуацији.

За формулу са \(n\) исказних слова постоји тачно \(2^n\) различитих валуација, јер свако слово може добити вредност 0 или 1. Вредности формуле при свим валуацијама систематски приказујемо таблицом истинитости: за свако исказно слово, сваку подформулу и целу формулу уводимо по једну колону, а за сваку валуацију по један ред. Затим за сваки ред рачунамо вредности подформула, од најмањих ка највећим.

Пример 3.6 Таблица истинитости за формулу \(F = (p \lor q) \land \neg r\) из претходног примера:

\(p\) \(q\) \(r\) \(p \lor q\) \(\neg r\) \((p \lor q) \land \neg r\)
0 0 0 0 1 0
0 0 1 0 0 0
0 1 0 1 1 1
0 1 1 1 0 0
1 0 0 1 1 1
1 0 1 1 0 0
1 1 0 1 1 1
1 1 1 1 0 0

Формула је тачна у три од осам валуација, а валуација из примера 3.5 (\(p=1, q=0, r=1\)) одговара шестом реду.

Поступак конструисања таблице истинитости лако се програмира. Модул itertools генерише све валуације, а формулу задајемо као функцију:

import itertools

skup = {0, 1}  # Могуће вредности исказних променљивих
iskazna_slova = ['p', 'q', 'r']  # Имена исказних променљивих

def F(p, q, r):
    return (p or q) and not r  # Формула коју анализирамо

broj_iskaznih_slova = 3  # Број променљивих које користимо у формули F

# Генеришемо све могуће валуације за дате променљиве
valuacije = itertools.product(skup, repeat=broj_iskaznih_slova)

# Исписујемо заглавље табеле са именима променљивих и формулом
for i in range(broj_iskaznih_slova):
    print(iskazna_slova[i] + '   ', end="")
print('F')

# Пролазимо кроз све валуације и исписујемо њихове вредности са резултатом функције
for v in valuacije:
    print(*v, int(F(*v)), sep="   ")
p   q   r   F
0   0   0   0
0   0   1   0
0   1   0   1
0   1   1   0
1   0   0   1
1   0   1   0
1   1   0   1
1   1   1   0

Алат за рад са исказним формулама

Уз уџбеник постоји и алат у коме за унету формулу одмах добијате таблицу истинитости (са подформулама), врсту формуле (таутологија, контрадикција или контингенција), СДНФ и СКНФ, Карноову мапу и минималне облике формуле. Формулу можете унети у ознакама из уџбеника или са тастатуре: на пример, \(p \land q \Rightarrow \neg r\) може се написати и као p & q -> ~r или p and q => not r.

Алат се може користити овде или отворити у новом прозору.

Таутологије и семантичка еквиваленција

Дефиниција 3.5 (Таутологија, контрадикција, контингенција)  

  • Таутологија је формула која је тачна при свакој валуацији.
  • Контрадикција је формула која је нетачна при свакој валуацији.
  • Контингенција (неутрална формула) је формула која је тачна при неким валуацијама, а нетачна при другим.

Формула из примера 3.6 је контингенција, формула \(p \lor \neg p\) је таутологија, а формула \(p \land \neg p\) контрадикција.

Дефиниција 3.6 (Семантичка еквиваленција) Исказне формуле \(F\) и \(G\) су семантички еквивалентне ако имају исту вредност при свакој валуацији, тј. ако за сваку валуацију \(v\) важи \(v(F) = v(G)\). Тада пишемо \(F \equiv G\).

Из таблице за еквиваленцију непосредно следи да је \(F \equiv G\) ако и само ако је формула \(F \Leftrightarrow G\) таутологија. Зато се сваки закон облика „\(A \Leftrightarrow B\) је таутологија“ може користити као еквиваленција \(A \equiv B\): у формули смемо заменити подформулу \(A\) формулом \(B\), а да се вредност формуле ни при једној валуацији не промени. То омогућава поједностављивање формула, што у дигиталној електроници и програмирању значи мања кола и једноставнији код.

Табела познатих таутологија

Назив таутологије Формула
Закон искључења трећег \(p \lor \neg p\)
Закон непротивречности \(\neg (p \land \neg p)\)
Закон двоструке негације \(\neg \neg p \Leftrightarrow p\)
Идемпотентност \(p \land p \Leftrightarrow p\)
\(p \lor p \Leftrightarrow p\)
Комутативност \(p \land q \Leftrightarrow q \land p\)
\(p \lor q \Leftrightarrow q \lor p\)
Асоцијативност \((p \land q) \land r \Leftrightarrow p \land (q \land r)\)
\((p \lor q) \lor r \Leftrightarrow p \lor (q \lor r)\)
Дистрибутивни закони \(p \land (q \lor r) \Leftrightarrow (p \land q) \lor (p \land r)\)
\(p \lor (q \land r) \Leftrightarrow (p \lor q) \land (p \lor r)\)
Де Морганови закони \(\neg (p \land q) \Leftrightarrow \neg p \lor \neg q\)
\(\neg (p \lor q) \Leftrightarrow \neg p \land \neg q\)
Закони апсорпције \(p \land (p \lor q) \Leftrightarrow p\)
\(p \lor (p \land q) \Leftrightarrow p\)
Закон уклањања импликације \((p \Rightarrow q) \Leftrightarrow \neg p \lor q\)
Закон контрапозиције \((p \Rightarrow q) \Leftrightarrow (\neg q \Rightarrow \neg p)\)
Закон транзитивности импликације \(\left((p \Rightarrow q) \land (q \Rightarrow r)\right) \Rightarrow (p \Rightarrow r)\)
Закон уклањања еквиваленције \((p \Leftrightarrow q) \Leftrightarrow (p \Rightarrow q) \land (q \Rightarrow p)\)
Закон сажимања \((p \land q) \lor (p \land \neg q) \Leftrightarrow p\)
\((p \lor q) \land (p \lor \neg q) \Leftrightarrow p\)

При трансформацијама формула згодно је користити и константе \(1\) (формула која је увек тачна) и \(0\) (формула која је увек нетачна). За њих важи: \[ p \land \neg p \equiv 0, \qquad p \lor \neg p \equiv 1, \qquad p \land 1 \equiv p, \qquad p \lor 0 \equiv p, \qquad p \land 0 \equiv 0, \qquad p \lor 1 \equiv 1. \]

Доказ да је формула таутологија

Постоје три уобичајена начина.

1. Таблицом истинитости. Проверимо вредност формуле у свих \(2^n\) валуација. Поступак је увек примењив, али за већи број слова постаје дуг (за 5 слова таблица има 32 реда).

2. Трансформацијама. Полазну формулу низом познатих еквиваленција преводимо у циљну, наводећи у сваком кораку закон који смо применили.

Пример 3.7 Доказаћемо да је \(\neg(p \Rightarrow q) \equiv p \land \neg q\): \[ \begin{aligned} \neg(p \Rightarrow q) &\equiv \neg(\neg p \lor q) && \text{уклањање импликације} \\ &\equiv \neg\neg p \land \neg q && \text{Де Морганов закон} \\ &\equiv p \land \neg q && \text{двострука негација.} \end{aligned} \]

На исти начин добијамо закон контрапозиције: \[ \neg q \Rightarrow \neg p \equiv \neg\neg q \lor \neg p \equiv q \lor \neg p \equiv \neg p \lor q \equiv p \Rightarrow q. \]

3. Свођењем на противречност. Претпоставимо да постоји валуација при којој формула има вредност 0 и из те претпоставке изведемо противречност. Метод је нарочито брз за формуле чији је главни везник импликација, јер је импликација нетачна само у једном случају.

Пример 3.8 Доказаћемо да је закон транзитивности \(F = \left((p \Rightarrow q) \land (q \Rightarrow r)\right) \Rightarrow (p \Rightarrow r)\) таутологија.

Претпоставимо да је \(v(F) = 0\) за неку валуацију \(v\). Импликација је нетачна само ако је претпоставка тачна, а последица нетачна, па је \[v\big((p \Rightarrow q) \land (q \Rightarrow r)\big) = 1 \quad \text{и} \quad v(p \Rightarrow r) = 0.\]

Из \(v(p \Rightarrow r) = 0\) следи \(v(p) = 1\) и \(v(r) = 0\). Из прве једнакости је \(v(p \Rightarrow q) = 1\), а како је \(v(p) = 1\), мора бити \(v(q) = 1\). Тада је \(v(q \Rightarrow r) = 1 \Rightarrow 0 = 0\), што је у супротности са \(v(q \Rightarrow r) = 1\).

Дакле, не постоји валуација при којој је \(F\) нетачна, па је \(F\) таутологија.

Логичко закључивање

Закључивање почиње од тврђења која прихватамо као тачна — премиса (хипотеза) — и из њих изводи нова тврђења. Закључак је исправан ако је тачан кад год су тачне све премисе.

Дефиниција 3.7 (Семантичка последица) Нека је \(\Pi = \{F_1, F_2, \dots, F_n\}\) скуп исказних формула и \(F\) исказна формула. Формула \(F\) је семантичка последица скупа \(\Pi\) ако за сваку валуацију \(v\) важи: \[ v(F_1) = v(F_2) = \dots = v(F_n) = 1 \quad \Longrightarrow \quad v(F) = 1, \] односно ако не постоји валуација при којој су све премисе тачне, а \(F\) нетачна. Тада пишемо \(F_1, F_2, \dots, F_n \models F\).

Пример 3.9 Формула \(q\) је семантичка последица скупа \(\{\neg p \lor q,\ p\}\). Формуле \(p\) и \(\neg p \lor q\) истовремено имају вредност 1 само при валуацији \(v(p) = 1,\ v(q) = 1\), а тада је и \(v(q) = 1\).

Да бисмо проверили да ли је нека формула семантичка последица датих премиса, можемо користити следећу теорему.

Теорема 3.1 Формула \(F\) је семантичка последица скупа формула \(\{F_1, F_2, \dots, F_n\}\) ако и само ако је формула \[(F_1 \land F_2 \land \dots \land F_n) \Rightarrow F\] таутологија.

Доказ. Импликација \((F_1 \land \dots \land F_n) \Rightarrow F\) је нетачна при валуацији \(v\) тачно онда када је \(v(F_1 \land \dots \land F_n) = 1\) и \(v(F) = 0\), односно када су све премисе тачне, а \(F\) нетачна. Дакле, импликација је таутологија ако и само ако таква валуација не постоји, а то је управо дефиниција семантичке последице.

Правила закључивања

Најчешће коришћена правила закључивања су:

Назив Правило
модус поненс \(p \Rightarrow q,\ p \ \models\ q\)
модус толенс \(p \Rightarrow q,\ \neg q \ \models\ \neg p\)
хипотетички силогизам \(p \Rightarrow q,\ q \Rightarrow r \ \models\ p \Rightarrow r\)
дисјунктивни силогизам \(p \lor q,\ \neg p \ \models\ q\)

Модус поненс омогућава да из импликације и њене претпоставке закључимо последицу:

  • прва премиса: ако је \(p\), онда је \(q\),
  • друга премиса: \(p\) је тачно,
  • закључак: \(q\) је тачно.

Пример 3.10  

  • прва премиса: ако је данас субота, онда немам наставу \((p \Rightarrow q)\),
  • друга премиса: данас је субота \((p)\),
  • закључак: дакле, немам наставу \((q)\).

Модус толенс је такође ваљан облик закључивања, али на основу порицања:

  • прва премиса: ако је \(p\), онда је \(q\),
  • друга премиса: \(q\) је нетачно,
  • закључак: \(p\) је нетачно.

Пример 3.11  

  • прва премиса: ако пада киша, онда је земља мокра \((p \Rightarrow q)\),
  • друга премиса: земља није мокра \((\neg q)\),
  • закључак: дакле, не пада киша \((\neg p)\).

Пример 3.12  

  • Хипотетички силогизам: „Ако учим, положићу испит. Ако положим испит, идем на море. Дакле, ако учим, идем на море.“
  • Дисјунктивни силогизам: „Кључеви су у торби или у јакни. Нису у торби. Дакле, у јакни су.“

Да су ова правила исправна, лако се проверава помоћу теореме 3.1. На пример, модус поненс је исправан јер је формула \((p \land (p \Rightarrow q)) \Rightarrow q\) таутологија.

Честе грешке у закључивању

Два облика закључивања „изгледају“ исправно, али то нису:

  • потврђивање последице: \(p \Rightarrow q,\ q \ \not\models\ p\) — „Ако пада киша, земља је мокра. Земља је мокра. Дакле, пада киша.“ Земља може бити мокра и зато што је неко заливао башту.
  • порицање претпоставке: \(p \Rightarrow q,\ \neg p \ \not\models\ \neg q\) — „Ако пада киша, земља је мокра. Не пада киша. Дакле, земља није мокра.“

У оба случаја валуација \(v(p) = 0,\ v(q) = 1\) чини премисе тачним, а закључак нетачним.

Нормалне форме

Нормалне форме су стандардни облици записа исказних формула. Олакшавају поређење, анализу и обраду формула, посебно у дигиталној логици и у рачунарским алгоритмима.

Дефиниција 3.8 (Литерал, конјункт, дисјункт)  

  • Свака исказна променљива или њена негација назива се литерал. Исказно слово је позитивни, а његова негација негативни литерал.
  • Конјункт је формула састављена од једног или више литерала повезаних конјункцијом, нпр. \(p \land \neg q \land r\).
  • Дисјункт је формула састављена од једног или више литерала повезаних дисјункцијом, нпр. \(p \lor \neg q \lor r\).

Пример 3.13  

  • Позитивни литерали: \(p\), \(q\), \(r\).
  • Негативни литерали: \(\neg p\), \(\neg q\), \(\neg r\).

Дефиниција 3.9 (ДНФ и КНФ) Исказна формула је у дисјунктивној нормалној форми (ДНФ) ако има облик \[ F_1 \lor F_2 \lor \dots \lor F_n, \] где је сваки \(F_i\) конјункт, тј. \(F_i = l_{i_1} \land l_{i_2} \land \dots \land l_{i_m}\), а \(l_{i_j}\) су литерали.

Исказна формула је у конјунктивној нормалној форми (КНФ) ако има облик \[ F_1 \land F_2 \land \dots \land F_n, \] где је сваки \(F_i\) дисјункт, тј. \(F_i = l_{i_1} \lor l_{i_2} \lor \dots \lor l_{i_m}\).

Пример 3.14  

  • \((p \land \neg q) \lor (\neg p \land r) \lor q\) је у ДНФ, јер је дисјункција три конјункта.
  • \((\neg p \lor q) \land (\neg p \lor \neg r) \land r\) је у КНФ, јер је конјункција три дисјункта.
  • \((\neg p \lor q) \land \neg p \land \neg r \land q\) је у КНФ.
  • \((\neg p \lor q) \land \neg(p \lor r) \land r\) није ни у КНФ3 ни у ДНФ.

Дефиниција 3.10 (СДНФ и СКНФ) Исказна формула је у савршеној дисјунктивној нормалној форми (СДНФ, или потпуној — ПДНФ) ако је у ДНФ и у сваком конјункту се свака исказна променљива формуле појављује тачно једном.

Слично, формула је у савршеној конјунктивној нормалној форми (СКНФ, или ПКНФ) ако је у КНФ и у сваком дисјункту се свака исказна променљива формуле појављује тачно једном.

Пример 3.15  

  • \((\neg p \land q \land \neg r) \lor (p \land \neg q \land \neg r) \lor (p \land \neg q \land r)\) је у СДНФ.
  • \((\neg p \lor q \lor \neg r) \land (p \lor \neg q \lor \neg r) \land (p \lor \neg q \lor r)\) је у СКНФ.
  • \((p \land \neg q) \lor (\neg p \land r) \lor (q \land r)\) није у СДНФ4 (јесте у ДНФ).

Ако је \(G \equiv F\) и \(G\) је у ДНФ (КНФ, СДНФ, СКНФ), кажемо да је \(G\) ДНФ (КНФ, СДНФ, СКНФ) формуле \(F\).

Свођење формуле на нормалну форму

Свака исказна формула може се еквивалентним трансформацијама свести и на ДНФ и на КНФ, у три корака:

  1. уклонимо \(\Leftrightarrow\) и \(\Rightarrow\) помоћу закона уклањања еквиваленције и импликације;
  2. спустимо негације до исказних слова помоћу Де Морганових закона и закона двоструке негације;
  3. применимо дистрибутивност: за КНФ дистрибутивност дисјункције према конјункцији, а за ДНФ конјункције према дисјункцији.

Пример 3.16 Свешћемо формулу \(F = \neg(p \Rightarrow q) \lor r\) на ДНФ и КНФ: \[ \begin{aligned} \neg(p \Rightarrow q) \lor r &\equiv \neg(\neg p \lor q) \lor r && \text{уклањање импликације} \\ &\equiv (p \land \neg q) \lor r && \text{Де Морган, двострука негација} \quad (\text{ДНФ}) \\ &\equiv (p \lor r) \land (\neg q \lor r) && \text{дистрибутивност} \quad (\text{КНФ}). \end{aligned} \]

Пример 3.17 За формулу \(p \Leftrightarrow q\) формула \((\neg p \lor q) \land (p \lor \neg q)\) је СКНФ, а формула \((p \land q) \lor (\neg p \land \neg q)\) је СДНФ, јер је \[ \begin{aligned} p \Leftrightarrow q &\equiv (p \Rightarrow q) \land (q \Rightarrow p) \\ &\equiv (\neg p \lor q) \land (p \lor \neg q) && \text{СКНФ} \\ &\equiv (\neg p \land p) \lor (\neg p \land \neg q) \lor (q \land p) \lor (q \land \neg q) && \text{ДНФ, није СДНФ} \\ &\equiv 0 \lor (\neg p \land \neg q) \lor (p \land q) \lor 0 \\ &\equiv (\neg p \land \neg q) \lor (p \land q) && \text{СДНФ.} \end{aligned} \]

Примена: проблем задовољивости (SAT)

Формула је задовољива ако постоји бар једна валуација при којој има вредност 1. Проблем задовољивости (SAT) гласи: за дату формулу у КНФ утврдити да ли је задовољива. То је један од најважнијих проблема рачунарства — на њега се своде многи практични проблеми планирања, распоређивања и провере исправности хардвера и софтвера.

Наивно решење је провера свих \(2^n\) валуација. Ако рачунар проверава милијарду валуација у секунди, за формулу са 50 слова (\(2^{50} \approx 1{,}1 \cdot 10^{15}\) валуација) потребно му је око 13 дана, а за формулу са 100 слова (\(2^{100} \approx 1{,}3 \cdot 10^{30}\) валуација) око \(4 \cdot 10^{13}\) година — неколико хиљада пута више од старости свемира. Време расте експоненцијално са бројем слова.

Савремени SAT решавачи не испробавају све валуације, већ користе паметне алгоритме, па у практичним проблемима често решавају и формуле са милионима променљивих. Ипак, није познато да ли постоји алгоритам који брзо решава сваки пример — SAT је NP-комплетан проблем.

Стивен Кук (Stephen Cook) је 1971. године доказао да је проблем задовољивости NP-комплетан. Тај резултат је поставио темеље теорије сложености израчунавања и отворио питање „P = NP?“, које је и данас један од највећих нерешених проблема математике.

Булове функције

Таблица истинитости показује да вредност формуле зависи само од вредности њених исказних слова. Формула са \(n\) слова тако одређује пресликавање које свакој \(n\)-торци нула и јединица придружује 0 или 1. Таква пресликавања називамо Буловим функцијама: она описују везу између неколико бинарних улаза и једног бинарног излаза, па ће нам бити основни алат и у поглављу о дигиталној логици.

Дефиниција 3.11 (Булова функција) Булова функција од \(n\) променљивих је свако пресликавање \[f : \{0, 1\}^n \to \{0, 1\}.\]

Функција од \(n\) променљивих задата је таблицом са \(2^n\) редова, а у сваком реду вредност може бити 0 или 1. Зато Булових функција од \(n\) променљивих има \(2^{2^n}\). На пример, Булових функција једне променљиве има четири:

Табела 3.1: Све четири Булове функције једне променљиве
\(p\) \(g_1\) \(g_2\) \(g_3\) \(g_4\)
0 0 0 1 1
1 0 1 0 1
  • \(g_1(p)=0\) „нула-функција“,
  • \(g_2(p)=p\) „идентичка функција“,
  • \(g_3(p)=\neg p\) „негација“,
  • \(g_4(p)=1\) „јединична функција“.

Булових функција две променљиве, тј. бинарних операција на скупу \(\{0, 1\}\), има \(2^{2^2} = 16\) (табела 3.2):

Табела 3.2: Свих 16 Булових функција две променљиве
\(p\) \(q\) \(f_0\) \(f_1\) \(f_2\) \(f_3\) \(f_4\) \(f_5\) \(f_6\) \(f_7\) \(f_8\) \(f_9\) \(f_{10}\) \(f_{11}\) \(f_{12}\) \(f_{13}\) \(f_{14}\) \(f_{15}\)
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

Свакој од функција \(f_0, f_1, \dots, f_{15}\) можемо придружити исказну формулу:

  • \(f_0(p, q) = 0\) „нула-функција“,
  • \(f_1(p, q) = p \land q\) „конјункција“,
  • \(f_2(p, q) = \neg (p \Rightarrow q)\) „негација импликације“,
  • \(f_3(p, q) = p\),
  • \(f_4(p, q) = \neg (q \Rightarrow p)\),
  • \(f_5(p, q) = q\),
  • \(f_6(p, q) = p \veebar q\) „ексклузивна дисјункција“,
  • \(f_7(p, q) = p \lor q\) „дисјункција“,
  • \(f_8(p, q) = \neg (p \lor q)\) „негација дисјункције“ (Лукашијевичева функција, Пирсова стрелица \(p \downarrow q\)),
  • \(f_9(p, q) = p \Leftrightarrow q\) „еквиваленција“,
  • \(f_{10}(p, q) = \neg q\),
  • \(f_{11}(p, q) = q \Rightarrow p\),
  • \(f_{12}(p, q) = \neg p\),
  • \(f_{13}(p, q) = p \Rightarrow q\) „импликација“,
  • \(f_{14}(p, q) = \neg (p \land q)\) „негација конјункције“ (Шеферова функција \(p \uparrow q\)),
  • \(f_{15}(p, q) = 1\) „јединична функција“.

Од ових 16 операција свакодневни говор „види“ само неколико: конјункцију („и“), дисјункцију („или“), импликацију („ако … онда“) и еквиваленцију („ако и само ако“), уз негацију („није“) као једину занимљиву функцију једне променљиве. Зато смо управо њих изабрали за везнике исказног рачуна. Тај избор условљен је језиком, а не математиком: остале операције нису ништа мање важне, само за њих немамо кратке речи. У поглављу о дигиталној логици видећемо да су у техници најважније баш две операције које у говору готово не користимо — Шеферова функција \(\uparrow\) и Пирсова стрелица \(\downarrow\).

Формула за дату Булову функцију

За сваку Булову функцију могуће је одредити исказну формулу која је описује. Да бисмо поједноставили запис, позитивни литерал \(p_i\) означаваћемо са \(p_i^1\), а негативни литерал \(\neg p_i\) са \(p_i^0\). Тада је \(v(p_i^{x}) = 1\) ако и само ако је \(v(p_i) = x\).

Теорема 3.2 (СДНФ Булове функције) Нека је \(f\) Булова функција од \(n\) променљивих која није идентички једнака 0 и нека је \[ X = \{(x_1, x_2, \dots, x_n) \in \{0, 1\}^n \mid f(x_1, x_2, \dots, x_n) = 1\} \] скуп свих \(n\)-торки за које \(f\) има вредност 1. Тада за формулу \[ F_1(p_1, p_2, \dots, p_n) = \bigvee_{(x_1, x_2, \dots, x_n) \in X} \left( p_1^{x_1} \land p_2^{x_2} \land \dots \land p_n^{x_n} \right) \] и сваку валуацију \(v\) важи \(v(F_1) = f(v(p_1), v(p_2), \dots, v(p_n))\).

Теорема 3.3 (СКНФ Булове функције) Нека је \(f\) Булова функција од \(n\) променљивих која није идентички једнака 1 и нека је \[ Y = \{(x_1, x_2, \dots, x_n) \in \{0, 1\}^n \mid f(x_1, x_2, \dots, x_n) = 0\} \] скуп свих \(n\)-торки за које \(f\) има вредност 0. Тада за формулу \[ F_2(p_1, p_2, \dots, p_n) = \bigwedge_{(x_1, x_2, \dots, x_n) \in Y} \left( p_1^{1 - x_1} \lor p_2^{1 - x_2} \lor \dots \lor p_n^{1 - x_n} \right) \] и сваку валуацију \(v\) важи \(v(F_2) = f(v(p_1), v(p_2), \dots, v(p_n))\).

Формуле \(F_1\) и \(F_2\) су управо СДНФ и СКНФ функције \(f\): сваком реду у коме \(f\) има вредност 1 одговара један конјункт, а сваком реду у коме има вредност 0 један дисјункт.

Пример 3.18 Одредићемо бар једну исказну формулу за Булову функцију \(f\) дату таблицом:

\(p\) \(q\) \(r\) \(f(p, q, r)\)
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0

Применом теорема 3.2 и 3.3 добијамо:

\(p\) \(q\) \(r\) \(f(p, q, r)\) Конјункти Дисјункти
0 0 0 0 \(p^1 \lor q^1 \lor r^1\)
0 0 1 1 \(p^0 \land q^0 \land r^1\)
0 1 0 1 \(p^0 \land q^1 \land r^0\)
0 1 1 0 \(p^1 \lor q^0 \lor r^0\)
1 0 0 0 \(p^0 \lor q^1 \lor r^1\)
1 0 1 1 \(p^1 \land q^0 \land r^1\)
1 1 0 1 \(p^1 \land q^1 \land r^0\)
1 1 1 0 \(p^0 \lor q^0 \lor r^0\)

СДНФ функције \(f\) је \[ (\neg p \land \neg q \land r) \lor (\neg p \land q \land \neg r) \lor (p \land \neg q \land r) \lor (p \land q \land \neg r), \] а СКНФ \[ (p \lor q \lor r) \land (p \lor \neg q \lor \neg r) \land (\neg p \lor q \lor r) \land (\neg p \lor \neg q \lor \neg r). \]

Пажљивим погледом на таблицу видимо да \(f\) има вредност 1 тачно када \(q\) и \(r\) имају различите вредности, тј. \(f(p, q, r) = q \veebar r\). Иста функција може се, дакле, описати и много краћом формулом. Проналажење што једноставније формуле (минимизација) важно је у пракси, јер краћа формула значи мање логичких кола.

Функција sdnf исписује СДНФ формуле задате као Пајтон функција, тачно по теореми 3.2:

import itertools  # Увозимо itertools модул за генерисање свих могућих валуација.

# Дефинишемо функцију која враћа СДНФ за задату формулу F.
def sdnf(F, n, iskazna_slova=["p", "q", "r", "s", "t"]):
    skup = {0, 1}  # Дефинишемо скуп вредности променљивих
    negacija = "¬"  # Симбол за негацију који ћемо користити у СДНФ изразу.
    konjunkcija = " ∧ "  # Симбол за конјункцију.
    disjunkcija = " ∨ "  # Симбол за дисјункцију.

    # Генеришемо све могуће валуације за n променљивих.
    valuacije = itertools.product(skup, repeat=n)
    konjunkti = list()  # Креирамо листу у којој ћемо чувати све конјункте који чине СДНФ.

    # Пролазимо кроз све валуације.
    for v in valuacije:
        if F(*v) == True:  # Проверавамо да ли за дату валуацију формула F враћа True тј има вредност 1.
            literali_za_konjunkt = list()  # Креирамо листу за чување литерала за тренутни конјункт.

            # За сваку променљиву у тренутној валуацији креирамо одговарајући литерал.
            for i in range(n):
                if v[i] == 0:  # Ако је вредност променљиве 0, додајемо негативан литерал.
                    literali_za_konjunkt.append(negacija + iskazna_slova[i])
                else:  # Ако је вредност променљиве 1, додајемо позитиван литерал.
                    literali_za_konjunkt.append(iskazna_slova[i])

            # Спајамо литерале конјункцијом и додајемо креиран конјункт у листу.
            konjunkti.append("(" + konjunkcija.join(literali_za_konjunkt) + ")")

    # Спајамо све конјункте дисјункцијом да бисмо добили запис формуле F у СДНФ.
    sdnf_string = disjunkcija.join(konjunkti)
    return sdnf_string  # Враћамо добијени СДНФ стринг.

Функција itertools.product((0, 1), repeat=n) креира све \(n\)-торке нула и јединица, односно све валуације (за три променљиве: (0, 0, 0), (0, 0, 1), (0, 1, 0) итд.). Функција sdnf за сваку валуацију проверава да ли F враћа True. Ако враћа, од те валуације прави конјункт: за вредност 0 додаје негативан литерал (нпр. ¬p), а за вредност 1 позитиван (нпр. p). Литерале спаја конјункцијом (∧), а све добијене конјункте на крају дисјункцијом (∨).

Примери коришћења функције sdnf:

def implikacija(p, q):
    return not p or q


def ekvivalencija(p, q):
    return p == q


def F1(p, q, r):
    return (not p and q) == (implikacija(r, not q) or p)


def F2(a, b, c, d):
    I = implikacija(a, b)
    II = ((b or c) == (not a))
    III = b or (d != a)
    IV = implikacija((c and d), b)
    return I and II and III and IV


def F3(p, q):
    return not (not (p and q) == (not p or not q))


print(sdnf(F1, 3))
print(sdnf(F2, 4, iskazna_slova=["a", "b", "c", "d"]))
print(sdnf(F3, 2))
print(sdnf(implikacija, 2))
print(sdnf(ekvivalencija, 2))
(¬p ∧ q ∧ ¬r)
(¬a ∧ b ∧ ¬c ∧ ¬d) ∨ (¬a ∧ b ∧ ¬c ∧ d) ∨ (¬a ∧ b ∧ c ∧ ¬d) ∨ (¬a ∧ b ∧ c ∧ d)

(¬p ∧ ¬q) ∨ (¬p ∧ q) ∨ (p ∧ q)
(¬p ∧ ¬q) ∨ (p ∧ q)

Формула F3 је негација Де Моргановог закона, дакле контрадикција, па је њен СДНФ празан.

Минимизација: Карноове мапе

СДНФ и СКНФ се лако читају из таблице, али су обично дугачке. Најједноставнији облик формуле за малу функцију (до четири променљиве) најлакше се налази помоћу Карноове мапе (Морис Карно, 1953).

Карноова мапа је таблица вредности функције у којој су врсте и колоне поређане тако да се суседна поља разликују у вредности тачно једне променљиве. Зато се колоне за две променљиве не ређају као \(00, 01, 10, 11\), већ као \(00, 01, 11, 10\) (Грејов код). Суседна су и поља на супротним ивицама мапе: прва и последња колона, као и прва и последња врста, разликују се такође у једној променљивој — мапу треба замислити као да јој се ивице додирују.

Ако су два суседна поља једнака 1, одговарајући конјункти СДНФ разликују се само у једној променљивој, па се по закону сажимања \((A \land x) \lor (A \land \neg x) \equiv A\) та променљива губи. Одатле правила минимизације:

  1. јединице се групишу у правоугаонике од 1, 2, 4 или 8 суседних поља (групе се могу и преклапати, и прелазити преко ивица мапе);
  2. групе треба да буду што веће, а што мање их треба да покрије све јединице;
  3. свака група даје један конјункт у коме су само промењиве које су у целој групи сталне: промењива са вредношћу 1 улази као \(x\), а са вредношћу 0 као \(\neg x\).

Дисјункција добијених конјунката је минимална ДНФ. Груписањем нула на исти начин добија се минимална КНФ: свака група нула даје дисјункт, а промењива која је у групи стално 1 улази као \(\neg x\), а стално 0 као \(x\).

Пример 3.19 Функција већине \(f(p, q, r)\) из задатка 10 има вредност 1 тачно када су бар два аргумента једнака 1, тј. у врстама 3, 5, 6 и 7 таблице. Њена Карноова мапа приказана је на слици 3.1: врсте одговарају вредности \(p\), а колоне вредностима \(qr\) у Грејовом редоследу.

Слика 3.1: Карноова мапа функције већине: три групе по две јединице

Јединица у пољу \(p = 1, qr = 11\) улази у три групе. Група у колони \(qr = 11\) има сталне \(q = 1\) и \(r = 1\), па даје конјункт \(q \land r\); група у врсти \(p = 1\) са колонама \(01\) и \(11\) даје \(p \land r\), а са колонама \(11\) и \(10\) даје \(p \land q\). Минимална ДНФ је \[ f(p, q, r) = (p \land q) \lor (p \land r) \lor (q \land r), \] што је знатно краће од СДНФ са четири конјункта од по три литерала.

Пример 3.20 Функција \(f(p, q, r, s)\) има вредност 1 у врстама 0, 2, 5, 7, 8, 10, 13 и 15 таблице. На Карноовој мапи са четири промењиве (слика 3.2) врсте одговарају вредностима \(pq\), а колоне вредностима \(rs\), обе у Грејовом редоследу.

Слика 3.2: Карноова мапа са групом у средини и групом од четири угла

Четири јединице у средини мапе чине групу у којој су сталне само \(q = 1\) и \(s = 1\), па она даје конјункт \(q \land s\). Четири угла мапе су међусобно суседна (преко ивица), а у тој групи су сталне \(q = 0\) и \(s = 0\), што даје \(\neg q \land \neg s\). Дакле, \[ f(p, q, r, s) = (q \land s) \lor (\neg q \land \neg s) \equiv q \Leftrightarrow s, \] а функција уопште не зависи од \(p\) и \(r\).

За више од четири промењиве Карноове мапе постају непрегледне, па се користе алгоритамски поступци. Најпознатији је Квајн–Мекласкијев поступак: систематски се спајају конјункти који се разликују у једној промењивој, тако се добијају сви прости импликанти (највеће могуће групе), а затим се бира најмањи скуп простих импликаната који покрива све јединице. Тако ради и алат за исказне формуле уз овај уџбеник, у коме вредности функције можете мењати кликом на таблицу истинитости, а на Карноовој мапи сами бирати групе и видети њихове конјункте.

Примере можете отворити и у алату: функција већине, функција са четири промењиве.

Булове алгебре

До сада смо упознали два „рачуна“: скуповни, са унијом, пресеком и комплементом, и исказни, са дисјункцијом, конјункцијом и негацијом. Већ у поглављу о скуповима приметили смо да се њихови закони поклапају:

Табела 3.3: Исти закони у исказном и скуповном рачуну
Закон Исказни рачун Скуповни рачун
Комутативност \(p \lor q \equiv q \lor p\) \(A \cup B = B \cup A\)
Дистрибутивност \(p \land (q \lor r) \equiv (p \land q) \lor (p \land r)\) \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\)
Апсорпција \(p \lor (p \land q) \equiv p\) \(A \cup (A \cap B) = A\)
Де Морганов закон \(\neg(p \lor q) \equiv \neg p \land \neg q\) \((A \cup B)' = A' \cap B'\)
Искључење трећег \(p \lor \neg p \equiv 1\) \(A \cup A' = U\)

Да ли је то случајност? Или постоји општа структура из које се оба рачуна могу извести, тако да сваки закон доказујемо само једном, а он онда важи и за исказе и за скупове? Таква структура постоји и назива се Булова алгебра. Њене операције записујемо неутралним знацима \(+\), \(\cdot\) и \(\overline{\phantom{a}}\), који не подсећају ни на исказе ни на скупове. Исти запис уобичајен је и у дигиталној логици.

Дефиниција 3.12 (Булова алгебра) Булова алгебра је уређена шесторка \((B, +, \cdot, \overline{\phantom{a}}, 0, 1)\) где је:

  • \(B\) скуп који садржи бар два различита елемента, \(0\) и \(1\);
  • \(+\) („сабирање“) и \(\cdot\) („множење“) бинарне операције на скупу \(B\);
  • \(\overline{\phantom{a}}\) („комплемент“) унарна операција на скупу \(B\);

при чему за све \(a, b, c \in B\) важе следеће аксиоме:

Назив Аксиома за \(+\) Аксиома за \(\cdot\)
Комутативност \(a + b = b + a\) \(a \cdot b = b \cdot a\)
Асоцијативност \(a + (b + c) = (a + b) + c\) \(a \cdot (b \cdot c) = (a \cdot b) \cdot c\)
Дистрибутивност \(a + b \cdot c = (a + b) \cdot (a + c)\) \(a \cdot (b + c) = a \cdot b + a \cdot c\)
Неутрални елемент \(a + 0 = a\) \(a \cdot 1 = a\)
Комплемент \(a + \overline{a} = 1\) \(a \cdot \overline{a} = 0\)

Као и у обичној алгебри, множење има предност над сабирањем (\(a + b \cdot c\) значи \(a + (b \cdot c)\)), а тачка се често изоставља: \(a \cdot b\) пишемо \(ab\). Ипак, \(0\) и \(1\) овде нису бројеви, већ само имена два посебна елемента скупа \(B\), а \(+\) и \(\cdot\) нису обично сабирање и множење. Аксиома дистрибутивности \(a + bc = (a + b)(a + c)\), на пример, за бројеве не важи.

Приметимо да аксиоме долазе у паровима: ако у једној од њих заменимо \(+\) са \(\cdot\), \(\cdot\) са \(+\), \(0\) са \(1\) и \(1\) са \(0\), добијамо другу аксиому из пара. Ово својство се назива принцип дуалности и важи за све законе Булове алгебре: пошто је дуал сваке аксиоме опет аксиома, дуалним корацима из доказа било ког закона добија се доказ његовог дуалног закона.

Закони се изводе из аксиома

Из аксиома се, без иједне таблице истинитости и без иједног Веновог дијаграма, изводе сви остали закони. Докажимо, на пример, идемпотентност \(a + a = a\): \[ \begin{aligned} a + a &= (a + a) \cdot 1 && \text{неутрални елемент} \\ &= (a + a)(a + \overline{a}) && \text{комплемент} \\ &= a + a\overline{a} && \text{дистрибутивност} \\ &= a + 0 && \text{комплемент} \\ &= a && \text{неутрални елемент.} \end{aligned} \] По принципу дуалности одмах важи и \(a \cdot a = a\). На исти начин изводе се и остали закони Булове алгебре:

Табела 3.4: Закони Булове алгебре
Назив Закон Дуални закон
Идемпотентност \(a + a = a\) \(a \cdot a = a\)
Ограниченост \(a + 1 = 1\) \(a \cdot 0 = 0\)
Апсорпција \(a + ab = a\) \(a(a + b) = a\)
Двоструки комплемент \(\overline{\overline{a}} = a\)
Де Морганови закони \(\overline{a + b} = \overline{a} \cdot \overline{b}\) \(\overline{a \cdot b} = \overline{a} + \overline{b}\)
Комплементи константи \(\overline{0} = 1\) \(\overline{1} = 0\)

Ово је суштина апстрактног приступа: доказ идемпотентности који смо управо извели истовремено је доказ да је \(p \lor p \equiv p\) у исказном рачуну, да је \(A \cup A = A\) у скуповном рачуну и да исто важи у свакој другој Буловој алгебри — само ако проверимо да она задовољава аксиоме.

Енглески математичар Џорџ Бул (George Boole) је 1854. године у књизи Закони мишљења (An Investigation of the Laws of Thought) први записао логичко закључивање као рачунање са симболима, по угледу на алгебру. Његова идеја је почетак математичке логике, а алгебра која носи његово име деценијама касније постала је математички језик рачунара.

Примери Булових алгебри

Пример 3.21 (Исказни рачун) Скуп \(B = \{0, 1\}\) истинитосних вредности, са операцијама \(a + b = a \lor b\), \(a \cdot b = a \land b\) и \(\overline{a} = \neg a\), је Булова алгебра. Аксиоме су управо таутологије из табеле познатих таутологија. Таблице операција су:

\(a\) \(b\) \(a + b\) \(a \cdot b\)
0 0 0 0
0 1 1 0
1 0 1 0
1 1 1 1

Множење се поклапа са множењем бројева, а сабирање скоро — разлика је само у томе што је \(1 + 1 = 1\). Зато се дисјункција назива и „логичко сабирање“, а конјункција „логичко множење“.

Ово је најважнија Булова алгебра у рачунарству: у поглављу о дигиталној логици видећемо да је то управо алгебра логичких кола. У њеном запису NAND коло рачуна \(Y = \overline{AB}\), NOR коло \(Y = \overline{A + B}\), а полусабирач даје \(S = A\overline{B} + \overline{A}B\) и \(C = AB\).

Пример 3.22 (Скуповни рачун) Нека је \(U\) непразан скуп и \(B = \mathcal{P}(U)\) скуп свих његових подскупова. Са операцијама \(X + Y = X \cup Y\), \(X \cdot Y = X \cap Y\) и \(\overline{X} = X'\) (комплемент у односу на \(U\)), уз \(0 = \emptyset\) и \(1 = U\), \(\mathcal{P}(U)\) је Булова алгебра. Аксиоме су закони из табеле 2.1 у поглављу о скуповима.

За \(U = \{x\}\) ова алгебра има само два елемента, \(\emptyset\) и \(\{x\}\), и понаша се исто као исказни рачун: \(\emptyset\) игра улогу нуле, а \(\{x\}\) улогу јединице.

Булова алгебра не мора да има везе ни са логиком ни са скуповима. Трећи пример је „вештачки“: елементи су природни бројеви, а операције су изабране баш тако да важе аксиоме.

Пример 3.23 (Булова алгебра делилаца броја 30) Нека је \(B = \{1, 2, 3, 5, 6, 10, 15, 30\}\) скуп свих делилаца броја 30 и нека су за \(a, b \in B\) операције дефинисане са \[ a + b = \text{НЗС}(a, b), \qquad a \cdot b = \text{НЗД}(a, b), \qquad \overline{a} = \frac{30}{a}, \] где је НЗС најмањи заједнички садржалац, а НЗД највећи заједнички делилац. Улогу нуле има број 1, а улогу јединице број 30. Тада је \((B, +, \cdot, \overline{\phantom{a}}, 1, 30)\) Булова алгебра.

Комутативност, асоцијативност и дистрибутивност важе за НЗС и НЗД било којих природних бројева. Неутрални елементи су добро изабрани, јер је \(\text{НЗС}(a, 1) = a\) и \(\text{НЗД}(a, 30) = a\) за сваки делилац \(a\) броја 30. Остаје аксиома комплемента: пошто је \(30 = 2 \cdot 3 \cdot 5\) производ различитих простих бројева, \(a\) и \(30/a\) немају заједничких простих чинилаца, па је \[ a + \overline{a} = \text{НЗС}\left(a, \tfrac{30}{a}\right) = 30, \qquad a \cdot \overline{a} = \text{НЗД}\left(a, \tfrac{30}{a}\right) = 1. \] На пример, \(\overline{6} = 5\), па је \(6 + \overline{6} = \text{НЗС}(6, 5) = 30\) и \(6 \cdot \overline{6} = \text{НЗД}(6, 5) = 1\).

Израчунајмо вредност израза \(F = (6 + 10) \cdot \overline{3}\). Прво је \(6 + 10 = \text{НЗС}(6, 10) = 30\) и \(\overline{3} = 30/3 = 10\), па је \[ F = 30 \cdot 10 = \text{НЗД}(30, 10) = 10. \]

Ова алгебра је само „прерушена“ алгебра подскупова скупа \(\{2, 3, 5\}\): сваком делиоцу одговара скуп његових простих чинилаца (на пример, \(6 \leftrightarrow \{2, 3\}\), \(1 \leftrightarrow \emptyset\), \(30 \leftrightarrow \{2, 3, 5\}\)), НЗС одговара унији, НЗД пресеку, а \(30/a\) комплементу.

Сва три примера можемо прегледно упоредити:

Табела 3.5: Три примера Булове алгебре
Булова алгебра \(B\) \(a + b\) \(a \cdot b\) \(\overline{a}\) \(0\) \(1\)
Исказни рачун \(\{0, 1\}\) \(a \lor b\) \(a \land b\) \(\neg a\) \(0\) \(1\)
Скуповни рачун \(\mathcal{P}(U)\) \(X \cup Y\) \(X \cap Y\) \(X'\) \(\emptyset\) \(U\)
Делиоци броја 30 \(\{1, 2, 3, 5, 6, 10, 15, 30\}\) \(\text{НЗС}(a, b)\) \(\text{НЗД}(a, b)\) \(30/a\) \(1\) \(30\)

Исказни рачун и скуповни рачун су, дакле, само различита лица исте структуре, а сваки закон Булове алгебре доказан из аксиома важи у оба. Иста структура описује и логичка кола у процесору, којима се бавимо у следећем поглављу.

Резиме

  • Искази су реченице које су тачне или нетачне. Везнике из говора („није“, „и“, „или“, „ако … онда“, „ако и само ако“) формализујемо операцијама \(\neg, \land, \lor, \Rightarrow, \Leftrightarrow\), задатим таблицама.
  • Исказне формуле граде се по прецизним правилима; њихова вредност при валуацији рачуна се рекурзивно, а све вредности приказује таблица истинитости са \(2^n\) редова.
  • Таутологије су увек тачне формуле. Формуле су еквивалентне ако имају исту вредност при свакој валуацији. Таутологије и еквиваленције доказујемо таблицом, трансформацијама или свођењем на противречност.
  • Семантичка последица описује исправно закључивање; основна правила су модус поненс, модус толенс, хипотетички и дисјунктивни силогизам.
  • Свака формула може се свести на ДНФ и КНФ; проблем задовољивости формуле у КНФ (SAT) један је од кључних проблема рачунарства.
  • Булова функција од \(n\) променљивих пресликава \(\{0,1\}^n\) у \(\{0,1\}\); таквих функција има \(2^{2^n}\), а бинарних операција 16. Свака Булова функција има СДНФ и СКНФ, које се читају директно из таблице.
  • Карноове мапе дају минималну ДНФ и КНФ функције до четири променљиве.
  • Булова алгебра \((B, +, \cdot, \overline{\phantom{a}}, 0, 1)\) је општа структура чији су примери исказни рачун, скуповни рачун и алгебра делилаца броја 30. Закон изведен из аксиома важи у свакој Буловој алгебри, а сви закони важе у паровима (принцип дуалности).

Задаци

Задаци за ово поглавље, са решењима, налазе се у збирци задатака: Исказни рачун.

  1. Ако је импликација тачна, онда је A довољан услов за B, а B је неопходан услов за A.↩︎

  2. Ако је еквиваленција тачна, онда је A неопходан и довољан услов за B и обрнуто.↩︎

  3. Није у КНФ зато што \(\neg(p \lor r)\) није дисјункт.↩︎

  4. У формули се појављују три исказна слова, а у сваком конјункту само два.↩︎