Logika formalna – nauka badająca poprawność rozwiązań


RACHUNEK KWANTYFIKATORÓW (funkcyjnych)



Pobieranie 0,96 Mb.
Strona9/9
Data30.05.2018
Rozmiar0,96 Mb.
1   2   3   4   5   6   7   8   9

RACHUNEK KWANTYFIKATORÓW (funkcyjnych)
Jeśli (x), xX, gdzie xø jest funkcją zdaniową, natomiast dla każdego xX jest (x) piszemy Λ (x), a zamiast istnieje xX ,to że (x) piszemy V (x). Symbol Λ( V ) nazywamy odpowiednio kwantyfikatorem ogólnym (egzystencjalnym) ( - ogólny,  - egzyst.) wiążącym zmienną x o zakresie ograniczonym do X.

Jeśli zbiór X jest ustalony, to często piszemy Λ (x) (V (x)).



Definicja

  1. Zasięgiem kwantyfikatora nazywamy wyrażenie ujęte w nawias, bezpośrednio występujące po kwantyfikatorze.

  2. Zmienna x występująca w danym miejscu wyrażenia jest zmienną wolną, jeśli nie występuje w zasięgu żadnego kwantyfikatora o wskaźniku x.

  3. Zmienna x jest związana przez kwantyfikator o wskaźniku x, jeśli występuje w jego zasięgu i w tym zasięgu jest zmienną wolną.

Przykład:

V (x>3)(x>1) Λ (x>0V(x>1))

↓ ↓ ↓ ↓

zm. zm. zm. zm.

związana wolna związana związana


Uwaga!

Kwantyfikatory przekształcają funkcję zdaniową jednej zmiennej w zdanie.

(x) f. zdaniowa→Λ (x) zdanie

→ V (x) zdanie


Zdanie Λ (x) jest prawdziwe ↔ każdy element aX spełnia (x).

Zdanie V (x) jest prawdziwe  istnieje element aX spełniający (x).



Uwaga!

  1. Zdanie Λ(x) jest prawdziwe ↔ {xX: (x)} = X

  2. Zdanie V(x) jest prawdziwe ↔{xX: (x)}  ø





Wniosek:

  1. Zdanie Λ(x) jest fałszywe ↔ {xX: (x)}  X

  2. Zdanie V(x) fałszywe ↔ {xX: (x)} =ø



KWANTYFIKATORY O ZAKRESIE OGRANICZONYM PRZEZ FUNKCJĘ ZDANIOWĄ
Niech (x), xX; (x), xX będą funkcjami zdaniowymi i Xø.

Wtedy V(x) oznacza dla każdego xX spełniającego (x) jest spełniona funkcja zdaniowa (x) zaś V(x) oznacza istnieje xX spełn.(x) i spełn. (x).



Twierdzenie

  1. Λ(x)  Λ((x)(x))

  2. V(x)  V((x)  (x))

Wyrażenia Λ(x) i V(x) można więc traktować jako skróty wyrażeń Λ((x)(x) i V((x)  (x)).
Dowód:

  1. Zdanie Λ(x) jest prawdziwe ↔ każdy element aX, który spełnia (x) spełnia także (x) ↔ {xX: (x)} < {xX:(x)}↔{xX:(x)}’{xX:(x)}↔ ↔{xX: ~ (x)}{xX:(x)}=X ↔ {xX~(x)(x)}=X ↔ {xX:(x)(x)}=X ↔ zdanie Λ((x)(x)) jest prawdziwe.

  2. Zdanie V(x) jest prawdziwe ↔ istnieje aX spełniające (x) i spełniające(x) ↔ istnieje aX spełn. (x) (x) ↔ {xX: (x) (x)}ø ↔ zdanie V((x)(x)) jest prawdziwe.

Schemat bez zmiennych wolnych jest zdaniem.

Element  X2 …Xn spełnia funkcję zdaniową V(x1,...,xn )↔ ↔zdanie Λ(x1, a2,...,an) jest prawdziwe ↔ dla każdego a1X1, zdanie (a1, a2,...,an) jest prawdziwe.

Element X2x…x Xn spełnia funkcję zdaniową V(x1,...,xn)↔zdanie V(x1,a2,...,an) jest prawdziwe ↔ istnieje a1X1 takie, że zdanie (x1,a2,...,an) jest prawdziwe.

Funkcja zdaniowa Λ(x1,...,xn)(V(x1,...,xn)) jest prawdziwa w X2 ...Xn jest każdy element X2...Xn spełnia tą funkcję zdaniową.
PRAWA RACHUNKU FUNKCYJNEGO
,,...- zmienne predykatywne (podstawiamy za nie funkcje zdaniowe).

Wyrażenie (formuła, schemat) zbudowane ze zmiennych predykatywnych, spójników zdaniowych, kwantyfikatorów i nawiasów nazywamy prawem rachunku funkcyjnego jeśli przedstawia funkcję zdaniową prawdziwą (zdanie prawdziwe) bez względu na to, jakie funkcje zdaniowe podstawiamy za zmienne predykatywne.



Przykład:

1) Λ(x)(y), yX → funkcja zdaniowa zmiennej y.


(y)

Musimy udowodnić, że dla dowolnej funkcji zdaniowej  funkcja zdaniowa (x) jest prawdziwa w X czyli, że każdy element z X spełnia (x).

Niech aX. Załóżmy, że a nie spełnia (x). Wtedy zdanie Λ(x)(a) jest fałszywe. Stąd zdanie Λ(x) jest prawdziwe i zdanie (a) jest fałszywe. Zatem dla każdego bX zdanie (b) jest prawdziwe, co przeczy temu, że (a) jest fałszywe. A więc każdy element aX spełniający (y) jest prawdziwy w X. Stąd Λ(x)(y) jest prawem rachunku funkcyjnego.

2) Λ(x)V(x) – zdanie

Załóżmy, że zdanie Λ(x)V(x) jest fałszywe. Wtedy Λ(x) jest prawdziwe i V(x) jest fałszywe. Stąd {xX: (x)} = X oraz {xX: (x) = ø. Zatem X = ø co przeczy generalnie założeniu, że xø.


  1. (y)V(x), yX

Niech aX. Gdyby zdanie (y)V(x) było fałszywe to zdanie (a) jest prawdziwe i zdanie V(x) byłoby fałszywe. Stąd {xX: (x)} = ø co przeczy temu, że a spełnia (x).

4) prawa de Morgana w rachunku funkcyjnym



    1. ~ V(x)Λ ~ (x)

    2. ~ Λ(x)V ~ (x)

Dowód:

    1. zdanie ~ V(x) jest prawdziwe ↔ zdanie V(x) jest fałszywe ↔

↔ {xX: (x)} = ø ↔ {xX: (x)}’ = X ↔{xX: ~ (x)} = X ↔

↔ zdanie Λ ~ (x) jest prawdziwe.



    1. zdanie ~ Λ(x) jest prawdziwe ↔ zdanie Λ(x) jest fałszywe ↔

↔ {xX: (x)}  X ↔ {xX: (x)}’ ø↔{xX: ~ (x)} ø ↔

↔ zdanie V ~ (x) jest prawdziwe.



Wniosek

  1. ~ V(x)  Λ ~ (x)

  2. ~ Λ(x)  V ~ (x)

  3. ~ Λ ~ (x)  V(x) (Δ)

  4. V ~ (x)  Λ(x)


Uwaga!

(Δ) wykorzystuje się w dowodach apagogicznych tzw. twierdzeń egzystencjalnych. Aby udowodnić V(x) zakładamy, że zdanie Λ ~(x) jest prawdziwe i staramy się wydedukować sprzeczność. Wtedy wnioskujemy, że prawdziwe jest zdanie ~ Λ ~ (x) czyli prawdziwe jest zdanie V(x). Dowody tego typu zalicza się do tzw. dowodów nieefektywnych.



Uwaga!

Powyższe prawa rachunku funkcyjnego można uogólnić na przypadek funkcji n- zmiennych.


PRAWA WŁĄCZANIA I WYŁĄCZANIA KWANTYFIKATORÓW
Niech  będzie zdaniem lub funkcją zdaniową, w której nie istnieje zmienna wolna X. Następne wyrażenia są prawami rachunku kwantyfikatorów:

  1. Λ((x) )(Λ(x)  )

  2. V((x)  )(V(x)  )

  3. Λ((x)  )(Λ(x)  )

  4. V((x)  )(V(x)  )

  5. Λ((x))(V(x))

  6. Λ((x))(Λ(x))

  7. V((x))(V(x))

Dowód:

  1. a)  zdanie

 prawda→ obie strony równania są prawdziwe

 fałsz. → zdanie Λ((x)  ) jest prawdziwe↔dla każdego elementu aX, zdanie (a)   jest prawdziwe↔dla każdego elementu aX zdanie (a) jest prawdziwe↔ zdanie Λ(x) jest prawdziwe↔zdanie Λ(x)   jest prawdziwe.



b)  funkcje zdaniowe (y), yY

Element bY spełniający funkcję zdaniową Λ((x)  (y))↔zdanie Λ((x)  (b)) jest prawdziwe↔dla każdego aX zdanie (a)  (b) jest prawdziwe↔dla każdego aX zdanie (a) jest prawdziwe lub zdanie (b) jest prawdziwe↔zdanie Λ(x) jest prawdziwe lub (b) jest prawdziwe↔element bY spełnia funkcję zdaniową Λ(x)  (y).



a)  zdanie

Zdanie Λ((x)  ) jest prawdziwe↔dla każdego elementu aX zdanie (a)   jest prawdziwe↔dla każdego elementu aX zdanie (a) jest prawdziwe i zdanie  jest prawdziwe↔zdanie Λ(x) jest prawdziwe i zdanie  jest prawdziwe↔zdanie Λ(x)   jest prawdziwe.



b)  funkcja zdaniowa (y), yY

Element bY spełnia funkcję zdaniową Λ((x)  (y))↔zdanie dla każdego xX ((x)  (b)) jest prawdziwe↔dla każdego elementu aX zdanie (a)  (b) jest prawdziwe↔dla każdego elementu aX zdanie (a) jest prawdziwe i zdanie (b) jest prawdziwe↔zdanie Λ(x) jest prawdziwe i zdanie (b) jest prawdziwe↔zdanie Λ(x)  (b) jest prawdziwe↔element bX spełnia funkcję zdaniową Λ(x)  (y).



Wniosek:

  1. Λ((x)  )  Λ(x)  

  2. Λ((x)  )  Λ(x)  

Dowód:

2) V((x)  )  ~ Λ ~ (f(x)  )  ~(Λ( ~ (x)  ~ ))  ~ (Λ ~ (x)  ~ ) 

 ~ Λ ~ (x)    V(x)  
PRAWA ROZDZIELNOŚCI KWANTYFIKATORÓW


  1. Λ((x)  (x))(Λ(x)  (x))

Dowód 1

Zdanie Λ((x)  (x)) jest prawdziwe↔{xX: (x)  (x)} = X↔ ↔{xX: (x)}  {xX: (x)} = X↔zdanie Λ(x) jest prawdziwe i zdanie Λ (x) jest prawdziwe↔zdanie Λ(x)  Λ(x) jest prawdziwe.



Prawo rozdzielności kwantyfikatora ogólnego względem koniunkcji

2. (Λ(x)  Λ (x))Λ((x)  (x))



Przykład:

(x)  (x<0), xR

(x)  (x>0), xR

zdanie Λ(x<0  x>0) jest prawdziwe

Załóżmy, że zdanie Λ(x<0)  Λ(>0) jest fałszywe. Stąd implikacja Λ(x<0  x>0)

(Λ(x>0)) jest fałszywa. Zatem schemat Λ((x)  (x)(Λ(x)  V (x)) nie jest prawem rachunku funkcyjnego

3. V((x)  (x))(V(x)  V (x))

Prawo rozdzielności kwantyfikatora egzystencjalnego względem alternatywy

4. V((x)  (x))(V(x)  V (x))



PRAWAMI RACHUNKU FUNKCYJNEGO SĄ TAKŻE NASTĘPUJĄCE SCHEMATY:

  1. Λ((x)(x))(Λ (x) Λ (x))

  2. Λ((x)(x))(V(x) V (x))

Dowód 1

Λ((x)(x)) prawdziwe i Λ(x) Λ (x) jest fałszywe

↨ ↨

{xX: (x)(x)} = X Λ(x) prawda i Λ (x) fałsz



↨ ↨

{xX: ~ (x)  (x)} = X {xX: (x)} = X i {xX: (x)}  X

↨ ↨

{xX: ~ (x)}  {xX: (x)}=X {xX: (x)}’ = ø i {xX: (x)}X



↨ ↨

{xX: (x)}’  {xX: (x)}=X {xX: (x)}’=0 i {xX: (x)} X

sprzeczność


Uwaga!

Prawa rozdzielności i także te dwa ostatnie prawa można uogólnić na przypadek funkcji zdaniowych wielu zmiennych mogą tam także występować kwantyfikatory o zakresie ograniczonym przez funkcje zdaniowe.




PRAWA PRZESTAWIANIA KWANTYFIKATORÓW


  1. Λ Λ (x,y)Λ Λ (x,y)

  2. V V (x,y)V V (x,y)

  3. V Λ (x,y)Λ V (x,y)

Dowód 1:

Zdanie Λ Λ (x,y) jest prawdziwe ↔dla każdego aX zdanie Λ(a,y) jest prawdziwe

↔dla każdego aX i dla każdego bY zdanie (a,b) jest prawdziwe↔dla każdego bY i dla każdego aX zdanie (a,b) jest prawdziwe↔dla każdego bY zdanie

Λ(x,b) jest prawdziwe↔zdanie Λ Λ(x,y) jest prawdziwe.


Dowód 3:

Zdanie V Λ(x,y) jest prawdziwe↔istnieje takie aX takie, że zdanie Λ(a,y) jest prawdziwe↔istnieje aX takie, że dla każdego bY zdanie (a,b) jest prawdziwe↔dla każdego elementu bY istnieje aX (a = a) takie, że zdanie (a,b) jest prawdziwe↔dla każdego bY zdanie V(x,b) jest prawdziwe↔zdanie Λ V(x,y) jest prawdziwe.


SUMY I ILOCZYNY UOGÓLNIONE ZBIORÓW
Definicja

Niech A będzie rodziną zbiorów sumą rodziny zbiorów.



A nazywamy zbiorem elementów, z których każdy należy do przynajmniej jednego zbioru z rodziny A. (ozn. A)

xAV(xA)(A ={x: V(xA)})

Przekrojem (iloczynem) niepustej rodziny zbioru A nazywamy zbiór elementów, które należą do wszystkich elementów rodziny A. (ozn. A)

xAΛ(xA)(A ={x: Λ(xA)}


Uwagi !

  1. Istnienie przekroju A niepustej rodziny A wynika z aksjomatu wyróżnienia

(A ø →istnieje AA→A = {xA: Λ(xX)}

2. Przyjęte wcześniej aksjomaty zapewniają, że suma dowolnej skończonej ilości zbiorów jest zbiorem, nie zapewniają one, że suma uogólnionej dowolnej rodziny jest zbiorem. Z tego powodu w teorii mnogości przyjmuje się mocniejszą (uogólnioną) wersję aksjomatu sumy.




UOGÓLNIONY AKSJOMAT SUMY

Dla dowolnej rodziny zbioru A istnieje zbiór do którego należą elementy każdego ze zbiorów tej rodziny i tylko one.

Λ V Λ (xS V(xA))
Na mocy aksjomatu ekstensjonalności istnieje dokładnie jeden zbiór S o powyższej własności.

Zbiór ten oznaczamy symbolem A




Uwagi !

1. ø = ø



  1. ab = {a,b} (tzn. aksjomat sumy wynika z aksjomatu pary i uogólnionego aksjomatu sumy).

  2. Dopuszczenie istnienia przekroju pustej rodziny zbiorów prowadzi do sprzeczności

x ø Λ(xA) Λ(AøxA)→ każdy zbiór x jest elementem zbioru ø, a obiekt którego elementami są wszystkie zbiory nie jest zbiorem.



Definicja

Niech Xø, R = (x), Tø. Funkcję f: T→R nazywamy indeksowaną rodziną zbiorów.

Niech f(t) = At dla tT

Indeksowaną rodzinę zbiorów ozn. {At: tT} lub {At} tT.

Jeśli A = {At: tT} to zamiast A( A) piszemy At( At).

Wtedy x At V(xAt): x AtΛ(xAt)

Jeśli T = N, to zamiast An( An) piszemy An( An)

Jeśli T={1,...,n} to zamiast At( At) piszemy A1...An (A1 ...An)



Twierdzenie

Dla dowolnie indeksowanej rodziny zbioru {At: tT}



  1. dla każdego tT

At⊆At⊆VAt

  1. jeśli dla dowolnego tT

B⊆At⊆A, to B⊆ At i At⊆A
Jeśli Λ(At⊆A), to Λ Λ(xAtxA), a więc Λ Λ(xAtxA) i stąd Λ(V(xAt)xA)

Zatem Λ(xVAtxA) co daje V At⊆A.


Wniosek:

At jest najmniejszym zbiorem ( w sensie zawierania) zawierającym wszystkie zbiory At, At jest największym zbiorem zawartym we wszystkich zbiorach At.

Twierdzenie

Dla dowolnie indeksowanej rodziny zbiorów {At: tT} i {Bt: tT} jeśli dla każdego tT, At⊆Bt, to At⊆ Bt oraz At⊆ Bt.



Dowód:

Jeśli At⊆Bt dla dowolnego tT, to x At V(xAt)V(xBt)x Bt oraz x At(xAt)ΛxBtx Bt.

Stąd At⊆ Bt i At⊆ Bt.

Twierdzenie

Dla dowolnych indeksowanych rodzin zbiorów {At: tT} i {Bt: tT}:



  1. (AtBt) = At  Bt

  2. (AtBt) = At  Bt

  3. (AtBt) ⊆ At  Bt

  4. At  Bt ⊆ (At  Bt)

Dowód:

  1. x (At  Bt) V(xAt  Bt)V (xAt xBt) V(xAt)  V(xBt) x At  x Btx At  Bt.

  2. x (At  Bt) Λ(xAt  Bt) Λ(xAt  xBt) Λ(xAt)  Λ(xBt)

x At  x Btx At  Bt

  1. x (At  Bt) V(xAt  Bt) V(xAt  xBt) V(xAt)  V(xBt)

V(xAt)  V(xBt)x At  x Btx At  Bt.

1   2   3   4   5   6   7   8   9


©operacji.org 2019
wyślij wiadomość

    Strona główna