Język rachunku predykatów:
zmienne x, y, z
predykaty n-argumentowe P(x, y…), Q(x, y…)
funktory zdaniowe
kwantyfikatory: istnieje ∃, dla każdego ∀
Ustalenie dziedziny (uniwersum) U dla zmiennych x, y, z oraz określenie predykatów P, Q, R,… w U nazywamy interpretacją.
Przykład:
Każda liczba parzysta jest sumą dwóch liczb pierwszych.
$$\left. \ \begin{matrix}
U = \{ 0,\ 1,\ 2,\ 3\ldots\} \\
P\left( x \right) - \ "x\ jest\ parzysta" \\
\begin{matrix}
Q\left( x \right) - \ "x\ jest\ pierwsza" \\
R\left( x,y,z \right) - \ "z = x + y" \\
\end{matrix} \\
\end{matrix} \right\}\text{interpretacj}a$$
∀x(P(x)→∃y∃z(Q(y)∧Q(z)∧R(y,z,x)))
Formuła jest spełnialna, jeżeli jest zdaniem prawdziwym w pewnej interpretacji. Formuła jest prawdziwa (jest tautologią rachunku predykatów), jeżeli jest zdaniem prawdziwym w każdej interpretacji.
Przykład:
∃x∀yP(x, y) -> formuła spełnialna
U={0, 1, 2, 3,…}
P(x) = „x≤y”
∃x∀y(x≤y) - wartość logiczna 1
U={…, -2, -1, 0, 1, 2…}
∃x∀y(x≤y) - wartość logiczna 0
Wybrane prawa rachunku predykatów:
∀x(P(x)→P(x))
∼∀xP(x)≡∃x(∼P(x))
∼∃xP(x)≡∀x(∼P(x))
∀x(P(x)∧Q(x)) ≡ (∀xP(x)∧∀xQ(x))
∃x(P(x)∨Q(x)) ≡ (∃xP(x)∨∃xQ(x))
(∀xP(x)∨∀xQ(x)) → (∀x(P(x)∨Q(x))
∃x(P(x)∧Q(x))→(∃xP(x)∧∃xQ(x))
∀x(P(x)→Q(x)) → (∀xP(x)→∀xQ(x))
∃x(P(x)→Q(x)) ≡ (∀xP(x)→∃xQ(x))
∃x∀xP(x,y) → ∀x∃xP(x,y)
T6, T7, T8, T10 – implikacje odwrotne tych zdań nie są tautologiami.
Pokazano, że nie istnieje ogólna metoda (algorytm) rozstrzygający, czy zadana formuła rachunku predykatów jest tautologią. W ogólnym przypadku problem ten jest więc bardzo trudny.
Tautologię można czasami udowodnić korzystając z praw logiki oraz ze znanych tautologii.
Prawa logiki:
L = ∃x(P(x)→Q(x)) ≡ ∃x(∼P(x)∨Q(x))≡∃x ∼ P(x) ∨ ∃xQ(x) ≡ ∼∀xP(x) ∨ ∃xQ(x) ≡ ∀xP(x) → ∃xP(x) = P
Tabelka tylko dla predykatów jednoargumentowych:
$$P(x)\left\{ \begin{matrix}
1 - zawsze\ prawda \\
0 - zawsze\ falsz \\
T - czasem\ prawda,\ czasem\ falsz \\
\end{matrix} \right.\ $$
U={0, 1, 2, 3, …}
$$\left. \ \begin{matrix}
P\left( x \right) - \ x\ jest\ parzyste \\
Q\left( x \right) - \ x\ jest\ nieparzyste \\
R\left( x \right) - \ x\ jest\ pierwsze \\
\end{matrix} \right\} T$$
P(2) – 1
P(0) – 0
P(x) |
∼P(x) |
∃xP(x) |
∀xP(x) |
|---|---|---|---|
| 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| T | T | 1 | 0 |
P(x) |
Q(x) |
P(x)∨Q(x) |
P(x)∧Q(x) |
P(x)→Q(x) |
P(x)≡Q(x) |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | T | 1 | T | T | T |
| 0 | 1 | 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | T | T | 0 | 1 | T |
| T | 1 | 1 | T | 1 | T |
| T | 0 | T | 0 | T | T |
| T | T | 1, T | 0, T | 1, T | 0, 1, T |
P(x) |
Q(x) |
∀xP(x) (A) |
∀xQ(x)(B) |
A ∨ B (α) |
P(x)∨Q(x)(C) |
∀xC (β) |
α → β |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | T | 1 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 0 | T | 0 | 0 | 0 | T | 0 | 1 |
| T | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| T | 0 | 0 | 0 | 0 | T | 0 | 1 |
| T | T | 0 | 0 | 0 | 1, T | 1, 0 | 1 |
W dowodach, w których korzystamy z kwantyfikatorów, można stosować wszystkie reguły z rachunku zdań. Dodatkowo stosujemy następujące reguły wnioskowania:
$$\mathbf{O\exists:\ }\frac{\mathbf{\exists}_{\mathbf{x}}\mathbf{P}\left( \mathbf{x} \right)}{\mathbf{P}\left( \mathbf{a} \right)}\mathbf{\text{\ \ }}$$
$$\mathbf{O\forall:}\frac{\mathbf{\forall}_{\mathbf{x}}\mathbf{P}\left( \mathbf{x} \right)}{\mathbf{P}\left( \mathbf{b} \right)\mathbf{,\ P}\left( \mathbf{x}^{\mathbf{*}} \right)}\mathbf{\text{\ \ \ }}$$
$$\mathbf{O\exists:}\frac{\mathbf{P(b)}}{\mathbf{\exists}_{\mathbf{x}}\mathbf{P(x)}}$$
a jest nową stała niewystępującą w dowodzie, b jest dowolną istniejącą już stałą, x* jest nową zmienną wolną. Reguły te pozwalają udowodnić tylko niektóre wnioskowania. Można wprowadzić regułę D∀, ale jest na dosyć skomplikowana.
Przykład:
∀x(P(x)→Q(x)) → (∃xP(x) → ∃xQ(x))
1 : ∀X(P(x)→Q(x)) zal.
2 : ∃xP(x)
3 : P(a)O∃ 2
4 : P(a) → Q(a)O∀ 1
5 : Q(a)RO 3, 4
6 : ∃xQ(x)D∃ 5
nie wprost:
∀x ∼ P(x) → ∼∃xP(x)
1 : ∀x ∼ P(x) zal.
2 : ∃xP(x) z.d.n.
3 : P(a) O∃ 2
4 : ∼P(a)O∀ 1
sprzecznosc 2, 4