diskreciosios irodymas su KNF padekit

(p→q)→((p^r)→(q^r))


reikia įrodyti šy reiškinį su KNF. Šitas ženklas ^ reiškia konjunkscija, → - implikacija.

Kas tas KNF?

Konjunkcinė normalioji forma

(p→q)→((p∧r)→(q∧r))

Pirma pakeiskime visus A→B į (¬A)∨B:

(¬p∨q)→(¬(p∧r)∨(q∧r))
¬(¬p∨q)∨(¬(p∧r)∨(q∧r)).

Tuomet sukelkime visus ¬ kuo giliau į skliaustus ( keisime ¬(A∨B) į ((¬A)∧(¬B)), o ¬(A∧B) į ((¬A)∨(¬B)) ):

(¬¬p∧¬q)∨((¬p∨¬r)∨(q∧r)).

Panaikinkime ¬¬:

(p∧¬q)∨((¬p∨¬r)∨(q∧r)).

Dabar pertvarkysime konjunkcijas ir disjunkcijas taip, kad gautume KNF. Naudosime įprastus distributyvumo dėsnius ( (A∨B)∧C yra tapatu (A∧C)∨(B∧C), (A∧B)∨C yra tapatu (A∧C)∨(B∧C) ir panašiai ):

(p∧¬q)∨((¬p∨¬r∨q)∧(¬p∨¬r∨r))    [jau dabar galėtume numesti ¬r∨r ir kartu viso ¬p∨¬r∨r, bet atlikime viską skausmingai detaliai]
(p∨((¬p∨¬r∨q)∧(¬p∨¬r∨r)))∧(¬q∨((¬p∨¬r∨q)∧(¬p∨¬r∨r)))
(p∨¬p∨¬r∨q)∧(p∨¬p∨¬r∨r)∧(¬q∨¬p∨¬r∨q)∧(¬q∨¬p∨¬r∨r).

Paskutinė eilutė parodo (vieną) KNF, ekvivalenčią pradiniam reiškiniui. Kiekviena disjunkcija turi po elementarųjį reiškinį su jo neiginiu: atitinkamai, p ir ¬p, p ir ¬p, q ir ¬q bei r ir ¬r, todėl pradinė formulė yra tapačiai teisinga.

Aciu labai ;)