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

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

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

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

  • “Београд је главни град Србије.”
    • Ово је тачан исказ.
  • “5 је непаран број.”
    • Ово је тачан исказ.
  • “2 + 2 = 5.”
    • Ово је нетачан исказ.
  • “Ако данас пада киша, онда ће улица бити мокра.”
    • Тачност овог исказа зависи од временских услова, али је ипак исказ јер може бити оцењен као тачан или нетачан.
  • “Сунце је звезда.”
    • Ово је тачан исказ.

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

  • “Отвори врата.”
    • Ово је заповест или наредба; нема истинитосну вредност.
  • “Како се осећаш данас?”
    • Ово је питање; не може бити оцењено као тачно или нетачно.
  • “Ова реченица је нетачна.”
    • Ово је парадоксална изјава, не може се одредити истинитосна вредност.
  • “x + y = z.”
    • Ово је алгебарски израз без конкретних вредности; није могуће оценити као тачно или нетачно без додатних информација.

Сложени искази могу бити конструисани од једноставних исказа коришћењем логичких везника као што су и, или, конструкција ако…онда, није:

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

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

Исказна алгебра пружа формални оквир за рад са сложеним исказима. Записивање исказа се врши помоћу исказних слова и помоћу симбола логичких операција.

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

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

Операције интуитивне логике у исказној алгебри су:

  1. Негaција (\(\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 \oplus q\)
    1 1 0
    1 0 1
    0 1 1
    0 0 0

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

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

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

Пример

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

  • \(((\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\)

Валуација и вредност исказне формуле

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

Вредност исказне формуле \(F\) је логичка вредност (\(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)\)

Пример

Нека је дата исказна формула: \(F = (p \lor q) \land \neg r\)

Нека је дата валуација \(v\) дефинисана са:

  • \(v(p) = 1\)
  • \(v(q) = 0\)
  • \(v(r) = 1\)

Одредићемо вредност формуле \(F\) под овом валуацијом.

  1. Вредности исказних променљивих:

    • \(v(p) = 1\)
    • \(v(q) = 0\)
    • \(v(r) = 1\)

  2. Рачунање вредности подформула:

    • Дисјункција \(p \lor q\):

      \[ v(p \lor q) = v(p) \lor v(q) = 1 \lor 0 = 1 \]

    • Негaција \(\neg r\):

      \[ v(\neg r) = \neg v(r) = \neg 1 = 0 \]

  3. Вредност формуле \((p \lor q) \land \neg r\):

    \[ v(F) = v(p \lor q) \land v(\neg r) = 1 \land 0 = 0 \]

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

Tабела истинитости вредности

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

Пример

Табела истинитости за формулу \(F\) из претходног примера:

\(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

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

import itertools

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

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 \lor q \Rightarrow \neg r\) може бити написана као p / q -> ~r, као p and q => not r, или као p && q -> !r.

Унесите исказну формулу

Таутологије

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

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

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

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

Назив таутологије Формула
Закон искључења трећег \(p \lor \neg p\)
Закон непротивуречности \(\neg (p \land \neg p)\)
Идемпотентност конјункције \(p \land p \Leftrightarrow p\)
Идемпотентност дисјункције \(p \lor p \Leftrightarrow p\)
Закон двоструке негације \(p \Leftrightarrow \neg \neg p\)
Дистрибутивни закони \(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 \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\)

Логичко закључивање у исказној логици

Нека је \(\Pi=\{F_1,F_2,\dots F_n\}\) скуп исказних формула и \(F\) нека исказна формула. Кажемо да је \(F\) семантичка последица скупа \(\Pi\), ако и само ако не постоји ниједнa валуација \(v\) за које су све формуле из \(\Pi\) имају вредност 1, а \(F\) има вредност 0,: \[ \forall v \quad \text{за које је} \quad v(F_i) = 1 \quad \quad i=1,\dots n \quad \text{онда је} \quad v(F) = 1 \]

Формуле из скупа \(\Pi\) се називају хипотезе или премисе формуле \(F\) а често користимо запис \(F_1,F_2,\dots F_n \models F\)

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

Уколико желимо да проверимо да је неки исказ семантичка последица одређеног скупа премиса можемо користити следећу теорему:

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

Модус поненс и модус толенс

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

\[ p \Rightarrow q,\, p\,\ \models\, q \]

где је:

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

Пример

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

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

\[ p \Rightarrow q,\, \neg q\,\ \models\, \neg p \]

где је:

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

Пример

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

Семантичка еквиваленција формула

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

Пример

На основу табеле познатих таутологија имамо да су формуле \(\neg (p \land q)\) и \(\neg p \lor \neg q\) семантички еквивалентне, и то записујемо \(\neg (p \land q) = \neg p \lor \neg q\).

Једноставно речено две семантички еквивалентне формуле имају исто “значење” у смислу логичке вредности, без обзира на конкретне вредности исказних променљивих. То може бити јако корисно за поједностављивање исказних формула и за доказивање других еквиваленција јер семантичка еквиваленција омогућава замену једне формуле другом у логичким доказима без промене истинитосне вредности. Са друге стране у дигиталној електроници и програмирању, поједностављивање исказних формула може довести до ефикаснијег кода или хардвера.

Лењо израчунавање (енгл. lazy evaluation) је техника у програмирању где се одређене вредности израчунавају тек када су неопходне, а не унапред. Ово омогућава ефикасније коришћење меморије и брже извршавање програма у одређеним случајевима.

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

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

У првој петљи (од 1 до 10) за сваки број позивамо функцију neka_provera, која увек враћа True. У другој петљи, међутим, користимо израз i % 2 == 0 and neka_provera(i). Овде се функција neka_provera позива само ако је први услов i % 2 == 0 испуњен, односно само за парне бројеве. Ово илуструје лењо израчунавање: када први услов није задовољен (број је непаран), Пајтон не позива функцију neka_provera јер резултат израза не може више бити True. Ова техника омогућава ефикасније извршавање програма, јер се необављају непотребна израчунавања.

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

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

Свака исказна променљива или њена негaција назива се литерал. Често се користе и термини позитивни литерал (за исказно слово) и негативни литерала (за негацију исказног слова).

Пример

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

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

У случају да је исказна формула састављена од једног или више литерала повезаних оператором \(\lor\) онда се она назива дисјункт. На пример формула \((p \lor \neg q \lor r)\) је један дисјункт.

За неку исказну формулу кажемо да је написана у дисјунктивној нормалној форми (ДНФ) ако је написана као конјункт или дисјункција више конјункта. Слично за неку исказну формулу кажемо даје у конјунктивној нормалној форми ако је написана као дисјункт или конјункција више дисјункта.

Формалније, можемо рећи да је исказна формула написана у ДНФ ако има облик: \[ (F_1) \lor (F2) \lor \dotsb \lor (F_n) \] где је сваки \(F_i\) конјункт (конјункција једног или више литерала) тј. \[ F_i = l_{i_1} \land l_{i_2} \land \dotsb \land l_{i_m} \] где су \(l_{i_j}\) литерали.

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

Пример

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

  • \((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 ни у ДНФ.

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

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

Пример

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

  • \((\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 = F\) и ако је \(G\) у ДНФ/КНФ/СКНФ/СДНФ, онда за \(G\) кажемо да је ДНФ/КНФ/СКНФ/СДНФ формуле \(F\).

Пример

За формулу \(p \Leftrightarrow q\) формула:

  • \((\neg p \lor q) \land (p \lor \neg q)\) је СКНФ,
  • \((p \land q) \lor (\neg p \land \neg q)\) је СДНФ,

зато што:

\[p \Leftrightarrow q\] \[= (p \Rightarrow q) \land (q \Rightarrow p)\] \[= (\neg p \lor q) \land (p \lor \neg q) \quad\text{СКНФ}\] \[= (\neg p \land p) \lor (\neg p \land \neg q) \lor (q \land p) \lor (q \land \neg q)\quad\text{ДНФ, није СДНФ}\] \[= 0 \lor (\neg p \land \neg q) \lor (p \land q) \lor 0\] \[= (\neg p \land \neg q) \lor (p \land q)\quad\text{СДНФ}\]

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

Дата је исказна формула у конјунктивној нормалној форми (КНФ), а задатак је утврдити да ли постоји валуација таква да дата исказна формула има вредност 1. Ако таква расподела постоји, кажемо да формула задовољива, иначе није.

Овај проблем се назива проблем задовољивости (SAT проблем) и један је од најважнијих и најпознатијих проблема у рачунарству и теорији сложености. SAT проблем је NP-комплетан, што значи да је један од најтежих проблема за које не знамо да ли се могу ефикасно решити за све случајеве. Многи други тешки проблеми из рачунарства, као што су планирање, оптимизација и верификација хардвера, могу се свести на SAT проблем.

Наивно решење, које се огледа у констурисању истинитосне таблице и провери да ли постоји бар једна валуација за коју формула има вредност 1, би у најгорем случају захтевала \(2^n\) провера (где је \(n\) број исказних слова). Дакле број провера расте експоненцијално у односу на број исказних слова.

Главна снага данашњих рачунара огледа се управо у брзом спровођењу сложених рачунских операција, али и најбржем рачунару који постоји у овом тренутку било би потребно више хиљада година непрекидног рада како би на овај начин проверио да ли је исказна формула са 50 исказних слова задовољива или не. Ако претпоставимо да провера једне валуације траје једну милисекунду укупно време извршавања у најгорем случају би било \[2^{50} \cdot 1 = 1 125 899 906 842 624 \text{ милисекунди} \approx 1 125 899 906 842 \text{ секудни} \approx 35 703 \text{ година}.\]

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

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

Булова функција \(n\) променљивих је било које пресликавање скупа уређених \(n\)-торки из скупа \(\{0, 1\}\) у скуп \(\{0, 1\}\), тј. \(f : \{0, 1\}^n \rightarrow \{0, 1\}.\)

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

\(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\) “један функција”

Истим принципом имамо да булових функција са две променљиве има 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, f_2, \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 \oplus q\) “ексклузивна дисјункција”
  • \(f_7(p, q) = p \lor q\) “дисјункција”
  • \(f_8(p, q) = \neg (p \lor 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)\) “негација конјункције” (Шеферова функција)
  • \(f_{15}(p, q) = 1\)

Генерално за сваку Булову функцију са \(n\) променљивих (која је дата помоћу таблице) могуће је одредити бар једну исказну формулу. Како би поједноставили запис, у наставку за позитивне литерале \(p_i\) користићемо ознаку \(p_i^1\) а за негативне литерале \(\neg p_i\) користићемо ознаку \(p_i^0\)

Нека је \(f\) произвољна Булова функција дужине \(n\) која није идентички једнака 0 и нека је \(X\) скуп свих уређених \(n\)-торки из \(\{0, 1\}\) за које \(f\) има вредност 1, тј.

\[ X = \{(x_1, x_2, \dots, x_n) \in \{0, 1\}^n \mid f(x_1, x_2, \dots, x_n) = 1\}. \]

Тада за исказну формулу \(F_1(p_1, p_2, \dots, p_n)\), која је дата са:

\[ 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[F_1(p_1, p_2, \dots, p_n)] = f(v(p_1), v(p_2), \dots, v(p_n)). \]

Нека је \(f\) произвољна Булова функција дужине \(n\) која није идентички једнака 1 и нека је \(Y\) скуп свих уређених \(n\)-торки из \(\{0, 1\}\) за које \(f\) има вредност 0, тј.

\[ Y = \{(x_1, x_2, \dots, x_n) \in \{0, 1\}^n \mid f(x_1, x_2, \dots, x_n) = 0\}. \]

Тада за исказну формулу \(F_2(p_1, p_2, \dots, p_n)\), која је дата са:

\[ 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[F_2(p_1, p_2, \dots, p_n)] = f(v(p_1), v(p_2), \dots, v(p_n)). \]

Пример

Одредити бар једну исказну формулу за Булову функцију \(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

Применом претходна два тврђења имамо:

\(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\) је: \[ F = (p^0 \land q^0 \land r^1) \lor (p^0 \land q^1 \land r^0) \lor (p^1 \land q^0 \land r^1) \lor (p^1 \land q^1 \land r^0) \]

\[ = (\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) \]

Формула у СКНФ за функцију \(f\) је:

\[ F = (p^1 \lor q^1 \lor r^1) \land (p^1 \lor q^0 \lor r^0) \land (p^0 \lor q^1 \lor r^1) \land (p^0 \lor q^0 \lor r^0) \]

\[ = (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) \]

Имплементација функције за исписивање СДНФ за дату исказну формулу дата је у наставку:

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, који нам омогућава генерисање свих могућих комбинација вредности 0 и 1 за променљиве. Конкретно, функција itertools.product((0, 1), repeat=n) креира све n-торке, где свака комбинација представља једну валуацију променљивих (на пример, за три променљиве добијамо (0, 0, 0), (0, 0, 1), (0, 1, 0) и тако даље).

Функција sdnf(F, n, iskazna_slova=["p", "q", "r", "s", "t"]) пролази кроз све могуће валуације које генеришемо помоћу itertools.product. За сваку од тих валуација проверавамо да ли функција F враћа вредност True. Ако је вредност True, креирамо листу литерала за ту валуацију: - ако је вредност променљиве 0, додајемо негативан литерал (нпр. ¬p), - ако је 1, додајемо позитиван литерал (нпр. p).

Те литерале затим спајамо оператором конјункције (∧) у један конјункт са konjunkcija.join(literali_za_konjunkt) и додајемо у листу konjunkti. На крају, све конјункте из те листе спајамо оператором дисјункције (∨), чиме добијамо испис исказне формуле у СДНФ.

Примери коришћења функције 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)

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

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

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

  4. у формули се појавуљују укупно три исказна слова а у сваком конјункту само два па из тог разлога није написана у СДНФ.↩︎