Spełnialność formuł logicznych
Z Wikipedii
 |
Zasugerowano, aby ten artykuł zintegrować z artykułem spełnianie formuły zdaniowej. |
|
|
Zasugerowano, aby ten artykuł zintegrować z artykułem spełnialność formuły zdaniowej. |
Spełnialność formuł logicznych – własność polegająca na posiadaniu przez formułę logiczną takiego wartościowania, które czyni ją prawdziwą. O takim wartościowaniu mówimy, że spełnia ono daną formułę i nazywamy je wartościowaniem spełniającym.
Można pokazać, że jeśli formuła logiczna jest tautologią to jej negacja nie jest spełnialna.
Problem stwierdzania, czy zadana formuła logiczna jest spełnialna, to bardzo ważny ze względów teoretycznych problem teorii złożoności obliczeniowej. W zależności od postaci formuły jest on uważany za problem łatwy (tj. istnieje algorytm wielomianowy pozwalający na jego rozwiązanie) lub trudny (tj. prawdopodobnie algorytm wielomianowy dla niego nie istnieje).
