2212790601

Ćwiczenie 2

Tautologie. Konsekwencje logiczne. Rezolucja. Logika pierwszego rzędu

2.1    Zadania teoretyczne

2.1.1    Tautologie

1. Sprawdzić, czy formuła (p V q) (~ p => q) jest tautologią.

Rozwiązanie:

(a) metoda zero-jedynkowa

p	</	pV?	~p	~p=* q	(P V ę) =S- (~ p =*• q)
0	II	0	1	0	1
0	1	1	1	i	1
1	0	1	0	i	1
1	1	1	0	i	1

(b)    skrócona metoda zero-jedynkowa

1.    it>[(pV₉)=>(~p=>ą)] = 0

2.    u>(pVg) = l    tu(~p=t-g)    =    0

3.    tn(~p) = l u;(<?) = 0 w(p) = 0

4.    (0 V 0) = 1

5.    0=1 SPRZECZNOŚĆ

Komentarz: 1. zakładamy falszywość formuły; 2. ponieważ funktorem głównym jest implikacja, stąd jej poprzednik musi    być prawdziwy, a następnik fałszywy; 3. warunek w (~ p ^    q)    =    0 jest    fałszywą    implikacją,

stąd w (~ p) —    1,    tzn. w (p)    = 0 i w (q) = 0; 4. podstawiamy w (p) = 0 i w (<j) =    0 do warunku    w    (p V q)    —    1;

5. otrzymujemy sprzeczność, zatem nie udowodniliśmy fałszywości formuły.

(c)    metoda przekształcenia do postaci normalnej

(P V q) => (~ p => q) =

1.    =~(pVę)V[~(~p)Vgj =

2.    =(~pA~?)V(pV?) =

3b.    = (~_pVpVę) A (~_ęVpVg) =

= 1 Al = 1

Obydwie dysjunkcje elementarne są tautologiami — pierwsza zawiera parę literałów komplementarnych {p, ~p}, druga zawiera parę {</, ~ </}.

Odpowiedź: Formuła jest tautologią.