64348 Scan0011

18 Funktory i formuły

1.7.2 Metoda tablic wartości logicznych

Postać dpn tworzymy biorąc te wiersze, dla których formuła jest prawdziwa i przypisując wartościom 1 literały pozytywne, a wartościom 0 — literały negatywne.

Postać kpn tworzymy biorąc te wiersze, dla których formuła jest fałszywa i przypisując wartościom 1 literały negatywne, a wartościom 0 — literały pozytywne.

Przykład 1.9 Dla funkcji określonej tablicą

V	Q	A
0	0	0
0	1	1
1	0	1
1	1	0

otrzymujemy:

•    dpn:    A — (~ p A q) V (p    A ~ q),

•    kpn:    A = (p    V q) A (~ p    V ~ q).

1.8 Zadania

1.    Zbadać, czy formuły A i B są logicznie równoważne.

(a) A = ~ p V q, B = ~ (p A ~ q)

(b) A = ~ {p => q), B = (p ^ ~ q) [ q

(c)    A = ~ (p i q), B=(~p) | (~ q)

2.    Uprościć formuły dla w (p) = 1, a następnie dla w (p) = 0.

(a)    (p V ~ q) A q Rozwiązanie:

•    dla    w (p) — 1,    {p V ~    q)    A q = (1    V    ~    q) A q =    1    A    q    =    q.

•    dla    w (p) = 0,    (p V ~    q)    A q = (0    V    ~    q) A q =    ~    q    A    q    = 0.

(b)    p V g

(c)    p => ą

(d)    P g