Podstawowe tautologie

Zanim przedstawimy podstawowe prawa rachunku zdań, zdefiniujemy tautologię.
Definicja
Prawem rachunku zdań (tautologią) nazywamy wyrażenie, które staje się zdaniem prawdziwym, gdy w miejsca zmiennych zdaniowych podstawimy dowolne zdania.
Do sprawdzania, czy zdanie jest tautologią, służy metoda zero-jedynkowa. Polega ona na wypełnieniu tabeli wartościami logicznymi \(0\) lub \(1\) wszystkich kolejnych zdań składowych. Rozpoczynamy od wypełnienia pierwszych kolumn wszystkimi możliwymi wartościami logicznymi zdań prostych występujących w danym zdaniu złożonym. W kolejnych kolumnach podajemy wartości logiczne coraz bardziej złożonych zdań, aż w ostatniej kolumnie otrzymamy badane zdanie złożone. Jeżeli w ostatniej kolumnie otrzymamy same jedynki, to znaczy, że badane zdanie jest zawsze prawdziwe, czyli jest tautologią. Jeżeli w ostatniej kolumnie pojawi się choć jedno zero, to badane zdanie nie jest tautologią.
Przykład
Sprawdzimy, czy zdanie \[(p \vee q) \Longleftrightarrow \underbrace{\big[p\ \wedge (\sim q \Rightarrow p)\big]}_{(1)}\] jest tautologią.
Widzimy, że podstawowymi zdaniami prostymi, z których złożone jest podane zdanie, są zdania \(p\) i \(q\). Będą to więc pierwsze elementy pierwszego wiersza tabeli. Mogą one przyjmować następujące wartości logiczne \(1\) i \(1\), \(1\) i \(0\), \(0\) i \(1\) albo \(0\) i \(0\). Wszystkie te możliwości umieszczamy w pierwszych dwóch kolumnach tabeli. Od razu ustalimy, jakie będą kolejne elementy w pierwszym wierszu tabeli. Patrząc na podane zdanie, zauważamy, że potrzebna nam będzie wartość logiczna: zaprzeczenia zdania \(q\) \((\sim q)\), alternatywy zdań \(p\) i \(q\) \((p \vee q)\), implikacji zdań \(\sim q\) i \(p\) \((\sim q \Rightarrow p)\), koniunkcji zdań \(p\) i \(\sim q \Rightarrow p\) oznaczonej przez \((1)\) oraz całej równoważności. Szkielet tabeli wygląda więc następująco:
\( p\) \( q\) \( \sim q\) \( p \vee q\) \( \sim q \Rightarrow p\) \( (1)\) \( (p \vee q) \Leftrightarrow (1)\)
1 1
1 0
0 1
0 0
Trzecią kolumnę tabeli wypełniamy wartościami logicznymi zdania \(\sim q\), biorąc pod uwagę wyłącznie wartości logiczne zdania \(q\) znajdujące się w drugiej (zacieniowanej) kolumnie tabeli.
\( p\) \( q\) \( \sim q\) \( p \vee q\) \( \sim q \Rightarrow p\) \( (1)\) \( (p \vee q) \Leftrightarrow (1)\)
1 1 0
1 0 1
0 1 0
0 0 1
Czwartą kolumnę tabeli wypełniamy wartościami logicznymi zdania \( p \vee q\), biorąc pod uwagę wyłącznie wartości logiczne zdań \(p\) oraz \(q\) znajdujące się w pierwszej i drugiej (zacieniowanej) kolumnie tabeli.
\( p\) \( q\) \( \sim q\) \( p \vee q\) \( \sim q \Rightarrow p\) \( (1)\) \( (p \vee q) \Leftrightarrow (1)\)
1 1 0 1
1 0 1 1
0 1 0 1
0 0 1 0
Piątą kolumnę tabeli wypełniamy wartościami logicznymi zdania \( \sim q \Rightarrow p\), biorąc pod uwagę wyłącznie wartości logiczne zdań \(\sim q\) oraz \(p\) znajdujące się w trzeciej i pierwszej (zacieniowanej) kolumnie tabeli.
\( p\) \( q\) \( \sim q\) \( p \vee q\) \( \sim q \Rightarrow p\) \( (1)\) \( (p \vee q) \Leftrightarrow (1)\)
1 1 0 1 1
1 0 1 1 1
0 1 0 1 1
0 0 1 0 0
Szóstą kolumnę tabeli wypełniamy wartościami logicznymi zdania \(\big[p\ \wedge (\sim q \Longrightarrow p)\big]\) oznaczonego przez \((1)\), biorąc pod uwagę wyłącznie wartości logiczne zdań \(p\) oraz \( \sim q \Rightarrow p\) znajdujące się w pierwszej i piątej (zacieniowanej) kolumnie tabeli.
\( p\) \( q\) \( \sim q\) \( p \vee q\) \( \sim q \Rightarrow p\) \( (1)\) \( (p \vee q) \Leftrightarrow (1)\)
1 1 0 1 1 1
1 0 1 1 1 1
0 1 0 1 1 0
0 0 1 0 0 0
Siódmą kolumnę tabeli wypełniamy wartościami logicznymi całej naszej równoważności \( (p \vee q) \Leftrightarrow (1)\), biorąc pod uwagę wyłącznie wartości logiczne zdań \(p\vee q\) oraz \( (1)\) znajdujące się w czwartej i szóstej (zacieniowanej) kolumnie tabeli.
\( p\) \( q\) \( \sim q\) \( p \vee q\) \( \sim q \Rightarrow p\) \( (1)\) \( (p \vee q) \Leftrightarrow (1)\)
1 1 0 1 1 1 1
1 0 1 1 1 1 1
0 1 0 1 1 0 0
0 0 1 0 0 0 1
Skoro w ostatniej kolumnie otrzymaliśmy wartość logiczną \(0\), to zdanie \[(p \vee q) \Longleftrightarrow \underbrace{\big[p\ \wedge (\sim q \Rightarrow p)\big]}_{(1)}\] nie jest tautologią. Korzystając z tabeli możemy wskazać wartości logiczne podstawowych zdań składowych \(p\) i \(q\), dla których ta równoważność jest fałszywa. Są one widoczne w pierwszych dwóch kolumnach przedostatniego wiersza, czyli wiersza, w którym otrzymaliśmy w ostatniej kolumnie \(0\). Zatem równoważność jest fałszywa, jeżeli zdanie \(p\) ma wartość logiczną \(0\), a zdanie \(q\) wartość logiczną \(1\).
Przykład
Sprawdzimy, czy zdanie \[(p\ \Rightarrow\: \sim q)\ \vee\ (p\ \wedge\ q)\] jest tautologią.
Podobnie jak w poprzednim przykładzie, sprawdzenie wykonamy metodą zero-jedynkową.
\( p\) \( q\) \( \sim q\) \( p \Rightarrow \:\sim q\) \( p\wedge q\) \( (p\Rightarrow \:\sim q)\vee(p \wedge q)\)
1 1 0 0 1 1
1 0 1 1 0 1
0 1 0 1 0 1
0 0 1 1 0 1
Ponieważ w ostatniej kolumnie tabeli mamy same jedynki, to zdanie \[(p\ \Rightarrow\: \sim q)\ \vee\ (p\ \wedge\ q)\] jest tautologią.
Korzystając z metody zero-jedynkowej, można udowodnić podstawowe prawa rachunku zdań.
Fakt
Podstawowe tautologie:
  1. prawo podwójnego zaprzeczenia \[\sim(\sim p) \Longleftrightarrow p\]
    Na podstawie poniższej tabeli zdanie \(\sim(\sim p) \Longleftrightarrow p\) jest tautologią.
    \( p\) \( \sim p\) \( \sim (\sim p)\) \( \sim (\sim p) \Leftrightarrow p \)
    1 0 1 1
    0 1 0 1
  2. prawo wyłączonego środka \[p\:{ \vee}\:(\sim p)\]
    Na podstawie poniższej tabeli zdanie \(p\:{ \vee}\:(\sim p)\) jest tautologią.
    \( p\) \( \sim p\) \( p \vee (\sim p)\)
    1 0 1
    0 1 1
  3. prawo sprzeczności \[\sim \big[p \:{ \wedge}\: (\sim p)\big] \]
    Na podstawie poniższej tabeli zdanie \(\sim \big[p \:{ \wedge}\: (\sim p)\big] \) jest tautologią.
    \( p\) \( \sim p\) \( p\: \wedge (\sim p)\) \( \sim \big[p\: \wedge (\sim p)\big] \)
    1 0 0 1
    0 1 0 1
  4. łączność koniunkcji \[ p\:{ \wedge}\: (q\:{ \wedge}\: r) \Longleftrightarrow (p\:{ \wedge}\: q)\:{ \wedge}\: r\]
    Na podstawie poniższej tabeli zdanie \( \underbrace{p\:{ \wedge}\: (q\:{ \wedge}\: r)}_{(1)} \Longleftrightarrow \underbrace{(p\:{ \wedge}\: q)\:{ \wedge}\: r}_{(2)}\) jest tautologią.
    \( p\) \( q\) \( r\) \( q \wedge r\) \( (1)\) \( p \wedge q\) \( (2)\) \( (1) \Leftrightarrow (2)\)
    1 1 1 1 1 1 1 1
    1 1 0 0 0 1 0 1
    1 0 1 0 0 0 0 1
    1 0 0 0 0 0 0 1
    0 1 1 1 0 0 0 1
    0 1 0 0 0 0 0 1
    0 0 1 0 0 0 0 1
    0 0 0 0 0 0 0 1
  5. łączność alternatywy \[p\:{ \vee}\: (q\:{ \vee}\: r) \Longleftrightarrow (p\:{ \vee}\: q)\:{ \vee}\: r\]
    Na podstawie poniższej tabeli zdanie \(\underbrace{p\:{ \vee}\: (q\:{ \vee}\: r)}_{(1)} \Longleftrightarrow \underbrace{(p\:{ \vee}\: q)\:{ \vee}\: r}_{(2)}\) jest tautologią.
    \( p\) \( q\) \( r\) \( q \vee r\) \( (1)\) \( p \vee q\) \( (2)\) \( (1) \Leftrightarrow (2)\)
    1 1 1 1 1 1 1 1
    1 1 0 1 1 1 1 1
    1 0 1 1 1 1 1 1
    1 0 0 0 1 1 1 1
    0 1 1 1 1 1 1 1
    0 1 0 1 1 1 1 1
    0 0 1 1 1 0 1 1
    0 0 0 0 0 0 0 1
  6. prawo kontrapozycji \[p\Rightarrow q \Longleftrightarrow (\sim q \Rightarrow \:\sim p)\]
    Na podstawie poniższej tabeli zdanie \(\underbrace{p\Rightarrow q}_{(1)} \Longleftrightarrow \underbrace{(\sim q \Rightarrow \:\sim p)}_{(2)}\) jest tautologią.
    \( p\) \( q\) \( (1)\) \( \sim q\) \( \sim p\) \( (2)\) \( (1) \Leftrightarrow (2)\)
    1 1 1 0 0 1 1
    1 0 0 1 0 0 1
    0 1 1 0 1 1 1
    0 0 1 1 1 1 1
  7. rozdzielność alternatywy względem koniunkcji \[p\:{ \vee}\: (q\:{ \wedge}\: r) \Longleftrightarrow (p\:{ \vee}\: q) \:{ \wedge}\: (p\:{ \vee}\: r)\]
    Na podstawie poniższej tabeli zdanie \(\underbrace{p\:{ \vee}\: (q\:{ \wedge}\: r)}_{(1)} \Longleftrightarrow \underbrace{(p\:{ \vee}\: q) \:{ \wedge}\: (p\:{ \vee}\: r)}_{(2)}\) jest tautologią.
    \( p\) \( q\) \( r\) \( q \wedge r\) \( (1)\) \( p \vee q\) \( p \vee r \) \( (2) \) \( (1) \Leftrightarrow (2)\)
    1 1 1 1 1 1 1 1 1
    1 1 0 0 1 1 1 1 1
    1 0 1 0 1 1 1 1 1
    1 0 0 0 1 1 1 1 1
    0 1 1 1 1 1 1 1 1
    0 1 0 0 0 1 0 0 1
    0 0 1 0 0 0 1 0 1
    0 0 0 0 0 0 0 0 1
  8. rozdzielność koniunkcji względem alternatywy \[p\:{ \wedge}\: (q\:{ \vee}\: r) \Longleftrightarrow (p\:{ \wedge}\: q) \:{ \vee}\: (p\:{ \wedge}\: r)\]
    Na podstawie poniższej tabeli zdanie \(\underbrace{p\:{ \wedge}\: (q\:{ \vee}\: r)}_{(1)} \Longleftrightarrow \underbrace{(p\:{ \wedge}\: q) \:{ \vee}\: (p\:{ \wedge}\: r)}_{(2)}\) jest tautologią.
    \( p\) \( q\) \( r\) \( q \vee r\) \( (1)\) \( p \vee q\) \( p \vee r \) \( (2) \) \( (1) \Leftrightarrow (2)\)
    1 1 1 1 1 1 1 1 1
    1 1 0 1 1 1 0 1 1
    1 0 1 1 1 0 1 1 1
    1 0 0 0 0 0 0 0 1
    0 1 1 1 0 0 0 0 1
    0 1 0 1 0 0 0 0 1
    0 0 1 1 0 0 0 0 1
    0 0 0 0 0 0 0 0 1
  9. prawo przechodniości implikacji \[\big[(p\Rightarrow q)\:{ \wedge}\: (q\Rightarrow r)\big] \Longrightarrow (p\Rightarrow r)\]
    Na podstawie poniższej tabeli zdanie \(\underbrace{\big[(p\Rightarrow q)\:{ \wedge}\: (q\Rightarrow r)\big]}_{(1)} \Longrightarrow \underbrace{(p\Rightarrow r)}_{(2)}\) jest tautologią.
    \( p\) \( q\) \( r\) \( p \Rightarrow q\) \( q \Rightarrow r\) \( (1)\) \( (2)\) \( (1) \Rightarrow (2)\)
    1 1 1 1 1 1 1 1
    1 1 0 1 0 0 0 1
    1 0 1 0 1 0 1 1
    1 0 0 0 1 0 0 1
    0 1 1 1 1 1 1 1
    0 1 0 1 0 0 1 1
    0 0 1 1 1 1 1 1
    0 0 0 1 1 1 1 1
  10. prawo zaprzeczenia implikacji \[\sim (p\Rightarrow q) \Longleftrightarrow \big[\:p\:{ \wedge}\: (\sim q)\big]\]
    Na podstawie poniższej tabeli zdanie \(\underbrace{\sim (p\Rightarrow q)}_{(1)} \Longleftrightarrow \underbrace{\big[\:p\:{ \wedge}\: (\sim q)\big]}_{(2)}\) jest tautologią.
    \( p\) \( q\) \( p \Rightarrow q\) \( (1)\) \( \sim q\) \( (2)\) \( (1) \Leftrightarrow (2)\)
    1 1 1 0 0 0 1
    1 0 0 1 1 1 1
    0 1 1 0 0 0 1
    0 0 1 0 1 0 1
  11. prawo zaprzeczenia koniunkcji (I prawo de Morgana) \[\sim (p\:{ \wedge}\: q) \Longleftrightarrow \big[(\sim p )\:{ \vee} \:(\sim q)\big]\]
    Na podstawie poniższej tabeli zdanie \(\underbrace{\sim (p\:{ \wedge}\: q)}_{(1)} \Longleftrightarrow \underbrace{\big[(\sim p )\:{ \vee} \:(\sim q)\big]}_{(2)}\) jest tautologią.
    \( p\) \( q\) \( p \wedge q\) \( (1)\) \( \sim p\) \( \sim q\) \( (2)\) \( (1) \Leftrightarrow (2)\)
    1 1 1 0 0 0 0 1
    1 0 0 1 0 1 1 1
    0 1 0 1 1 0 1 1
    0 0 0 1 1 1 1 1
  12. prawo zaprzeczenia alternatywy (II prawo de Morgana) \[\sim (p\:{ \vee}\: q) \Longleftrightarrow \big[(\sim p )\:{ \wedge}\: (\sim q)\big]\]
    Na podstawie poniższej tabeli zdanie \(\underbrace{\sim (p\:{ \vee}\: q)}_{(1)} \Longleftrightarrow \underbrace{\big[(\sim p )\:{ \wedge}\: (\sim q)\big]}_{(2)}\) jest tautologią.
    \( p\) \( q\) \( p \vee q\) \( (1)\) \( \sim p\) \( \sim q\) \( (2)\) \( (1) \Leftrightarrow (2)\)
    1 1 1 0 0 0 0 1
    1 0 1 0 0 1 0 1
    0 1 1 0 1 0 0 1
    0 0 0 1 1 1 1 1
W kolejnych jednostkach omówimy szczegółowo najczęściej wykorzystywane tautologie: prawo kontrapozycji, prawo zaprzeczenia implikacji, prawo zaprzeczenia alternatywy oraz prawo zaprzeczenia koniunkcji.