Predikátová logika I.řádu

Predikátová logika (PL) je rozšířením výrokové logiky. Na rozdíl od výrokové logiky si všímá i struktury vět samotných a obsahuje predikáty a kvantifikátory. PL pracuje s primitivními formulemi (predikáty) vypovídajícími o vlastnostech a vztazích mezi předměty jistého univerza diskursu (individui). 

Pouze jen malá část úsudků může být formalizována a dokázána v rámci výrokové logiky. Pokusme se např. ověřit typ (zjevně správného) úsudku charakterizovaný následujícím příkladem:

Všechny žáby jsou zelené. 

Tento kůň je zelený.

_______________________

-> Tento kůň je žába.

Ve výrokové logice bychom celé výroky označili pouze třemi symboly např. p, q a r. Formalizace by vypadala tudíž (p ∧ q) É r, což je zcela špatně protože výroky nejsou nezávislé a za druhé má výsledek formule vyjít, že je úsudek platný a ne naopak.  

 

Formalizace v predikátové logice 1.řádu (PL1):

Predikátová logika umožňuje uvažování nad vlastnostmi, jež jsou sdíleny mnoha objekty, díky použití proměnných a kvantifikátorů. V predikátové logice 1.řádu by byl uvedený úsudek formalizován takto: ∀x [B(x) É Z(x)], Z(K) |= B(K), resp. následující formulí 

∀x [B(x) É Z(x)] ∧ Z(K) É B(K)  

kde,

  • x ...je předmětová (individuová) proměnná pocházející ze specifické univerzální množiny (zvané univerzum) 
  • K ...je individuová konstanta z daného univerza (v uvedeném příkladě "tento kůň"),
  • B, Z ...jsou určité vlastnosti předmětů z universa diskursu, označovaných také jako predikáty. Predikát B v našem příkladě říká, že objekt, reprezentovaný proměnnou x je žába. Predikát Z zase, že proměnná v závorkách je zelená. Výraz Z(K) tudíž znamená, že proměnná tento kůň má vlastnost být zelený.
  • zápis ∀x [ ] ...značí, že pro všechna individua z univerza platí to, co je uvedeno v hranatých závorkách (znak ∀ je jedním z kvantifikátorů)

Pokud bychom chtěli formalizovat úsudky, které navíc vypovídají i o vlastnostech vlastností a vztahů a o vztazích mezi vlastnostmi a vztahy, museli bychom použít predikátovou logiku druhého řádu a vyššího. Tou se ale nebudeme zabývat.

 

Definice formálního jazyka predikátové logiky PL1  

1.  Abeceda predikátové logiky je tvořena následujícími skupinami symbolů:

        a.  Logické symboly

                i.   Individuové proměnné:         x, y, z,... (příp. s indexy)

                ii.  Symboly pro spojky:              ¬, ∨, ∧, É, ≡

                iii.  Symboly pro kvantifikátory     ∀, ∃                     

        b.  Speciální symboly (určují specifiku jazyka)

                i.      Predikátové symboly:         Pn, Qn, ...          n - arita = počet argumentů

                ii.      Funkční symboly:              fn, gn, ...          

         c.  Pomocné symboly /závorky/:        (,)     /případně i [,],{,}/

 2.  Gramatika, která udává, jak tvořit:

         a.  Termy: každá individuová proměnná i konstanta je term

         b.  Atomické formule: jsou-li t1,…,tn termy, pak výraz p(t1,…,tn) je atomická formule

         c.  Formule:

                i.      Každá atomická formule je formule

                ii.     Je-li výraz A, B formule a x proměnná pak i výrazy: ¬A, ∀xA a ∃xA, (A ∨ B), (A ∧  B), (A  É B), (A  ≡ B) jsou formulemi

 

Převod z přirozeného jazyka do jazyka PL1

Tvorba kvantifikátorů:

  • ∀     „všichni“, „žádný“, „nikdo“, ...   "
  • ∃      „někdo“, „něco“, „někteří“, „existuje“, ...

Větu musíme často ekvivalentně přeformulovat, pozor: v češtině dvojí zápor !

Jako pomůcka k řešení může sloužit tato zásada:
  • Po všeobecném kvantifikátoru následuje formule ve tvaru implikace ∀ + É
  • Po existenčním kvantifikátoru formule ve tvaru konjunkce  ∃ + ∧

Při ekvivalentních úpravách používáme de Morganovy zákony PL1 :

  • ¬∀xA ⇔ ∃x¬A
  •  ¬∃xA ⇔ ∀x¬A   

Příklady:

Není pravda, že všichni vodníci jsou zelení. ⇔ Někteří vodníci nejsou zelení.

¬∀x [V(x) É Z(x)] ⇔ ∃x [V(x) ∧ ¬Z(x)]  

Není pravda, že někteří vodníci jsou zelení. ⇔ Žádný vodník není zelený. 

¬∃x [V(x) ∧ Z(x)] ⇔ ∀x [V(x) É ¬Z(x)]  

Everybody loves somebody sometimes.

∀x ∀y ∀z L(x,y,z)

Marie má ráda pouze vítěze.

∀x [R(m,x) É V(x)]

 

Volné a vázané a čisté proměnné

Volné proměnné jsou ty, které nejsou spjaty s kvantifikátorem, zatímco vázané jsou.

Formule s čistými proměnnými jsou takové, kdy každý kvantifikátor má své vlastní proměnné. V druhém konjunktu bychom proto museli x přejmenovat například na z a y přejmenovat na r apod. Pro označení rozdílných proměnných se často používají apostrofy.

Substituce termů za proměnné

A(t/x)  vznikne z A korektní substitucí termu t za proměnnou x
 
Pravidla substituce termů:
  • Substituovat lze pouze za volné výskyty proměnné x ve formuli A a při substituci nahrazujeme všechny volné výskyty proměnné x ve formuli A termem t.
  • Žádná individuová proměnná vystupující v termu t se po provedení substituce t/xnesmí stát ve formuli A vázanou (v takovém případě není term t za proměnnou x ve formuli A substituovatelný).
Příklad:

A(x):    P(x) É ∀y Q(x, y)  ...provedeme-li substituci termu f(y) ⇒A(f(y)/x):

A(f(y)): P(f(y)) É ∀y Q(f(y), y).

⇒term f(y) není substituovatelný za x v dané formuli A, protože y je vázaná proměnná a substitucí bychom změnili smysl celé formule 

Interpretace jazyka PL1 

Interpretace jazyka predikátové logiky 1. řádu je tato trojice objektů (která je někdy nazývána interpretační struktura):

A)    Neprázdná množina M, která se nazývá universum diskursu a její prvky jsou individua.

B)    Interpretace funkčních symbolů jazyka, která přiřazuje každému n-árnímu funkčnímu symbolu f určité zobrazení fM: Mn ® M. 

C)    Interpretace predikátových symbolů jazyka, která přiřazuje každému n-árnímu predikátovému symbolu p jistou n-ární relaci pM nad M, tj. podmnožinu Kartézského součinu Mn.

 

Ohodnocení (valuace) individuových proměnných je zobrazení e, které každé proměnné x přiřazuje hodnotu e(x) ∈ M (prvek univerza) 
 
Příklad interpretace:

Uvažujme jazyk predikátové logiky s následujícími konstantami:

  • h ...binární funkční symbol,    p ...binární predikátový symbol

Pro tento jazyk definujme interpretaci následujícím způsobem:

  • Universum diskursu M je množina všech nezáporných celých čísel {0, 1, 2,...}.
  • Realizace funkčních symbolů jsou definovány takto:
    • h  ... zobrazení M2 ® M definované takto: h(x, y) = x + y
  • Realizace predikátových symbolů jsou definovány takto:
    • p  ... podmnožina množiny M2 definovaná jako množina všech dvojic <x,y>, pro které platí x = y,

Formule  

p(h(x,y), x)), neboli x + y = x 

     ...je v uvedené interpretaci pravdivá např. pro ohodnocení proměnných e(x)=3, e(y)=0 a nepravdivá např. pro ohodnocení e(x)=3, e(y)=2. Formule je splnitelná v dané interpretaci, není však v této interpretaci pravdivá.

 

Formule

"x"y p(h(x,y), h(y,x)), neboli "x"y [x + y = y + x]

    ...je v uvedené interpretaci pravdivá pro každé ohodnocení a je tedy pravdivá v uvedené interpretaci. Není však tautologií - to by formule musela být pravdivá v každé interpretaci (kdybychom predikát p intepretovali jako ostrou nerovnost, tak už je formule nepravdivá pro každé ohodnocení).

Definice splnitelnosti formuli v PL1 
  • Formule A je splnitelná v interpretaci I, jestliže existuje ohodnocení e proměnných takové, že platí |=IA[e].
  • Formule A je pravdivá v interpretaci I, značíme |=IA, jestliže pro všechna možná ohodnocení e individuových proměnných platí, že |= IA[e].
  • Model formule A je interpretace I, ve které je A pravdivá.
  • Formule Aje splnitelná, jestliže existuje interpretace I, ve které je splněna, tj. jestliže existuje interpretace I a valuace e takové, že |=IA[e].
  • Formule A je tautologií (logicky pravdivá), značíme |= A,jestliže je pravdivá v každé interpretaci.
  • Formule A je kontradikcí, jestliže nemá model, tedy neexistuje interpretace I, která by formuli A splňovala.
  • Model množiny formulí {A1,…,An} je taková interpretace I, ve které jsou pravdivé všechny formule A1,...,An.
  • Formule B logicky vyplývá z formulí A1, …, An, značíme A1,…,An|= B, jestliže B je pravdivá v každém modelu množiny formulí A1,…,An. Tedy pro každou interpretaci I, ve které jsou pravdivé formule A1, …, An (|= IA1,…,|=IAn) platí, že je v ní pravdivá také formule B (|= IB).

 

Sémantické ověřování platnosti úsudku

Úsudek je platný, pokud je závěr pravdivý ve všech modelech předpokladů. Ale, těchto modelů může být nekonečně mnoho. Přesto můžeme na základě „logického tvaru“ modelů předpokladů (tedy množinových úvah) ověřit, zda zaručují pravdivost závěru.

Grafické ověřování pomocí Vénových diagramů

Všechny opice (P) mají rády banány (Q). 

Judy je opice.

_______________________

-> Judy má ráda banány.

 

⇒ úsudek je platný

Všechni vodníci (V) jsou inteligentní (I). 

Někdo není vodník.

_______________________

-> Někdo není inteligentní.

 

⇒ úsudek není platný, nevím jestli ten nevodník spadá do množiny inteligentních nebo mimo ní (otazníky) - mohla by nastat okolnost kdy je závěr neplatný proto je neplatný

 

Syntaktické ověřování platnosti úsudku 

viz. rezoluční metoda v PL1

 

 Čerpáno ze skript Logika pro Informatiky (Doc. RNDr. Marie Duží)