Klasyczny rachunek zdań



Pobieranie 1,67 Mb.
Strona3/16
Data25.03.2018
Rozmiar1,67 Mb.
1   2   3   4   5   6   7   8   9   ...   16

DOWÓD ZAŁOŻENIOWY


WPROST

1. p  q  r

2. r  s zał.

3. s


4. (r  s)  (s r ) prawo transpozycji

5. s r RO 4 i 2

6. r RO 5 i 3

7. (p  q  r) [ r ( p  q )] prawo transpozycji

8. r ( p  q ) RO 7 i 1

9. ( p  q ) RO 8 i 6

10. ( p  q ) ( p  q) prawo de Morgana

11. ( p  q )  ( p  q) OE 10

12.  p  q RO 11 i 9

13.  q OK. 12


NIE WPROST

1. p  q  r

2. r  s zał.

3. s


4 q zdnwp.

5. p  q DA 4

6. r RO 1 i 5

7. s RO 2 i 7

sprzeczność wierszy 7 i 3
EX 16. Wiemy, że jeśli program komputerowy działa poprawnie, to zaczyna i zakończy swoje działanie. Wiemy też, że nasz program rozpoczął swoje działanie i nie działał poprawnie. Wnioskujemy stąd, że program nie zakończył działania.

Niech


p = „ program rozpoczął działanie”

q = „program zakończył działanie”

r = „ program nie działa poprawnie”

P1= „r  p  q”

P2 =” p  r

W= „q „
DOWÓD ZAŁOŻENIOWY (WPROST)

1 „r  p  q

2. p  r zał..

3. p  q  q prawo opuszczania koniunkcji

4. (r  p  q)  (p  q  q)  (r  q) prawo syl. warunkowego

5. (r  p  q)  (p  q  q) DK 1 i 3

6. r  q RO 4 i 5

7. r OK. 2

8. q ? ? ? 6 i 7

Wniosek:

a) źle prowadzony dowód

b) brak dowodu

Sprawdźmy, metodą matrycową, czy zdanie Q=„(r  p  q)  ( p  r)  q” jest tautologią.

1 1 0

Q=”(r  p  q)  ( p  r)  q”


1 1 1 1 1 1

Brak sprzeczności w wartościowaniu, a zatem zdanie Q nie jest tautologią. W związku z tym zdanie q = „program nie zakończył działania” nie posiada dowodu z założeń

P1= „r  p  q” i P2 =” p  r”. Oznacza to więc, że program może zacząć działanie i zakończyć działanie i nie działać poprawnie z jakiegoś innego powodu.


Ex 17.

Na podstawie prawa (p  q) [ (q  r)  (p  r)], reguł podstawiania i odrywania oraz następujących twierdzeń arytmetyki

Tw. 1(x * y >0)  {[(x > 0)  (y > 0)]  [( x < 0)  (y < 0)]}

Tw.2{[(x > 0)  (y > 0)]  [( x < 0)  (y < 0)]}  ( x + y = x +y )

udowodnić twierdzenie (x * y >0 )  (x + y = x + y)
1.( p  q) [ (q  r)  (p  r)]

2. p  q Tw1 RP p / (x * y >0) ;

3. q  r. Tw2 q / {[(x > 0)  (y > 0)]  [( x < 0)  (y<0)]}

r / x + y  = x  + y 

4. (q  r)  (p  r) RO 1 i 2

5. p  r RO 3 i 4

5’. (x * y >0 )  (x + y = x + y)
Ex 18. Udowodnij twierdzenie:

(x + y >0)  {(x * y >0)  [(x > 0)  (y > 0)]}


Założenia:

(x + y >0)  [( x < 0)  (y < 0)]

(x * y >0)  [(x > 0)  (y > 0)]  [( x < 0)  (y < 0)]
Niech

p =” x + y >0”

q =”( x < 0)  (y < 0)”

r = „x * y >0”

s = „(x > 0)  (y > 0)”

TEZA: p(r  s)


DOWÓD:

p  q


r  q  s zał.

(r  q  s)  [s (r  q)] prawo rach. zdań

s (r  q) RO 3 i 2

q  (r  s) RP 4 s/ q ; q/ s

(p  q)  {[( q (r  s )]  [p (r  s)]} syll. hipoteczny

[( q (r  s )]  [p (r  s)] RO 6 i 2

p (r  s) RO 7 i 5

8’.(x + y >0)  {(x * y >0)  [(x > 0)  (y > 0)]}



RACHUNEK KWANTYFIKATORÓW (I - RZĘDU)
Rachunek zdań nie stanowi całego języka stosowanego w rozumowaniach matematycznych. Dopiero język rachunku zdań i język rachunku kwantyfikatorów pozwala na wyrażanie myśli dowolnych teorii matematycznych i sprawdzanie ich sprawdzanie ich prawdziwości za pomocą formalnego postępowania dowodowego.

Język rachunku kwantyfikatorów I rzędu


stałe nazwowe: a, b, c, ...

zmienne nazwowe : x, y, z,...

predykaty: F,. G, ..., S,..

operatory logiczne :, , , , 

kwantyfikatory: Ex, Ax

znaki pomocnicze: ( ), [ ], { },...


Ad 1. Stałe nazwowe pełnią taką sama rolę w omawianym języku jak nazwy jednostkowe w języku naturalnym, tzn. oznaczają one indywidua. W matematyce stałymi są np. nazwy liczb

Np. a = 5; b = żona Jana Kowalskiego


Ad. 2 zmienne nazwowe są zmiennymi, za które można podstawiać nazwy przedmiotów, ale ze ściśle określonego zbioru D zwanego dziedziną dyskursu. Dzięki zmiennym w odróżnieniu od języka naturalnego można budować tzw. funkcje zdaniowe, które nie są zdaniami oznajmującymi, a zatem nie są też zdaniami w sensie logicznym. Dopiero wstawiając za zmienne określone nazwy otrzymujemy z nich zdania w sensie logicznym: np.

  1. x jest większe od 10

  2. x jest mniejsze od y

  3. x jest podzielne przez 2

  4. x jest żoną y

Funkcjami zdaniowymi nie są takie wyrażenia, jak: x + y, czy x2 - z, gdyż po podstawieniu nie sa zdaniami lecz nazwami.
Ad 3. Predykaty oznaczają własności albo relacje. Np. F= „być liczba naturalną”, R=” jest większe niż” itp. Zamiast pisać :Maria jest żoną Andrzeja - można zapisać R(a, b), zamiast pisać : x jest liczba naturalną, można napisać N(x). Argumentami predykatu są stałe nazwowe lub zmienne nazwowe. Predykaty występują więc ze swoimi argumentami np. P(x), Q(x, y), czy S(x, y, z). Predykaty można dzielić w zależności od ilości jego argumentów na jedno, dwu, trzy i więcej argumentowe. Np. F= „być liczba naturalną”, R=” jest większe niż” itp. Zamiast pisać: Maria jest żoną Andrzeja - można zapisać R(a, b), zamiast pisać: x jest liczba naturalną, można napisać N(x). W matematyce stałymi predykatowymi są np. symbole relacji: >, <, >=, <=, identyczności: =, czy różności: .
Ad 4. Operatory logiczne pełnia analogiczna role jak w rachunku zdań, tzn. łączą zdania z predykatami np. [ (1= 0)  (2 3 )]  [ (2 > 7)  (2 + 5 = 7)] a także funkcje zdaniowe. np ( jeśli P(x, y) oznacza x > y, a R(x, y) oznacza x  y a S( x, y) oznacza x < y, to wypowiedź: ( x >y )  (x  y)  (x < y) można zapisać : P(x, y)  R(x, y)  S(x, y)
Ad 5. Zwroty takie, jak: „dla każdego x” oraz „dla pewnego x”, „ dla niektórych x” lub „ istnieje takie x, że” odgrywają w języku matematyki zasadniczą rolę i łącznie z operatorami logicznymi, stałymi i zmiennymi pozwalają już na wypowiadanie każdej myśli matematycznej. Są one nazywane kwantyfikatorami. Pierwsze z tych wyrażeń nazywamy kwantyfikatorem ogólnym lub dużym, natomiast pozostałe nazywamy szczegółowym lub egzystencjalnej albo małym. Kwantyfikator mały symbolizowany jest przez Ex, duży Ax, duży. Często alternatywnie używa się innych symboli

Kwantyfikatory wiążą zmienne. Wyrażenia znajdujące się w nawiasie występującym bezpośrednio po kwantyfikatorze nazywamy zasięgiem. Np. w wyrażeniu Ay [x + x = x + y], zasięgiem kwantyfikatora jest wyrażenie: x + x = x + y, natomiast w wyrażeniu: Ax Ay (x >y)  (x  y) zasięgiem kwantyfikatora Ay jest wyrażenie x >y a zasięgiem kwantyfikatora Ax jest wyrażenie Ay (x >y). Zamiast pisać Ax Ay piszemy często Axy. Mówimy, że zmienna występująca w wyrażeniu przy symbolu kwantyfikatora jest przez ten kwantyfikator związana, w przeciwnym przypadku jest zmienną wolna.


Ex 19. Wskazać zakresy kwantyfikatora w następujących zdaniach predykatywne. Wyróżnić zmienne wolne i związane. Kreski nad zmiennymi wskazują, że zmienna w danym wystąpieniu jest zmienną związaną

  1. Ax[Ey [((x + y)2 < z)  ( u + x < v)]  ( y +x = u)]




  1. Ay[Ex [((x + y)2 < z)  ( u + x < v)]  ( z +x = u)]

Zasięgiem kwantyfikatora Ax jest wyrażenie Ey [((x + y)2 < z)  ( u + x < v)]  ( y +x = u)], zaś zasięgiem kwantyfikatora Ey jest wyrażenie [((x + y)2 < z)  ( u + x < v)]. Zmienne związane są u góry podkreślone.

Zasięgiem kwantyfikatora ogólnego A jest wyrażenie Ex [((x + y)2 < z)  ( u + x < v)] 

 ( z +x = u)], zaś zasięgiem kwantyfikatora szczegółowego E jest wyrażenie [((x + y)2 < z) 

 ( z + x < v)].
Jeżeli wszystkie zmienne występujące w funkcji zdaniowej zostaną w każdym swym wystąpieniu związane kwantyfikatorami, to funkcja staje się zdaniem. Np. funkcja zdaniowa (x + y = y + x) staje się zdaniem Ax Ay (x + y = y + x), gdyż zarówno zmienna x i y w każdym swym wystąpieniu zostały związane kwantyfikatorami.
Ex 20. Które z poniższych wyrażeń są zdaniami, a które tylko funkcjami zdaniowymi?.
P(x, y, z)

Ax P(x, y, z)

E x Ax P(x, y, z)

Ax Ey Az P (x, y, z)


Ponieważ tylko w przypadku d) wszystkie zmienne zostały związane, zatem tylko w tym przypadku wyrażenie jest zdaniem.
PRAWA RACHUNKU KWANTYFIKATORÓW
W rachunku zdań rozpatrywane były takie zdania złożone, które przy dowolnym podstawieniu wartości logicznych za zdania składowe przyjmowały wartość 1 , czyli prawdę. Takie wypowiedzi są nazywane tautologiami rachunku zdań. Przez analogię z rachunkiem zdań wypowiedzi ( formuły) rachunku kwantyfikatorów, które są prawdziwe w każdej dziedzinie przy dowolnej interpretacji predykatów, które w nim występują, tzn. przy dowolnym rozumieniu symboli F, G, P, R, Q itd. jako wyrażeń odnoszących się do pewnych własności lub relacji z danej dziedziny.
I Prawa rozdzielności kwantyfikatorów

Ex [P (x) Q(x)] Ex P (x) Ex Q(x)

Ax [P (x) Q(x)] Ax P (x)  Ax Q(x)
II Prawa de Morgana dla kwantyfikatorów

1.Ex P(x) Ax P(x)

2.Ax P(x)  Ex P(x)
III. Prawa zastępowania kwantyfikatorów

Ax P(x)  Ex P(x)

Ex P(x)  Ax P(x)
IV. Prawa przestawiania kwantyfikatorów

Ax Ay R(x, y) Ay Ax R(x, y)

Ex Ey R(x, y)  Ey Ex R(x, y)

ExAy R(x, y)  Ay Ex R(x, y)


V. Inne prawa

Ax P(x)  P(a) schemat podstawiania

P(a)  E(x) P(x) prawo abstrahowania od konkretności


METODA ZAŁOŻENIOWA DOWODZENIA TEZ RACHUNKU KWANTYFIKATORÓW

Rachunek kwantyfikatorów otrzymujemy dołączając do reguł pierwotnych założeniowego systemu rachunku zdań - w odpowiednio rozszerzonej postaci i wzbogacamy je o reguły pierwotne dla kwantyfikatorów. To rozszerzenie polega na tym, że termin zdanie rozumiemy obecnie jako termin oznaczający dowolną funkcję zdaniową lub zdanie rachunku kwantyfikatorów.


Reguły pierwotne dla kwantyfikatorów:
Ax P(x)

OA: reguła opuszczania kwantyfikatora ogólnego

P(x)
Np. z założenia Ax (x = x) wyprowadzamy wyrażenie x = x

P(x)

Ax P(x) DA: reguła dołączania kwantyfikatora ogólnego ( zmienna x nie może być zmienną wolną w założeniach dowodu)
Np. z założenia x > 2 wyprowadzamy wyrażenie x >2  x=2, ale nie można wyprowadzić z niego wyrażenia Ax (x > 2  x = 2), gdyż zmienna x jest wolna w założeniu .

Ex P(x)

P(a) OE1: reguła opuszczania kwantyfikatora szczegółowego ( stosując tę regułę

kilkakrotnie wprowadzamy nową stałą różną od stałych systemu i od uprzednio

wprowadzonych w tym dowodzie za pomocą tej reguły)

Ex R( x, y)


R(ay, y) OE2: ( stała musi być zrelatywizowana do zmiennej wolnej y będącej w zasięgu

kwantyfikatora)
Np. mamy dwa założenia 1) Ex (x =2) i 2) Ex (x = 4). Z 1) można wyprowadzić zdanie 3) a =2 , lecz z 2) nie można już wyprowadzić zdania 4) a = 4
Np. z założenia 1) Ex ( x > y) ( dla dowolnej liczby y istnieje większa od niej liczba) nie można wyprowadzić wyrażenia 2) a > y ( pewna liczba jest większa od dowolnej liczby y) ale można wyprowadzić 3) ay >y ( od dowolnej liczby x jest większa pewna liczba ay)

P ( a) P(x) P(y)

Ex P(x) ; Ex P(x) ; Ex P(x) DE: (dołączania kwantyfikatora szczegółowego)
Np. jeżeli mamy założenie 1) a= 5, to można wyprowadzić za pomocą tej reguły zdanie

2) Ex (x = 5) ( stąd, że dowolny lub pewien określony przedmiot ma własność P wynika, żde istnieje przedmiot posiadający tę własność )





1   2   3   4   5   6   7   8   9   ...   16


©operacji.org 2019
wyślij wiadomość

    Strona główna