Prawda formuł

Jeśli mamy kilka atomowych stwierdzeń, które umieszczamy w formule, możemy spróbować zdecydować, czy cała formuła jest prawdziwa czy fałszywa.

Prawdziwość stwierdzenia

Pierwszą rzeczą, którą określimy, jest wartość prawdziwości stwierdzenia. Biorąc pod uwagę stwierdzenie p, powinniśmy być w stanie zdecydować, czy jest ono prawdziwe, czy fałszywe. Prawdziwe stwierdzenie będzie miało wartość prawdy 1, a fałszywe stwierdzenie będzie miało wartość prawdy 0.

Wartość prawdy jest wtedy regułą e, która przypisuje albo 0 albo 1 danemu stwierdzeniu. Jeśli napiszemy e(p), chcemy określić wartość prawdy stwierdzenia p. Jeśli p jest równe stwierdzeniu "dwa razy dwa jest cztery", to e(p) = 1, ponieważ jest to prawdziwe stwierdzenie. Jeśli q jest równe stwierdzeniu "Václav Klaus jest kobietą", to e(q) = 0, ponieważ Vasek nie jest kobietą. Zatem e jest funkcją, która zwraca, czy stwierdzenie jest prawdziwe.

Należy pamiętać, że e nie jest jakąś magiczną funkcją, która wie wszystko o świecie. Zachowuje się tak, jak jej każemy. Nie wie, czy Václav Klaus jest mężczyzną czy kobietą. Powinniśmy zadeklarować na początku obliczeń, jak powinna zachowywać się funkcja oceniająca. Jeśli powiemy jej, że Václav Klaus jest kobietą, zwróci e(q) = 1.

Prawdziwość spójników zdaniowych

Aby określić prawdziwość formuły, musimy wiedzieć, jak ocenić prawdziwość spójników zdaniowych. To znaczy, jeśli znamy ocenę e(p) i e(q), jaka będzie wartość prawdziwości formuł p ∧ q, $p \Rightarrow q$, itd.

Każdy spójnik propozycjonalny zachowuje się inaczej i jest używany do czegoś innego, więc omówimy każdy spójnik osobno.

Wartość prawdziwa koniunkcji

Koniunkcja jest oznaczona przez p ∧ q i brzmi "p i również q". Jako przykład rozważmy formułę "Republika Czeska znajduje się w Europie Środkowej, a jednocześnie jej stolicą jest Praga". Kiedy całe zdanie będzie prawdziwe?

Sam spójnik "a jednocześnie" pomoże nam określić prawdę. Wyraźnie mówi nam, że chce, aby zarówno stwierdzenia po lewej, jak i po prawej stronie były prawdziwe. Tak więc, jeśli oba stwierdzenia p i q są prawdziwe, czyli e(p) = 1 i e(q) = 1, to cała koniunkcja jest prawdziwa. W przeciwnym razie, gdy jedno ze stwierdzeń jest fałszywe lub oba są fałszywe, cała formuła jest fałszywa.

Przykładem koniunkcji, która nie jest prawdziwa może być "Wełtawa jest rzeką i jednocześnie Wełtawa przepływa przez Rosję". Prawdą jest, że Wełtawa jest rzeką, ale nie jest prawdą, że przepływa przez Rosję, więc cały spójnik nie jest prawdziwy.

Poniższa tabela wyraźnie to stwierdza:

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

Pierwsze dwie kolumny to wartości prawdziwościowe stwierdzeń p i q, a trzecia kolumna to wartość prawdziwościowa formuły p ∧ q.

Wartość prawdy dysjunkcji

Dysjunkcja jest oznaczona przez p ∨ q i brzmi "p lub q". Przykład: "Rosja jest w Europie lub Azji". Kiedy całe zdanie będzie prawdziwe?

W przypadku dysjunkcji potrzebujemy tylko co najmniej jednej z opcji, aby była prawdziwa. Spójnik "lub" daje nam wybór, czy lewa lub prawa część spójnika jest prawdziwa. Jedyną niewielką różnicą w stosunku do zwykłej mowy jest to, że logiczne lub jest prawdziwe, nawet jeśli oba stwierdzenia są spełnione w tym samym czasie. Nie jest to całkowicie zwyczajne; często w zwykłej mowie używamy "lub" w sposób wykluczający, tj. "albo ... albo ...".

Jest na ten temat klasyczny dowcip: rodzina wybiera nowy samochód w sklepie z używanymi rzeczami. Tata mówi sprzedawcy: "zdecydowaliśmy się na niebieski lub czerwony samochód". Sprzedawca sprzedaje im oba samochody. Jest to ilustracja różnicy między logicznym a mówionym lub: tata prawdopodobnie miał na myśli, że wybiorą jeden z samochodów, podczas gdy sprzedawca uznał za ważną opcję sprzedanie im obu samochodów.

Poprzednie zdanie z Rosją jest prawdziwe, ponieważ oba stwierdzenia są prawdziwe. Zdanie "liczba 7 jest podzielna przez 3 lub liczba 7 jest liczbą pierwszą" jest prawdziwe, ponieważ siedem jest liczbą pierwszą. Może nie być podzielna przez trzy, ale to już nie ma znaczenia. Tabela wartości prawdy:

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

Prawdziwość implikacji

Implikacja jest oznaczona przez $p \Rightarrow q$ i brzmi "jeśli p, to q". Przykładem implikacji może być zdanie "jeśli wypijemy dużo wódki, to będziemy wymiotować". Kiedy to zdanie będzie prawdziwe?

Implikacja logiczna jest najbardziej skomplikowanym ze wszystkich spójników i nawet w mowie potocznej jest często źle rozumiana i mylona z równoważnością. Spróbujmy odpowiedzieć na pytanie, czy implikacja odwrotna jest również prawdziwa: $q \Rightarrow p$.

Wiemy, że jeśli wypijemy dużo wódki, będziemy wymiotować. Czy prawdą jest również, że jeśli wymiotujemy, to wypiliśmy dużo wódki? Z pewnością nie, mogliśmy wypić zupełnie inny alkohol i nadal być chorzy, lub mogliśmy być chorzy z powodu czegoś zupełnie innego. Tak więc odwrotna implikacja może nie mieć automatycznego zastosowania. Jeśli $p \Rightarrow q$ ma zastosowanie i $q \Rightarrow p$ ma zastosowanie w tym samym czasie, jest to równoważność, patrz poniżej.

Inny przykład: "jeśli jutro będzie padać, Honza weźmie ze sobą parasol". Teraz powiem ci, że Honza zabrał ze sobą parasol. Pytanie brzmi, czy tego dnia padało? Wiele osób ma tendencję do mówienia, że oczywiście, że tak, ponieważ Honza zabrał ze sobą parasol, gdy miało padać. Ale nie tak skonstruowane jest oryginalne zdanie!

W rzeczywistości Honza mógł wziąć parasol w innym celu, o którym nie mamy pojęcia. Może Honza zabiera ze sobą parasol za każdym razem, gdy idzie odwiedzić swoją teściową, aby móc wydłubać jej oko. A może postanowił kupić nowy parasol i chce wyrzucić stary. Są to uzasadnione powody, dla których Honza mógł zabrać ze sobą parasol, nawet jeśli nie padało.

Teraz możemy odpowiedzieć na pytanie, kiedy implikacja będzie prawdziwa. Jeśli oba stwierdzenia są prawdziwe, to implikacja na pewno będzie prawdziwa: "jeśli 42 jest liczbą naturalną, to jest dodatnia". Oba stwierdzenia są prawdziwe, więc cała implikacja jest prawdziwa. Innym przykładem może być implikacja "jeśli 42 jest liczbą naturalną, to jest ujemna". Ta implikacja nie jest prawdziwa, ponieważ próbujemy wywnioskować z prawdy coś, co nie jest prawdą.

Na koniec pozostają nam przypadki, w których pierwsze stwierdzenie jest fałszywe. W takim przypadku nie jesteśmy już zainteresowani prawdziwością drugiego stwierdzenia. Jeśli zaczynamy od nieprawdy, możemy bełkotać do woli. Są to zdania takie jak "jeśli 1 jest liczbą ujemną, to jesteśmy chińskim bogiem zabawy" lub "jeśli Beatlesi są słynną firmą budowlaną, to słońce jest niebieskie". W takich przypadkach implikacja jest automatycznie prawdziwa, ponieważ jest po prostu oparta na nieprawdzie. Tabela:

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

Prawdziwość równoważności

Równoważność jest napisana p ⇔ q i brzmi "p właśnie wtedy, gdy q". Przykładem równoważności może być "liczba x jest podzielna przez dwa tylko wtedy, gdy jest parzysta". Kiedy całe zdanie będzie prawdziwe?

W przypadku równoważności oczekujemy, że dwa stwierdzenia będą w takiej symbiozie, że albo oba są prawdziwe, albo żadne z nich nie jest prawdziwe. Zatem albo liczba x jest parzysta i podzielna przez dwa, albo nie jest. Nie może być tak, że x jest parzysta, ale nie jest podzielna przez dwa.

Przykład. Aby równoważność była spełniona, za każdym razem, gdy George siedzi w toalecie, musi czytać książkę. W tym samym czasie, gdy czyta książkę, musi siedzieć na toalecie. Nie może być tak, że czyta książkę w łóżku.

Równoważność może być wyrażona przez dwie implikacje. Tak więc p ⇔ q można przepisać 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 operacją jednoargumentową, zapisujemy ją za pomocą przecinka p' lub tego symbolu: $\neg p$. Negacja unieważni nasze oryginalne stwierdzenie. Jeśli mamy stwierdzenie "Lucie Bílá jest piosenkarką", to przez negację otrzymamy stwierdzenie "Nieprawdą jest, że Lucie Bílá jest piosenkarką" lub w skrócie "Lucie Bílá nie jest piosenkarką". Prawie zawsze możemy utworzyć negację, umieszczając "Nieprawdą jest, że..." przed stwierdzeniem.

Negacja odwraca wartość prawdy, tj. zamienia 0 w 1 i 1 w 0. Możemy napisać $\neg0=1$ i $\neg1=0$.

Należy uważać na pewne podchwytliwe rzeczy. Weźmy stwierdzenie "limonka jest biała". Jakie jest jego zaprzeczenie? Można by pomyśleć, że "limonka jest czarna", ale to nieprawda! Korzystając z poprzedniej lekcji, negacją byłoby stwierdzenie "nieprawdą jest, że limonka jest biała". Czy to oznacza, że musi być czarne? Nie, może być różowawe.

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

Prawdziwość całej formuły

Możemy teraz ocenić prawdziwość dwóch stwierdzeń, które są połączone spójnikiem zdaniowym. Ocenimy całą formułę w całkowicie analogiczny sposób. Jeśli mamy formułę $(p \Rightarrow q) \wedge r$, to w momencie, gdy ocenimy na przykład formułę $(p \Rightarrow q)$ do 1, otrzymamy klasyczną koniunkcję 1 ∧ r, którą już wiemy, jak rozwiązać.

Poprzez kolejne zastosowanie najprostszych spójników propozycjonalnych dochodzimy do ostatecznej wartości prawdziwościowej całej formuły. Często używa się do tego tak zwanej metody tabelarycznej, którą opiszemy poniżej.

Metoda tabelaryczna

Metoda tabelaryczna jest używana do obliczania bardziej złożonych formuł. W pierwszych kolumnach n zapisujemy symbole n propozycjonalne, z którymi działa formuła, a w kolejnych kolumnach kolejno umieszczamy podformuły, które formuła zawiera. Przykład uczyni to bardziej zrozumiałym:

Załóżmy formułę $(p \vee q) \wedge (q \Rightarrow p)$. Na początku zapisujemy wszystkie symbole propozycjonalne, tj. p i q, oraz wszystkie ich kombinacje ewaluacyjne:

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

Następnie dodajmy kolumny dla każdej podformuły 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 oceniamy te formuły i dodajemy zera lub jedynki do kolumn. W tabeli mamy wszystkie niezbędne informacje. Kontynuujemy, oceniając p ∨ q w pierwszym wierszu, a następnie dodajemy 1 po p i 1 po q. W ten sposób otrzymujemy wyrażenie 1 ∨ 1. Wynikiem oceny tego wyrażenia jest ponownie 1, więc w tabeli wpisujemy 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 uzupełniamy tabelę po kolei:

$$\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 pozostaje ocenić całą formułę. Dla przykładu oznaczmy ją jako $\varphi=(p \vee q) \wedge (q \Rightarrow p)$. Dodajemy kolumnę z $\varphi$ do tabeli i oceniamy ją, używając poprzednich dwóch kolumn do oceny.

$$\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 teraz kompletna i daje nam wartość prawdy formuły we wszystkich możliwych ocenach. Na przykład, jeśli e(p) = 1 i jednocześnie e(q) = 1, to formuła jest prawdziwa. Jeśli e(p) = 0 i e(q) = 1, to formuła nie jest prawdziwa.

Zauważ, że nie możemy powiedzieć, że "formuła jest prawdziwa". To zdanie nie ma sensu, ponieważ aby powiedzieć, że formuła jest prawdziwa, musielibyśmy powiedzieć , w jakiej wartościowaniu formuła jest prawdziwa. Możemy więc powiedzieć, że "formuła $\varphi$ jest prawdziwa w wycenie e₁ i nie jest prawdziwa w wycenie e₂".

Jedynym przypadkiem, w którym możemy powiedzieć, że formuła jest prawdziwa, jest sytuacja, w której jest ona prawdziwa we wszystkich możliwych wycenach. Na przykład formuła $p \vee \neg p$ jest prawdziwa we wszystkich ocenach, więc możemy powiedzieć, że formuła jest prawdziwa. Podobnie w przypadku, gdy formuła jest fałszywa we wszystkich ocenach.

Takie formuły mają wtedy specjalną etykietę. Formuła, która jest prawdziwa we wszystkich ocenach, nazywana jest tautologią. Formuła, która nie jest spełniona w żadnej ocenie, nazywana jest sprzecznością.