Skip to Content

Prawa rachunku zdań

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ń.

  1. \( \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'.
  2. \( \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:

\(\lnot (P\wedge (Q\vee \lnot P))\).

Rozwiązanie:

  • 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:

  1. wszystkie znaczki \(\vee\) na \(\wedge\) i odwrotnie,
  2. 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\).