W arytmetyce liczb zachodzi prawo rozdzielności dodawania względem mnożenia. Mówi ono tyle, że a⋅(b+c)=a⋅b+a⋅c. Okazuje się, że analogiczne prawo ma miejsce w rachunku zdań:
- P∧(Q∨R)≡(P∧Q)∨(P∧R).
Łatwym zadaniem jest sprawdzenie, że równanie to jest tożsamością.
Jest też drugie prawo, w pewnym sensie dualne do pierwszego:
- P∨(Q∧R)≡(P∨Q)∧(P∨R).
Prawa te nazywane są prawami rozdzielności rachunku zdań.
Warto zauważyć, że w arytmetyce nie ma odpowiednika drugiego prawa rozdzielności: nie jest tożsamością równanie a+(b⋅c)=(a+b)⋅(a+c). Jest nią a⋅(b+c)=a⋅b+a⋅c.
Prawa De Morgana
Dwa szczególne przypadki tautologii, są nazywane prawami De Morgana. Mają one duże znaczenie, gdyż pozwalają w wygodny sposób przenosić negację (¬) w ramach wyrażenia rachunku zdań.
- ¬(P∧Q)≡(¬P∨¬Q), czyli nieprawda, że ,P i Q', to to samo co ,nie P' lub ,nie Q'.
- ¬(P∨Q)≡(¬P∧¬Q), czyli nieprawda, że ,P lub Q', to to samo co ,nie P' i jednocześnie ,nie Q'.
|
Ćwiczenie Korzystając z praw De Morgana, zamienić poniższe zdanie na równoważne, tak by znak ¬ występował w nowym zdaniu tylko tuż przed zmiennymi:
|
- Najpierw korzystając z prawa dla ∧, dostajemy ¬P∨¬(Q∨¬P).
- Teraz korzystamy z prawa dla ∨ i dostajemy ¬P∨(¬Q∧¬¬P).
- Kasujemy podwójną negację przed P i otrzymujemy ¬P∨(¬Q∧P).
Dzięki prawom De Morgana i metodzie zamiany implikacji na alternatywę, można tak przepisać każde wyrażenie, by występowały w nim tylko operacje ∨,∧,¬,⊥,⊤, a negacja występowała jedynie tuż przed zmiennymi.
Dualność
Jeśli przez chwilę zapomnimy o wszelkich intuicjach związanych z rachunkiem zdań, a jedynie na napisy, możemy dostrzec tzw. dualność. Jeśli mianowicie weźmiemy jakąkolwiek tożsamość rachunku zdań, zawierającą tylko operacje ∨,∧,¬,⊤,⊥ i zmienne, a następnie zamienimy:
- wszystkie znaczki ∨ na ∧ i odwrotnie,
- wszystkie znaczki ⊥ na ⊤ i odwrotnie,
to otrzymamy również tożsamość. Uzyskaną tożsamość nazywamy dualną do danej na początku.
Jako ćwiczenie można sprawdzić jaka tożsamość jest dualna do P∨(⊤∧⊥)≡P∧⊤.