« poprzedni punkt   następny punkt »


8.4. Formalne przedstawienie rachunku predykatów

W tej części wykładu przedstawimy rachunek predykatów w sposób bardziej formalny, niż to było do tej pory, tzn. dokładnie określimy język i semantykę tego rachunku. We wszystkich dalszych rozważaniach, będziemy starannie oddzielali wyrażenia języka, tzn. składnię, od ich znaczenia, tzn. semantyki.

Niech V0 będzie zbiorem zmiennych zdaniowych, V-zbiorem zmiennych indywiduowych (zmienne przebiegające inne dziedziny niż {prawda, fałsz}), Ρ-zbiorem nazw dla relacji, Φ- zbiorem nazw dla funkcji. Poprawnie zbudowane wyrażenia języka predykatów, to termy, odpowiadające wyrażeniom algebraicznym, i formuły, odpowiadające wyrażeniom Booleowskim (lub inaczej, funkcjom zdaniowym).

Definicja 8.4.1

Zbiór termów jest to najmniejszy zbiór zawierający V i taki, że jeśli f jest nazwą funkcji n argumentowej, a t1, ..., tn termami, to f(t1, ...,tn) jest termem.

Zbiór formuł jest to najmniejszy zbiór wyrażeń zawierających zbiór zmiennych zdaniowych V0 i taki, że

Uwaga. Jeśli funkcja lub relacja jest dwuargumentowa, to jej symbol umieszczamy tradycyjnie między argumentami pisząc x+y, a nie +(x,y), jak w powyższej definicji.

Na przykład, jeśli x i y są zmiennymi indywiduowymi, a + i * są symbolami operacji dwuargumentowych, to (x+y)* x jest termem. Natomiast wyrażenia ((x+y)* x)<(x+y)), ( ∀ x) ((x+y)* x)<(x+y)), ( ∃ x) (x>x*x ∨ ( ∀ y)((x+y)* x<(x+y)) ) są formułami.

Aby obliczyć wartość formuły rachunku zdań wystarczyło znać wartości zmiennych zdaniowych w niej występujących. W formułach rachunku predykatów występują zmienne, funkcje i relacje. Na ogół nie można ustalić wartości formuły nie znając interpretacji symboli w niej występujących. Pytanie jaka jest wartość wyrażenia ( ∀ x)( ∃ y) (x ⊕ y > x) musi pozostać bez odpowiedzi dopóki nie ustalimy przestrzeni wartości dla zmiennych indywiduowych x, y i dopóki nie przyjmiemy znaczenia dla operacji ⊕ i relacji >.

Zatem, aby określić semantykę (znaczenie) wyrażeń rachunku predykatów, musimy najpierw ustalić zbiór, który przebiegać będą zmienne indywiduowe i interpretację symboli funkcyjnych i predykatywnych w tym zbiorze. Ustaloną interpretację symboli funkcyjnych i relacyjnych, będziemy nazywali strukturą algebraiczną (lub czasami strukturą danych), a ustalone wartości dla zmiennych - wartościowaniem. Dla wygody, będziemy myśleli o wartościowaniu, jako o funkcji, która zmiennym ze zbioru V0 ∪V przypisuje wartości. Oczywiście, nie wszystkie wartości zmiennych są nam potrzebne przy obliczaniu wartości konkretnej formuły, bo każda formuła ma tylko skończoną liczbę zmiennych, od których zależy jej wartość.

Niech STR będzie pewną ustaloną strukturą algebraiczną. Oznaczmy przez tSTR(v) wartość termu t przy interpretacji w strukturze STR i wartościowaniu v. Przyjmujemy następującą rekurencyjną definicję:

tSTR(v) = v(x), jeśli term t jest po prostu zmienną indywiduową x, oraz

tSTR(v) = fSTR(t1(v),..., tn(v)), gdy t jest termem złożonym, postaci f(t1,..., tn), a fSTR n-argumentową operacją w STR będącą interpretacją symbolu funkcyjnego f.

Przykład 8.4.1

Rozważmy term ((x ⊕ y) ⊗ z), w którym x, y, z są zmiennymi indywiduowymi, a ⊕, ⊗ dwuargumentowymi operacjami. Jeśli zinterpretujemy ten term w strukturze liczb rzeczywistych, przyjmując jako interpretację ⊕ dodawanie, a jako interpretację ⊗ mnożenie liczb rzeczywistych, to przy wartościowaniu v, takim że v(x)=2, v(y)= 3, v(z)=5, wartością rozważanego termu jest 25. Rzeczywiście mamy:

((x ⊕ y) ⊗ z)R(v) = (x ⊕ y) R(v) * z R(v) = (x R(v) + y R(v))* z R(v) = (2+3)*5 = 25.

Jeśli natomiast zinterpretujemy ten sam term w strukturze P(N), wszystkich podzbiorów zbioru liczb naturalnych, przyjmując jako interpretację ⊕ sumę teoriomnogościową, a jako interpretację ⊗ przecięcie teoriomnogościowe zbiorów, to przy wartościowaniu v, takim że v(x)={2}, v(y)={3}, v(z)={5} wartością termu jest zbiór pusty. Rzeczywiście mamy:

((x ⊕ y) ⊗ z)P(N)(v) = (x ⊕ y)P(N)(v) ∩ zP(N)(v) = (xP(N)(v) ∪ yP(N)(v)) ∩ {5} =
({2} ∪ {3}) ∩ {5} = {2,3} ∩ {5} = ∅.

W podobny sposób, przez indukcję ze względu na postać formuły definiujemy semantykę formuł rachunku predykatów. Niech STR oznacza wybraną strukturę algebraiczną, w której będziemy interpretować symbole funkcyjne i relacyjne, i niech v będzie ustalonym wartościowaniem. Wyrażenie STR, v |= α(x) oznacza, że wartością formuły α(x) zinterpretowanej w strukturze STR i przy wartościach zmiennych określonych w wartościowaniu v, jest prawda. O formule α(x) będziemy wtedy mówili, że jest spełniona przez wartościowanie v w strukturze STR. Pojęcie spełniania definiujemy rekurencyjnie ze względu na postać formuły następująco:

STR, v |= p wttw v(p)=1, gdy p jest zmienną zdaniową,

STR, v |= r(t1,..., tn) wttw rSTR(tiSTR(v),..., tnSTR(v)) jest zdaniem prawdziwym

STR, v |= ¬ α(x) wttw nie zachodzi STR, v |= α(x)

STR, v |= ( α(x) ∨ β(x)) wttw STR, v |= α(x) lub STR, v |= β(x)

STR, v |= ( α(x) ∧ β(x)) wttw STR, v |= α(x) i STR, v |= β(x)

STR, v |= ( α(x) → β(x)) wttw STR, v |= ¬ α(x) lub STR, v |= β(x)

STR, v |= ( ∀x) α(x) wttw STR, v(a/x) |= α(x) dla wszystkich a ∈ STR

STR, v |= ( ∃x) α(x) wttw STR, v(a/x) |= α(x) dla pewnego a ∈ STR.

Zwróćmy uwagę na definicję spełniania dla formuł z kwantyfikatorem. Formuła ( ∀x) α(x) jest spełniona przez wartościowanie v w strukturze STR wtedy i tylko wtedy, gdy każde wartościowanie v(a/x) otrzymane z v przez wstawienie dowolnego elementu a jako wartości zmiennej x, spełnia formułę α(x). Formuła ( ∃x) α(x) jest spełniona przez wartościowanie v w strukturze STR wtedy i tylko wtedy, gdy chociaż jedno wartościowanie v(a/x) otrzymane z v przez wstawienie elementu a jako wartości zmiennej x, spełnia formułę α(x).

Powiemy, że formuła α jest prawdziwa w strukturze STR wtedy i tylko wtedy, gdy jest ona spełniona przez każde wartościowanie w tej strukturze, tzn. gdy dla każdego v, STR,v|= α(x). Fakt ten zapisujemy krótko STR|= α.

Przykład 8.4.2

  1. Formuła (x + y >2) jest spełniona przez wartościowanie v, takie że v(x)=1 i v(y)=3 w strukturze liczb naturalnych, tzn. N, v |= (x + y >2). Zatem formuła ( ∃ x)( ∃ y)(x + y >2) jest prawdziwa w strukturze N, N |= ( ∃ x)( ∃ y)(x + y >2).W konsekwencji, formuła ( ∃ x)( ∃ y)(x + y >z) jest spełniona w strukturze liczb naturalnych przez wartościowanie v takie, że v(z)=2. Co więcej, ta ostatnia formuła spełniona jest dla każdej wartości zmiennej z w strukturze liczb naturalnych. Mamy więc N |= ( ∀ z) ( ∃ x) ( ∃ y)(x + y >z ).

  2. Jeśli formułę ((x + y) >2) rozważymy w zbiorze liczb rzeczywistych R, to dla wartościowania v, takiego że v(x)= 2- v(y) mamy R, v |= ¬ (x+y)>2. Zatem

    R |= ( ∃ x)( ∃ y)( ¬ ((x + y) >2)).

    Wynika stąd, że istnieje taka wartość dla zmiennej z, że formuła ( ∃ x)( ∃ y)( ¬ ((x + y) >z)) przyjmuje wartość prawda w R, czyli dla wartościowania v takiego, że v(z)=2 mamy R,v |= ( ∃ x)( ∃ y)( ¬ ((x + y) >z)). Łatwo zauważymy, że niezależnie od tego jaką wartość ma zmienna z w wartościowaniu v, spełniona jest formuła ( ∃ x)( ∃ y)( ¬ ((x + y) >z)), a więc mamy

    R |= ( ∀ z) ( ∃ x)( ∃ y)( ¬ ((x + y) >z)).

Pytanie 8.4.1 Zapisz następujące zdania w postaci formuł i zbadaj ich prawdziwość w strukturze liczb rzeczywistych.

  1. Między dowolnymi dwoma różnymi liczbami rzeczywistymi istnieje zawsze różna od nich liczba rzeczywista.

  2. Suma dowolnych dwóch liczb rzeczywistych jest mniejsza od iloczynu tych liczb.

Zobacz odpowiedź


« poprzedni punkt   następny punkt »