6700449620

1 Logika i rachunek zdań

Yet there is the constant desire to find some point in the twisting, knotting, raveling nets of space-time on which a metaphorical fln-ger can be put to indicate that here, here, is the point where it all

— Terry Pratchett, Hogfather

Zadanie 1.1. Które z następujących zdań są prawdziwe, a które fałszywe:

(a)    (2 >3) A (3 >2);

(b)    (2 > 3) V (3 > 2);

(c)    (2 > 3) => (3 > 2);

(d)    Jeżeli luty w pewnym roku ma 30 dni, to ten rok ma nieparzystą ilość dni;

(e)    Styczeń ma 31 dni lub marzec nie ma 31 dni?

Zadanie 1.2. Wykaż metodą zero-jedynkową, że każde z wyrażeń jest prawem logicznym: (a) pV - p (prawo wyłączonego środka) ;

(b)    (pA(~p|) (prawo sprzeczności)-,

(c)    p <=> ( — (— p)) (prawo podwójnej negacji)-,

(d)    MpAq)] •*=>• [(~ p) V (~ q)] (I prawo de Morgana¹)-,

(e)    [~ (p V q)] •*=> [(- p) A (~ q)] (// prawo de Morgana)-,

(f)    [pA(p => q)] ==> q (prawo odrywania);

(g)    b (P => q)l <=k [p V (~ q)] (prawo negacji implikacji)-,

(h)    (p V q) •(=> (q V p) (prawo przemienności alternatywy)-,

(i)    (p Aq) -*=k (q A p) (prawo przemienności koniunkcji);

(j)    pV(qVr] (pVq)Vr (prawo łączności alternatywy)-,

(k)    pA(qAr) -<=> (p A q) Ar (prawo łączności koniunkcji)-,

(l)    [p A (q Vr)] •;=> [(pAq)V(pAr)) (prawo rozdzielności koniunkcji względem alternatywy)-,

(m)    [p V (q Ar)] -s=> [(pVq)A(pVr)] (prawo rozdzielności alternatywy względem koniunkcji)-,

(n)    (~ p ==> p) => p (II prawo Clawusa,²)-,

(o)    (p =j• q) <=*• [(- q) => (~p)] (prawo transpozycji)-,

(p)    I(P =k q) A (q =*• r)] => (p =*• r) (prawo przechodności implikacji)-,

(q)    (P •*=*■ q) •*=► I(P => q)A(q =>• p)].

Zadanie 1.3. Sprawdzić, czy następujące zdania są tautologiami:

(a) l(p V q) A bp)l =► q; (b) p => [bp)Vq];    (c) ~-[pAbpAq)].

Zadanie 1.4. Oceń wartość logiczną zdań i zapisz je z użyciem kwantyfikatorów:

(a)    Istnieje taka liczba    rzeczywistej x zachodzi (d) Istnieje takie x < 1, że

rzeczywista x, że    nierówność x² — 9 < 0;    x² < 1.

^X ^ ^—    Di_a każdego x, jeśli x > 1,

(b)    Dla każdej liczby    to x² > 0;

1

‘Augustus De Morgan (1806-1871), angielski matematyk i logik.

2

Christophorus Clayius (1538-1612), wioski matematyk i astronom.