Jakiś problem?

Bez kategorii

Rachunek predykatów, przykład teorii w rachunku predykatów

by  •  • 0 Comments

Jeśli \textnormal{n} jest liczbą pierwszą to \textnormal{n} jest liczbą nieparzystą lub \textnormal{n} jest równe 2.

Opisaliśmy je wtedy formułą

p \Rightarrow (q \vee r).

w której p,q,r odpowiadały odpowiednio zdaniom

    1. \textnormal{n} jest liczbą pierwszą,
    2. \textnormal{n} jest liczbą nieparzystą,
    3. \textnormal{n} jest równe 2.

Podstawiając zamiast zdania \textnormal{n} jest liczbą pierwszą zmienną zdaniową \textnormal{p} ukrywamy jednak część informacji. Zdanie to mówi przecież o pewnej liczbie \textnormal{n}, co więcej zdania {p,q} i \textnormal{r} dotyczą tej samej liczby \textnormal{n}. Zapiszmy więc p(n) zamiast {p} aby podkreślić fakt że prawdziwość {p} zależy od tego jaką konkretną wartość przypiszemy zmiennej \textnormal{n}. Zdanie p(n) będzie prawdziwe jeśli za \textnormal{n} podstawimy jakąś liczbę pierwszą i fałszywe w przeciwnym przypadku. Zgodnie z tą konwencją nasze zdanie przyjmie postać

p(n) \Rightarrow (q(n) \vee r(n)).

Zwróćmy uwagę jednak, że trudno ocenić prawdziwość zdania \textnormal{p} dopóki nie podstawimy w miejsce \textnormal{n} jakiejś konkretnej liczby. Z drugiej strony jednak zdanie jakąkolwiek liczbę nie postawimy w miejsce \textnormal{n} zdanie będzie prawdziwe. Możemy więc przeformułować je jako

Dla każdej liczby naturalnej \textnormal{n}, jeśli \textnormal{n} jest liczbą pierwszą to \textnormal{n} jest liczbą nieparzystą lub \textnormal{n} jest równe 2.

Aby móc formalnie zapisywać zdania takie jak powyższe wprowadzimy kwantyfikator \forall który będzie oznaczał ,,dla każdego” oraz \exists który będzie oznaczał ,,istnieje”. Każde wystąpienie kwantyfikatora będzie dotyczyło pewnej zmiennej. W naszym przykładzie napiszemy

\forall_n p(n) \Rightarrow (q(n) \vee r(n)). \quad \mbox{(1.1)}

Możemy teraz powiedzieć, że powyższa formuła jest prawdziwa w zbiorze liczb naturalnych, gdzie p(n),q(n),r(n) będą oznaczać odpowiednio \textnormal{n} jest liczbą pierwszą, \textnormal{n} jest liczbą nieparzystą, \textnormal{n} jest równe 2.

Przy tej samej interpretacji p(n),q(n) moglibyśmy wyrazić zdanie

Istnieje parzysta liczba pierwsza.

jako

\exists_n p(n) \wedge \neg q(n) \quad \mbox{(1.2)}

Kwantyfikatory ograniczone

Kwantyfikatory ograniczone są skrótami które definujemy następująco

1. \forall_{x:\phi} \psi \stackrel{\textrm{def}}{\equiv} \forall_x \phi \Rightarrow \psi
2. \exists_{x:\phi} \psi \stackrel{\textrm{def}}{\equiv} \exists_x \phi \wedge \psi

i czytamy

1. dla każdego \textnormal{x} które spełnia {\phi} spełnione jest {\psi}
2. istnieje \textnormal{x} spełniające {\phi} które spełnia {\psi}

Zgodnie z tą konwencją formułę 1.1 możemy zapisać następująco

\forall_{n:p(n)} q(n) \vee r(n).

Podobnie formułę 1.2 zapiszemy jako

\exists_{n:p(n)}\neg q(n)

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *