Wartość logiczna formuł

Jeśli mamy jakieś zdania atomowe, które złożymy w formułę, możemy spróbować rozstrzygnąć, czy cała formuła jest prawdziwa, czy fałszywa.

Wartość logiczna zdania

Najpierw doprecyzujmy, czym jest wartość logiczna zdania. Jeśli mamy zdanie p, powinniśmy umieć rozstrzygnąć, czy jest prawdziwe, czy fałszywe. Zdanie prawdziwe będzie miało wartość logiczną 1, a fałszywe 0.

Wartościowanie to przepis e, który danemu zdaniu przypisuje albo 0, albo 1. Jeśli napiszemy e(p), chcemy poznać wartość logiczną zdania p. Jeśli p jest zdaniem „dwa razy dwa to cztery”, to e(p) = 1, bo jest to zdanie prawdziwe. Jeśli q jest zdaniem „Twój dziadek jest kobietą”, to e(q) = 0, bo dziadek kobietą nie jest. e jest więc funkcją, która mówi nam, czy zdanie jest prawdziwe.

Trzeba tu sobie uświadomić, że e nie jest jakąś magiczną funkcją, która wie wszystko na świecie. Zachowuje się tak, jak jej każemy. Ona nie wie, czy twój dziadek jest mężczyzną, czy kobietą. To my na początku obliczeń powinniśmy zadeklarować, jak ma się zachowywać funkcja wartościująca. Jeśli powiemy jej, że twój dziadek jest kobietą, to zwróci nam e(q) = 1.

Wartość logiczna spójników

Żeby ustalić wartość logiczną formuły, musimy wiedzieć, jak wyznaczyć wartość logiczną spójników. Czyli jeśli znamy wartościowanie e(p) i e(q), jaka będzie wartość logiczna formuł p ∧ q, $p \Rightarrow q$ itp.

Każdy spójnik logiczny zachowuje się inaczej i służy do czegoś innego, więc omówimy każdy spójnik osobno.

Wartość logiczna koniunkcji

Koniunkcję oznaczamy p ∧ q i czytamy „p i jednocześnie q”. Jako przykład weźmy formułę „Polska leży w Europie Środkowej i jednocześnie jej stolicą jest Warszawa”. Kiedy całe to zdanie będzie prawdziwe?

W ustaleniu wartości logicznej pomoże nam już sam spójnik „i jednocześnie”. Mówi on wprost, że oba zdania, po lewej i po prawej stronie, mają być prawdziwe. Jeśli więc oba zdania p i q są prawdziwe, czyli e(p) = 1 i e(q) = 1, to prawdziwa jest też cała koniunkcja. W przeciwnym przypadku, gdy jedno ze zdań jest fałszywe albo oba są fałszywe, cała formuła jest fałszywa.

Przykładem koniunkcji, która nie jest prawdziwa, może być: „Wisła jest rzeką i jednocześnie Wisła płynie przez Rosję”. To prawda, że Wisła jest rzeką, ale nieprawda, że płynie przez Rosję, więc cała koniunkcja nie jest prawdziwa.

Przejrzyście zapisuje to następująca tabela:

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

W pierwszych dwóch kolumnach są wartości logiczne zdań p i q, a w trzeciej wartość logiczna formuły p ∧ q.

Wartość logiczna alternatywy

Alternatywę oznaczamy p ∨ q i czytamy „p lub q”. Przykład: „Rosja leży w Europie lub w Azji.” Kiedy całe zdanie będzie prawdziwe?

W przypadku alternatywy wystarczy nam, żeby co najmniej jedna z możliwości była prawdziwa. Spójnik „lub” daje nam wybór, wystarczy, że prawdziwa będzie jego lewa albo prawa część. Jedyna drobna różnica w porównaniu z mową potoczną polega na tym, że logiczne „lub” jest prawdziwe także wtedy, gdy oba zdania są spełnione jednocześnie. W mowie potocznej nie jest to zbyt typowe, często używamy „lub” w sensie wykluczającym, czyli „albo …, albo …”.

Jest na to klasyczny dowcip: rodzina wybiera w komisie nowy samochód. Tata mówi sprzedawcy: „zdecydowaliśmy, że weźmiemy niebieski lub czerwony samochód”. Sprzedawca sprzedał im oba samochody. To ilustracja różnicy między logicznym a potocznym „lub”: tata miał pewnie na myśli, że wybiorą z tych samochodów dokładnie jeden, a sprzedawca uznał, że sprzedanie im obu jest dozwoloną możliwością.

Wcześniejsze zdanie o Rosji jest prawdziwe, bo prawdziwe są oba zdania. Zdanie „liczba 7 jest podzielna przez 3 lub liczba 7 jest liczbą pierwszą” jest prawdziwe, bo siódemka jest liczbą pierwszą. Wprawdzie nie jest podzielna przez trzy, ale to nam już nie przeszkadza. Tabela wartości logicznych:

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

Wartość logiczna implikacji

Implikację oznaczamy $p \Rightarrow q$ i czytamy „jeżeli p, to q”. Przykładem implikacji może być zdanie „jeżeli wypijemy dużo wódki, to będziemy wymiotować”. Kiedy to zdanie będzie prawdziwe?

Implikacja logiczna jest najbardziej zdradliwym ze wszystkich spójników i także w mowie potocznej często bywa źle rozumiana i mylona z równoważnością. Spróbujmy odpowiedzieć na pytanie, czy jednocześnie zachodzi też implikacja odwrotna: $q \Rightarrow p$.

Wiemy, że jeśli wypijemy dużo wódki, to będziemy wymiotować. Czy zachodzi jednocześnie, że jeśli wymiotujemy, to wypiliśmy dużo wódki? Na pewno nie, mogliśmy pić zupełnie inny alkohol i i tak mogło nam się zrobić niedobrze, albo może nam być niedobrze z zupełnie innego powodu. Implikacja odwrotna nie musi więc automatycznie zachodzić. Jeśli zachodzi $p \Rightarrow q$ i jednocześnie zachodzi $q \Rightarrow p$, jest to równoważność, o której dalej.

Inny przykład: „jeżeli jutro będzie padać, to Janek weźmie ze sobą parasol”. A teraz powiem ci, że Janek wziął ze sobą parasol. Pytanie brzmi: czy tego dnia padało? Mnóstwo ludzi ma skłonność do odpowiedzi, że oczywiście tak, przecież Janek wziął ze sobą parasol, kiedy miało padać. Tylko że pierwotne zdanie wcale tak nie jest zbudowane!

Janek w rzeczywistości mógł wziąć parasol z jakiegoś innego powodu, o którym nie mamy pojęcia. Może Janek zawsze bierze ze sobą parasol, kiedy idzie odwiedzić teściową, żeby móc jej wydłubać oko. Albo postanowił, że kupi sobie nowy parasol, a stary chce wyrzucić. Wszystko to są uprawnione powody, dla których Janek mógł wziąć ze sobą parasol, chociaż wcale nie musiało padać.

Teraz już możemy odpowiedzieć na pytanie, kiedy implikacja będzie prawdziwa. Gdy oba zdania są prawdziwe, implikacja na pewno będzie prawdziwa: „jeżeli 42 jest liczbą naturalną, to jest dodatnia”. Oba zdania są prawdziwe, więc cała implikacja jest prawdziwa. Kolejnym przykładem może być implikacja „jeżeli 42 jest liczbą naturalną, to jest ujemna”. Ta implikacja nie jest prawdziwa, bo z prawdy próbujemy wyprowadzić coś, co prawdą nie jest.

Na koniec zostają przypadki, w których pierwsze zdanie jest fałszywe. Wtedy wartość logiczna drugiego zdania już nas nie interesuje. Jeśli wychodzimy od fałszu, możemy dalej pleść, co nam się podoba. Są to zdania typu „jeżeli 1 jest liczbą ujemną, to jesteśmy chińskim bogiem humoru” albo „jeżeli Beatlesi są znaną firmą budowlaną, to słońce jest niebieskie.” W takich przypadkach implikacja jest automatycznie prawdziwa, bo po prostu wychodzi od fałszu. Tabela:

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

Wartość logiczna równoważności

Równoważność zapisujemy p ⇔ q i czytamy „p wtedy i tylko wtedy, gdy q”. Przykładem równoważności może być „liczba x jest podzielna przez dwa wtedy i tylko wtedy, gdy jest parzysta”. Kiedy całe zdanie będzie prawdziwe?

Przy równoważności oczekujemy, że oba zdania są w takiej symbiozie, że albo zachodzą oba, albo nie zachodzi żadne. Czyli albo liczba x jest parzysta i jednocześnie podzielna przez dwa, albo nie jest ani jednym, ani drugim. Nie może się zdarzyć, że x byłoby parzyste, ale nie byłoby podzielne przez dwa.

Przykład: „Jurek czyta książkę wtedy i tylko wtedy, gdy siedzi w toalecie.” Żeby równoważność była spełniona, to zawsze, kiedy Jurek siedzi w toalecie, musi czytać książkę. A jednocześnie zawsze, kiedy czyta książkę, musi siedzieć w toalecie. Nie może się zdarzyć, że czyta książkę na przykład w łóżku.

Równoważność możemy wyrazić za pomocą dwóch implikacji. Czyli p ⇔ q moglibyśmy zapisać jako $p \Rightarrow q$ i jednocześnie $q \Rightarrow p$. Tabela:

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

Negacja

Negacja jest działaniem jednoargumentowym. Zapisujemy ją albo kreską p', albo takim symbolem: $\neg p$. W polskich szkołach najczęściej pisze się $\sim p$. Negacja zaprzecza pierwotnemu stwierdzeniu. Jeśli mamy zdanie „Ola jest piosenkarką”, to przez negację dostaniemy zdanie „Nieprawda, że Ola jest piosenkarką” albo w skrócie „Ola nie jest piosenkarką”. Praktycznie zawsze możemy utworzyć negację tak, że przed zdaniem postawimy „Nieprawda, że…”

Negacja odwraca wartość logiczną, czyli z 0 robi 1, a z 1 robi 0. Możemy więc napisać $\neg0=1$ i $\neg1=0$.

Uważaj na niektóre zdradliwe rzeczy. Weźmy stwierdzenie „wapno jest białe”. Jaka jest jego negacja? Komuś mogłoby przyjść do głowy, że „wapno jest czarne”, ale to nieprawda! Kiedy użyjemy poprzedniej reguły, negacją będzie zdanie „nieprawda, że wapno jest białe”. Czy to koniecznie znaczy, że musi być czarne? Nie znaczy, może być na przykład różowiutkie.

Tabela wszystkich spójników

$$\begin{array}{cccccc} p&q&p \wedge q&p \vee q&p \Rightarrow q&p \Leftrightarrow q\\ 1&1&1&1&1&1\\ 1&0&0&1&0&0\\ 0&1&0&1&1&0\\ 0&0&0&0&1&1 \end{array}$$

Wartość logiczna całej formuły

Teraz już umiemy ustalić wartość logiczną dwóch zdań połączonych spójnikiem logicznym. Całą formułę wyznaczamy zupełnie analogicznie. Jeśli mamy formułę $(p \Rightarrow q) \wedge r$, to w momencie, gdy wyznaczymy wartość formuły $(p \Rightarrow q)$, na przykład 1, dostajemy zwykłą koniunkcję 1 ∧ r, którą już umiemy rozwiązać.

Stopniowo stosując najprostsze spójniki logiczne, dojdziemy do wartości logicznej całej formuły. Często używa się do tego tak zwanej metody tabelkowej (zero-jedynkowej), która jest opisana dalej.

Metoda tabelkowa

Metody tabelkowej używa się przy wyznaczaniu wartości bardziej złożonych formuł. W pierwszych n kolumnach zapisujemy n zmiennych zdaniowych, z którymi formuła pracuje, a w kolejnych kolumnach stopniowo umieszczamy cząstkowe podformuły, które formuła zawiera. Na przykładzie będzie to jaśniejsze:

Weźmy formułę $(p \vee q) \wedge (q \Rightarrow p)$. Na początku wpisujemy do tabeli wszystkie zmienne zdaniowe, czyli p i q, oraz wszystkie kombinacje ich wartości:

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

Dalej dopisujemy kolumny dla poszczególnych podformuł p ∨ q i $q \Rightarrow p$.

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

Teraz wyznaczamy wartości tych formuł i uzupełniamy kolumny zerami albo jedynkami. W tabeli mamy wszystkie potrzebne informacje. Postępujemy tak, że gdy wyznaczamy p ∨ q w pierwszym wierszu, za p podstawiamy 1 i za q też 1. Dostajemy w ten sposób wyrażenie 1 ∨ 1. Jego wartością jest znowu 1, więc wpisujemy do tabeli jedynkę:

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

W ten sposób stopniowo uzupełniamy całą tabelę:

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

Teraz zostaje wyznaczyć wartość całej formuły. Oznaczmy ją na przykład $\varphi=(p \vee q) \wedge (q \Rightarrow p)$. Dodajemy do tabeli kolumnę z $\varphi$ i wyznaczamy jej wartości, przy czym korzystamy już z dwóch poprzednich kolumn.

$$\begin{array}{ccccc} p&q&p \vee q&q \Rightarrow p&\varphi\\ 1&1&1&1&1\\ 1&0&1&1&1\\ 0&1&1&0&0\\ 0&0&0&1&0 \end{array}$$

Tabela jest już kompletna i podaje nam wartość logiczną formuły we wszystkich możliwych wartościowaniach. Na przykład jeśli e(p) = 1 i jednocześnie e(q) = 1, to formuła jest prawdziwa. W przypadku, gdy e(p) = 0 i e(q) = 1, formuła prawdziwa nie jest.

Zauważ, że nie możemy powiedzieć „formuła jest prawdziwa”. To zdanie nie ma sensu, bo żeby powiedzieć, że formuła jest prawdziwa, musielibyśmy powiedzieć, w jakim wartościowaniu jest prawdziwa. Możemy więc powiedzieć, że „formuła $\varphi$ jest prawdziwa w wartościowaniu e₁ i nie jest prawdziwa w wartościowaniu e₂”.

Jedynym przypadkiem, w którym moglibyśmy powiedzieć, że formuła jest prawdziwa, jest sytuacja, gdy jest prawdziwa we wszystkich możliwych wartościowaniach. Na przykład formuła $p \vee \neg p$ jest prawdziwa we wszystkich wartościowaniach, więc możemy powiedzieć, że formuła jest prawdziwa. Podobnie w przypadku, gdy formuła będzie fałszywa we wszystkich wartościowaniach.

Takie formuły mają swoje specjalne nazwy. Formuła, która jest prawdziwa we wszystkich wartościowaniach, nazywa się tautologią. Formuła, która nie jest spełniona w żadnym wartościowaniu, nazywa się kontrtautologią (formułą sprzeczną).