Prawo logiczne
prawa rachunku zdań · tautologie · tablice zero–jedynkowe
Rachunek zdań
Logika matematyczna
Tautologie
Definicja
Prawem logicznym (prawem rachunku zdań) nazywamy taki schemat zdania złożonego, dla którego zdanie utworzone według tego schematu jest zawsze prawdziwe, niezależnie od wartości logicznych zdań w nim występujących.
Prawa logiczne zwane są także prawami rachunku zdań oraz tautologiami, tzn. zdaniami, które są zawsze prawdziwe, niezależnie od wartości logicznych zdań składowych.
Ważniejsze prawa logiczne
Przykładowe tautologie rachunku zdań zapisane w języku symboli logicznych
Prawo tożsamości dla implikacji
\(p \Rightarrow p\)
Prawo tożsamości dla równoważności
\(p \Leftrightarrow p\)
Prawo podwójnego przeczenia
\(p \Leftrightarrow \sim(\sim p)\)
Prawo wyłączonego środka
\(p \vee \sim p\)
Prawo wyłączonej sprzeczności
\(\sim(p \wedge \sim p)\)
Prawo przemienności alternatywy
\((p \vee q) \Leftrightarrow (q \vee p)\)
Prawo przemienności koniunkcji
\((p \wedge q) \Leftrightarrow (q \wedge p)\)
Prawo łączności alternatywy
\([(p \vee q) \vee r] \Leftrightarrow [p \vee (q \vee r)]\)
Prawo łączności koniunkcji
\([(p \wedge q) \wedge r] \Leftrightarrow [p \wedge (q \wedge r)]\)
Prawo negacji implikacji
\(\sim(p \Rightarrow q) \Leftrightarrow (p \wedge \sim q)\)
Prawo idempotentności alternatywy
\(p \Leftrightarrow (p \vee q)\)
Prawo idempotentności koniunkcji
\(p \Leftrightarrow (p \wedge q)\)
Prawo pochłaniania
\(p \Rightarrow (p \vee q)\) lub \((p \wedge q) \Rightarrow p\)
Prawo kontrapozycji
\((p \Rightarrow q) \Leftrightarrow (\sim q \Rightarrow \sim p)\)
Prawo symplifikacji
\(p \Rightarrow (q \Rightarrow p)\)
Prawa De Morgana
\(\sim(p \vee q) \Leftrightarrow (\sim p \wedge \sim q)\) oraz
\(\sim(p \wedge q) \Leftrightarrow (\sim p \vee \sim q)\)
Prawo Claviusa
\((\sim p \Rightarrow p) \Rightarrow p\)
Prawo Dunsa Scotusa
\(\sim p \Rightarrow (p \Rightarrow q)\)
Prawo Fregego
\([p \Rightarrow (q \Rightarrow r)] \Rightarrow [(q \Rightarrow q) \Rightarrow (p \Rightarrow r)]\)
Prawa transpozycji
\((p \Rightarrow q) \Rightarrow (\sim p \Rightarrow \sim q)\) oraz
\((\sim p \Rightarrow q) \Rightarrow (\sim q \Rightarrow p)\)
Prawo odrywania (modus ponens)
\([(p \Rightarrow q) \wedge p] \Rightarrow q\)
Wybrane dowody praw logicznych
Dowody praw logicznych (praw rachunku zdań, tautologii) najczęściej przeprowadzamy tzw. metodą zero–jedynkową. Rozważamy wszystkie możliwe wartości logiczne zdań składowych, tworzymy tabelę z poszczególnymi zdaniami złożonymi, a następnie analizujemy ostatnią kolumnę.
Skoro rozpatrywane wyrażenie jest prawem logicznym, to w ostatniej kolumnie, niezależnie od wartości logicznych zdań \(p, q, r\), zawsze otrzymujemy wartość \(1\) (prawdę).
I prawo De Morgana
\(\sim(p \vee q) \Leftrightarrow (\sim p \wedge \sim q)\)
\[
\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
p & q & p \wedge q & \sim(p \wedge q) & \sim p & \sim q & (\sim p) \vee(\sim q) &
\sim(p \wedge q) \Leftrightarrow((\sim p) \vee(\sim q)) \\
\hline
1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\
\hline
1 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\
\hline
0 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \\
\hline
0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\
\hline
\end{array}
\]
II prawo De Morgana
\(\sim(p \wedge q) \Leftrightarrow (\sim p \vee \sim q)\)
\[
\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
p & q & p \vee q & \sim(p \vee q) & \sim p & \sim q & (\sim p) \wedge(\sim q) &
\sim(p \vee q) \Leftrightarrow((\sim p) \wedge(\sim q)) \\
\hline
1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\
\hline
1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\
\hline
0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\
\hline
0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\
\hline
\end{array}
\]
Prawo negacji implikacji
\(\sim(p \Rightarrow q) \Leftrightarrow (p \wedge \sim q)\)
\[
\begin{array}{|c|c|c|c|c|c|c|}
\hline
p & q & p \Rightarrow q & \sim(p \Rightarrow q) & \sim q & p \wedge(\sim q) &
(\sim(p \Rightarrow q)) \Leftrightarrow(p \wedge(\sim q)) \\
\hline
1 & 1 & 1 & 0 & 0 & 0 & 1 \\
\hline
1 & 0 & 0 & 1 & 1 & 1 & 1 \\
\hline
0 & 1 & 1 & 0 & 0 & 0 & 1 \\
\hline
0 & 0 & 1 & 0 & 1 & 0 & 1 \\
\hline
\end{array}
\]
Prawo rozdzielności koniunkcji względem alternatywy
\((p \wedge(q \vee r)) \Leftrightarrow((p \wedge q) \vee(p \wedge r))\)
\[
\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
p & q & r & q \vee r & p \wedge(q \vee r) & p \wedge q & p \wedge r & (p \wedge q) \vee(p \wedge r) &
(p \wedge(q \vee r)) \Leftrightarrow((p \wedge q) \vee(p \wedge r)) \\
\hline
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
\hline
1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 \\
\hline
1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 \\
\hline
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
\hline
0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\
\hline
0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\
\hline
0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\
\hline
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
\hline
\end{array}
\]
Prawo rozdzielności alternatywy względem koniunkcji
\((p \vee(q \wedge r)) \Leftrightarrow((p \vee q) \wedge(p \vee r))\)
\[
\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
p & q & r & q \wedge r & p \vee(q \wedge r) & p \vee q & p \vee r & (p \vee q) \wedge(p \vee r) &
(p \vee(q \wedge r)) \Leftrightarrow((p \vee q) \wedge(p \vee r)) \\
\hline
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
\hline
1 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\
\hline
1 & 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\
\hline
1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\
\hline
0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
\hline
0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\
\hline
0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \\
\hline
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
\hline
\end{array}
\]
