7. Normalna postać koniunkcyjno – alternatywna
21 grudnia 2010
Wyrażenie a jest w postaci normalnej koniunkcyjno – alternatywnej a’ wtedy i tylko wtedy, gdy jest koniunkcją pewnej liczby alternatyw a1, a2, a3, …, an, przy czym członami alternatyw są zmienne zdaniowe lub negacje zmiennych zdaniowych:
Twierdzenie. Jeśli a jest w postaci normalnej koniunkcyjno – alternatywnej i a jest koniunkcją alternatyw a1, a2, a3, …, an, to a jest tautologią wtedy i tylko wtedy, gdy w każdej alternatywie a1, a2, a3, …, an , pewna zmienna występuje bez negacji i z negacją.
a’ = (p ˅ q ˅ …~ p ˅ ~ r) ˄ …˄ (p ˅ ~ s ˅ …).
a1 = (p ˅ q ˅ …~ p ˅ ~ r), …, an = (p ˅ ~ s ˅ …).
Przykłady.
| Formuła w postaci n.k.a. |
Tautologia? |
| (p ˅ ~ p) ˄ (q ˅ r ˅ ~ q) |
tak |
| (p ˅ q ˅ ~ p) ˄ (q ˅ ~ r) |
nie |
| P ˅ ~ q ˅ r ˅ ~ p |
tak |
| (p ˅ ~ q) ˄ (~ p ˅ q) |
nie |