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.

• 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).

(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).

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

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