Roztrzygalność- tautologia.
: 28 cze 2016, o 14:22
Cytat pochodzi z ... 15_p5.htmlProblem sprawdzenia, czy formuła klasycznej logiki predykatów jest tautologią, jest nierozstrzygalny. Jeśli dana formuła rachunku predykatów jest tautologią, to umiemy się o tym przekonać w skończonym czasie. Jeśli jednak nie jest to tautologia, to nie ma takiej metody, która po skończonej liczbie kroków pozwoliłaby przerwać postępowanie i zdecydować, że to nie jest tautologia. J
Nie mogę zrozumieć dlaczego jest to problem nieroztrzygalny. Przecież wystarczy sprawdzić wszystkie możliwości, których jest \(\displaystyle{ 2^n}\) gdzie \(\displaystyle{ n}\) to ilość klauzul, które przyjmują wartość 0/1. Sprawdzamy wszystkie możliwości. Jeżeli któraś wyewaluuje nam wartość zdania do fałszu to mamy rozstrzygnięcie.