Przykłady z logiki zdań

W artykule pokażemy kilka wzorów i ich możliwych obliczeń przy użyciu metody tabelarycznej.

Pierwszy przykład

Spróbujmy sprawdzić, kiedy ta formuła jest prawdziwa: $\phi=(p \wedge q) \vee \neg q$ Zapiszmy symbole propozycjonalne p i q w tabeli:

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

Następnie zapiszmy w tabeli pierwszą część formuły: (p ∨ q), negację $\neg q$, a następnie całą formułę:

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

Teraz obliczymy wartości dla trzeciej kolumny, czyli koniunkcji prostej, a także dla negacji - tam po prostu wstawiamy wartości odwrotne niż w drugiej kolumnie:

$$\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 obliczamy wartości w ostatniej kolumnie. Tak wygląda cała formuła. Biorąc pod uwagę naszą tabelę, obliczamy więc dysjunkcję "między trzecią i 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

Ten sam problem, inna formuła: $(p \wedge \neg q) \Leftrightarrow (\neg p \Rightarrow q)$ Widzimy, że formuła zawiera symbole propozycjonalne p i q oraz ich negacje. Najpierw tworzymy tabelę z tymi dwoma symbolami 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}$$

Następnie dodajemy formuły $\phi=p \wedge \neg q$ i $\neg p \Rightarrow q$, które możemy już łatwo ocenić, ponieważ mamy zarówno ocenę poszczególnych stwierdzeń, jak i ich negacje w tabeli. Tabela wygląda następująco:

$$\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}$$

Ostatnią rzeczą, którą musimy zrobić, jest ocena całej formuły, która jest 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 nieco bardziej skomplikowany, wypróbujemy trzy symbole propozycjonalne, co sprawi, że obliczenia w tabeli będą bardziej złożone. Formuła będzie wyglądać następująco: $\phi=(\neg(p\Rightarrow q)) \wedge (r\Leftrightarrow(\neg p \vee q))$.

Ponieważ istnieją trzy symbole propozycjonalne, całkowita liczba wariantów oceny 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}$$

Następnie będziemy postępować jak w poprzednim przypadku, oceniając każdą kolumnę we wszystkich ośmiu wierszach. Cała tabela będzie wyglądać następująco:

$$\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

Ten przykład nie jest już wprowadzany jako prosta formuła, ale jako problem słowny. Trzech przyjaciół, którzy chcą pójść na szaloną imprezę, gdzie modelki topless będą rozdawać przekąski, nie do końca się lubią i ustalają warunki, na jakich pójdą na imprezę. Nazywają się Martin, James i Peter. Zasady są następujące:

1. Jeśli pójdzie Marcin, pójdzie też Jakub.

• Piotr pójdzie na imprezę lub, jeśli Marcin pójdzie, Jakub nie pójdzie.
• Piotr przyjdzie, jeśli Marcin nie przyjdzie lub Jakub nie przyjdzie.

Pytanie brzmi: czy wszyscy mogą przyjść na imprezę? Jeśli nie, to kto może pójść na imprezę i nie złamać żadnych zasad?

Pierwszą rzeczą, którą musimy zrobić, jest przekształcenie poprzednich stwierdzeń werbalnych w symbole i formuły propozycjonalne. Oznaczmy więc symbole propozycjonalne M, J i P (Martin, James, Peter), które zawsze będą oznaczać stwierdzenie typu "Martin pójdzie na imprezę". Możemy przepisać pierwszą regułę jako $M \Rightarrow J$ - "jeśli M, to J", lub "jeśli Martin idzie na imprezę, to James idzie na imprezę".

Druga reguła może zostać przepisana w następujący sposób. Reguła zaczyna się od "Peter przyjdzie na imprezę lub...", więc oczywiście potrzebujemy dysjunkcji. Na razie to zapiszemy: P∨… Następna część zdania mówi: "Jeśli Martin przyjdzie, James nie przyjdzie". Jest to implikacja i nadal musimy użyć negacji po prawej stronie. "James nie przyjdzie" = $\neg J$. Cała implikacja wyglądałaby następująco: $M \Rightarrow \neg J$ Dodamy to do poprzedniej dysjunkcji: $P \vee M \Rightarrow \neg J$.

Przepiszemy trzecią regułę w następujący sposób: zaczynamy od "Peter will come right then". To implikuje równoważność: P ⇔ … Następnie mamy "Marcin nie przyjdzie lub Jakub nie przyjdzie", co przepisujemy następująco: $\neg M \vee \neg J$ Łączymy: $(P\Leftrightarrow (\neg M\vee \neg J))$.

Teraz umieszczamy wszystkie formuły w tabeli i obliczamy 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 wszyscy trzej chłopcy mogą pójść na szaloną imprezę. Odpowiedź można znaleźć w pierwszym wierszu. Daje nam to odpowiedź na przypadek, w którym wszyscy chłopcy pójdą - jest to sygnalizowane trzema jedynkami w pierwszych trzech kolumnach. Czy wszystkie warunki zostały spełnione? Pierwszy tak (czwarta kolumna), drugi również (piąta kolumna), ale ostatni nie (ostatnia kolumna), jest zero. Oznacza to, że jeśli wszystkie trzy zostaną spełnione, trzeci warunek nie zostanie spełniony.

Szukamy więc tych wierszy, w których pozycje symbolizujące warunki (tj. trzy ostatnie kolumny) są jedynkami. Jedynka oznacza, że warunek jest spełniony. Widzimy, że ma to miejsce w dwóch przypadkach. Jeśli James i Peter pojadą, ale Martin nie, a następnie jeśli pojedzie tylko Peter.

Można to również obliczyć, dodając do tabeli formułę $\phi$, która będzie koniunkcją wszystkich trzech warunków. Będzie to wyglądać następująco: $\phi = ((M\Rightarrow J)\wedge (P\vee (M\Rightarrow \neg J))\wedge (P\Leftrightarrow (\neg M\vee \neg J)))$ Oznacza to, że wszystkie formuły (wszystkie warunki) są spełnione. Tabela będzie wyglądać następująco:

$$\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 metody tabelarycznej

Ponieważ napisałem program, który może automatycznie zbudować całą tabelę z danej formuły, muszę użyć go poprawnie, więc poniżej znajduje się kilka innych 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)$. Table:

$$\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: $(\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: $\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}$$