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.
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:
- formuła spełnialna
U={0, 1, 2, 3,…}
P(x) = „x≤y”
- wartość logiczna 1
U={…, -2, -1, 0, 1, 2…}
- wartość logiczna 0
Wybrane prawa rachunku predykatów:
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:
Tabelka tylko dla predykatów jednoargumentowych:
U={0, 1, 2, 3, …}
P(2) - 1
P(0) - 0
1
0
1
1
0
1
0
0
T
T
1
0
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
(…)
…
1
1
T
1
T
T
0
T
0
T
T
T
T
1, T
0, T
1, T
0, 1, T
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:
a jest nową stała niewystępującą w dowodzie, b…
... zobacz całą notatkę
Komentarze użytkowników (0)