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

Usunięta treść Dodana treść
zamiana MDL:NawGórna->Subst:Naw
Linia 46:
 
Ponieważ zdanie <math> (p \implies q) \or 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:
 
Pierwszym krokiem jest założenie, że zdanie nasze jest fałszem:
Załóżmy, że
: <math> [(p \implies q) \or 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 \and 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.
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:
Linia 81 ⟶ 94:
</div>
 
A teraz metodą poznaną wcześniej, o wiele krócej:
 
Załóżmy, że <math> [\neg (p \or \neg q) \implies (\neg p \and 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 \or \neg q)] = 1 \and [\neg p \and q] = 0 </math>
Zajmijmy się lewą stroną implikacji.
: <math> [\neg (p \or \neg q)] = 1 </math>
Stąd
: <math> [(p \or \neg q)] = 0 </math>
Alternatywa jest fałszem, gdy obydwa jej składniki są fałszywe, czyli <math> p = 0 \and \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 \and q</math>
Podstawiamy nasze {{math|p}} i {{math|q}}
: <math> \neg 0 \and 1 = 1 \and 1 = 1 </math>
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 {{math|p}}, {{math|q}}, {{math|r}}. Zobaczmy najpierw, jakby wyglądał początek takiej tabelki.
Linia 150 ⟶ 178:
 
Ponieważ zdanie to ma zawsze wartość logiczną równą {{math|1}}, więc jest prawem rachunku zdań.
 
A teraz szybszą metodą bez robienia tabelek.
Załóżmy, że
: <math> [ \neg (p \and q \and r) \iff ( \neg p \or \neg q \or \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 \and q \and r) ] = 1 \and [ \neg p \or \neg q \or \neg r ] = 0 </math>
Zajmiemy się
: <math> [ \neg p \or \neg q \or \neg r ] = 0 </math>
: <math> \neg p = 0 \and \neg q = 0 \and \neg r = 0 </math>
: <math> p = 1 \and q = 1 \and r = 1 </math>
Sprawdzamy
: <math> [ \neg (1 \and 1 \and 1) ] = [ \neg 1 ] = 0 </math>
Otrzymaliśmy sprzeczność, więc w tym przypadku zdanie jest prawdą.
 
Drugi przypadek:
: <math> [ \neg (p \and q \and r) ] = 0 \and [ \neg p \or \neg q \or \neg r ] = 1 </math>
Zajmijmy się:
: <math> [ \neg (p \and q \and r) ] = 0 </math>
: <math> [ (p \and q \and r) ] = 1 </math>
: <math> p = 1 \and q = 1 \and r = 1 </math>
Sprawdzamy
: <math> [ \neg 1 \or \neg 1 \or \neg 1 ] = [ 0 \or 0 \or 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.
 
==== Prawa De Morgana ====