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

Предикати

У претходном поглављу дефинисали смо да је исказ свака категоричка реченица која може бити тачна (истинита) или нетачна (неистинита), али не и оба истовремено. Као пример реченице која није исказ, навели смо „\(x + y = z\)“, јер овај алгебарски израз није могуће оценити као тачан или нетачан без додатних информација.

Међутим, уколико имамо конкретне вредности за \(x\), \(y\) и \(z\), ова реченица би представљала исказ. Наравно, тај исказ је у неким случајевима тачан, на пример за \(x = 1\), \(y = 3\) и \(z = 4\), док би за \(x = 2\), \(y = 5\) и \(z = 1\) био нетачан.

У овом поглављу бавићемо се управо реченицама које садрже променљиве, попут „\(x + y = z\)“, и које за конкретне вредности тих променљивих постају искази. Овакве реченице називаћемо предикатима.

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

Пример

Претпоставимо да говоримо о реалним бројевима. Примери неких предиката дати су у наставку:

  • \(P_1(x): x^2 > 0\).

    Исказ је нетачан за \(x=0\) у супротном је тачан.

  • \(P_2(x): e^x \neq 0\).

    Исказ је тачан за све вредности \(x\).

  • \(P_4(x,y,z):\) Ако је \(x > y\), тада је \(x \cdot z > y \cdot z\).

    Исказ је нетачан за (\(z \le 0\)), у супротном је тачан.

Прво што можемо приметити из овог примера јесте да је важно јасно навести домен односно скуп вредности из кога можемо узимати вредности променљивих. Исти предикат може имати различиту истинитост у зависности од домена, на пример предикат \(P_1(x)\) који може бити и тачан и нетачан за реалне бројеве је увек тачан ако говоримо о природним бројевима. Више детаља о домену размотрићемо у наставку код интерпретрације предикатске формуле.

За предикат \(P_2(x)\) можемо рећи да је тачан за свако \(x\) и то симобички записујемо \(\forall x\,P_2(x)\). Симбол \(\forall\) се назива универзални квантификатор и чита се “за свако”.

За предикат \(P_1(x)\) не можемо рећи да је тачан за све вредности променљиве \(x\) из домена али можемо рећи да постоји једна вредност (нпр. \(x = 2\)) за коју је добијени исказ тачан и то симобичи записујемо \(\exists x\, P_1(x)\). Симбол \(\exists\) се назива егзистенцијални квантификатор и чита се “постоји”.

Коришћењем квантификатора и елементарних предиката добијамо квантификоване предикате. Да би квантификован предикат \(\forall x P(x)\) био тачан, \(P(x)\) мора да буде тачан за сваку вредност \(x\) из домена. Слично да би квантификовани предикат \(\exists x P(x)\) био тачан, \(P(x)\) мора да буде тачан за бар једну вредност \(x\) из домена. Сада је јасно да квантификован предикат има истинитосну вредност и представља исказ! Предикати са више променљивих је квантификован и представља исказ ако су квантификоване све променљиве које се у њему јављају.

Пример

  • “За сваки природан број \(n\) важи \(n > 2\).”

    Исказ је нетачан.

  • “Постоји природан број \(n\) за који важи \(n > 2\).”

    Исказ је тачан.

  • “За сваки \(x \in \mathbb{R}\) постоји \(y \in \mathbb{R}\) за који важи \(x + y = 0\).”

    Исказ је тачан.

Коришћењем квантификатора и логичких операција, исказ “Не постоји највећи (природан) број” можемо симболички записати: \(\neg (\exists n)(\forall m)(n \geq m)\).

У овом исказу јавља се негација испред квантификованог предиката и генерално може се поставити питања шта је негација исказа \(\exists x\, P(x)\) тј. \(\neg (\exists x\, P(x))\)? То значи да не постоји \(x\) за коју је предикат \(P(x)\) тачан, односно за све вредности \(x\) предикат \(P(x)\) је нетачан тј. \(\forall x\, \neg P(x)\).

Сличнo, негација исказа \(\forall x\, P(x)\) коју записујемо \(\neg (\forall x P(x))\) каже да није тачно да је предикат \(P(x)\) тачан за сваку вредност \(x\), односно постоји вредност \(x\) за коју је предикат P(x) нетачан тј. \(\exists x\, \neg P(x)\).

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

  • \((\neg (\forall x P(x)) = \exists x \neg P(x)\).

  • \(\neg (\exists x P(x)) = \forall x \neg P(x)\).

Коришћењем ових особина,имамо да је претходни исказ \[\neg (\exists n)(\forall m)(n \geq m) = (\forall n)(\exists m)\neg(n \geq m) = (\forall n)(\exists m)(n < m)\] што сада можемо прочитати “За сваки (природан) број постоји број који је већи од њега.”

Језик предикатске формуле

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

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

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

Дакле, унапред се морају знати:

  • \(Const\) — скуп симбола константи,

  • \(Fun\) — скуп операцијских симбола,

  • \(Rel\) — скуп релацијских симбола,

  • \(Ar\) — дужина (арност) одговарајуће операције или релације, тј. \(Ar: Fun \cup Rel \longrightarrow \mathbb{N}.\)

Четворка \((Fun, Rel, Const, Ar)\) се назива језик (првог реда) предикатске формуле.

У наставку, за симболе константи користићемо ознаке \(a, b, c, a_1, b_1, c_1, \dots\) за операцијске симболе \(f, g, h, f_1, g_1, h_1, \dots\) и за релацијске симболе \(\alpha, \beta, \gamma, \alpha_1, \beta_1, \gamma_1, \dots\)

Предикатска формула

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

  1. Симболи променљивих и константи су изрази.

  2. Ако су \(t_1, \dots, t_n\) изрази и \(f\) операцијски симбол дужине \(n\), онда је \(f(t_1, \dots, t_n)\) такође израз.

Пример

Ако је \(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)\) нису изрази.

Често уместо записа \(g(x), f(x, y)\) користимо \(g\, x\) и \(x\, f\, y\).

Коришћењем израза и релацијских симбола добијамо елементарне формуле:

  • Ако су \(t_1, t_2, \dots, t_n\) изрази и \(\alpha\) релацијски симбол дужине \(n\), тада је \(\alpha(t_1, t_2, \dots, t_n)\) елементарна формула.

  • Ако су \(t_1\) и \(t_2\) изрази, тада је и \(t_1 = t_2\) елементарна формула.

Пример

Нека је \(\alpha\) бинарни релацијски симбол, \(\beta\) релацијски симбол дужине 3, \(f\) бинарни операцијски симбол, \(x\) и \(y\) симболи променљивих и \(c\) симбол константе. Елементарне формуле су:

  • \(\alpha(x, y)\),

  • \(\alpha(f(x, y), c)\),

  • \(\beta(x, y, f(x, c))\).

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

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

Пример

Нека су \(x\), \(y\) и \(z\) симболи променљивих, \(a\) и \(b\) симболи константи, \(f\), \(g\), \(h\) операцијски и \(\alpha\) релацијски симбол дужине \(Ar(f) = 1\), \(Ar(g) = 2\), \(Ar(h) = 3\) и \(Ar(\alpha) = 2\). Примери предикатски формула су:

  • \(\alpha\big( x, f\big( g(y, a) \big) \big)\),

  • \((\exists y)(x = y \Rightarrow (\forall x) \alpha(x, a))\),

  • \(\alpha\big( a, g\big( x, h(a, b, f(x)) \big) \big) \Rightarrow (\exists x)(\forall z)\big( z = a \lor (\forall y)(x = f(y)) \big)\)

Појављивања променљивих

Коришћењем квантификатора можемо квантификовати све или само неке променљиве у предикатској формули. Кажемо да је појављивање променљиве \(x\) у предикатској формули \(F\) везано ако је то појављивање у подформули облика \((\forall x) F\) или \((\exists x) F\). Свако појављивање променљиве \(x\) које није везано је слободно појављивање.

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

За предикатску формулу кажемо да је затворена ако не садржи слободне променљиве и она представља исказ који је тачан или нетачан. Са друге стране за предикатску формулу \(F\) код које су \(x_1\), \(x_2\), \(\dots\), \(x_n\) слободне променљиве кажемо да је отворена и обележавамо са \(F(x_1, x_2, \dots, x_n)\). Број \(n\) представља дужину формуле \(F\).

Пример

Формула Ознака
\((\forall x)\, x = y \lor (\exists y) \neg y = z \land (\forall z)\, x = z\) \(F(x, y, z)\)
\((\forall x)\big( x = y \lor (\exists y) \neg y = z \big)\) \(F(y, z)\)
\((\forall x)\big( x = z \lor (\exists y) \neg y = z \big)\) \(F(z)\)
\((\forall x)\big( (\exists y)\, x = y \lor (\exists z) \neg x = z \big)\) \(F\) је затворена формула

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

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

Пример

Различите интерпретације формуле \(\alpha(f(x, y), c)\):

  • \(<(+(x, y), 3)\),

  • \(=(\cup(x, y), \emptyset)\),

  • \(=(\lor(x, y), 0)\),

или у другачијем запису:

  • \(x + y < 3\),

  • \(x \cup y = \emptyset\),

  • \(x \lor y = 0\).

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

  1. Ако је \(c\) неки симбол константе, онда је његова интерпретација \(I(c)\) елемент скупа \(D\), тј. \(I(c) \in D\).

  2. Ако је \(f\) операцијски симбол дужине \(n\), онда је његова интерпретација \(I(f)\) операција дужине \(n\) на скупу \(D\), тј. \(I(f): D^n \longrightarrow D\).

  3. Ако је \(\alpha\) неки релацијски симбол дужине \(n\), онда је његова интерпретација \(I(\alpha)\) релација дужине \(n\) на скупу \(D\), тј. \(I(\alpha) \subseteq D^n\).

Пример

Нека су \(f\) и \(g\) бинарни операцијски знаци, \(\rho\) бинарни релацијски знак, \(a\) и \(b\) симболи константи. Једна од могућих интерпретација \(L = (D, I)\) овог језика је:

  • \(D = \mathbb{R},\)
  • \(I(f)\) је сабирање реалних бројева,
  • \(I(g)\) је множење реалних бројева,
  • \(I(\rho)\) је релација \(<\) на скупу реалних бројева,
  • \(I(a) = 0\) и
  • \(I(b) = 1\).

Вредност предикатске формуле

Да бисмо дефинисали вредности предикатске формуле потребно је још да имамо вредности променљивих. Као и код исказног рачуна ово придруживање називамо валуација. За дефинисање валуације потребно је знати домен па се она сада дефинише при одређеној интерпретацији, која нам одређује домен. У исказном рачуну домен нам је увек био скуп \(\{0, 1 \}\).

Дакле, валуација \(v\) при интерпретацији \(L = (D, I)\) је пресликавање скупа свих променљивих у домен \(D\). \(v(x) \in D\) је вредност променљиве \(x\) при валуацији \(v\).

Слично као што смо дефинисали предикатску формулу (преко израза и елементарне предикатске форумуле) можемо дефинисати и њену вредност.

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

  1. Ако је \(c\) константа, онда је \(L_v(c) = I(c)\).
  2. Ако је \(x\) променљива, онда је \(L_v(x) = v(x)\).
  3. Ако су \(t_1, \dots, t_n\) изрази, \(f\) операцијски симбол дужине \(n\) и \(F = I(f)\) његова интерпретација, онда је \[ L_v(f(t_1, \dots, t_n)) = F\big( L_v(t_1), \dots, L_v(t_n) \big). \]

Пример

Нека су \(f\) и \(g\) бинарни операцијски знаци, \(c\) симбол константе, \(x\) и \(y\) променљиве, \(L = (\mathbb{Z}, I)\) интерпретација дата са \(I(f) = +\), \(I(g) = \cdot\), \(I(c) = 3\) и \(v\) валуација за коју је \(v(x) = 2\) и \(v(y) = 5\). Тада је вредност формуле \(f(x, g(y, c))\), при интерпретацији \(L\) и валуацији \(v\), једнака \(2 + (5 \cdot 3) = 17\).

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

  1. Ако су \(t_1\) и \(t_2\) изрази, онда је \[ L_v(t_1 = t_2) \text{ једнако } 1 \Leftrightarrow L_v(t_1) = L_v(t_2). \]
  2. Ако су \(t_1, \dots, t_n\) изрази, \(\alpha\) релацијски симбол дужине \(n\) и \(\rho = I(\alpha)\) његова интерпретација, онда је \[ L_v\big( \alpha(t_1, \dots, t_n) \big) \text{ једнако } 1 \Leftrightarrow \rho\big( L_v(t_1), \dots, L_v(t_n) \big). \]

Истинитосна вредност (сложене) предикатске формуле:

  1. Ако је \(F\) формула, онда је \(L_v(\neg F) = \neg L_v(F)\).
  2. Ако су \(F\) и \(G\) формуле онда је \(L_v(F \land G) = L_v(F) \land L_v(G)\).
  3. Ако су \(F\) и \(G\) формуле онда је \(L_v(F \lor G) = L_v(F) \lor L_v(G)\).
  4. Ако су \(F\) и \(G\) формуле онда је \(L_v(F \Rightarrow G) = L_v(F) \Rightarrow L_v(G)\).
  5. Ако су \(F\) и \(G\) формуле онда је \(L_v(F \Leftrightarrow G) = L_v(F) \Leftrightarrow L_v(G)\).
  6. Ако је \(F\) формула и \(x\) променљива, онда је \(L_v\big( (\forall x) F \big) = 1\) ако и само ако је \(L_v(F) = 1\) за све вредности \(v(x) \in D\).
  7. Ако је \(F\) формула и \(x\) променљива, онда је \(L_v\big( (\exists x) F \big) = 1\) ако и само ако је \(L_v(F) = 1\) за бар једну вредност \(v(x) \in D\).

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

Пример

Нека је \(f\) бинарни операцијски знак, \(c\) симбол константе и \(L = (\mathbb{R}, I)\) интерпретација дата са \(I(f) = \cdot\) и \(I(c) = 1\). Тада су формуле:

  • \(f(c, x) = x\),

  • \((\forall x) f(c, x) = x\)

  • \((\exists x) f(c, x) = x\)

тачне при интерпретацији \(L\).

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

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

Пример

Ваљане формуле изведене из таутологија исказног рачуна:

  • \((F \Rightarrow G) \Leftrightarrow (\neg F \lor G)\),
  • \(\neg (F \land G) \Leftrightarrow (\neg F \lor \neg G)\).

Неке ваљане формуле

  • \((\forall x)(\forall y) F(x, y) \Leftrightarrow (\forall y)(\forall x) F(x, y)\),
  • \((\exists x)(\exists y) F(x, y) \Leftrightarrow (\exists y)(\exists x) F(x, y)\),
  • \((\exists x)(\forall y) F(x, y) \Rightarrow (\forall y)(\exists x) F(x, y)\),
  • \((\forall x)\big( F_1(x) \land \ldots \land F_m(x) \big) \Leftrightarrow (\forall x) F_1(x) \land \ldots \land (\forall x) F_m(x)\),
  • \((\forall x)\big( F_1(x) \lor \ldots \lor F_m(x) \lor G_1 \lor \ldots \lor G_n \big) \Leftrightarrow (\forall x)\big( F_1(x) \lor \ldots \lor F_m(x) \big) \lor G_1 \lor \ldots \lor G_n\),
  • \((\exists x)\big( F_1(x) \lor \ldots \lor F_m(x) \big) \Leftrightarrow (\exists x) F_1(x) \lor \ldots \lor (\exists x) F_m(x)\),
  • \((\exists x)\big( F_1(x) \land \ldots \land F_m(x) \land G_1 \land \ldots \land G_n \big) \Leftrightarrow (\exists x)\big( F_1(x) \land \ldots \land F_m(x) \big) \land G_1 \land \ldots \land G_n\).

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