Przykłady z rachunku zdań

W tym artykule pokażemy kilka formuł i ich możliwe wartościowania, korzystając z metody tabelkowej.

Pierwszy przykład

Spróbujemy ustalić, kiedy ta formuła jest prawdziwa: $\phi=(p \wedge q) \vee \neg q$. Zapisujemy do tabeli zmienne zdaniowe p i q:

$$\begin{array}{cc} p&q\\ 1&1\\ 1&0\\ 0&1\\ 0&0 \end{array}$$

Dalej dopisujemy do tabeli pierwszą część formuły: (p ∧ q), negację $\neg q$, a potem całą formułę:

$$\begin{array}{ccccc} p&q&p \wedge q&\neg q&\phi\\ 1&1\\ 1&0\\ 0&1\\ 0&0 \end{array}$$

Teraz uzupełniamy trzecią kolumnę (to zwykła koniunkcja) i kolumnę z negacją – tam wystarczy wpisać wartości odwrotne do tych z drugiej kolumny:

$$\begin{array}{ccccc} p&q&p \wedge q&\neg q&\phi\\ 1&1&1&0\\ 1&0&0&1\\ 0&1&0&0\\ 0&0&0&1 \end{array}$$

Na koniec uzupełniamy wartości w ostatniej kolumnie. To jest cała formuła. W naszej tabeli liczymy więc alternatywę „między trzecią a czwartą kolumną”. Wynik:

$$\begin{array}{ccccc} p&q&p \wedge q&\neg q&\phi\\ 1&1&1&0&1\\ 1&0&0&1&1\\ 0&1&0&0&0\\ 0&0&0&1&1 \end{array}$$

Drugi przykład

To samo zadanie, inna formuła: $\phi=(p \wedge \neg q) \Leftrightarrow (\neg p \Rightarrow q)$. Widzimy, że w formule są zmienne zdaniowe p i q oraz ich negacje. Najpierw utworzymy więc tabelę z dwiema zmiennymi i ich negacjami:

$$\begin{array}{cccc} p&q&\neg p&\neg q\\ 1&1&0&0\\ 1&0&0&1\\ 0&1&1&0\\ 0&0&1&1 \end{array}$$

Dalej dodajemy formuły $p \wedge \neg q$ i $\neg p \Rightarrow q$, których wartości łatwo już wyznaczymy, bo w tabeli mamy zarówno wartościowania poszczególnych zdań, jak i ich negacji. Tabela wygląda tak:

$$\begin{array}{cccccc} p&q&\neg p&\neg q&(p\wedge \neg q)&(\neg p\Rightarrow q)\\ 1&1&0&0&0&1\\ 1&0&0&1&1&1\\ 0&1&1&0&0&1\\ 0&0&1&1&0&0 \end{array}$$

Na koniec zostaje nam wyznaczyć wartość całej formuły, czyli równoważności między dwiema ostatnimi kolumnami:

$$\begin{array}{ccccccc} p&q&\neg p&\neg q&(p\wedge \neg q)&(\neg p\Rightarrow q)&\phi\\ 1&1&0&0&0&1&0\\ 1&0&0&1&1&1&1\\ 0&1&1&0&0&1&0\\ 0&0&1&1&0&0&1 \end{array}$$

Trzeci przykład

Trzeci przykład będzie już trochę trudniejszy. Spróbujemy z trzema zmiennymi zdaniowymi, przez co obliczanie tabeli się skomplikuje. Formuła będzie wyglądać tak: $\phi=(\neg(p\Rightarrow q)) \wedge (r\Leftrightarrow(\neg p \vee q))$.

Ponieważ mamy trzy zmienne zdaniowe, łączna liczba możliwych wartościowań wyniesie osiem:

$$\begin{array}{ccc} p&q&r\\ 1&1&1\\ 1&1&0\\ 1&0&1\\ 1&0&0\\ 0&1&1\\ 0&1&0\\ 0&0&1\\ 0&0&0 \end{array}$$

Dalej postępujemy tak samo jak w poprzednim przypadku: wyznaczamy wartość każdej kolumny we wszystkich ośmiu wierszach. Cała tabela będzie wyglądać tak:

$$\begin{array}{ccccccccc} p&q&r&\neg p&(p\Rightarrow q)&(\neg p\vee q)&\neg (p\Rightarrow q)&(r\Leftrightarrow (\neg p\vee q))&\phi\\ 1&1&1&0&1&1&0&1&0\\ 1&1&0&0&1&1&0&0&0\\ 1&0&1&0&0&0&1&0&0\\ 1&0&0&0&0&0&1&1&1\\ 0&1&1&1&1&1&0&1&0\\ 0&1&0&1&1&1&0&0&0\\ 0&0&1&1&1&1&0&1&0\\ 0&0&0&1&1&1&0&0&0 \end{array}$$

Czwarty przykład

Tego przykładu nie zadamy już jako zwykłej formuły, ale jako zadanie tekstowe. Trzej kumple, którzy chcą iść na dziką imprezę, gdzie modelki topless będą roznosić przekąski, niezbyt się lubią i stawiają sobie warunki, pod którymi na imprezę pójdą. Mają na imię Marcin, Jakub i Piotr. Zasady są następujące:

1. Jeśli pójdzie Marcin, to pójdzie też Jakub.
2. Na imprezę przyjdzie Piotr lub, jeśli przyjdzie tam Marcin, to nie przyjdzie tam Jakub.
3. Piotr przyjdzie wtedy i tylko wtedy, gdy nie przyjdzie Marcin lub nie przyjdzie Jakub.

Pytanie brzmi: czy na imprezę mogą przyjść wszyscy? Jeśli nie, kto może się na imprezie pojawić bez łamania żadnej zasady?

Najpierw musimy przepisać powyższe zdania słowne na zmienne zdaniowe i formuły. Oznaczmy więc zmienne zdaniowe M, J i P (Marcin, Jakub, Piotr); każda z nich będzie oznaczać zdanie typu „Marcin pójdzie na imprezę”. Pierwszą zasadę moglibyśmy zapisać tak: $M \Rightarrow J$ – „jeżeli M, to J”, czyli „jeżeli Marcin pójdzie na imprezę, to Jakub pójdzie na imprezę”.

Drugą zasadę zapisalibyśmy tak. Zasada zaczyna się zdaniem „Na imprezę przyjdzie Piotr lub…”, więc najwyraźniej będziemy potrzebować alternatywy. Na razie zapiszemy to: P∨… Dalsza część zdania mówi: „jeśli przyjdzie tam Marcin, to nie przyjdzie tam Jakub”. To jest implikacja, przy czym po prawej stronie musimy jeszcze użyć negacji. „nie przyjdzie Jakub” = $\neg J$. Cała implikacja wyglądałaby tak: $M \Rightarrow \neg J$. Dołączamy ją do poprzedniej alternatywy: $P \vee (M \Rightarrow \neg J)$.

Trzecią zasadę zapiszemy tak: zaczynamy od „Piotr przyjdzie wtedy i tylko wtedy, gdy”. To oznacza równoważność: P ⇔ … Dalej mamy „nie przyjdzie Marcin lub nie przyjdzie Jakub”, co zapiszemy tak: $\neg M \vee \neg J$. Składamy całość: $(P\Leftrightarrow (\neg M\vee \neg J))$.

Teraz wpisujemy wszystkie formuły do tabeli i wyznaczamy wartości:

$$\begin{array}{cccccc} M&J&P&(M\Rightarrow J)&(P\vee (M\Rightarrow \neg J))&(P\Leftrightarrow (\neg M\vee \neg J))\\ 1&1&1&1&1&0\\ 1&1&0&1&0&1\\ 1&0&1&0&1&1\\ 1&0&0&0&1&0\\ 0&1&1&1&1&1\\ 0&1&0&1&1&0\\ 0&0&1&1&1&1\\ 0&0&0&1&1&0 \end{array}$$

Pytanie brzmiało, czy na dziką imprezę mogą pójść wszyscy trzej chłopcy. Odpowiedź znajdziemy w pierwszym wierszu. Odpowiada on przypadkowi, w którym pójdą wszyscy chłopcy – sygnalizują to trzy jedynki w pierwszych trzech kolumnach. Czy są spełnione wszystkie warunki? Pierwszy tak (czwarta kolumna), drugi też (piąta kolumna), ale ostatni nie (ostatnia kolumna), tam jest zero. Oznacza to, że jeśli pójdą wszyscy trzej, nie będzie spełniony trzeci warunek.

Szukamy więc tych wierszy, w których na pozycjach odpowiadających warunkom (czyli w trzech ostatnich kolumnach) są same jedynki. Jedynka oznacza, że warunek jest spełniony. Widzimy, że zdarza się to w dwóch przypadkach: gdy pójdą Jakub i Piotr, ale Marcin nie, oraz gdy pójdzie tylko Piotr.

Możesz to też obliczyć tak, że dodasz do tabeli formułę $\phi$, która będzie koniunkcją wszystkich trzech warunków. Będzie więc wyglądać tak: $\phi = ((M\Rightarrow J)\wedge (P\vee (M\Rightarrow \neg J))\wedge (P\Leftrightarrow (\neg M\vee \neg J)))$. Wyraża to dokładnie to, czego chcemy: żeby wszystkie formuły (wszystkie warunki) były spełnione. Tabela wyglądałaby wtedy tak:

$$\begin{array}{ccccccc} M&J&P&(M\Rightarrow J)&(P\vee (M\Rightarrow \neg J))&(P\Leftrightarrow (\neg M\vee \neg J))&\phi\\ 1&1&1&1&1&0&0\\ 1&1&0&1&0&1&0\\ 1&0&1&0&1&1&0\\ 1&0&0&0&1&0&0\\ 0&1&1&1&1&1&1\\ 0&1&0&1&1&0&0\\ 0&0&1&1&1&1&1\\ 0&0&0&1&1&0&0 \end{array}$$

Kilka przykładów na metodę tabelkową

Ponieważ napisałem sobie program, który z danej formuły umie automatycznie zbudować całą tabelę, muszę go porządnie wykorzystać, dlatego poniżej jest jeszcze kilka rozwiązanych formuł:

Formuła: $((a\wedge \neg b)\vee (b\wedge (b\Rightarrow a)))$. Tabela:

$$\begin{array}{ccccc} a&b&(a\wedge \neg b)&(b\wedge (b\Rightarrow a))&((a\wedge \neg b)\vee (b\wedge (b\Rightarrow a)))\\ 1&1&0&1&1\\ 1&0&1&0&1\\ 0&1&0&0&0\\ 0&0&0&0&0 \end{array}$$

Formuła: $(a\vee \neg a)\Leftrightarrow (b\wedge \neg b)$. Tabela:

$$\begin{array}{ccccc} a&b&(a\vee \neg a)&(b\wedge \neg b)&((a\vee \neg a)\Leftrightarrow (b\wedge \neg b))\\ 1&1&1&0&0\\ 1&0&1&0&0\\ 0&1&1&0&0\\ 0&0&1&0&0 \end{array}$$

Formuła: $\neg (a\vee b)\Leftrightarrow (\neg b\wedge \neg a)$. Tabela:

$$\begin{array}{ccccc} a&b&\neg (a\vee b)&(\neg b\wedge \neg a)&(\neg (a\vee b)\Leftrightarrow (\neg b\wedge \neg a))\\ 1&1&0&0&1\\ 1&0&0&0&1\\ 0&1&0&0&1\\ 0&0&1&1&1 \end{array}$$

Formuła: $\phi=(\neg p \Leftrightarrow (q \wedge r)) \Rightarrow (p \vee \neg (p \wedge q))$. Tabela:

$$\begin{array}{cccccccc} p&q&r&(q\wedge r)&\neg (p\wedge q)&(\neg p\Leftrightarrow (q\wedge r))&(p\vee \neg (p\wedge q))&\phi\\ 1&1&1&1&0&0&1&1\\ 1&1&0&0&0&1&1&1\\ 1&0&1&0&1&1&1&1\\ 1&0&0&0&1&1&1&1\\ 0&1&1&1&1&1&1&1\\ 0&1&0&0&1&0&1&1\\ 0&0&1&0&1&0&1&1\\ 0&0&0&0&1&0&1&1 \end{array}$$

Formuła: $\phi=\neg(p\Leftrightarrow \neg q) \wedge (r \Rightarrow \neg p) \wedge (p \vee r)$. Tabela:

$$\begin{array}{ccccccc} p&q&r&\neg (p\Leftrightarrow \neg q)&(r\Rightarrow \neg p)&(p\vee r)&\phi\\ 1&1&1&1&0&1&0\\ 1&1&0&1&1&1&1\\ 1&0&1&0&0&1&0\\ 1&0&0&0&1&1&0\\ 0&1&1&0&1&1&0\\ 0&1&0&0&1&0&0\\ 0&0&1&1&1&1&1\\ 0&0&0&1&1&0&0 \end{array}$$