http://www.sciaga.pl/tekst/30305-31-rachunek_zdan_kwantyfikatory_definicje_i_twierdzenia

Rachunek zdań, kwantyfikatory, dowód, twierdzenie

Zdaniami w logice nazywamy zdania orzekające, o których decydujemy, że są prawdziwe lub fałszywe.(to znaczy można określić wartość logiczną zdania). Np. Łódź jest stolicą Polski (zdanie uznane za fałszywe) , Kot jest ssakiem (zdanie uznane za prawdziwe)

Zdania proste można łączyć funktorami zdaniotwórczymi:
(lub),
(i),
(jeżeli...to...), ,
 (nieprawda, że...), tworząc w ten sposób zdanie złożone.

Zdania proste zapisujemy: p, q, r, s,

1. zdanie ¬ p (nieprawda, że p) nazywamy zaprzeczeniem (negacją zdania).

Negacja zmienia wartość logiczną zdania na przeciwną

2. zdanie p
   q (p i q) nazywamy koniunkcją zdań p i q. Koniunkcja zdań jest prawdziwa, gdy oba zdania są prawdziwe. W przeciwnym wypadku jest fałszywa.

3. Zdanie p
   q (p lub q) nazywamy alternatywą zdań p i q. Alternatywa dwóch zdań jest prawdziwa, gdy co najmniej jedno ze zdań jest prawdziwe, a fałszywa, gdy obydwa zdania są fałszywe.

Zdanie p ⇒ q (jeśli p to q) to okres warunkowy nazywany dziś często implikacją zdań p i q. Zdanie p nazywamy poprzednikiem okresu warunkowego implikacji, zdanie q jego następnikiem. Okres warunkowy Implikacja jest fałszywy tylko wtedy, gdy poprzednik jest prawdziwy a następnik fałszywy.

Okresem warunkowym Implikacją zdań: Dzisiaj jest niedziela (np. fałsz). Nie idę do szkoły (np. prawda), jest zdanie: Jeśli dzisiaj jest niedziela to nie idę do szkoły,(wobec powyższego wyboru wartości logicznych -prawda).

Zdanie p
q (p wtedy i tylko wtedy gdy q) nazywamy równoważnością zdań p i q. Równowartość jest prawdziwa gdy zdania p i q są obydwa prawdziwe, albo obydwa fałszywe.

Równoważnością zdań: Punkt x jest równo odległy od ramion kąta. Punkt k leży na dwusiecznej kąta, jest zdanie: Punkt k jest równo odległy od ramion kąta wtedy i tylko wtedy, gdy leży na dwusiecznej tego kąta.

Niektóre prawa rachunku zdań.

~
~

Prawa de Morgana

~

~

Prawo podwójnego przeczenia.

Prawa przemienności

Prawa łączności

Prawa rozdzielności

Prawa tautologii

Kwantyfikatorami nazywamy zwroty: “dla każdego x” i oznaczamy symbolem
(kwantyfikator ogólny),

“istnieje x, takie że” i oznaczamy symbolem
(kwantyfikator szczegółowy).

Definicje i twierdzenia

Wśród pojęć matematycznych wyróżniamy takie, których nie określamy - pojęcia pierwotne (np: punkt, liczba, zbiór) oraz takie, które należy określić czyli zdefiniować.

Definicja jest wyrażeniem opisującym znaczenie określonego terminu przy pomocy pojęć pierwotnych lub wcześniej definiowanych.

np: równoległobokiem nazywamy czworokąt, który ma dwie pary boków równoległych.

Dwie definicje tego samego pojęcia nazywamy równoważnymi.

Matematyka jest sformułowana w twierdzeniach. Mają one zwykle postać implikacji p
q.

Zdanie p jest założeniem twierdzenia, a zdanie q jego tezą.

Aksjomaty (pewniki) są twierdzeniami, które przyjmujemy bez dowodu. Wszystkie pozostałe twierdzenia wymagają dowodu.

W dowodzie wprost, wychodzimy od założeń twierdzenia, uważając je wszystkie za prawdziwe i wyciągając kolejne wnioski, dochodzimy do prawdziwości tezy.

Np.: twierdzenie: Niech a, b, c będą dowolnymi liczbami rzeczywistymi to:

a>b
a+c>b+c

dowód: a>b
a-b>0
a+c-b-c>0
a+c-(b+c)>0
a+c>b+c. C.n.d.

Dowód nie wprost polega na uznaniu założeń twierdzenia za prawdziwe i dołączeniu do nich hipotezy z.d.n. ¬p, która jest zaprzeczeniem tezy p twierdzenia.

Następnie, poprzez kolejne wnioski, otrzymujemy:

a] koniunkcję sprzeczności założeń i hipotezy

lub

b] fałszywe zdanie wyprowadzane z hipotezy z.d.n..

Założenia twierdzenia uznaliśmy za prawdziwe. Z z.d.n. wyprowadziliśmy zaprzeczenie tezy. Sprzeczność. Absolutna - wedle aksjomatów.

Lub wyprowadziliśmy jakie inne zdanie nieprawdziwe.

Ponieważ okres warunkowy z prawdy [domniemanej w z.d.n. ] wyprowadza tylko i wyłącznie prawdę, musi prawda do prawdy prowadzić, że nie może być inaczej! nie może bo tak zdecydował aksjomat--- to

to z.d.n. pociąga fałsz [a przecie pociąga!] jeno wtedy gdy z.d.n.. jest fałszywe.

Czyli teza p jest prawdziwa

wobec ¬¬ p = p ↔ (P ^c) ^c = P.

po prostu:

Dowód nie wprost to

wykazanie prawdziwości lewej strony równoważności

( p → q ) ↔ [ ( p ∧ ¬q) → 0]

poprzez wykazanie prawdziwości prawej

pamiętamy przecież, że: ( p → q ) ↔ ¬ ( p ∧ ¬q)

Np.: Twierdzenie: Liczba * jest liczbą niewymierną.dowód: Przypuśćmy, że liczba * jest liczbą wymierną, to znaczy, że *=p/q gdzie p i q są liczbami całkowitymi. Z tego wynika że, [p/q]² =2, czyli p²=2q², a zatem p p=2q q. Jeżeli liczby p i q rozłożymy na czynniki pierwsze, czynnik 2 występuje w iloczynie p p parzystą liczbę razy (taką samą liczbę razy w każdym czynniku p), lub nie występuje wcale, a w iloczynie 2 q q nieparzystą liczbę razy. Zatem obydwa iloczyny nie mogą być równe. Z tego wynika, że *nie jest liczbą wymierną. C.n.d.

Typy Zdanie w postaci

p ⇒ q zwiemy twierdzeniem prostym,

q ⇒ p zwiemy twierdzeniem odwrotnym,

¬p ⇒ ¬q zwiemy twierdzeniem przeciwnym, kontrapozycja

¬q ⇒ ¬p zwiemy twierdzeniem przeciwstawnym kontrapozycja

kontrapozycja = zaprzeczeń odwrócenie kolejności

Twierdzenie proste i twierdzenie przeciwstawne kontrapozycja są

jednocześnie prawdziwe, albo jednocześnie fałszywe.

p ⇒ q ≡ ¬q ⇒ ¬p

Twierdzenie odwrotne i twierdzenie przeciwne kontrapozycja są

jednocześnie prawdziwe, albo jednocześnie fałszywe.

Prawo transpozycji

q ⇒ p ≡ ¬ q ⇒ ¬ p .

Wniosek: zamiast dowodzić dane twierdzenie, można dowieść jego kontrapozycję. kontrapozycja = odwrócona kolejność zanegowanych

Prawo transpozycji

p ⇒ q ⇔ ¬ q ⇒ ¬ p ↔ P ⊆ Q ⇔ Q ^c ⊆ P ^c

Inną metodą dowodzenia jest zasada indukcji matematycznej, która zostanie omówiona w rozdziale X.

Dodatek:

Tw. p ⇒ q ≡ ¬q ⇒ ¬p

Dowód wprost:

p ⇒ q ≡ ¬ ( p ∧ ¬q) ≡ ¬ p ∨ ¬¬ q ≡ ¬(¬ q) ∨ ¬ p ≡ ¬q ⇒ ¬p

4

---