Przykład do definicji Koniunkcyjna postac normalna

(p v ~q v r) ^ (~p v ~r) ^ ~q

Obrazek z godziny 15:17 Tam gdzie duże K powinny być kropki kurwa

(p -> 1) ^ (q -> r) -> (p -> r)

~[(p -> q) ^ (q -> r) ] v ( p -> r)

~[(~p v q) ^ (~q v r)] v (`p v r)

~(~p v q) v ~(~q v r) v (~p v r)

(~~p ^ ~q) v (~~q ^ ~r) v (~p v r)

(p ^ ~q) v (q ^ ~r) v (~p v r)

[(p v q) ^ (p v ~r) ^ (~q v q) ^ (~q v ~r) ] v (~p v r)

( p v q v ~p v r) ^ (p v ~r v ~p v r) ^ (~q v q v ~p v r) ^ (~p v ~r v ~p v r)

Przykład do DEF postac klauzylowa formuly w KPN

A: (pp v ~q v r) ^ (~p v ~r) ^ ~q

∑(A) = { {p, ~q, r} , {~p, ~r}, {~p} }

Uzasadnienie algorytmu 1.2
Formuła A jest tautologia KRZ

Fakt 1.1 (równoważność pionowa xD)

Formuła Ą nie jest spełnialna

Fakt 1.8

Formuła KPN(~A) nie jest spełnialna

Fakt 1.8

Zbiór suma(KPN(~A)) nie jest spełnialna

Twierdzenie 1.3
suma(KPN(~A)) |- _RZ

Na mocy faktu 1.7 istnieje algorytm pozwalający sprawdzić czy ze zb. ∑(KPN(~A)) da się wyprowadzić klauzulę pustą

PRZYKŁAD TAKI BĘDZIE NA EGZAMINIE HAHAHAHAHAHAHAHAHAHA

NIE WOLNO TABELKOWO BO REZOLUCJA RZĄDZI !!

\Przykład 1.

Problem : Czy formuła A: ( p -> q) -> (~q -> ~p) jest tautologią KRZ ?

Zasotosujemy powyższy algorytm

Za b przyjmujemy negacje formuły

1. B: ~[)p ->q) -> (~Q -> ~P)]

2. Sprowadzamy B do postaci KPN(B) Musimy pozbyć się omplikacji ~(p -> q) <-> p ^ ~q

(p -> q) ^ ~(~q -> ~q )

(~p v q) ^ ~q ^ ~~p

(~p v q) ^ ~q ^ p – KPN(B)

3. KPN (B) przedstawiamy w postaci klauzulowej:

Suma(KPN(B)) = { (~p ^ q) , {~q} , {p}}

Czy da się wyprowadzić z tego zbiór pusty ? jak myślicie moi drodzy

{~p, q} {~q}

RZ

{~p} {p}

RZ

Odp. A jest tautologia KRZ

Przykład 2

A: p v q -> p ^ ~q

Wykorzystam znowu nasz powyższy algorytmm
Za B przyjmujemy negacje A
1. B: ~(p v q -> p ^ ~q)

2. Sprowadzamy b do postaci KPN(V)

Pozbywamy się znowu implikacji tamtym prawem :D

(p v q) ^ ~(p ^ ~q)

Prawo DeMorgana wprowadzając je do srodka ? wtf

(p v q) ^ (~p v ~~q)

(p v q) ^ (~ p v q}

Przedstawiamy KPN(B) w postaci klauzulowej

Suma(KPN(B) = { {p,q} {~p, q} }

{ p,q } {~p,q}

RZ(rezolucja)

{q}

Nic dalej nie możemy zrobić czyli widać ze nie jest to tautologia :D Nie da się otrzymać rezolucji pustej :D

Przykłady 3 już jest ale super :D

A: ( p -> q) ^ (q -> r) -> (p -> r)

1. B: ~[ (p -> q) ^ (q ->r) -> (p ->r) ]

2. SprowadzamyB do postaci KPN(B)

(p -> q) ^ (q -> r) ^ ~(p -> r
Prawa do zabawy

~(A->B) <-> A^ ~B

(A -> B) <-> ~A v B

(~p v q) ^ (~q v r) ^ p ^ ~r – KPN(B)

1. Podstawiamy do postaci klauzulowej

Suma(KPN(B)) = { { ~p,q}, {~q,r} ,{p}, {~r}}

{~p,q} {~q,r}

{~p,r} {p}

{r} {~r}

I wszystko się zredukowało :D:D Klauzula pusta A jest tautologia :D:D:D:D

Przykładzik 4 ale zapierdalamy z koksem :D

~(p ^ q) <-> (~p v ~q)

B: ~[~(p ^ q) <-> (~p v ~q)]

Sprowadzamy B do postaci KPN(B) ale jest rownowaznosc to trzeba na 2 implikacje rozjebac

~[(~(p^q) -> (~p v ~q)) ^ ((~p v ~q) -> ~(p ^ q))]

~[~(p ^ q) -> (~p v ~q)] v ~[(~p v ~q) -> ~(p ^ q)] < prawo de morgana

~(p ^ q) ^ ~(~p v ~q)] v [( ~p v ~q) ^ p ^ q]

[(~p v ~q) ^ p ^ q] v [( ~p v ~q) ^ p ^ q] Możemy opuścić jeden składnik bo jedno musi być prawdziwe

(~p v ~q) ^ p ^ q – KPN(B)

Przedstawiamy B w postaci klauzulowej:

Suma(KPN(B) = {{~p,~q}, {p], {q}}

{~p,~q}{p}

{~q} {q}

I znowu się skróciło i zyjemy długo i szczęśliwie :D

JEST TAUTOLOGIA CZAISZ TO :D ?nie

Przykład 5

~(p -> q) -> p ^ q

~[~(p -> q) -> p ^ q ]

Sprowadzamy B do KNP

~(p -> q) ^ ~(p ^ q)

P ^ ~q ^ (~p ^ ~q) – KNP(B)

Przedstawiamy w postaci klauzulowej

Suma KPN(B) = { {p}, {~q} {~p,~q}}

{p} {~p, ~q}
{~q}

Nie da się dalej zastosować reguły rezolucji :D bieżmy takie pary by chociaż raz zastosować te RZ :D