Klasyczny rachunek zdań



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

DOWODY ZAŁOŻENIOWE



Ex. 21. Zbudować dowód założeniowy poniższego twierdzenia
Ex Ay R(x, y)  Ay Ex R(x, y)
1. Ex Ay R(x, y) zał.

2. Ay R(a, y) OE 1

3. R(a, y) OA 2

4. Ex(x, y) DE 3

5. Ay Ex(x, y) DA 4

Ex 22. Zbudować dowód założeniowy poniższego twierdzenia

P(x)  Ex Q(x)  Ex [P(x)  Q(x)]


1. Ex P(x)  Ex Q(x) zał.

2. Ex P(x) OK. 1

3. Ex Q(x)

4. P(a) OE 2

5. Q(b) OE 3

6. P(a)  Q(b) DK 5 i 6

Urywa się dowód - niemożliwość zastosowania reguły DE
Ex. 23. Zbudować dowód założeniowy poniższego twierdzenia
Ay Ex R(x, y)  ExAy R(x, y)

1. Ay Ex R(x, y) zał.

2. Ex R(x, y) OA 1

3. R(ay,y) OE 2

4. Ay R(ay , y) DA 3

Urywa się dowód - niemożliwość zastosowania DE


Ex. 24

Udowodnij metodą założeniową, że zdanie Q=„Ex [ F(x)  G(x) ]  [Ex F(x)  Ex G(x)]” jest tautologią rachunku kwantyfikatorów.

1.Ex [ F(x)  G(x) ] zał.

2. F(a)  G(a) OE 1

3. F(a)

4. G(a) OK. 2



5. Ex F(x) DE 3 i 4

6. Ex G(x)

7. Ex F(x)  Ex G(x) DK 5 i 6
Ex. 25

Udowodnij metodą założeniową, że zdanie Q = „Ex[ F(x)  G(x) ]  [Ex F(x)  Ex G(x)]” jest tautologią rachunku kwantyfikatorów.


Ex[ F(x)  G(x)] zał.

Ex F(x)


F(a) G(a) OE 1

F(b) OE 2

?

Niech F(x) będzie x < 0 i a G(x) będzie x2 < 0 wtedy otrzymujemy:



Q*= „Ex[(x < 0) (x2 < 0)]  [Ex (x < 0) Ex (x2 < 0)]
Ex. 26 Udowodnij metodą założeniową, że zdanie Q = „AxAy[ R(x, y)  S(x, y)]  [ExEy R(x, y)  ExEy S(x, y )]” jest tezą rachunku kwantyfikatorów.
1. AxAy [R(x, y)  S(x, y)] zał.

2. ExEy R(x, y)

3. R(a, b)  S(a, b) OA 1

4. R(a, b) OE 2

5. S(a, b) RO 3 i 4

6. ExEy S(x, y) DE 5


Ex. 27 Udowodnij metodą założeniową, że zdanie Ax P(x)  Ax Q(x)  Ax [P(x)  Q(x)] jest tezą rachunku kwantyfikatorów.

Dowód założeniowy tzw. rozgałęziony (wiersze z podwójną numeracją)

1. Ax P(x)  Ax Q(x) zał.

1.1 Ax P(x) zał dod.

1.2. P (x) OA 1.1

1.3 P(x)  Q(x) DA 1.2

1.4 Ax [P(x)  Q(x)] DA 1.3

Ax P(x)  Ax [P(x)  Q(x)] 1.1  1.4

2.1 Ax Q(x) zał dod.

2.2 Q(x) OA 2.1

2.3 P(x)  Q(x)] DA 2.2

2.4 Ax [P(x)  Q(x)] DA 2.3

3. Ax Q(x) Ax [P(x)  Q(x)] 2.1  2.4

4. {Ax P(x)Ax [P(x) Q(x)]}  {Ax Q(x) Ax [P(x)  Q(x)]} . {Ax P(x)  Ax Q(x)} Ax [P(x)  Q(x)] Prawo dyl konst. pr.{(pr) .(qr)  (p  q)  r}

5. {Ax P(x)  Ax [P(x)  Q(x)]}  {Ax Q(x) Ax [P(x)  Q(x)]} . {Ax P(x)  Ax}

DK 1, 2, 3

6. Ax [P(x)  Q(x)] RO 4i 5




Ex. 27 Zapisz następujące wypowiedzi w języku kwantyfikatorów
Każdy matematyk jest muzykalny

Niektórzy matematycy są muzykalni.

Żaden matematyk nie jest muzykalny

Niektórzy matematycy nie są muzykalni

Tylko matematycy są muzykalni

Każdy matematyk jest uczniem pewnego matematyka

Pewien matematyk nie ma uczniów wśród matematyków.

Niech F= „być matematykiem”, G =”być muzykalnym”. D =zbiór ludzi a

x należy do D. R= ” być uczniem”
Ad. 1 Ax [F(x)  G(x)]

Ad. 2 Ex [F(x)  G(x)]

Ad. 3 Ax [F(x)  G(x)]

Ad. 4 Ex [F(x)  G(x)]

Ad. 5 Ax [G(x)  F(x)]

Ad. 6 Ax [F(x)  Ey (F(y)  R(x,y))]

Ad 7. Ex[F(x)  Ey (F(y)  R(y,x))]


Ex. 28 Zapisz następujące wypowiedzi w języku kwantyfikatorów

Istnieje ktoś kto ma przyjaciela

Każdy jest czyimś przyjacielem.

Każdy jest przyjacielem wszystkich

Nikt nie jest niczyim przyjacielem
Zaimki osobowe: „ktoś”, „nikt” , „wszyscy” są synonimami wyrażeń „ pewien człowiek”, „żaden człowiek” i „ wszyscy ludzie”. Niech P=” być człowiekiem”, a R=” być przyjacielem”. D = zbiór indywiduów a zmienne z, y należą do D.

Ad. 1 Ex[P(x) Ey (P(y)  R(x,y))]

Ad. 2 Ax [P(x)  Ey (P(y)  R(x,y))]

Ad 3. Ax[P(x)  Ay (P(y)  R(x,y))]



Ad 4. Ax[P(x) Ey (P(y)  R(x,y))]
Ex 29. Niech będą funkcjami zdaniowymi określonymi dla liczb naturalnych. Za ich pomocą , korzystając ze znanych operacji arytmetycznych, takich jak x+y, x * y, symboli dla liczb oraz symboli logicznych, zapisać następujące funkcje

x jest liczba parzystą

x nie jest liczba parzysta

x nie jest liczba pierwszą

Nie istnieje największa liczba naturalna

Nie istnieje największa liczba pierwsza

Każda liczba przy dzieleniu przez 2 daje resztę zero lub 1

Pomiędzy liczbami n i 2n istnieje co najmniej jedna liczba pierwsza (Tw. Czebyszewa)

Każda liczba nieparzysta większa od 3 rozkłada się na sumę dwu liczb pierwszych

( hipoteza Goldbacha)


Ad 1. Ey x=2* y

Ad 2. Ey x= 2 *y



Ad 3. EyEz [((y = x)  (y=1))  x=y*z]

Ad 4. Ex Ay (x y) co jest równoważne Ax Ey (x < y)

Ad 5. AxEt [AyAz x = y * z  y = 1 y = x]  [Ay A z ( t = y * z  y = 1 y = t)  x < t]



Ad 6. AxAyAz[(x =2*y +z  z < 2)  (z = 1  z = 0)]

Ad 7 An [ Ex(AyAz x = y * z  y = 1 y = x)  ]

Ad 8 Ax[(x>3  Ey (x=2* y) Ez(AwAt z = w * t  w = 1 w = z)  Ev(AwAt z = w * t  w = 1 w = v)  x=z+v] lub równoważnie



Ax(2*x+1>3) Ez Ev (AwAt ((z = w * t  w = 1 w = z)  (z = w * t  w = 1 w = v))  x=z+v]
ZBIORY - PODSTAWOWE POJĘCIA
Zbiorami i relacjami zajmuje się nauka zwana teorią mnogości. Jednakże pojęcie zbioru można wprowadzić także na gruncie rachunku kwantyfikatorów. Możemy mówić o dwóch koncepcjach zbioru a) logicznej G. Fregego oraz matematycznej - Cantora i innych. Pojęcie zbioru ujętego logicznie będzie się przedstawiało krótko mówiąc jako własność elementów, albo inaczej obiektów spełniających pewną funkcję zdaniową.
Niech „{x: P(x)}” lub „oznacza zbiór tych x, że P(x) . Symbol „{: }” oznacza operator abstrakcji, który tworzy nazwę zbioru z predykatu. Sens symbolu „” ustala tzw. prawo eliminacji: y {x: P(x)}  P(y). W myśl tego prawa przedmiot y jest elementem zbioru tych x, które maja własność P wtw. gdy przedmiot y ma własność P. Na oznaczenie zbiorów używamy najczęściej symboli A, B, C .... .Wyrażenie „x  A” czytamy „x jest elementem zbioru A” lub „x należy do zbioru A”. Zamiast wyrażenia „  x  A” piszemy „x A” „ x nie należy do A”.
1. Zbiór uniwersalny

V={ x: x = x}xVx = x nazywamy zbiorem pełnym (należą do niego wszystkie te przedmioty, które spełniają funkcje zdaniową x = x) . Ponieważ powyższą definicję można zapisać następująco: xVx = x a tezą jest „Ax (x = x)”, zatem tezą jest też

Ax (x = x)  AxV stwierdzającą, że każdy przedmiot należy do zbioru pełnego


2. Zbiór pusty

={x: x  x} nazywamy zbiorem pustym (należą do niego wszystkie te przedmioty, które spełniają funkcję zdaniową x  x. Ponieważ powyższą definicję można zapisać następująco: x: x  x a tezą jest „  Ex (x  x)”, zatem tezą jest też Ex (x  x)  Ex x stwierdzającą, że żaden przedmiot nie należy do zbioru pustego



Ex. 30. Niech zbiór pełny V będzie zbiorem liczb naturalnych. Przy użyciu funkcji zdaniowych

z= x*y, x/y i kwantyfikatorów zapisać funkcje zdaniowe jednej zmiennej wyznaczające zbiory

liczb parzystych - A

liczb nieparzystych - B

liczb pierwszych - C

zbiór jednoelementowy złożony z 3 - D


a) x  AEy (x=2* y)

b) x  BAy [Ez (y =2* z)  (x/y)]

c) x  C  AyAz [ x = y * z y =x  y =1]

d) x D  Ay[ x = y y =3]


Ex. 32. Elementami zbiorów mogą być również zbiory. Jeżeli A jest dowolnym zbiorem, to {A} symbolizuje zbiór jednostkowy, którego elementem jest zbiór A., co zapisujemy A{A}.

A{A}, tak samo jak a{a}. Ponadto porządek elementów w zbiorach nie odgrywa żadnej roli, zatem{a, b}={b, a}


Wśród podanych niżej zbiorów A,. B, C, D wskaż

  1. zbiór o najmniejszej liczbie elementów

  2. zbiór o największej liczbie elementów

  3. zbiory identyczne

  4. zbiory mające dokładnie jeden element wspólny

  5. zbiory nie mające żadnego elementu wspólnego

A={1, 2, 3,. 4, 5}

B={2, {1, 4}, {3, 5, 6}}


C={{1, 2, 3, 4, 5}}

D={3, {2}, {{5}}}

E={{3-1}, 3, {{3+2}}}


OPERACJE NA ZBIORACH I ICH GEOMETRYCZNE INTERPRETACJE


  1. Sumą A  B nazywamy taki zbiór złożony z tych elementów, które należą do zbioru A lub do B

x  (A  B)  x  A  x B

A B

2. Iloczynem ( przekrojem) A  B nazywamy taki zbiór złożony z tyc elementów, które należą do A i należą do B


x  (A  B)  x  A  x B

V


A B
a

3. Różnicą A – B nazywamy taki zbiór złożony z tych elemntów, które należą do A, a nie należą do B


x  (A – B)  x  A  x B

V
A B


  1. Dopełnieniem zbioru A nazywamy taki zbiór A’ złożony z tych wszystkich elemntów, które nie należą do zbioru A

x  A’ x A

a zatem A’=V-A


A
V



  1. Dwa zbiory A i B są równe wtw. , gdy każdy elemnt który należy do zbioru A należy takżę do B i na odwrót

x  A  x B


A B





  1. Między zbiorami A i B zachodzi relacja zawierania się ( inkluzji) A B wtw. gdy każdy elemnt który należy do zbioru A należy także do B

x  A  x B

V


B A




Ex. 33. Obliczyć A  B, A  B, A-B, B-A dla następujących zbiorów
A={a, b, c}, B={c, d}

A={{a, b}, c}, B={c, d}

A={{a, {a}}, a}, B={a, {a}}

A={a, {a}, {b}}, B={{a}, {b}}


TWIERDZENIA RACHUNKU ZBIORÓW
Opierając się na wprowadzonych definicjach (sumy, iloczynu, różnicy, dopełnienia , zawierania ) oraz na prawach rachunku zdań można udowodnić odpowiednie twierdzenia dotyczące zbiorów.

Aksjomat ekstensjonalności dla zbiorów

Ax(xA xB)A=B

Aksjomat ten stwierdza, że zbiory złożone z tych samych elementów są identyczne


DOWODY TWIERDZEŃ
Założeniowe


1. A=B  Ax (xA  xB)
1. A=B zał.

2. . xA xA taut. p  p

3. xA xB Ex I 1 i 2

4. Ax (xA  xB) DAk 3


Reguła ekstensjonalności:
Ex.I: V1= V2

P

P(V1// V2)


Reguła ExI : Jeżeli żadna zmienna wolna wyrażenia V1 nie jest związana w wyrażeniu P na miejscu zastąpienia; żadna zmienna wolna wyrażenia V2 nie staje się związana na miejscu zastąpienia w wyrażeniu stanowiącym wynik zastąpienia
2. A=BAB  BA
A=B zał.

A=B  Ax (xA  xB) Tw. Udow.

Ax (xA  xB) RO 1 i 2

Ax (xA xB)  Ax [(xA xB)  (xB xA)]

taut. (p q ) (pq) (qp)

5. Ax [(xA xB)  (xB xA)] RO 4 i 3

6. Ax (xA xB) Ax (xB xA) Prwo rozkła. Kw. Ogóln. na konjuncję

7. AB  BA Def. zaw i 6


3. ABAB=A
AB zał.

Ax (xA xB) Def zaw.i 1

Ax(xA  xB xA) taut. (pq) (p  q p)

Ax(xA  Bx A) Def Ilocz. Zbiorów i 3

A  B =A RO Aks. Ekstens. i 4
Ex 34. Podać dowody praw de Morgana dla zbiorów i podać ich interpretację graficzną
( A  B)’= ‘A’B

(AB)’= A’  B’



PRAWA ALGEBRY ZBIORÓW
Prawa algebry zbiorów są zbudowane ze zmiennych reprezentujących nazwy zbiorów, stałych: , , -, V, , , = oraz operatorów logicznych. Nie występuje w nich symbol 

1. AA prawo zwrotności zawierania się zbiorów

2. AB BC AC prawo przechodniości zawierania się zbiorów

3. A  B= B A prawa przemienności iloczynu

4. AB= BA prawa sumy zbiorów

5. AB = (A’B’)’ prawo zastępowania sumy zbiorów iloczynem

6. A  B = (A’B’)’ ’ prawo zastępowania iloczynu zbiorów sumą

7. A’’= A dopełnienie dopełnienia zbioru A jest równe zbiorowi A

8. AA’ =V suma zbioru A i jego dopełnienia jest równa zbiorowi uniwersalnemu

 A zbiór pusty jest zawarty w dowolnym zbiorze

10. AV każdy zbiór jest zawarty w zbiorze uniwersalnym

11. AB  CD  AC BD Prawo dodawania inkluzji stronami



Ex. 35. Operacja AB=(A-B)  (B-A) nazywa się różnicą symetryczną

podać interpretację graficzną

wykazać, że AA=

wykazać, że (AB) C = A(BC)

wykazać, że jeżeli A  B=, to AB= A  B


RELACJE
Zbiory jednoelementowe i dwuelementowe
Def 1.

Zbiór jednolementowy utworzony z przedmiotu x, to taki zbiór , którego jedynym elementem jest przedmiot x; oznaczamy go przez {x} i definiujemy:

y{x}y=x

Zbiór utworzony z elementów x, y, to taki zbiór którego jedynymi elementami są przedmioty x, y i tylko te; oznaczamy go przez {x, y} i definiujemy:

z{x,y}z = x  z=y
Z definicji tej wynika następująca teza:

{x,y}={y,x}


Def 2. Za pomocą pojęć rachunku zbiorów można zdefiniować pojęcie pary uporządkowanej o pierwszym elemencie x i drugim elemencie y, która będziemy oznaczać za pomocą symbolu x, y

x, y={{x}, {x,y}}

Na podstawie tej definicji można udowodnić twierdzenie:
x, y = z, u  x =z  y =u

x, y  z, u  x z  y u

x, y  y, z
Def. 3 Relacja dwuczłonowa R jest to zbiór par uporządkowanych; relacja n- członowa R jest zbiorem n- elementowych układów uporządkowanych. Na oznaczenie relacji wprowadzamy następujące symbole:

x, y R xRy

x1,..., xn R R(x1,..., xn)
Def. 4 Zbiór D(R) nazywa się dziedziną relacji R Dp(R) nazywa się przeciwdziedziną relacji

Zbiór C(R) nazywa się polem relacji R. Zbiory te określone są następująco:

a) x D(R) EyxRy

b) yDp(R) Ex xRy

c) C(R)=D(R)Dp(R)
Dla relacji n-członowej określa się pojęcie 1-ej, 2-ej,...n-ej dziedziny

C(R)=D1(R) ... Dn(R)


WYKRESY RELACJI
Iloczyn ( produkt) kartezjański dwóch zbiorów

Def. x, y  A  Bx A y B


Zbiór A  B nazywa się iloczynem kartezjańskim zbiorów A i B. Jest to zbiór par uporządkowanych, których pierwsze elementy należą do zbioru A, a drugie należą do B.
Relacja R o polu X

Zbiór R złożony z pewnych par uporządkowanych x, y, gdzie x i y należą do X nazywamy relacją dwuczłonową R o polu X , tzn. podzbiór produktu kartezjańskiego R X  X co zapisujemy x, y  R.


Ta definicja jest w istocie definicją geometryczną. Na ogół rozumie się przez nią związek a nie zbiór. Sam zbiór par nazywa się wtedy wykresem relacji R.
Ex. 36. Niech X={1, 2, 3, 4, 5, 6}. Produkt kartezjański Z= X  X składa się z 36 par. Rozpatrzmy podzbiór R produktu Z złożony z następujących par uporządkowanych:

1,1,1,2,1,3,1,4,1,5,1,6,

2,2,2,4,2,6,3,3,3,6

4,4,5,5,6,6

Jaka relacja zachodzi pomiędzy x i y?. Widać, że R jest relacja podzielności y przez x.

x, yRx/y
















































































































X 1 2 3 4 5 6
Wykres relacji podzielności R



Ex 37. Niech będzie relacja R w zbiorze A={1, 2, 3} określoną przez ..Narysuj wykres relacji R

3

0. 1 2

Wykres relacji R jest grafem skierowanym z pętlami



OPERACJE ALGEBRAICZNE NA RELACJACH

Niech R i S będą dwoma relacjami w zbiorze X.

1. Sumą relacji R i S nazywa się relację T taką, która zachodzi między elementami x i y wtedy i tylko wtedy, gdy między nimi zachodzi relacja R lub S co zapisujemy:

x R  Sy  xRy  xSy



  1. Różnicą relacji R i S nazywamy relację Q taką, że która zachodzi między elementami x i y wtedy i tylko wtedy, gdy między nimi zachodzi relacja R, a nie zachodzi relacja S, co zapisujemy

x R-S y xRy   xSy



  1. Iloczynem relacji R i S nazywamy relację Q taką, że która zachodzi między elementami x iy wtedy i tylko wtedy, gdy zachodzi między nimi zarówno relacja R jak i S, co zapisujemy:

xR  Sy xRy  xSy
4. Iloczynem względnym relacji R i S nazywamy relację Q taką, że , która zachodzi między elemntami x i y wtedy i tylko wtedy, gdy istnieje takie z, że między x i z zachodzi relacja R, a między z i y zachodzi relacja S, co zapisujemy:

x R | S y E z (xRz  zSy)


5. Negacją relacji (dopełnieniem) R nazywamy relację R’ taką, która zachodzi między elementami x i y wtedy i tylko wtedy, gdy nie zachodzi między nimi relacja R, co zapisujemy:

xR’y  xRy


6. Konwersem relacji 6. R nazywamy relację R-1 taką, która zachodzi między elementami x i y wtedy i tylko wtedy, gdy zachodzi między y a x relacja R, co zapisujemy

x R-1 y  yRx


Ex 37. Udowodnić, że dla każdych x, y X
xR  Sy  (xRy  xSy)

xR  Sy  (xRy  xSy)

xR’y  (xRy)
Dowód 1.

xR  Sy x, y  R  Sx, y R  x, y S xRy  xSy




WŁASNOŚCI FORMALNE RELACJI
1. Relacje zwrotne w zbiorze X oznaczamy symbolem refl(X) i definiujemy

R  refl(X)  AxX (xRx)


2. Relacje symetryczne w zbiorze X oznaczamy symbolem sym(X) i definiujemy

R  sym(X)  AxyX (xRy yRx)


3. Relacje asymetryczne w zbiorze X oznaczamy symbolem as(X) i definiujemy

R  as(X)  AxyX (xRy yRx)


4. Relacje antysymetryczne w zbiorze X oznaczamy symbolem ants(X) i definiujemy

R  ants(X)  AxyX (xRy  yRx x = y)

5. Relacje przechodnie w zbiorze X oznaczamy symbolem trans(X) i definiujemy

R  trans(X)  Axyz X (xRy yRzxRz) AxyzX (xRy  yRz  xRz)


6.Relacje spójne w zbiorze X oznaczamy symbolem con(X) i definiujemy

R  con(X)  Axy X (xRy  yRx)





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


©operacji.org 2019
wyślij wiadomość

    Strona główna