====== Logika - Zadanie 67. ======

$(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