Klasyczny rachunek zdań



Pobieranie 1,67 Mb.
Strona14/16
Data25.03.2018
Rozmiar1,67 Mb.
1   ...   8   9   10   11   12   13   14   15   16

2. Nie istnieje zbiór wszystkich zbiorów.

Gdyby bowiem istniał zbiór wszystkich zbiorów A, to rodzina 2A wszystkich podzbiorów A byłaby sama podzbiorem A.



FUNKCJE OBLICZALNE
Funkcje obliczalne zwane też funkcjami rekurencyjnymi stanowią bardzo ważny dział logiki, pozwalają one na precyzyjne sformułowanie wielu zagadnień dotyczących algorytmów. Okazuje się bowiem, że za pomocą tego pojęcia można zdefiniować pojęcie efektywnej procedury rozstrzygania, czy też obliczania. Intuicyjna treść pojęcia funkcji obliczalnej wyjaśnia się nieraz za pomocą następującego sformułowania: Funkcja jest obliczalna, gdy istnieje efektywna metoda, za pomocą której można obliczyć jej wartość dla dowolnego ciągu jej argumentów. W latach trzydziestych udało się sprecyzować określenie pojęcia funkcji obliczalnej; podano też kilka równoważnych definicji tego pojęcia.

Zamk(X,K)

Najmniejszy zbiór, zawierający zbiór X i zamknięty ze względu na zbiór operacji K.
Zbiór funkcji obliczalnych określa się często posługując się pojęciem najmniejszego zbioru, zawierającego określone funkcje wyjściowe i zamkniętego na określone operacje.

Def 1. Zbiór X jest zamknięty ze względu na funkcję f , gdy dla każdego x f(x) X
Ex1. Niech funkcja S będzie określona w następujący sposób S(n)=n+1 dla każdego nN Zbiór liczb naturalnych N, jest zamknięty na funkcję następnika, gdyż następnik liczby naturalnej też jest liczba naturalną.
Def. 2. Zbiór X jest zamknięty ze względu na zbiór funkcji K co oznaczamy Zamk(X,K) wtedy i tylko wtedy, gdy jest zamknięty ze względu na każdą funkcję należącą do K
Def. 3. Najmniejszy zbiór zawierający zbiór X i zamknięty ze względu na zbiór operacji (funkcji) K jest to iloczyn wszystkich zbiorów, które zawierają zbiór X i są zamknięte ze ze względu na zbiór operacji (funkcji)
Ex 51. Posługując się tym pojęciem można zdefiniować wiele zbiorów np. zbiór liczb naturalnych, zbiór tautologii rachunku zdań itp.
Zbiór N liczb naturalnych, jest to najmniejszy zbiór zawierający zbiór X={0} i zamknięty ze względu na funkcję S następnika

Zbiór tez (tautologii) aksjomatycznego systemu rachunku zdań Łukasiewicza Ł3, jest to najmniejszy zbiór, do którego należą trzy aksjomaty i zamknięty ze względu na operację (reguły) odrywania, podstawiania i zastępowania członów definicji



Definicja Funkcji obliczalnych
Funkcje obliczalne należą do takiego zbioru funkcji, których zarówno dziedziną jak i przeciwdziedziną jest zbiór liczb naturalnych.
Zbiór X funkcji wyjściowych

Z(x), czyli jednoargumentowa funkcja stała, przyjmująca 0 dla dowolnego xN



S(x)= x+1, czyli funkcji następnika

(x1,..., xn)= xi , czyli n-argumentowej funkcji identycznościowej

Ex. 52. Podaj wartości dla wyżej podanych funkcji, dla argumentów będących kolejnymi liczbami naturalnymi

a) Z(1)=0, Z(2)=0,..., Z(10)=0, ...

b) S(0)=1, S(1)=2,...,S(10)=11, ...

c) (x)=x, ( x1, x2)= x2, ( x1, x2, x3)= x3, ...



1   ...   8   9   10   11   12   13   14   15   16


©operacji.org 2019
wyślij wiadomość

    Strona główna