(p\vee q)\wedge(p\vee r)
Załóżmy, że istnieje formuła CNF_1 jej równoważna. W jednej z klauzul musiałaby zawierać literał p lub \neg p, ponieważ inaczej dla wartościowań \{(p,T),(q,F),(r,F)\} i \{(p,F),(q,F),(r,F)\} przybierałaby tę samą wartość, podczas gdy nasza formuła przybiera dla pierwszego T, a dla drugiego F. Co więcej, dla p prawdziwego \cdots pierdolę, dalej nie robię. Człowiek się stara, a w zamian tylko kłamstwa i oskarżenia.
Pytanie do autora: Nie wystarczyłoby podać dowolnej tautologi? Wtedy każda klauzula zawiera przynajmniej jeden literał zarówno pozytywny, jak i negatywny (w każdym wartościowaniu albo jeden albo drugi będzie prawdziwy). Co z kolei oznacza, że literał ten wystąpił więcej niż raz, czyli spełnia warunki zadania. Pozdrawiam.
Re: Chyba nie bo tautologie można zapisać jako T co będzie przy okazji CNF