Uklonjeni sadržaj Dodani sadržaj
Nema sažetka izmjene
Poništena izmjena 40656432 korisnika Vujkovica brdo (razgovor)
Red 28:
 
:Upravo to - rasprava. Ovo trenutno nije rasprava nego revert rat. Ja ću sada vratiti na Ripperovu verziju i očekujem da daljnje izmjene na članku neće biti dok se ne postigne dogovor na stranici za razgovor. Ukoliko dođe do novih revertova, članak ću zaključati do postizanja konsenzusa --[[Korisnik:Edgar Allan Poe|<font face="Freestyle Script" color="black" size="4px">Biljezim se sa štovanjem</font>]][[Razgovor sa korisnikom:Edgar Allan Poe|<font face="Freestyle Script" color="black" size="4px">,Poe</font>]] 16:49, 29 juli 2016 (CEST)
 
== Логика првог реда ==
Логика првог реда или предикативни рачун првог реда је формални систем који се користи у математици, филозофији, лингвистици и рачунарству. Овде ћемо изложити само основни и најформалнији део нужан као потпора чланцима теорије скупова.
Логика првог реда или предикатска логика првог реда се базира на:
*објектима,
*својствима (унарним предикатима над објектима),
*релацијама (н-арним предикатима над објектима),
*функцијама (пресликавањима објеката на објекте).
===Синтакса логике првог реда===
Исказ → ПростИсказ
|Исказ Свеза Исказ<br/>
|Квантификатор Променљива Исказ<br/>
|¬ Реченица<br/>
|(Реченица)<br/>
ПростИсказ → Предикат(Објект, Објект, ...)
| Објект = Објект<br/>
Објект = Функција(Објект, Објект, ...)
| Константа<br/>
| Променљива<br/>
Свеза → ∨ | ∧ | ⇒ | ⇔<br/>
Квантификатор → ∃ | \forall
Константа → <tekst> тј. "A" | "1" | "а"
Променљива → x | y | z |...<br/>
Предикат → otac| brat| poseduje| ...<br/>
Функција → saberi| predji|...
Објекти су:<br/>
константе: <текст>, тј. 0, 1, "a", "ababa"<br/>
имена функција: <math>\operatorname{otac}, \operatorname{brat}, \operatorname{predji}, \operatorname{saberi}, ...</math> tj. <math>\operatorname{predji}(a, b,...), \operatorname{predji}(a), <\operatorname{saberi}(0), \operatorname{saberi}(0,1), ...</math><br/>
 
Исказ је предикат над једним или више објеката. Предикат је неко својство или релација међу објектима који може бити истинит или лажан.<br/> У горњим примерима <math>\operatorname{otac}(sin, kci,...)</math> значи да <math>sin, kci, ...</math> имају заједничког оца, <math>\operatorname{brat}(brat,brat,...)</math> да су <math>brat,brat,...</math> браћа.<br/>
ПростИсказ је предикат примењен на објекте. Нпр. <br/>
<math>\operatorname{poseduje}(Pero,auto)</math> тј. Перо поседује ауто,
<math>\operatorname{brat}(Mujo,Suljo)</math> тј, Мујо и Суљо су браћа.<br/>
 
Семантика Исказа и ПростогИсказа је истина или лаж.<br/>
 
Свезе се користе при конструкцији (сложених) Исказа<br/>
<math>\operatorname{brat}(Mujo,Suljo) \and \operatorname{poseduje}(Mujo,auto) \and \neg \operatorname{poseduje}(Suljo,auto)</math> тј. Мујо и Суљо су браћа, Мујо има ауто а Суљо нема.
 
===Квантификатори===
Користе се ако се Исказ односи на колекцију објеката како би се избегло бројање објеката
 
* Универзални квантификаторr: <math>\forall x</math>
Исказ је истинит за све вредности променљиве x.
 
<math>\forall x \operatorname{pas}(x) \Rightarrow \operatorname{sisar}(x)</math> Сви пси су сисари
 
* Егзистенцијални квантификаторr: <math>\exists x</math>
Исказ је истинит за бар једну вредност променљиве x.
 
<math>\exists x(\operatorname{macka}(x) \and \operatorname{boja}(x,crna) \and \operatorname{poseduje}(Marija,x))</math> Марија има (бар једну) мачку црне боје
<math>\exists x(\forall y \operatorname{pas}(y) \Rightarrow \operatorname{voli}(x,y)) \and (\forall z \operatorname{macka}(z) \Rightarrow \operatorname{mrzi}(x,z))</math> На овом свету постоји бар једна особа која воли псе и мрзи мачке
 
===Употреба квантификатора===
* Универзални квантификатор се користи импликативно
<math>\forall x \operatorname{covek}(x) \and \operatorname{covek}(x)</math> Све на овом свету је човек и сисар
* Егзистенцијални квантификатор се користи везивно:
<math>\exists x \operatorname{poesduje}(Jovan,x) \Rightarrow \operatorname{pas}(x)</math> На овом свету има нешто што Јован не поседује или постоји на овом свету пас
===Угнеждени квантификатори===
* Поредак квантификатора истог типа у исказу је неважан
<math>\forall x \forall y(\operatorname{roditelj}(x,y) \and \operatorname{musko}(y) \Rightarrow \operatorname{sin}(y,x))</math>
<math>\exists x \exists y(\operatorname{voli}(x,y) \and \operatorname{voli}(y,x))</math>
* Поредак квантификатора различитог типа у исказу је неважан
<math>\forall x \exists y(\operatorname{voli}(x,y))</math> Свако воли некога, тј. свако има неког кога воли
<math>\exists y \forall x(\operatorname{voli}(x,y))</math> Постоји на овом свету неко кога свако воли
 
===Подручје или зона важења променљиве===
* Подручје или зона важења променљиве је исказ на који је квантификатор применљив.
* Променљива у логичком изразу се везује за најближи квантифиватор унутар исказа у коме се појављује
<math>\exists x (\operatorname{pas}(x) \and \forall x(\operatorname{zut}(x)))</math> Пси постоје и сви су жути. x у жут(x) је универзално квантифициран.
* У добро написаној формули све променљиве морају бити квантификоване:
<math>\exists x P(y)</math> Ова формула није добро написана
 
===Логичка веза међу квантификаторима===
•Логичка веза међу универзалним и егзистенцијалним квантификатором:<br/>
 
<math>\forall x \neg \operatorname{voli}(x,bandit) \Leftrightarrow \neg \exists x \operatorname{voli}(x,bandit)</math><br/>
<math>\forall x \operatorname{voli}(x,bog) \Leftrightarrow \neg \exists x \neg \operatorname{voli}(x,bog)</math>
 
•Опште важећи идентитети:<br/>
 
<math>\forall x \neg P \Leftrightarrow \neg \exists x P</math><br/>
<math>\neg \forall x P \Leftrightarrow \exists x \neg P</math><br/>
<math>\forall \forall x P \Leftrightarrow \neg \exists x \neg P</math><br/>
<math>\exists x P \Leftrightarrow \neg \forall x \neg P</math><br/>
<math>\forall x P(x) \and Q(x) \Leftrightarrow \forall x P(x) \and \forall x Q(x)</math><br/>
<math>\exists x P(x) \or Q(x) \Leftrightarrow \exists x P(x) \or \exists x Q(x)</math>
 
===Једнакост===
* Једнакост се укључује као примитивни логички предикат.
* Примери:
<math>\exists x \exists y(\operatorname{poseduje}(Jovan, x) \and \operatorname{pas}(x) \and \operatorname{poseduje}(Jovan,y) \or \operatorname{pas}(y) \and \neg (x=y))</math>
Јован има два пса. Једнакост се користи овде да се обезбеди да су <math>x</math> и <math>y</math> различити, тј. да се искључи интерпретација да <math>x</math> и <math>y</math> могу бити исти пас
<math>\forall x \exists y \operatorname{sinOtac}(x, y) \and \forall z(\operatorname{sinOtac}(x,z) \Rightarrow y=z)</math>
Сваки син има оца. Друга свеза \forall z(\operatorname{sinOtac}(x,z) \Rightarrow y=z) обезбеђује да сваки син има једног оца.
 
==Логике вишег реда==
* У логици првог реда квантификатори су применљиви само на објекте.
* У логици другог реда квантификатори су применљиви само на предикате и функције:
<math>\forall x \forall y [ (x=y) \Leftrightarrow (\forall \operatorname{p} \operatorname{p}(x) \Leftrightarrow \operatorname{p} (y)) ]</math> Два објекта су једнака ако и само ако имају иста својства.
 
<math>\forall \operatorname{f} \forall \operatorname{g} [ (\operatorname{f} = \operatorname{g}) \Leftrightarrow (\forall x \operatorname{f}(x) = \operatorname{g}(x)) ]</math> Две функције су једнаке ако и само ако имају исте вредности за све могуће аргументе.
 
* Логика трећег реда допушта квантификацију предиката, итд.
На пример, предикат другог реда <math>p</math> може бити <math>\operatorname{refleksivan}(p)</math> тј. бинарни предикат <math>p</math> је релација рефлексивности.