Login lub e-mail Hasło   

Prawa rachunku zdań (matematyka)

DEFINICJA Prawem rachunku zdań nazywamy zdanie złożone, które jest zawsze prawdziwe np. . Rzeczywiście zdanie jest zawsze prawdziwe. Mówiąc „Byłem w kinie...
Wyświetlenia: 6.642 Zamieszczono 04/05/2007
 
Definicja
DEFINICJA

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

Rzeczywiście zdanie p \or \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 \or \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.

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

Zobaczmy kolejny przykład. Udowodnimy, że zdanie (p \implies q) \or 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) \or p jest zawsze prawdziwe (pokazuje nam to ostatnie kolumna, po prawej stronie), możemy wywnioskować, że jest tautologią (czyli prawem rachunku zdań).

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 \or \neg q),

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

\neg p \and q.

Czyli całe zdanie przybierze postać:

\neg (p \or \neg q) \implies (\neg p \and 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


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 = 23 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 \and q \and r) \iff (\neg p \or \neg q \or \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ń.

Prawa De Morgana

 

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

  • I prawo De Morgana:
    \neg ( p \or q ) \iff \neg p \and \neg q
    (Zaprzeczenie alternatywy dwóch zdań jest równoważne koniunkcji zaprzeczeń tych zdań)
  • II prawo De Morgana:
    \neg ( p \and q ) \iff \neg p \or \neg q
    (Zaprzeczenie koniunkcji dwóch zdań jest równoważne alternatywie zaprzeczeń tych zdań)

Prawa te są oczywiście tautologiami. W ćwiczeniu ??? 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”...

 

Treść udostępniana na licencji GNU Free Documentation License . Źródło: Wikibooks.pl

Podobne artykuły


36
komentarze: 7 | wyświetlenia: 5708
29
komentarze: 63 | wyświetlenia: 2717
25
komentarze: 4 | wyświetlenia: 5043
23
komentarze: 8 | wyświetlenia: 1877
21
komentarze: 7 | wyświetlenia: 8358
20
komentarze: 15 | wyświetlenia: 1257
20
komentarze: 3 | wyświetlenia: 9118
22
komentarze: 27 | wyświetlenia: 3917
17
komentarze: 7 | wyświetlenia: 10316
14
komentarze: 12 | wyświetlenia: 4420
11
komentarze: 2 | wyświetlenia: 1570
10
komentarze: 2 | wyświetlenia: 3629
58
komentarze: 20 | wyświetlenia: 81170
48
komentarze: 31 | wyświetlenia: 9272
 
Autor
Dodał do zasobów: juliusz
Artykuł

Powiązane tematy






Brak wiadomości


Dodaj swoją opinię
W trosce o jakość komentarzy wymagamy od użytkowników, aby zalogowali się przed dodaniem komentarza. Jeżeli nie posiadasz jeszcze swojego konta, zarejestruj się. To tylko chwila, a uzyskasz dostęp do dodatkowych możliwości!
 

© 2005-2018 grupa EIOBA. Wrocław, Polska