✖

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: ϕ = (p ∧ q) ∨ ¬q. Zapisujemy do tabeli zmienne zdaniowe p i q:

pq11100100

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

pqp∧q¬qϕ11100100

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

pqp∧q¬qϕ1110100101000001

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:

pqp∧q¬qϕ11101100110100000011

Drugi przykład

To samo zadanie, inna formuła: ϕ = (p ∧ ¬q) ⇔ (¬p ⇒ 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:

pq¬p¬q1100100101100011

Dalej dodajemy formuły p ∧ ¬q i ¬p ⇒ 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:

pq¬p¬q(p∧¬q)(¬p⇒q)110001100111011001001100

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

pq¬p¬q(p∧¬q)(¬p⇒q)ϕ1100010100111101100100011001

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: ϕ = (¬(p ⇒ q)) ∧ (r ⇔ (¬p ∨ q)).

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

pqr111110101100011010001000

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:

pqr¬p(p⇒q)(¬p∨q)¬(p⇒q)(r⇔(¬p∨q))ϕ111011010110011000101000100100000111011111010010111000001111010000111000

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 ⇒ 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” = ¬J. Cała implikacja wyglądałaby tak: M ⇒ ¬J. Dołączamy ją do poprzedniej alternatywy: P ∨ (M ⇒ ¬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: ¬M ∨ ¬J. Składamy całość: (P ⇔ (¬M ∨ ¬J)).

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

MJP(M⇒J)(P∨(M⇒¬J))(P⇔(¬M∨¬J))111110110101101011100010011111010110001111000110

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łę ϕ, która będzie koniunkcją wszystkich trzech warunków. Będzie więc wyglądać tak: ϕ = ((M ⇒ J) ∧ (P ∨ (M ⇒ ¬J)) ∧ (P ⇔ (¬M ∨ ¬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:

MJP(M⇒J)(P∨(M⇒¬J))(P⇔(¬M∨¬J))ϕ11111001101010101011010001000111111010110000111110001100

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 ∧ ¬b) ∨ (b ∧ (b ⇒ a))). Tabela:

ab(a∧¬b)(b∧(b⇒a))((a∧¬b)∨(b∧(b⇒a)))11011101010100000000

Formuła: (a ∨ ¬a) ⇔ (b ∧ ¬b). Tabela:

ab(a∨¬a)(b∧¬b)((a∨¬a)⇔(b∧¬b))11100101000110000100

Formuła: ¬(a ∨ b) ⇔ (¬b ∧ ¬a). Tabela:

ab¬(a∨b)(¬b∧¬a)(¬(a∨b)⇔(¬b∧¬a))11001100010100100111

Formuła: ϕ = (¬p ⇔ (q ∧ r)) ⇒ (p ∨ ¬(p ∧ q)). Tabela:

pqr(q∧r)¬(p∧q)(¬p⇔(q∧r))(p∨¬(p∧q))ϕ1111001111000111101011111000111101111111010010110010101100001011

Formuła: ϕ = ¬(p ⇔ ¬q) ∧ (r ⇒ ¬p) ∧ (p ∨ r). Tabela:

pqr¬(p⇔¬q)(r⇒¬p)(p∨r)ϕ11110101101111101001010001100110110010010000111110001100

Rozdziały: Rachunek zdań, Wartość logiczna formuł, Przykłady z rachunku zdań