39867 Scan0015 (2)

2.3 Wynikanie logiczne 23

Ponieważ otrzymaliśmy sprzeczność, stąd formuła nie może przyjmować wartości 0. Zatem jest tautologią.

2.2.3    Metoda przekształcenia do postaci normalnej

Definicja 2.2 Parą literałów komplementarnych nazywamy zbiór {p, ~ p}, gdzie p jest dowolnym atom,em.

Uwaga 2.1 Dla pary literałów komplementarnych zachodzą związki: pV~j)sl, p A ~ p = 0.

Twierdzenie 2.1 Formuła w koniunkcyjnej postaci normalnej jest tautologią wtw, gdy wszystkie tworzące ją dysjunkcje zawierają pary literałów komplementarnych, a więc gdy wszystkie czynniki koniunkcji są tautologiami.

Twierdzenie 2.2 Formuła w dysjunkcyjnej postaci normalnej jest kon-trtautologią wtw, gdy wszystkie tworzące ją koniunkcje zawierają pary literałów komplementarnych, a więc gdy wszystkie składniki dysjunkcji są kontrtautologiami.

Przykład 2.3 Czy formuła z przykładu 1.8 jest tautologią? Po przekształceniu mamy:

(p V q) => (q V r) = (~ p V q V r) A (~ q V q V r) = (~ p V q V r) A 1.

Pierwsza dysjunkcja nie jest tautologią (nie zawiera literałów komplementarnych), druga jest tautologią (zawiera parę {~ q,q}), zatem formuła nie jest tautologią (dla w (p) = 1, w (q) = 0, w (r) = 0 ma wartość 0).

2.3    Wynikanie logiczne

Definicja 2.3 Zbiór formuł U = {A\,... ,A_n} nazywamy (jednocześnie) spełnialnym, gdy istnieje taka interpretacja, że wartością każdej formuły Ai jest 1. Interpretację o tej własności nazywamy modelem zbioru formuł.