Spełnialność formuł logicznych
Z Wikipedii, wolnej encyklopedii
 |
Zasugerowano, aby zintegrować ten artykuł z artykułem spełnianie formuły zdaniowej. Nie opisano powodu propozycji integracji. |
|
|
Zasugerowano, aby zintegrować ten artykuł z artykułem spełnialność formuły zdaniowej. Nie opisano powodu propozycji integracji. |
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).
