Prawa rachunku zdań (zwane inaczej tautologiami) to zdania połączone operatorami logicznymi w taki sposób, że ich wartość logiczna jest zawsze równa 1, niezależnie od wartości logicznych zdań składowych.
Przykład:
Jeśli pies ma na imię Burek to pies ma na imię Burek.
Zdaniem składowym jest (dwukrotnie użyte) zdanie „Pies ma na imię Burek” - i niezależnie od tego, czy jest ono prawdziwe, czy nie, zdanie „Jeśli pies ma na imię Burek to pies ma na imię Burek” jest prawdziwe.
Powyższy przykład obrazuje prawo tożsamości:
\(p \Rightarrow p\) - każde zdanie implikuje samo siebie.
Innym znanym prawem rachunku zdań jest prawo podwójnego przeczenia:
\(p \Leftrightarrow \neg ( \neg p)\) - każde zdanie jest równoważne podwójnej negacji samego siebie.
Kolejne podstawowe prawo rachunku zdań to prawo wyłączonego środka:
\(p \vee \neg p\) - któreś ze zdań \(p\) i \( \neg p\) musi być prawdziwe.
Z prawem wyłączonego środka związane jest tzw. prawo sprzeczności:
\( \neg (p \wedge \neg p)\) - nie może być jednocześnie prawdziwe zdanie i jego zparzeczenie
Prawdziwe są także następujące prawa dla koniunkcji i alternatywy:
\(p \Leftrightarrow p \wedge p\) oraz \(p \Leftrightarrow p \vee p\).
Dla Koniunkcji i alternatywy prawdziwe są:
(1) przemienność
\(p \wedge q \Leftrightarrow q \wedge p\)
\(p \vee q \Leftrightarrow q \vee p\)
(2) łączność
\([(p \wedge q) \wedge r ] \Leftrightarrow [p \wedge ( q \wedge r )]\)
\([(p \vee q) \vee r ] \Leftrightarrow [p \vee ( q \vee r )]\)
(3) rozdzielność
\([ p \wedge (q \vee r)] \Leftrightarrow [ (p \wedge q) \vee (p \wedge r)]\) - rozdzielność koniunkcji względem alternatywy
\([ p \vee (q \wedge r)] \Leftrightarrow [ (p \vee q) \wedge (p \vee r)]\) - rozdzielność alternatywy względem koniunkcji
W celu sprawdzenia, czy dane zdanie jest prawem rachunku zdań (to znaczy, czy jest prawdziwe dla każdego wartościowania poszczególnych jego zmiennych) można posłużyć się tabelką.
Przykład:
Sprawdźmy, czy rozdzielność alternatywy względem koniunkcji jest prawem rachunku zdań.
W nagłówkach umieszczone są wszystkie składowe badanego zdania.
Na początek wypisujemy dla zdań \(p\), \(q\) i \(r\) wszystkie ich możliwe wartości (każde z nich może być prawdziwe lub fałszywe, więc w sumie mamy 8 możliwości). Następnie, korzystając ze znajomości zasad dotyczących wartościowania poszczególnych operatorów logicznych (w tym przypadku koniunkcji i alternatywy) określamy prawdziwość poszczególnych składowych zdania. Na koniec porównujemy wartości lewej i prawej strony zdania (tj. sprawdzamy czy są one sobie równoważne - kolumny wyróżnione kolorem czerwonym). Obie strony mają taką samą wartość dla wszystkich możliwych wartości zdań \(p\), \(q\) i \(r\), zatem zdanie jest tautologią.
Zadanie:
Sprawdzić czy prawem rachunku zdań są pozostałe opisane tutaj prawa.