Spełnialność formuł logicznych
Z Wikipedii
Spełnialność formuł logicznych to 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 wielomianowy algorytm dla niego nie istnieje).
