Matematyka dla liceum/Logika/Prawa rachunku zdań

prawa rachunku zdań, prawo rachunku zdań

DEFINICJA Prawem rachunku zdań nazywamy zdanie złożone, które jest zawsze prawdziwe np. $p\lor \neg p$.

Rzeczywiście zdanie $p\lor \neg p$ jest zawsze prawdziwe. Mówiąc „Byłem w kinie lub nie byłem w kinie” nie skłamiemy. Prawo rachunku zdań nazywane jest też prawem logicznym lub tautologią. Innym przykładem zdania, zawsze prawdziwego jest zdanie „jeśli nieprawdą jest, że jadłem śniadanie lub nie jadłem obiadu, to nie jadłem śniadania i jadłem obiad”.

Ale jak sprawdzić, czy dane zdanie jest prawdziwe? Możemy do tego wykorzystać metodę „zero-jedynkową”. Zacznijmy od przykładu podanego na samym początku, czyli zdania $p\lor \neg p$. Najlepiej utworzyć do tego odpowiednią tabelkę i analizujemy wszystkie możliwości. W przypadku prostego zdania p mamy tylko dwie możliwości, jego wartość logiczna może wynosić albo 1 albo 0; czyli w tabelce pod p wstawiamy 1 i 0 i wyliczamy wartości logiczne poszczególnych zdań, które dodaliśmy do tabelki. Należy zauważyć, że nie można wpisać 1 dla zarówno p i ¬p, gdyż prowadzi to do sprzeczności. Podobnie, pod oba zdania nie można wpisać 0, gdyż i to prowadzi do sprzeczności. Przyjrzyjmy się możliwym przykładom umieszczonym w tabelce:

p	¬p	p ∨ ¬p
1	0	1
0	1	1

Zobaczmy kolejny przykład. Udowodnimy, że zdanie $(p\implies q)\lor p$ jest tautologią. Najpierw w pierwszej (p) i w drugiej kolumnie (q) wypisujemy wszystkie możliwości, których tym razem będzie cztery.

p	q	(p ⇒ q)	(p ⇒ q) ∨ p
1	1	1	1
1	0	0	1
0	1	1	1
0	0	1	1

Ponieważ zdanie $(p\implies q)\lor p$ jest zawsze prawdziwe (pokazuje nam to ostatnia kolumna, po prawej stronie), możemy wywnioskować, że jest tautologią (czyli prawem rachunku zdań).

Teraz jako ciekawostka metoda dowodu nie wprost, dla tych co nie lubią rysować tabelek. Zaczynamy:

Pierwszym krokiem jest założenie, że zdanie nasze jest fałszem: Załóżmy, że

$[(p\implies q)\lor p]=0$

Z definicji alternatywy wiemy, że jest ona fałszywa gdy oba jej składniki są fałszywe, czyli

$[p\implies q]=0\land p=0$.

Stąd widzimy, że nasza implikacja $p\implies q$ jest zawsze prawdziwa, bo p jest fałszem. Zatem całe zdanie jest prawdziwe. Otrzymaliśmy sprzeczność z założeniem, czyli nasze zdanie jest tautologią.

Jak widać metoda jest szybka i może oszczędzić dużo czasu przy bardziej skomplikowanych zdaniach. Trzeba pamiętać, że jeśli nie uzyskamy sprzeczności, to otrzymaliśmy przykład kiedy zdanie jest fałszem. Zwłaszcza kiedy mamy kilka przypadków kończymy sprawdzanie pozostałych w momencie gdy w którymś z nich nie otrzymaliśmy sprzeczności.

A jak pokazać, że zdanie „jeśli nieprawdą jest, że jadłem śniadanie lub nie jadłem obiadu, to nie jadłem śniadania i jadłem obiad” jest „politycznie poprawne”, czyli zawsze prawdziwe. Nawet intuicyjnie ciężko jest zrozumieć to zdanie, więc musimy je przerobić na zapis matematyczny. Mamy dwa zdania proste:

p: jadłem śniadanie

q: jadłem obiad.

Zdanie podrzędne „nieprawdą jest, że jadłem śniadanie lub nie jadłem obiadu” zapiszemy jako:

$\neg (p\lor \neg q)$,

a zdanie „nie jadłem śniadania i jadłem obiad” jako:

$\neg p\land q$.

Czyli całe zdanie przybierze postać:

$\neg (p\lor \neg q)\implies (\neg p\land q)$.

Teraz tworzymy tabelę dla tego „logicznego giganta” i sprawdzamy wszystkie możliwości.

p	q	¬p	¬q	p ∨ ¬q	¬(p ∨ ¬q)	¬p ∧ q	¬(p ∨ ¬q) ⇒ (¬p ∧ q)
1	1	0	0	1	0	0	1
1	0	0	1	1	0	0	1
0	1	1	0	0	1	1	1
0	0	1	1	1	0	0	1

A teraz metodą poznaną wcześniej, o wiele krócej:

Załóżmy, że $[\neg (p\lor \neg q)\implies (\neg p\land q)]=0$ Z definicji wiemy, że implikacja jest fałszywa w jednym przypadku: $1\implies 0$. Zatem nasza implikacja jest fałszywa gdy:

$[\neg (p\lor \neg q)]=1\land [\neg p\land q]=0$

Zajmijmy się lewą stroną implikacji.

$[\neg (p\lor \neg q)]=1$

Stąd

$[(p\lor \neg q)]=0$

Alternatywa jest fałszem, gdy obydwa jej składniki są fałszywe, czyli $p=0\land \neg q=0$, czyli q jest prawdą. Skoro znamy już p i q. Popatrzmy teraz na prawą stronę implikacji.

$\neg p\land q$

Podstawiamy nasze p i q

$\neg 0\land 1=1\land 1=1$

Otrzymaliśmy sprzeczność z założeniem, czyli nasze zdanie jest zawsze prawdziwe.

No dobra, ale jak najłatwiej wypisać wszystkie możliwości, gdy zdanie składa się z wielu zmiennych np. z trzech p, q, r. Zobaczmy najpierw, jakby wyglądał początek takiej tabelki.

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	...

Widzimy, że mamy $8=2^{3}$ możliwości. Teraz jak je wypisać? Hmm... na samej górze mamy same jedynki, pod kolumną r mamy od góry 1, 0, 1, 0, 1 itp., czyli wartości co chwilę zmieniają, pod kolumną q wartości się zmieniają co dwa, a pod kolumną p co cztery. Czyli już mamy sposób:

• na samej górze dajemy same jedynki,
• pod trzecią kolumną (r) zmieniamy wartości co jeden,
• pod drugą kolumną (q) zmieniamy wartości co dwa,
• pod pierwszą kolumną (p) zmieniamy wartości co cztery.

Sytuacja dla czterech, pięciu, czy sześciu zmiennych będzie bardzo podobna, tylko gdzieniegdzie będzie trzeba zmieniać wartość co osiem, co szesnaście itp.

Czy zdanie $\neg (p\land q\land r)\iff (\neg p\lor \neg q\lor \neg r)$ jest tautologią? Sprawdźmy.

p	q	r	¬p	¬q	¬r	p ∧ q ∧ r	¬(p ∧ q ∧ r)	¬p ∨ ¬q ∨ ¬r	¬(p ∧ q ∧ r) ⇔ (¬p ∨ ¬q ∨ ¬r)
1	1	1	0	0	0	1	0	0	1
1	1	0	0	0	1	0	1	1	1
1	0	1	0	1	0	0	1	1	1
1	0	0	0	1	1	0	1	1	1
0	1	1	1	0	0	0	1	1	1
0	1	0	1	0	1	0	1	1	1
0	0	1	1	1	0	0	1	1	1
0	0	0	1	1	1	0	1	1	1

Ponieważ zdanie to ma zawsze wartość logiczną równą 1, więc jest prawem rachunku zdań.

A teraz szybszą metodą bez robienia tabelek. Załóżmy, że

$[\neg (p\land q\land r)\iff (\neg p\lor \neg q\lor \neg r)]=0$

Z definicji równoważności, są dwa przypadki kiedy jest fałszywa. Zatem musimy rozpatrzyć je obydwa. Pierwszy przypadek:

$[\neg (p\land q\land r)]=1\land [\neg p\lor \neg q\lor \neg r]=0$

Zajmiemy się

$[\neg p\lor \neg q\lor \neg r]=0$

$\neg p=0\land \neg q=0\land \neg r=0$

$p=1\land q=1\land r=1$

Sprawdzamy

$[\neg (1\land 1\land 1)]=[\neg 1]=0$

Otrzymaliśmy sprzeczność, więc w tym przypadku zdanie jest prawdą.

Drugi przypadek:

$[\neg (p\land q\land r)]=0\land [\neg p\lor \neg q\lor \neg r]=1$

Zajmijmy się:

$[\neg (p\land q\land r)]=0$

$[(p\land q\land r)]=1$

$p=1\land q=1\land r=1$

Sprawdzamy

$[\neg 1\lor \neg 1\lor \neg 1]=[0\lor 0\lor 0]=0$

Zatem sprzeczność z założeniem, więc i w tym przypadku zdanie jest prawdziwe. A skoro w obydwu przypadkach zdanie jest prawdziwe, to jest to tautologia.

Prawa De Morgana

prawa De Morgana, I prawo De Morgana, II prawo De Morgana

Na koniec przedstawimy prawa De Morgana dotyczące zaprzeczeń zdań złożonych:

• I prawo De Morgana:

  $\neg (p\lor q)\iff \neg p\land \neg q$

  (Zaprzeczenie alternatywy dwóch zdań jest równoważne koniunkcji zaprzeczeń tych zdań)

• II prawo De Morgana:

  $\neg (p\land q)\iff \neg p\lor \neg q$

  (Zaprzeczenie koniunkcji dwóch zdań jest równoważne alternatywie zaprzeczeń tych zdań)

Prawa te są oczywiście tautologiami. W ćwiczeniu 9 zostaniesz poproszony o udowodnienie tych praw.

Jak napisać zdanie „każdy pies ma cztery łapy” lub „są ludzie, którzy nie umieją liczyć”? W następnym podrozdziale dowiemy się, jak pisać zdania takiego typu, czyli zdania odnoszące się do własności pewnego zbioru. Dowiemy się, co oznacza tajemnicze słowo „kwantyfikator”...