Informatyka MIMUW

Wprowadzenie

Na początku rozdziału o logice zdaniowej rozważaliśmy zdanie

Jeśli $\mathrm {n}$ jest liczbą pierwszą to $\mathrm {n}$ jest liczbą nieparzystą lub $\mathrm {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. $\mathrm {n}$ jest liczbą pierwszą,

2. $\mathrm {n}$ jest liczbą nieparzystą,

3. $\mathrm {n}$ jest równe 2.

Podstawiając zamiast zdania $\mathrm {n}$ jest liczbą pierwszą zmienną zdaniową $\mathrm {p}$ ukrywamy jednak część informacji. Zdanie to mówi przecież o pewnej liczbie $\mathrm {n}$, co więcej zdania ${p,q}$ i $\mathrm {r}$ dotyczą tej samej liczby $\mathrm {n}$. Zapiszmy więc $p(n)$ zamiast ${p}$ aby podkreślić fakt że prawdziwość ${p}$ zależy od tego jaką konkretną wartość przypiszemy zmiennej $\mathrm {n}$. Zdanie $p(n)$ będzie prawdziwe jeśli za $\mathrm {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 $\mathrm {p}$ dopóki nie podstawimy w miejsce $\mathrm {n}$ jakiejś konkretnej liczby. Z drugiej strony jednak zdanie jakąkolwiek liczbę nie postawimy w miejsce $\mathrm {n}$ zdanie będzie prawdziwe. Możemy więc przeformułować je jako

Dla każdej liczby naturalnej $\mathrm {n}$, jeśli $\mathrm {n}$ jest liczbą pierwszą to $\mathrm {n}$ jest liczbą nieparzystą lub $\mathrm {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 $\mathrm {n}$ jest liczbą pierwszą, $\mathrm {n}$ jest liczbą nieparzystą, $\mathrm {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)}$