logika Mateusz: Witam, może mi ktoś powiedzieć dla jakich przypadków dana formuła logiczna NIE jest spełniana? Mamy zdanie składające się z alternatywy klauzul. Klauzulą nazywamy koniunkcję literałów (zmienna bądź jej zaprzeczenie). Przykład: (x₁ ⋀ ¬x₂) ⋁ ¬x₂. Jest ona spełniona dla x₁ = 1 i x₂ = 0. No więc nasuwa się jedna teza: Każde zdanie jest spełnione wtedy i tylko wtedy, gdy przynajmniej jedna klauzula jest spełniona. A spełniona jest wtedy gdy nie występują w niej zmienne x_n i ¬x_n. Idę dobrym torem? Jeśli nie to proszę o podanie kontrprzykładu

Saris: Klauzula to alternatywa zmiennych lub ich negacji. Forma logiczna do koniunkcja klauzul. Coś chyba pokręciłeś.

Mateusz: http://www.spoj.com/ALGOLIGA/problems/AL_29_02/ nawiązałem do tego

Saris: Dobra trochę sobie odświeżyłem pamieć. To co ty masz to DNF (disjunctive normal form − dysjunkcyjna postać normalna) czyli formuła logiczna w postaci alternatywy klauzul dualnych. Ja spotykałem się raczej z postacią CNF (koniunkcyjna postać normalna) czyli w postaci koniunkcji klauzul. Różnica jest taka, spełnialność pierwszej to problem łatwy (wielomianowy), a drugiej gdy ilość literałów w klauzuli przekracza 2 to problem NP−zupełny. Nieważne. Spełnialność DNF: "Problem znajdowania wartościowania spełniającego formuły w postaci DNF jest problemem łatwym, tzn. istnieje algorytm wielomianowy rozwiązujący ów problem. Jeśli bowiem jest choć jedna klauzula dualna, która nie zawiera ani fałszu ani jednocześnie pewnej zmiennej i jej negacji, możemy wszystkim wystąpieniom pozytywnym przyporządkować prawdę, negatywnym zaś fałsz, przez co ta klauzula dualna będzie spełniona, a zatem i cały DNF. Jeśli natomiast każda klauzula dualna zawiera albo fałsz (a więc jest fałszywa), albo jednocześnie zmienną i jej zaprzeczenie (z których przynajmniej jedno musi być fałszywe), to oznacza to, że nie jest ona spełnialna." Czyli Twoja teza jest prawdziwa o ile dodasz w niej, że oprócz tego, że nie wystąpi dany literał i jego negacja, to reszta literałów będzie wartościowana na prawdę. Ogólnie poczytaj sobie to: https://pl.wikipedia.org/wiki/Problem_spe%C5%82nialno%C5%9Bci https://pl.wikipedia.org/wiki/Koniunkcyjna_posta%C4%87_normalna https://pl.wikipedia.org/wiki/Dysjunkcyjna_posta%C4%87_normalna Dla Ciebie najbardziej przyda się link 3.

Mateusz: Dziękuję