trafił mi się taki dowód do zrobienia:
I chyba nie rozumiem co my mamy tutaj dowieść. Jeśli \(\displaystyle{ F}\) jest sprzeczna, to wystarczy za \(\displaystyle{ F'}\) wziąć \(\displaystyle{ p \wedge \neg p}\) i mamy taką formułę. Jeśli \(\displaystyle{ F}\) jest spełnialna, to weźmy formułę \(\displaystyle{ F' = p}\)... no ale strzelam, że nie o to chodziło w zadaniu. Chyba, że chodzi o formułę równoważną do F, no ale można byłoby to napisać wprost, że "istnieje formuła równoważna długości \(\displaystyle{ O(N)}\)", oczywiście z drugiej strony konwersja F do postaci CNF (tym najbardziej popularnym algorytmem) może mieć wykładniczo wiele literałów, więc nie aplikuje się kompletnie do zadania.Pokaż, że dla danej formuły zdaniowej \(\displaystyle{ F}\) o długości \(\displaystyle{ N}\) istnieje formuła zdaniowa \(\displaystyle{ F'}\) w CNF o długości \(\displaystyle{ O(N)}\), spełnialna wtedy i tylko wtedy, gdy \(\displaystyle{ F}\) jest spełnialna
Może ktoś już miał takie zadanie i wie "co autor miał na myśli"? Czy może to ja już za dużo zapomniałem z logiki?
