5  Предикатски рачун

Исказни рачун посматра исказе као целине и не види шта се у њима тврди. Зато у њему не можемо записати ни тако једноставан закључак као што је „Сви људи су смртни. Сократ је човек. Дакле, Сократ је смртан.“ — сва три исказа су различита слова, а веза између њих се губи. Предикатски рачун „отвара“ исказе: уводи променљиве, особине и односе међу објектима и квантификаторе „за свако“ и „постоји“. То је језик у коме су записане математичке дефиниције и теореме, али и упити над базама података, спецификације програма и правила система вештачке интелигенције.

Предикати

У поглављу о исказном рачуну видели смо да реченица „\(x + y = z\)“ није исказ, јер њену тачност не можемо да оценимо док не знамо вредности \(x\), \(y\) и \(z\). Када те вредности задамо, реченица постаје исказ: за \(x = 1\), \(y = 3\), \(z = 4\) тачан, а за \(x = 2\), \(y = 5\), \(z = 1\) нетачан. Оваквим реченицама бавимо се у овом поглављу.

Дефиниција 5.1 (Предикат) Предикат је реченица која садржи једну или више променљивих и која постаје исказ када се свакој променљивој додели конкретна вредност из унапред задатог непразног скупа, домена. Предикат са \(n\) променљивих називамо \(n\)-арним и записујемо \(P(x_1, \dots, x_n)\).

Пример 5.1 Нека је домен скуп реалних бројева.

  • \(P_1(x)\colon\ x^2 > 0\) — нетачан за \(x = 0\), а тачан за свако друго \(x\).
  • \(P_2(x)\colon\ e^x \neq 0\) — тачан за свако \(x\).
  • \(P_3(x, y, z)\colon\) „ако је \(x > y\), онда је \(x \cdot z > y \cdot z\)“ — нетачан када је \(x > y\) и \(z \le 0\), а у свим осталим случајевима тачан.

Предикати не морају бити математички. Ако је домен скуп студената, \(S(x)\): „\(x\) је положио ДМС“ је унарни, а \(D(x, y)\): „\(x\) и \(y\) су у истој групи“ бинарни предикат.

Домен је део предиката: исти запис може имати различиту истинитост на различитим доменима. Предикат \(P_1(x)\) је на скупу реалних бројева некад тачан, а некад нетачан, док је на скупу природних бројева \(\mathbb{N} = \{1, 2, 3, \dots\}\) увек тачан.

Унарни предикат \(P(x)\) на домену \(D\) одређује скуп \(\{x \in D \mid P(x)\}\) оних елемената за које је тачан — управо тако смо у поглављу о скуповима задавали скупове описом. Бинарни предикат на исти начин одређује скуп уређених парова, тј. релацију, чиме ћемо се бавити у поглављу о релацијама.

Квантификатори

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

Дефиниција 5.2 (Квантификатори) Нека је \(P(x)\) предикат на домену \(D\).

  • Универзални квантификатор \(\forall\) чита се „за свако“: исказ \((\forall x)\, P(x)\) је тачан ако је \(P(x)\) тачан за сваку вредност \(x \in D\).
  • Егзистенцијални квантификатор \(\exists\) чита се „постоји“: исказ \((\exists x)\, P(x)\) је тачан ако је \(P(x)\) тачан за бар једну вредност \(x \in D\).

Квантификован предикат има истинитосну вредност — он је исказ. Код предиката са више променљивих исказ добијамо тек када је свака променљива квантификована или замењена конкретном вредношћу.

Да бисмо показали да је \((\exists x)\, P(x)\) тачно, довољан је један сведок: вредност \(x\) за коју \(P(x)\) важи. Да бисмо показали да је \((\forall x)\, P(x)\) нетачно, довољан је један контрапример: вредност \(x\) за коју \(P(x)\) не важи. Обрнуто је тешко: тачност \((\forall x)\, P(x)\) не доказује никакав број примера — потребан је доказ за произвољно \(x\).

На коначном домену \(D = \{d_1, d_2, \dots, d_n\}\) квантификатори су само скраћени запис дугих конјункција и дисјункција: \[ (\forall x)\, P(x) \equiv P(d_1) \land P(d_2) \land \dots \land P(d_n), \qquad (\exists x)\, P(x) \equiv P(d_1) \lor P(d_2) \lor \dots \lor P(d_n). \] На бесконачном домену такав запис није могућ, и зато су квантификатори суштински нови појам.

Пример 5.2  

  • „За сваки природан број \(n\) важи \(n > 2\)“, тј. \((\forall n)\, n > 2\) на домену \(\mathbb{N}\) — нетачан исказ; контрапример је \(n = 1\).
  • „Постоји природан број \(n\) за који важи \(n > 2\)“, тј. \((\exists n)\, n > 2\) — тачан исказ; сведок је \(n = 3\).
  • „За сваки реалан број \(x\) постоји реалан број \(y\) за који је \(x + y = 0\)“, тј. \((\forall x)(\exists y)\, x + y = 0\) на домену \(\mathbb{R}\) — тачан исказ; за дато \(x\) сведок је \(y = -x\).

Ограничени квантификатори

У математици често квантификујемо само по делу домена: „за сваки прост број“, „постоји паран број“. Пишемо \((\forall x \in A)\, P(x)\) и \((\exists x \in A)\, P(x)\), а ови записи су скраћенице: \[ (\forall x \in A)\, P(x) \equiv (\forall x)\big(x \in A \Rightarrow P(x)\big), \qquad (\exists x \in A)\, P(x) \equiv (\exists x)\big(x \in A \land P(x)\big). \] Уз универзални квантификатор иде импликација, а уз егзистенцијални конјункција. Ово правило се лако заборави, а последице су озбиљне.

Честа грешка: погрешан везник уз квантификатор

Нека је домен скуп природних бројева. Реченица „Сваки прост број је непаран“ записује се \((\forall x)\big(\text{Прост}(x) \Rightarrow \text{Непаран}(x)\big)\) и нетачна је (контрапример \(x = 2\)).

  • Запис \((\forall x)\big(\text{Прост}(x) \land \text{Непаран}(x)\big)\) тврди нешто сасвим друго: да је сваки природан број прост и непаран.
  • Запис \((\exists x)\big(\text{Прост}(x) \Rightarrow \text{Паран}(x)\big)\) није запис реченице „Неки прост број је паран“: тачан је већ због \(x = 1\), јер 1 није прост број, па је импликација тачна. Исправан запис је \((\exists x)\big(\text{Прост}(x) \land \text{Паран}(x)\big)\).

Изаберите формулу и домен. Поља у којима је формула под квантификатором тачна су тиркизна, а остала црвена; уоквирен је сведок, односно контрапример. Кликом на број га додајете у домен или уклањате из њега — тако видите како иста формула мења истинитост на различитим доменима.

Превођење реченица на језик логике

Превођење реченица говора у формуле је вештина која се стиче вежбом. Помаже да прво одредимо домен и предикате, а затим да реченицу прочитамо „логички“: сви су нешто — \(\forall\) и импликација; неки јесу нешто — \(\exists\) и конјункција; нико није нешто — \(\forall\) и импликација са негацијом.

Пример 5.3 Нека је домен скуп свих људи, \(S(x)\): „\(x\) је студент“ и \(P(x)\): „\(x\) је положио ДМС“.

Табела 5.1: Четири основна облика тврђења
Реченица Формула
Сви студенти су положили ДМС. \((\forall x)\big(S(x) \Rightarrow P(x)\big)\)
Неки студенти су положили ДМС. \((\exists x)\big(S(x) \land P(x)\big)\)
Ниједан студент није положио ДМС. \((\forall x)\big(S(x) \Rightarrow \neg P(x)\big)\)
Нису сви студенти положили ДМС. \((\exists x)\big(S(x) \land \neg P(x)\big)\)

Ако је \(Z(x, y)\): „\(x\) зна \(y\)“, онда је „Свако зна неког“ \((\forall x)(\exists y)\, Z(x, y)\), а „Постоји неко кога сви знају“ \((\exists y)(\forall x)\, Z(x, y)\). Ове две реченице тврде различите ствари, што је тема следећег одељка.

Редослед квантификатора

Два квантификатора исте врсте смеју да замене места: \((\forall x)(\forall y)\, P(x, y)\) и \((\forall y)(\forall x)\, P(x, y)\) тврде исто, а исто важи и за \(\exists\). Квантификатори различите врсте не смеју да замене места.

У \((\forall x)(\exists y)\, P(x, y)\) сведок \(y\) бира се после \(x\) и може да зависи од њега. У \((\exists y)(\forall x)\, P(x, y)\) мора постојати један исти \(y\) који одговара свим \(x\). На домену \(\mathbb{R}\) је \((\forall x)(\exists y)\, x + y = 0\) тачно (за свако \(x\) узмемо \(y = -x\)), а \((\exists y)(\forall x)\, x + y = 0\) нетачно — не постоји број који би био супротан свим бројевима истовремено.

Друго тврђење је јаче: ако постоји један \(y\) који одговара свим \(x\), онда за свако \(x\) постоји \(y\) (баш тај). Зато увек важи \[ (\exists y)(\forall x)\, P(x, y) \Rightarrow (\forall x)(\exists y)\, P(x, y), \] а обрнута импликација у општем случају не важи.

Релација „\(x\) воли \(y\)“ на домену од четири особе задата је таблицом: у реду \(x\) и колони \(y\) је 1 ако \(x\) воли \(y\). Формула \((\forall x)(\exists y)\) захтева јединицу у сваком реду, а \((\exists y)(\forall x)\) колону пуну јединица. Кликом на поље мењате релацију, а превлачењем миша преко формуле видите њеног сведока или контрапример.

Негација квантификованих исказа

Шта значи „Није тачно да постоји \(x\) за које важи \(P(x)\)“? Да ниједно \(x\) не задовољава \(P(x)\), тј. да за свако \(x\) важи \(\neg P(x)\). Слично, „Није тачно да за свако \(x\) важи \(P(x)\)“ значи да постоји \(x\) за које \(P(x)\) не важи.

Теорема 5.1 (Де Морганови закони за квантификаторе) \[ \neg (\forall x)\, P(x) \equiv (\exists x)\, \neg P(x), \qquad \neg (\exists x)\, P(x) \equiv (\forall x)\, \neg P(x). \]

На коначном домену ово су баш Де Морганови закони исказног рачуна: негација конјункције \(P(d_1) \land \dots \land P(d_n)\) је дисјункција негација. Правило гласи: када негацију провлачимо кроз квантификатор, \(\forall\) прелази у \(\exists\) и обрнуто, а негација наставља ка унутрашњости формуле.

Пример 5.4 Исказ „Не постоји највећи природан број“ записујемо \(\neg (\exists n)(\forall m)\, n \geq m\). Провлачењем негације добијамо \[ \neg (\exists n)(\forall m)\, n \geq m \equiv (\forall n)\, \neg (\forall m)\, n \geq m \equiv (\forall n)(\exists m)\, \neg(n \geq m) \equiv (\forall n)(\exists m)\, n < m, \] што читамо „За сваки природан број постоји већи од њега“.

Негација исказа „Сви студенти су положили ДМС“ није „Ниједан студент није положио ДМС“, већ „Бар један студент није положио ДМС“: \[ \neg (\forall x)\big(S(x) \Rightarrow P(x)\big) \equiv (\exists x)\, \neg\big(S(x) \Rightarrow P(x)\big) \equiv (\exists x)\big(S(x) \land \neg P(x)\big). \] Користили смо еквиваленцију \(\neg(A \Rightarrow B) \equiv A \land \neg B\) из исказног рачуна.

Језик предикатског рачуна

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

У предикатским формулама јављају се:

  • симболи променљивих и константи,
  • операцијски (функцијски) симболи,
  • релацијски симболи,
  • симболи логичких операција \(\neg\), \(\land\), \(\lor\), \(\Rightarrow\), \(\Leftrightarrow\),
  • квантификатори \(\forall\) и \(\exists\), и
  • помоћни симболи: заграде и зарези.

Дефиниција 5.3 (Језик првог реда) Језик првог реда је четворка \((Fun, Rel, Const, Ar)\), где је \(Const\) скуп симбола константи, \(Fun\) скуп операцијских симбола, \(Rel\) скуп релацијских симбола, а \(Ar\colon Fun \cup Rel \to \mathbb{N}\) функција која сваком операцијском и релацијском симболу додељује дужину (арност), тј. број аргумената.

За константе користимо ознаке \(a, b, c, a_1, \dots\), за операцијске симболе \(f, g, h, f_1, \dots\), за релацијске симболе \(\alpha, \beta, \gamma, \rho, \dots\), а за променљиве \(x, y, z, x_1, \dots\) Симболи језика немају унапред значење: \(f\) није ни сабирање ни множење, већ само знак са два аргумента. Значење добијају тек у интерпретацији.

Дефиниција 5.4 (Терм) Терми (изрази) су низови симбола који се граде коначном применом правила:

  1. симболи променљивих и константи су терми;
  2. ако су \(t_1, \dots, t_n\) терми и \(f\) операцијски симбол дужине \(n\), онда је и \(f(t_1, \dots, t_n)\) терм.

Пример 5.5 Ако је \(f\) бинарни и \(g\) унарни операцијски симбол, \(x\) и \(y\) променљиве и \(c\) константа, онда су \(c\), \(x\), \(g(y)\), \(f(c, g(x))\) и \(g(f(g(c), y))\) терми, а \()f\,x\,y)\), \((c\,x)\), \(f(g)\,y\), \(f(x)\) и \(g(x, y)\) нису (\(f\) мора имати два, а \(g\) један аргумент). Уместо \(f(x, y)\) често пишемо \(x \mathbin{f} y\), као што пишемо \(x + y\) уместо \(+(x, y)\).

Терм означава објекат домена (број, скуп, особу), а не тврђење. Тврђења настају од терма помоћу релацијских симбола.

Дефиниција 5.5 (Предикатска формула) Ако су \(t_1, \dots, t_n\) терми и \(\alpha\) релацијски симбол дужине \(n\), онда је \(\alpha(t_1, \dots, t_n)\) елементарна формула; елементарна формула је и \(t_1 = t_2\). Предикатске формуле граде се коначном применом правила:

  1. елементарна формула је предикатска формула;
  2. ако је \(F\) формула, онда је и \(\neg F\) формула;
  3. ако су \(F\) и \(G\) формуле, онда су и \((F \land G)\), \((F \lor G)\), \((F \Rightarrow G)\) и \((F \Leftrightarrow G)\) формуле;
  4. ако је \(F\) формула и \(x\) променљива, онда су и \((\forall x) F\) и \((\exists x) F\) формуле.

Заграде изостављамо по истим правилима као у исказном рачуну, уз договор да квантификатори, као и негација, везују најјаче: \((\forall x)\, F \land G\) значи \(\big((\forall x)\, F\big) \land G\). Ако квантификатор треба да се односи на већи део формуле, тај део стављамо у заграде: \((\forall x)(F \land G)\).

Пример 5.6 Нека је \(Ar(f) = 1\), \(Ar(g) = 2\), \(Ar(h) = 3\) и \(Ar(\alpha) = 2\), \(x, y, z\) променљиве и \(a, b\) константе.

  • \(\alpha(x, y)\), \(\alpha(f(x), a)\) и \(g(x, a) = f(y)\) су елементарне формуле.
  • \(\alpha\big(x, f(g(y, a))\big)\) и \((\exists y)\big(x = y \Rightarrow (\forall x)\, \alpha(x, a)\big)\) су предикатске формуле.
  • \(\alpha\big(a, g(x, h(a, b, f(x)))\big) \Rightarrow (\exists x)(\forall z)\big(z = a \lor (\forall y)\, x = f(y)\big)\) је предикатска формула.
  • \(\alpha(x)\) и \((\forall f)\, f(x) = x\) нису формуле: \(\alpha\) има два аргумента, а у логици првог реда не квантификујемо по функцијама.

Слободна и везана појављивања променљивих

Подформула \(F\) у формули \((\forall x) F\), односно \((\exists x) F\), назива се домет квантификатора. Појављивање променљиве \(x\) је везано ако се налази у домету неког квантификатора по \(x\), а иначе је слободно.

Променљива је слободна у формули ако има бар једно слободно појављивање, а везана ако су сва њена појављивања везана. Формула без слободних променљивих је затворена и при задатој интерпретацији представља исказ. Формулу \(F\) са слободним променљивим \(x_1, \dots, x_n\) зовемо отвореном и записујемо \(F(x_1, \dots, x_n)\) — њена тачност зависи од вредности тих променљивих, као код предиката.

Разлику познајемо из математике. У \(\sum_{i=1}^{n} i^2\) променљива \(i\) је везана, а \(n\) слободна: вредност израза зависи од \(n\), а не од \(i\), и \(i\) смемо да преименујемо у \(k\) без промене значења. Исто важи за \(x\) у \(\int_0^1 x^2\,dx\) и у \(\{x \mid x > 3\}\). У програмирању везаној променљивој одговара локална променљива, на пример бројач петље, а слободној — параметар или глобална променљива.

Пример 5.7  

Формула Слободне променљиве Ознака
\((\forall x)\, x = y \lor (\exists y)\, \neg y = z \land (\forall z)\, x = z\) \(x, y, z\) \(F(x, y, z)\)
\((\forall x)\big(x = y \lor (\exists y)\, \neg y = z\big)\) \(y, z\) \(F(y, z)\)
\((\forall x)\big(x = z \lor (\exists y)\, \neg y = z\big)\) \(z\) \(F(z)\)
\((\forall x)\big((\exists y)\, x = y \lor (\exists z)\, \neg x = z\big)\) нема затворена

У првој формули квантификатор \((\forall x)\) се односи само на \(x = y\), па је последње појављивање \(x\) (у \(x = z\)) слободно. Иста променљива може у истој формули имати и слободна и везана појављивања.

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

Интерпретација и вредност формуле

Формула \(\alpha(f(x, y), c)\) сама по себи није ни тачна ни нетачна — не знамо шта значе \(\alpha\), \(f\) и \(c\), нити по ком скупу се крећу \(x\) и \(y\). Тек када то одредимо, формула добија смисао.

Пример 5.8 Иста формула \(\alpha(f(x, y), c)\) при различитим тумачењима симбола:

  • \(x + y < 3\) — домен \(\mathbb{R}\), \(f\) је сабирање, \(\alpha\) је релација \(<\), \(c\) је 3;
  • \(x \cup y = \emptyset\) — домен је скуп свих подскупова неког скупа, \(f\) је унија, \(\alpha\) је једнакост, \(c\) је празан скуп;
  • \(x \lor y = 0\) — домен \(\{0, 1\}\), \(f\) је дисјункција, \(\alpha\) је једнакост, \(c\) је 0.

Дефиниција 5.6 (Интерпретација) Интерпретација језика првог реда је уређени пар \(L = (D, I)\), где је \(D\) непразан скуп (домен), а \(I\) пресликавање које:

  1. сваком симболу константе \(c\) додељује елемент \(I(c) \in D\);
  2. сваком операцијском симболу \(f\) дужине \(n\) додељује операцију \(I(f)\colon D^n \to D\);
  3. сваком релацијском симболу \(\alpha\) дужине \(n\) додељује релацију \(I(\alpha) \subseteq D^n\).

Пример 5.9 Нека су \(f\) и \(g\) бинарни операцијски симболи, \(\rho\) бинарни релацијски симбол и \(a\) и \(b\) константе. Једна интерпретација овог језика је: \(D = \mathbb{R}\), \(I(f)\) је сабирање, \(I(g)\) множење, \(I(\rho)\) релација \(<\), \(I(a) = 0\) и \(I(b) = 1\). У њој формула \(\rho\big(a, g(x, x)\big) \lor x = a\) гласи \(0 < x \cdot x \lor x = 0\).

Да бисмо израчунали вредност отворене формуле, потребне су нам још и вредности слободних променљивих. Валуација при интерпретацији \(L = (D, I)\) је пресликавање \(v\) које свакој променљивој додељује елемент домена. У исказном рачуну валуација је исказним словима додељивала вредности из \(\{0, 1\}\); сада променљиве добијају вредности из \(D\).

Дефиниција 5.7 (Вредност терма) Вредност терма \(t\) при интерпретацији \(L\) и валуацији \(v\), у ознаци \(L_v(t)\), дефинише се рекурзивно:

  1. \(L_v(c) = I(c)\) за константу \(c\);
  2. \(L_v(x) = v(x)\) за променљиву \(x\);
  3. \(L_v\big(f(t_1, \dots, t_n)\big) = I(f)\big(L_v(t_1), \dots, L_v(t_n)\big)\).

Пример 5.10 Нека је \(L = (\mathbb{Z}, I)\), \(I(f) = +\), \(I(g) = \cdot\), \(I(c) = 3\) и \(v(x) = 2\), \(v(y) = 5\). Тада је \[ L_v\big(f(x, g(y, c))\big) = 2 + 5 \cdot 3 = 17. \]

Дефиниција 5.8 (Вредност формуле) Вредност формуле при интерпретацији \(L\) и валуацији \(v\) је елемент скупа \(\{0, 1\}\):

  1. \(L_v(t_1 = t_2) = 1\) ако и само ако је \(L_v(t_1) = L_v(t_2)\);
  2. \(L_v\big(\alpha(t_1, \dots, t_n)\big) = 1\) ако и само ако је \(\big(L_v(t_1), \dots, L_v(t_n)\big) \in I(\alpha)\);
  3. вредности формула \(\neg F\), \(F \land G\), \(F \lor G\), \(F \Rightarrow G\) и \(F \Leftrightarrow G\) рачунају се из вредности \(F\) и \(G\) као у исказном рачуну;
  4. \(L_v\big((\forall x) F\big) = 1\) ако и само ако је \(L_w(F) = 1\) за сваку валуацију \(w\) која се од \(v\) разликује највише у вредности \(x\);
  5. \(L_v\big((\exists x) F\big) = 1\) ако и само ако је \(L_w(F) = 1\) за бар једну такву валуацију \(w\).

Правила 4 и 5 кажу оно што смо интуитивно већ знали: при рачунању \((\forall x)\,F\) вредност \(x\) пролази кроз цео домен, а вредности осталих (слободних) променљивих остају какве јесу. Зато вредност затворене формуле не зависи од валуације.

Ако је \(L_v(F) = 1\) за сваку валуацију \(v\), кажемо да је формула \(F\) тачна у интерпретацији \(L\), а за интерпретацију \(L\) да је модел формуле \(F\).

Пример 5.11 Посматрајмо затворену формулу \((\exists x)(\forall y)\, \alpha(x, y)\) при три интерпретације у којима је \(\alpha\) релација \(\le\).

  • \(D = \{1, 2, 3\}\): формула тврди да постоји најмањи елемент. Тачна је, са сведоком \(x = 1\), јер је \(1 \le 1\), \(1 \le 2\) и \(1 \le 3\). Пошто је домен коначан, формулу можемо записати и без квантификатора, као дисјункцију три конјункције.
  • \(D = \mathbb{N}\): тачна, сведок је \(x = 1\).
  • \(D = \mathbb{Z}\): нетачна, јер за свако \(x\) је \(y = x - 1\) мање од њега.

Иста формула је тачна у неким, а нетачна у другим интерпретацијама — она није ни ваљана ни противречна.

Ваљане формуле

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

Дефиниција 5.9 (Ваљана, задовољива и еквивалентне формуле) Формула \(F\) је ваљана (логички истинита) ако је \(L_v(F) = 1\) за сваку интерпретацију \(L\) и сваку валуацију \(v\). Формула је задовољива ако је \(L_v(F) = 1\) за бар једну интерпретацију \(L\) и валуацију \(v\), а противречна ако није задовољива. Формуле \(F\) и \(G\) су еквивалентне, \(F \equiv G\), ако је \(F \Leftrightarrow G\) ваљана формула.

Свака таутологија исказног рачуна даје ваљане формуле: ако у таутологију уместо слова уврстимо предикатске формуле, добијамо ваљану формулу. На пример, \((F \Rightarrow G) \Leftrightarrow (\neg F \lor G)\) и \(\neg(F \land G) \Leftrightarrow (\neg F \lor \neg G)\) су ваљане за све формуле \(F\) и \(G\). Поред њих важе и закони који су својствени квантификаторима.

Табела 5.2: Неке ваљане формуле предикатског рачуна
Закон Ваљана формула
Де Морганови закони \(\neg(\forall x)\, F \Leftrightarrow (\exists x)\, \neg F\), \(\quad \neg(\exists x)\, F \Leftrightarrow (\forall x)\, \neg F\)
Замена истих квантификатора \((\forall x)(\forall y)\, F \Leftrightarrow (\forall y)(\forall x)\, F\), \(\quad (\exists x)(\exists y)\, F \Leftrightarrow (\exists y)(\exists x)\, F\)
Различити квантификатори \((\exists x)(\forall y)\, F \Rightarrow (\forall y)(\exists x)\, F\) (само у овом смеру)
\(\forall\) и конјункција \((\forall x)(F \land G) \Leftrightarrow (\forall x)\, F \land (\forall x)\, G\)
\(\exists\) и дисјункција \((\exists x)(F \lor G) \Leftrightarrow (\exists x)\, F \lor (\exists x)\, G\)
\(\forall\) и дисјункција \((\forall x)\, F \lor (\forall x)\, G \Rightarrow (\forall x)(F \lor G)\) (само у овом смеру)
\(\exists\) и конјункција \((\exists x)(F \land G) \Rightarrow (\exists x)\, F \land (\exists x)\, G\) (само у овом смеру)
Извлачење испред квантификатора, ако \(x\) није слободна у \(G\) \((\forall x)(F \lor G) \Leftrightarrow (\forall x)\, F \lor G\), \(\quad (\exists x)(F \land G) \Leftrightarrow (\exists x)\, F \land G\)
Преименовање везане променљиве, ако се \(y\) не јавља у \(F(x)\) \((\forall x)\, F(x) \Leftrightarrow (\forall y)\, F(y)\), \(\quad (\exists x)\, F(x) \Leftrightarrow (\exists y)\, F(y)\)
Од општег ка појединачном \((\forall x)\, F(x) \Rightarrow F(t)\), \(\quad F(t) \Rightarrow (\exists x)\, F(x)\), \(\quad (\forall x)\, F \Rightarrow (\exists x)\, F\)

Последња формула у табели важи зато што је домен увек непразан. У закону „од општег ка појединачном“ \(F(t)\) је формула добијена када се сва слободна појављивања \(x\) у \(F(x)\) замене термом \(t\), при чему ниједна променљива терма \(t\) не сме да постане везана.

Како показати да формула није ваљана

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

Пример 5.12 Покажимо да обрнута импликација у закону о различитим квантификаторима није ваљана, тј. да формула \[ (\forall y)(\exists x)\, \alpha(x, y) \Rightarrow (\exists x)(\forall y)\, \alpha(x, y) \] није ваљана. Нека је \(D = \mathbb{N}\) и \(\alpha\) релација \(>\). Претпоставка „за сваки број постоји већи“ је тачна, а закључак „постоји број већи од свих“ нетачан, па је импликација нетачна.

Слично, \((\forall x)(F \lor G) \Rightarrow (\forall x)\, F \lor (\forall x)\, G\) није ваљана: на домену \(\mathbb{N}\), где је \(F\) „\(x\) је паран“ и \(G\) „\(x\) је непаран“, сваки број је паран или непаран, али нису сви бројеви парни, нити су сви непарни.

Закључивање у предикатском рачуну

Формула \(G\) је логичка последица формула \(F_1, \dots, F_n\) ако је \(G\) тачна у свакој интерпретацији у којој су тачне све формуле \(F_1, \dots, F_n\). Правила закључивања из исказног рачуна (модус поненс, модус толенс, силогизми) и даље важе, а додају им се правила за квантификаторе:

  • универзална инстанцијација: из \((\forall x)\, F(x)\) следи \(F(c)\) за сваку константу \(c\);
  • егзистенцијална генерализација: из \(F(c)\) следи \((\exists x)\, F(x)\).

Пример 5.13 Закључак са почетка поглавља сада можемо записати и проверити. Нека је \(s\) константа „Сократ“: \[ (\forall x)\big(\text{Човек}(x) \Rightarrow \text{Смртан}(x)\big),\ \text{Човек}(s) \models \text{Смртан}(s). \] Универзалном инстанцијацијом из прве претпоставке добијамо \(\text{Човек}(s) \Rightarrow \text{Смртан}(s)\), а модус поненсом са \(\text{Човек}(s)\) закључак \(\text{Смртан}(s)\).

Закључак „Сви програмери знају логику. Ана зна логику. Дакле, Ана је програмер.“ није исправан: из \((\forall x)\big(P(x) \Rightarrow L(x)\big)\) и \(L(a)\) не следи \(P(a)\). Контрамодел: домен \(\{a\}\), при чему \(a\) зна логику и није програмер — обе претпоставке су тачне, а закључак нетачан. То је предикатски облик грешке „потврђивање последице“ из исказног рачуна.

Логика квантификатора почиње 1879. године књигом „Појмовно писмо“ (Begriffsschrift) немачког математичара Готлоба Фрегеа (Gottlob Frege), који је први увео квантификоване променљиве. Пре тога је више од две хиљаде година владала Аристотелова логика силогизама, заснована управо на четири облика тврђења из табеле 5.1. Курт Гедел (Kurt Gödel) је 1929. доказао да се свака ваљана формула може извести из аксиома коначним поступком (теорема о потпуности). Алонзо Черч (Alonzo Church) и Алан Тјуринг (Alan Turing) су 1936. независно показали да, за разлику од исказног рачуна, не постоји алгоритам који за произвољну предикатску формулу одлучује да ли је ваљана. Тај резултат је један од темеља теорије израчунљивости.

Примене

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

Математичке дефиниције

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

Функција \(f\colon A \to B\) је инјективна ако различите елементе слика у различите, а сурјективна ако је сваки елемент скупа \(B\) слика неког елемента: \[ (\forall x_1 \in A)(\forall x_2 \in A)\big(f(x_1) = f(x_2) \Rightarrow x_1 = x_2\big), \qquad (\forall y \in B)(\exists x \in A)\, f(x) = y. \] Редослед квантификатора у дефиницији сурјекције је битан: \((\exists x \in A)(\forall y \in B)\, f(x) = y\) би значило да један исти \(x\) има све елементе скупа \(B\) за слике, што је могуће само ако \(B\) има један елемент.

Низ \((a_n)\) тежи ка \(a\) ако \[ (\forall \varepsilon > 0)(\exists N \in \mathbb{N})(\forall n \geq N)\ |a_n - a| < \varepsilon , \] тј. за сваку, ма колико малу, тачност \(\varepsilon\) чланови низа од неког места надаље остају ближи броју \(a\) од \(\varepsilon\). Негацијом добијамо шта значи да низ не тежи ка \(a\): \[ (\exists \varepsilon > 0)(\forall N \in \mathbb{N})(\exists n \geq N)\ |a_n - a| \geq \varepsilon . \] На пример, низ \(a_n = (-1)^n\) не тежи ка 1: за \(\varepsilon = 1\) и свако \(N\) постоји непарно \(n \ge N\), а за њега је \(|a_n - 1| = 2 \ge 1\).

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

Програмирање: all и any

На коначном домену квантификатор је петља: \((\forall x \in D)\, P(x)\) проверава да ли је \(P(x)\) тачно за сваки елемент листе, а \((\exists x \in D)\, P(x)\) да ли је тачно за бар један. У Пајтону то раде уграђене функције all и any.

Квантификатори у Пајтону. Функција all враћа True ако су сви елементи тачни, а any ако је бар један тачан. Импликацију \(A \Rightarrow B\) пишемо као not A or B.

D = range(1, 17)

def prost(n):
    return n > 1 and all(n % d != 0 for d in range(2, n))

# (∀x)(Прост(x) ⇒ Непаран(x)) — „сваки прост број је непаран“
print(all(not prost(x) or x % 2 == 1 for x in D))

# контрапримери: прости бројеви који нису непарни
print([x for x in D if prost(x) and x % 2 == 0])

# Де Морганов закон: ¬(∀x) Прост(x) ≡ (∃x) ¬Прост(x)
print((not all(prost(x) for x in D)) == any(not prost(x) for x in D))

# редослед квантификатора на домену {-3, ..., 3}
Z = range(-3, 4)
print(all(any(x + y == 0 for y in Z) for x in Z))   # (∀x)(∃y) x + y = 0
print(any(all(x + y == 0 for x in Z) for y in Z))   # (∃y)(∀x) x + y = 0
False
[2]
True
True
False

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

Ако је домен празан, all([]) враћа True, а any([]) враћа False. То одговара логици: тврђење \((\forall x \in A)\, P(x)\), тј. \((\forall x)(x \in A \Rightarrow P(x))\), тачно је када је \(A\) празан, јер је импликација са нетачном претпоставком тачна. Кажемо да је такво тврђење тривијално (празно) тачно.

Базе података

Упит над базом података је предикат: база враћа све редове табеле за које је услов у делу WHERE тачан. Нека база има табеле student, predmet и polozio (која садржи парове студент–предмет). Студенти који су положили бар један предмет задовољавају \((\exists p)\, \text{Положио}(s, p)\), што се у језику SQL пише са EXISTS:

SELECT ime FROM student s
WHERE EXISTS (SELECT * FROM polozio p WHERE p.student_id = s.id);

SQL нема универзални квантификатор. Студенте који су положили све предмете налазимо помоћу Де Моргановог закона: \((\forall m)\, \text{Положио}(s, m) \equiv \neg (\exists m)\, \neg \text{Положио}(s, m)\) — „не постоји предмет који студент није положио“:

SELECT ime FROM student s
WHERE NOT EXISTS (
    SELECT * FROM predmet m
    WHERE NOT EXISTS (
        SELECT * FROM polozio p
        WHERE p.student_id = s.id AND p.sifra = m.sifra));

Релациони модел база података је од почетка заснован на предикатском рачуну, а двострука негација NOT EXISTS … NOT EXISTS је стандардан начин да се у SQL-у запише „за свако“.

Спецификација и провера програма

Шта програм треба да уради може се прецизно рећи предикатским формулама: предуслов описује исправне улазе, а постуслов шта мора да важи за резултат. На пример, после сортирања низа \(a_0, a_1, \dots, a_{n-1}\) мора да важи \[ (\forall i)\big(0 \le i < n - 1 \Rightarrow a_i \le a_{i+1}\big), \] а бинарна претрага има баш то као предуслов. У коду се такви услови проверавају тврдњама (assert):

def binarna_pretraga(a, x):
    assert all(a[i] <= a[i + 1] for i in range(len(a) - 1)), "низ није сортиран"
    ...

Алати за формалну верификацију (нпр. Dafny, Coq, Isabelle) иду корак даље: уместо да услов проверавају на појединим улазима, доказују да важи за сваки улаз — за шта је потребан управо предикатски рачун.

Логичко програмирање и вештачка интелигенција

У језику Пролог (Prolog) програм је скуп чињеница и правила, а свако правило је ваљана формула облика „за све \(x, y, z\): ако … онда …“:

roditelj(ana, bojan).
roditelj(bojan, vera).
predak(X, Y) :- roditelj(X, Y).
predak(X, Z) :- roditelj(X, Y), predak(Y, Z).

Последња два реда значе \((\forall x)(\forall y)\big(\text{Родитељ}(x, y) \Rightarrow \text{Предак}(x, y)\big)\) и \((\forall x)(\forall y)(\forall z)\big(\text{Родитељ}(x, y) \land \text{Предак}(y, z) \Rightarrow \text{Предак}(x, z)\big)\). На питање ?- predak(ana, vera). систем одговара true, јер закључак изводи применом универзалне инстанцијације и модус поненса. На истим идејама почивају системи засновани на знању, семантички веб и графови знања, у којима се чињенице о свету записују као атомске формуле, а правила као формуле са квантификаторима.

Резиме

  • Предикат је реченица са променљивим која постаје исказ када се променљивим доделе вредности из домена. Исти предикат на различитим доменима може имати различиту истинитост.
  • Квантификатори \(\forall\) („за свако“) и \(\exists\) („постоји“) праве исказе од предиката. За \(\exists\) довољан је један сведок, а за оповргавање \(\forall\) један контрапример. Уз \(\forall\) иде импликација, а уз \(\exists\) конјункција.
  • Редослед различитих квантификатора је битан: \((\exists y)(\forall x)\) повлачи \((\forall x)(\exists y)\), али не и обрнуто. Негацију провлачимо кроз квантификатор тако што \(\forall\) заменимо са \(\exists\) и обрнуто.
  • Формуле се граде од терма и релацијских симбола. Појављивање променљиве је везано ако је у домету квантификатора по тој променљивој, иначе је слободно; формула без слободних променљивих је затворена.
  • Значење формули даје интерпретација (домен и тумачење симбола), а вредностима слободних променљивих валуација. Ваљане формуле су тачне у свакој интерпретацији; да формула није ваљана показујемо контрамоделом.
  • Предикатски рачун је језик математичких дефиниција, упита над базама података, спецификација програма и логичког програмирања.

Задаци

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

  1. Бавимо се предикатским рачуном првог реда, у коме се квантификује само по елементима домена, а не и по скуповима, релацијама или функцијама.↩︎