W arytmetyce liczb zachodzi prawo rozdzielności dodawania względem mnożenia. Mówi ono tyle, że \(a\cdot (b+c)=a\cdot b + a\cdot c\). Okazuje się, że analogiczne prawo ma miejsce w rachunku zdań:
- \(P\wedge (Q\vee R)\equiv (P\wedge Q)\vee (P\wedge R)\).
Łatwym zadaniem jest sprawdzenie, że równanie to jest tożsamością.
Jest też drugie prawo, w pewnym sensie dualne do pierwszego:
- \(P\vee (Q\wedge R)\equiv (P\vee Q)\wedge (P\vee 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\cdot c) = (a+b) \cdot (a+c)\). Jest nią \(a\cdot (b+ c)=a\cdot b+a\cdot 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ę (\(\lnot\)) w ramach wyrażenia rachunku zdań.
- \( \lnot(P\wedge Q)\equiv (\lnot P\vee \lnot Q)\), czyli nieprawda, że ,P i Q', to to samo co ,nie P' lub ,nie Q'.
- \( \lnot(P\vee Q)\equiv (\lnot P\wedge \lnot 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 \(\lnot\) występował w nowym zdaniu tylko tuż przed zmiennymi:
|
- Najpierw korzystając z prawa dla \(\wedge\), dostajemy \(\lnot P\vee\lnot(Q\vee\lnot P)\).
- Teraz korzystamy z prawa dla \(\vee\) i dostajemy \(\lnot P\vee (\lnot Q\wedge \lnot\lnot P)\).
- Kasujemy podwójną negację przed P i otrzymujemy \(\lnot P\vee (\lnot Q\wedge 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 \(\vee,\wedge,\lnot,\bot,\top\), 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 \(\vee,\wedge,\lnot,\top,\bot\) i zmienne, a następnie zamienimy:
- wszystkie znaczki \(\vee\) na \(\wedge\) i odwrotnie,
- wszystkie znaczki \(\bot\) na \(\top\) 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\vee (\top\wedge \bot)\equiv P\wedge \top\).