8. Sprowadzanie do normalnej postaci k.a.
21 grudnia 2010
1. Usunąć z wyrażenia wszystkie równoważności stosując
(p ≡ q) ≡ [(p → q) ˄ (q → p)].
2. Usunąć z wyrażenia wszystkie implikacje stosując (p → q) ≡ (~ p ˅ q).
3. Dopóki można, to:
* upraszczać stosując (p ˅ p) ≡ p oraz (p ˄ p) ≡ p.
* usuwać zbędne negacje stosując prawo podwójnego przeczenia
~ ~ p ≡ p.
* stosować prawa de Morgana:
~ (p ˅ q) ≡ (~ p ˄ ~ q)
~ (p ˄ q) ≡ (~ p ˅ ~ q).
* stosować prawo rozłączności alternatywy względem koniunkcji:
p ˅ (q ˄ r) ≡ (p ˅ q) ˄ (p ˅ r).
Najczęściej stosowanymi prawami w otrzymywaniu z wyrażenia a jej postaci normalnej k.a. a’ są zatem:
1. (p ≡ q) ≡ (p → q) ˄ (q → p)
2. (p → q) ≡ ~ p ˅ q
3. ~ ~ p ≡ p
4. p ˅ q ≡ q ˅ p
5. p ˄ q ≡ q ˄p
6. p ˅ p ≡ p
7. p ˄ p ≡ p
8. p ˅ (q ˄ r) ≡ (p ˅ q) ˄ (p ˅ r)
9. ~ (p ˅ q) ≡ ~ p ˄ ~ q
10. ~ (p ˄ q) ≡ ~ p ˅ ~ q
11. p ˅ q ˅ r ≡ (p ˅ q) ˅ r ≡ p ˅ (q ˄ r)
12. p ˄ q ˄ r ≡ p ˄ (q ˄ r) ≡ (p ˄ q) ˄ r
Proste przykłady stosowania praw w doprowadzaniu wyrażeń logicznych do postaci n.k.a.:
Czy (p → ~ p) → ~ p jest tautologią?
1. (p → ~ p ) → ~ p
2. ~ (p → ~ p) ˅ ~ p
3. ~ (~ p ˅ ~ p) ˅ ~ p
4. ~ ~ p ˅ ~ p
5. p ˅ ~ p – tautologia
Czy (p ˄ ~ p) → q jest tautologią?
1. (p ˄ ~ p) → q
2. ~ (p ˄ ~p) ˅ q
3. ~ p ˅ ~ ~ p ˅ q
4. (~ p ˅ p ˅ q)- tautologia.
Czy (p → q) → ((p ˄ r) → (q ˄ r)) jest tautologią?
1. (p → q) → ((p ˄ r) → (q ˄ r))
2. ~ (p → q) ˅ ((p ˄ r) → (q ˄ r))
3. ~ (p → q) ˅ ~ (p ˄ r) ˅ (q ˄ r)
4. ~ (~ p ˅ q) ˅ ~ (p ˄ r) ˅ (q ˄ r)
5. (~ ~ p ˄ ~ q) ˅ ~ (p ˄ r) ˅ (q ˄ r)
6. (p ˄ ~ q) ˅ ~ (p ˄ r) ˅ (q ˄ r)
7. ((p ˄ ~ q) ˅ (~ p ˅ ~ r) ˅ (q ˄ r)
8. ((p ˄ ~ q) ˅ (~ p ˅ ~ r ˅ q)) ˄ ((p ˄ ~ q) ˅ (~ p ˅ ~ r ˅ r ))
9. (p ˅ ~ p ˅ ~ r ˅ q) ˄ (~ q ˅ ~ p ˅ ~ r ˅ q) ˄ ((p ˄ ~ q) ˅ (~ p ˅ ~ r ˅ r))
10. (p ˅ ~ p ˅ ~ r ˅ q) ˄ (~ q ˅ ~ p ˅ ~ r ˅ q) ˄
˄ (p ˅ ~ p ˅ ~ r ˅ r) ˄ (~ q ˅ ~ p ˅ ~ r ˅ r)
Uwaga. Podkreślony funktor lub wyrażenie zawierające funktor oznacza, że funktor ten na podstawie odpowiedniego prawa będzie przekształcony i inna postać. Nową postać zawiera następny krok (numer) procedury doprowadzania do postaci normalnej.