Scan0009 (2)

16 Funktory i formuły

•    p <=> q = (p => q) A (q => p) = (~ p V q) A (~ q V p),

• p | q = ~ (jo A g)    (dysfunkcja Sheffera jako negacja koniunkcji),

• P iq    (p V <?)    (binegacja jako negacja alternatywy),

•    P V g = (p | p) | {q | q).

1.6    Postacie normalne (kanoniczne)

Definicja 1.6 Literałem nazywamy atom oraz negację atomu. Atom jest literałem pozytywnym, a negacja atomu — literałem negatywnym.

Przykład 1.5

•    p, q — literały pozytywne,

•    ~ p, ~ q — literały negatywne,

•    ~ {p A q) — to nie jest literał.

Definicja 1.7 Formuła ma dysjunkcyjną postać normalną (dpn), jeśli jest dysjunkcją koniunkcji literałów (tzw. koniunkcji elementarnych).

Przykład 1.6

(p) V (p A r) V (~ q A r).

Definicja 1.8 Formuła ma koniunkcyjną postać normalną (kpn), jeśli jest koniunkcją dysjunkcji literałów (tzw. dysjunkcji elementarnych).

Przykład 1.7

(p V ~ p V q) A (~ r) A (q V r).

1.7    Konstruowanie postaci normalnych

Postacie normalne można otrzymać na drodze przekształceń lub bezpośrednio z tablicy wartości logicznych.