Wikibooks

Matematyka dla liceum/Logika/Prawa rachunku zdań: Różnice pomiędzy wersjami

Przeglądaj historię interaktywnie
← poprzednia edycjanastępna edycja →
Usunięta treść Dodana treść
WizualnieWikikod
m Zastępowanie przestarzałej składni LaTeX zgodnie z mw:Extension:Math/Roadmap
Linia 2:
{{index|prawa rachunku zdań, prawo rachunku zdań}}
{{Mat:Def|
'''Prawem rachunku zdań''' nazywamy zdanie złożone, które jest zawsze prawdziwe np. <math> p \orlor \neg p</math>.}}
 
Rzeczywiście zdanie <math> p \orlor \neg p </math> 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 <math>p \orlor \neg p</math>. Najlepiej utworzyć do tego odpowiednią tabelkę i analizujemy wszystkie możliwości. W przypadku prostego zdania {{math|p}} mamy tylko dwie możliwości, jego wartość logiczna może wynosić albo {{math|1}} albo {{math|0}}; czyli w tabelce pod {{math|p}} wstawiamy {{math|1}} i {{math|0}} i wyliczamy wartości logiczne poszczególnych zdań, które dodaliśmy do tabelki. Należy zauważyć, że nie można wpisać {{math|1}} dla zarówno {{math|p}} i {{math|&not;p}}, gdyż prowadzi to do sprzeczności. Podobnie, pod oba zdania nie można wpisać {{math|0}}, gdyż i to prowadzi do sprzeczności. Przyjrzyjmy się możliwym przykładom umieszczonym w tabelce:
 
<div align="center">
Linia 19:
</div>
 
Zobaczmy kolejny przykład. Udowodnimy, że zdanie <math> (p \implies q) \orlor p </math> jest tautologią. Najpierw w pierwszej ({{math|p}}) i w drugiej kolumnie ({{math|q}}) wypisujemy wszystkie możliwości, których tym razem będzie cztery.
 
<div align="center">
Linia 37:
</div>
 
Ponieważ zdanie <math> (p \implies q) \orlor p </math> 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:
Linia 43:
Pierwszym krokiem jest założenie, że zdanie nasze jest fałszem:
Załóżmy, że
: <math> [(p \implies q) \orlor p] = 0 </math>
Z definicji alternatywy wiemy, że jest ona fałszywa gdy oba jej składniki są fałszywe, czyli
: <math> [p \implies q] = 0 \andland p = 0 </math>.
Stąd widzimy, że nasza implikacja <math> p \implies q </math> jest zawsze prawdziwa, bo {{math|p}} jest fałszem.
Zatem całe zdanie jest prawdziwe.
Linia 56:
: {{math|q}}: jadłem obiad.
Zdanie podrzędne „nieprawdą jest, że jadłem śniadanie lub nie jadłem obiadu” zapiszemy jako:
: <math> \neg (p \orlor \neg q) </math>,
a zdanie „nie jadłem śniadania i jadłem obiad” jako:
: <math> \neg p \andland q </math>.
Czyli całe zdanie przybierze postać:
: <math> \neg (p \orlor \neg q) \implies (\neg p \andland q) </math>.
 
Teraz tworzymy tabelę dla tego „logicznego giganta” i sprawdzamy wszystkie możliwości.
Linia 88:
A teraz metodą poznaną wcześniej, o wiele krócej:
 
Załóżmy, że <math> [\neg (p \orlor \neg q) \implies (\neg p \andland q)] = 0 </math>
Z definicji wiemy, że implikacja jest fałszywa w jednym przypadku: <math> 1 \implies 0 </math>.
Zatem nasza implikacja jest fałszywa gdy:
: <math> [\neg (p \orlor \neg q)] = 1 \andland [\neg p \andland q] = 0 </math>
Zajmijmy się lewą stroną implikacji.
: <math> [\neg (p \orlor \neg q)] = 1 </math>
Stąd
: <math> [(p \orlor \neg q)] = 0 </math>
Alternatywa jest fałszem, gdy obydwa jej składniki są fałszywe, czyli <math> p = 0 \andland \neg q = 0 </math>, czyli q jest prawdą. Skoro znamy już {{math|p}} i {{math|q}}. Popatrzmy teraz na prawą stronę implikacji.
: <math> \neg p \andland q</math>
Podstawiamy nasze {{math|p}} i {{math|q}}
: <math> \neg 0 \andland 1 = 1 \andland 1 = 1 </math>
Otrzymaliśmy sprzeczność z założeniem, czyli nasze zdanie jest zawsze prawdziwe.
 
Linia 135:
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 <math> \neg (p \andland q \andland r) \iff (\neg p \orlor \neg q \orlor \neg r) </math> jest tautologią? Sprawdźmy.
 
<div align="center">
Linia 173:
A teraz szybszą metodą bez robienia tabelek.
Załóżmy, że
: <math> [ \neg (p \andland q \andland r) \iff ( \neg p \orlor \neg q \orlor \neg r ) ] = 0 </math>
Z definicji równoważności, są dwa przypadki kiedy jest fałszywa. Zatem musimy rozpatrzyć je obydwa.
Pierwszy przypadek:
: <math> [ \neg (p \andland q \andland r) ] = 1 \andland [ \neg p \orlor \neg q \orlor \neg r ] = 0 </math>
Zajmiemy się
: <math> [ \neg p \orlor \neg q \orlor \neg r ] = 0 </math>
: <math> \neg p = 0 \andland \neg q = 0 \andland \neg r = 0 </math>
: <math> p = 1 \andland q = 1 \andland r = 1 </math>
Sprawdzamy
: <math> [ \neg (1 \andland 1 \andland 1) ] = [ \neg 1 ] = 0 </math>
Otrzymaliśmy sprzeczność, więc w tym przypadku zdanie jest prawdą.
 
Drugi przypadek:
: <math> [ \neg (p \andland q \andland r) ] = 0 \andland [ \neg p \orlor \neg q \orlor \neg r ] = 1 </math>
Zajmijmy się:
: <math> [ \neg (p \andland q \andland r) ] = 0 </math>
: <math> [ (p \andland q \andland r) ] = 1 </math>
: <math> p = 1 \andland q = 1 \andland r = 1 </math>
Sprawdzamy
: <math> [ \neg 1 \orlor \neg 1 \orlor \neg 1 ] = [ 0 \orlor 0 \orlor 0 ] = 0 </math>
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.
Linia 200:
Na koniec przedstawimy prawa De Morgana dotyczące zaprzeczeń zdań złożonych:
* '''I prawo De Morgana''':
*: <math> \neg ( p \orlor q ) \iff \neg p \andland \neg q </math>
*: (Zaprzeczenie alternatywy dwóch zdań jest równoważne koniunkcji zaprzeczeń tych zdań)
* '''II prawo De Morgana''':
*: <math> \neg ( p \andland q ) \iff \neg p \orlor \neg q </math>
*: (Zaprzeczenie koniunkcji dwóch zdań jest równoważne alternatywie zaprzeczeń tych zdań)
 
Źródło: „https://pl.wikibooks.org/wiki/Matematyka_dla_liceum/Logika/Prawa_rachunku_zdań”