Klasyczny rachunek zdań


Zbiór funkcji obliczalnych jest zbiorem przeliczalnym o mocy



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

Zbiór funkcji obliczalnych jest zbiorem przeliczalnym o mocy 0

Dowód.


W definicji zbioru funkcji obliczalnych wychodzimy z przeliczalnego zbioru funkcji

(1) Z, S oraz . Ta ostatnia dla różnych n posiada przeliczalny zbiór układów zmiennych x1,..., xn a więc mamy także przeliczalny ciąg funkcji . Oznaczmy zbiór (1) przez X0. Dołączmy do X0 wszystkie funkcje zdefiniowane przez a) złożenie, b) rekursję, c) minimum efektywne zastosowane do zbioru funkcji X0 i oznaczmy je przez X1. Ogólne do zbioru Xi złożonego z funkcji dołączamy za pomocą omówionych operacji nowe funkcje i tworzymy zbiór Xi+1. Powstaje ciąg X0 X1 X2. . . zbiorów przeliczalnych. Każda funkcja obliczalna należy do jednego ze zbiorów Xi. Elementy zbiorów X0 ,X1, X2... ustawiamy w ciągi:
X0=

X1=

X2=

...............................



Licząc elementy na przekątnych ustawiamy je w ciąg:przypisując im kolejne liczby naturalne. A zatem zbiór funkcji obliczalnych jest przeliczalny.
Uwaga: Można udowodnić, że moc zbioru wszystkich funkcji wielu zmiennych, o argumentach i wartościach będących liczbami naturalnymi jest równa .

Podanie konkretnego przykładu funkcji nieobliczalnej jest jednak bardzo trudne, gdyż większość funkcji, z którymi spotykamy się w praktyce, to funkcje obliczalne.


Funkcje obliczalne mają szerokie zastosowanie w teorii maszyn cyfrowych. Komputery w swojej pracy nie wykonują nic innego, jak operacje składania, schemat rekursji prostej i schemat minimum efektywnego. Dla każdej funkcji obliczalnej istnieje urządzenie czy to mechaniczne lub elektroniczne (np. arytmometr), o bardzo dużej pamięci do zapisywania wyników pośrednich, obliczy wartość funkcji dla dowolnych argumentów. Wielkość pamięci która maszyna musi zużyć jest dla danego argumentu skończona, choć nie daje się z góry oszacować, podobnie czas liczenia również nie daje się z góry oszacować, choć jest skończony.
Teza Turinga
Funkcjami obliczalnymi są dokładnie te funkcje, dla których istnieje maszyna cyfrowa mająca skończoną ilość stanów wewnętrznych i nieskończoną pamięć, zdolna w skończonym, choć z góry nie dającym się oszacować czasie, obliczyć wartość funkcji dla zadanego argumentu i zatrzymać się po wykonaniu obliczenia.

Teza Churcha
Każde zagadnienie dla którego istnieje efektywny sposób rozwiązania, daje się wyrazić w odpowiednim tłumaczeniu za pomocą funkcji obliczalnych.
Ex 54. Zastosowanie funkcji obliczalnych w zagadnieniu gry w szachy:
Na 64 polach szachownicy znajduje się pewna ilość figur nie więcej niż 32, a nie mniej niż 2.

Każdemu ustawieniu figur można przyporządkować numer będący liczba naturalna. Ponumerujmy pola liczbami 0d 1 do 64, figury zaś:

Białe : 1- pionek, 2- wieża, 3- skoczek, 4-goniec, 5-hetman, 6- król

Czarne: 7- pionek, 8- wieża, 9- skoczek, 10-goniec, 11-hetman, 12- król


Jeżeli na polu o numerze i nie stoi figura, to piszemy ci=0

Jeżeli na polu o numerze i stoi figura o numerze c, to piszemy ci= c. Piszemy ponadto c0=0, jeżeli ruch maja białe , a c0=1 jeżeli ruch maja czarne. Niech q=13 będzie zasada numeracji

Pi=( c64 c63 c62... c1 c0)13 i=1, 2, ...n...

Niech


P1=(8 7 10 11 12 10 9 8 7 7 7 7 7 7 7 7 0 ...0 1 1 1 1 1 1 1 1 2 3 4 5 6 4 3 2 0)13

będzie początkowym ustawieniem, zaś

Pn=(1 0 0 0 7 0 4 0 0 0 2 0 0 0 0 12 0 6 0 0 2 0)13 n - tym ustawieniem zapisanym w systemie 13- nastkowym.

Można udowodnić, że funkcja f określona następująco:


1 jeżeli x jest numerem pozycji wygrywającej dla białych

2 jeżeli x jest numerem pozycji wygrywającej dla czarnych

f(x)= 3 jeżeli x jest numerem pozycji remisowej

0 jeżeli x nie jest numerem pozycji dopuszczalnej do gry w szachy


nie jest funkcją obliczalną. Wartość funkcji f dla liczby x przedstawionej przez Pn=1. Nie potrafimy jednak obliczyć wartości funkcji f dla liczby x przedstawionej zapisem P1

Algebry Boole’a




  1. Definicja Algebr Boole’a


Def.1 Algebrą Boole’a nazywamy zbiór X co najmniej dwóch elementów, jeżeli spełnione są następujące warunki:

  1. w zbiorze X istnieją dwa elementy wyróżnione, które oznaczamy przez 0 i 1

  2. w zbiorze X określone są trzy operacje A B, A  B, A” zwane odpowiednio sumą boole’owską, iloczynem boole’owskim i dopełnieniem, które nie wyprowadzają poza zbiór X, tzn. dla każdych elementów A i B należących do X również A B, A  B, A” należą do X

  3. na elementach zbioru X określona jest relacja równoważności oznaczona przez „=” spełniająca następujący warunek: dla każdych elementów A, B, C należących do X, jeżeli A=B, to również A’=B’, A  C =B  C, A  C =B C

  4. operacje wymienione w b) spełniają następujące aksjomaty

A1. A  B =B  A przemienność

B1. A  B =B  A

A2. A (B C)= (A  B)  (A C) rozdzielność

B2. A  (B  C) = (A  B)  (A C)

A3. A  0=A

B3. A 1=A

A4. AA’=1

B4. A  A’=0 własności stałych





  1. Przykłady Algebr Boole’a




  1. Algebrą Boole’a jest algebra zbiorów

Niech Z={1, 2, 3},a X będzie zbiorem podzbiorów zbioru Z. Załóżmy, że


{1, 2, 3}=1; {1, 2}=e1; {1, 3}=e2; {2, 3}=e3; {1}=e4; {2}=e5; {3}=e6; {0}=0
Czyli X={{1, 2, 3}, {1, 2}, {1, 3}, {2, 3}, {1}, {2}, {3}, {0}}={1, e1 ,e2 ,e3 ,e4 e5 ,e6,0}

Sprawdźmy, czy spełnione są aksjomaty algebry Boole’a dotyczące stałych 0, 1

Za A przyjmujemy pierwszy element, tzn. A={1,2,3}
A3. A  =A

1 0={1, 2, 3}{0}={1, 2, 3}= e1
B3. A  A’=0

1  (1 )’={1,2, 3} {0}={0}=0
A4. AA’=1

1  (1 )’ ={1,2, 3} {0}={1,2, 3}=1
B4. A 1=A

1 1 ={1,2, 3}{1,2, 3}={1,2, 3}= 1


  1. Algebrą Boole’a jest też rachunek zdań

Niech X będzie zbiorem wszystkich formuł rachunku zdań, zawierających 0, 1 i zmienne p1, p2,. . ., zamkniętych ze względy na operacje : , . Zbiór X ma następującą postać:


X={0, 1, p1,. p2, . . .,  p1,. . ., p1 p2, . . ., p1  p2 ,. . .}

Niech


„1” - oznacza symbol zdania prawdziwego

„0” - oznacza symbol zdania fałszywego

„” - oznacza operację dopełnienia „ ’ ”,

„”- oznacza operację iloczyn boole’owski „”

„”- oznacza operację sumy boole’owskiej „”

„” - oznacza relację równoważności


Sprawdźmy czy przy danej interpretackji spełnione są aksjomaty dla stałych Boole’a

A3. A  0=A

p 0  p
B3. A  A’=0

p  p  0


A4. AA’=1

p p1
B4. A 1=A

p1 p


  1. Algebrą Boole’a jest algebra sieci kontaktowych

Niech X będzie zbiorem wszystkich możliwych dwubiegunowych sieci kontaktów, z których każdy może być zamknięty, bądź otwarty. Elementami wyróżnionymi zbioru X będą:

0 - sieć składająca się z jednego, ciągle otwartego, kontaktu

1 -sieć składająca się z jednego, ciągle zamkniętego, kontaktu


operacje algebry boole’owskiej interpretujemy następująco:

„” – mnożenie sieci

„” – sumowanie sieci

„ ’ ” - negacja sieci

1. Jeżeli A i B są sieciami należącymi do X, to ich AB jest siecią otrzymaną przez równoległe połączenie sieci:

A

B
2. Jeżeli A i B są sieciami należącymi do X, to ich AB jest siecią otrzymaną przez szeregowe połączenie sieci:
A B

N
3. Negacja sieci polega na zmianie kontaktów z zamkniętych na otwarte, a z otwartych na zamknięte oraz wszystkie połączenia równoległe na połączenia szeregowe, a szeregowe na równoległe


Negacją sieci:
A

B
Będzie sieć:


A B

Sprawdźmy aksjomaty dla stałych


A3. A  0=A
A

0
Sieć A  0 składa się z dwóch kontaktów A oraz 0 połączonych równolegle. Ponieważ kontakt 0 jest stale otwarty więc działanie sieci zależy jedynie od kontaktu A. Sieć A  0 oraz A są więc równoważne


A

A

=


0

B3. A  A’=0


Sieć A  A’ składa się z sieci A oraz negacji A połączonych szeregowo

Jeżeli sieć A jest otwarta, to sieć A’ jest zamknięta i na odwrót. Za każdym razem suma sięci jest jednak otwarta co odpowiada sieci zawsze otwarte 0

A A’ 0

=
Podobnie sprawdzamy aksjomaty:



A4. AA’=1

B4. A 1=A




  1. Twierdzenia algebry Boole’a

Tw1. W każdej algebrze Boole’a istnieje tylko jeden wyrózniony element 0 i jeden wyróżniony element 1.


Dowód ( niewprost): Załóżmy że twierdzenie nie jest prawdziwe, a więc istnieją dwa różne elementy 0 i 0* oraz 1 i 1*, takie że 00* i 11* spełniające aksjomaty algebry Boole’a dla wszystkich A. W aksjomacie A3 A  0=A za A podstawmy najpierw 0*.

Mamy wówczas:

0*  0 = 0*

Ponieważ A3 jest on spełniony dla 0* otrzymujemy A  0*=A W aksjomacie A3 A  0*=A za A podstawmy teraz 0.

Mamy wówczas:

0  0* = 0

Wobec przemienności operacji sumy algebraicznej „” otrzymujemy:

0*  0=0  0*

0 = 0*

co jest sprzeczne z założeniem, że 00*. Analogicznie postępujemy dla 1 i 1*.


Tw. 2 Dla każdego elementu A dowolnej algebry Boole’a istnieje dokładnie jeden element B taki, że AB=1 i AB=0
Dowód (niewprost): Załóżmy że element A ma dwa uzupełnienia A’ i A* :


  1. A*= A*  0 A3

  2. A*  0=A* (A A’) B4

  3. A* (A A’)=(A*  A)  (A*A’) A2

  4. A*  A)  (A*A’)= (A  A*) (A*A’) A1

  5. (A  A*) (A*A’)=1 (A*A’) A4

  6. 1 (A*A’)= 1 (A’A*) A1

  7. 1 (A’A*)= (A A’)  (A’A*) A4

  8. (A A’)  (A’A*) =(A’ A)  (A’A*) A1

  9. (A’ A)  (A’A*)=A’ (A A*) A2

  10. A’ (A A*)=A’0 B4

  11. A’0=A’ A3

A*=A’ co jest sprzeczne z założeniem.


Tw. 3 Dla każdego elementu A algebry Boole’a A’’=A
Dowód:

1. AA’=1 A4



2. AA’=0 B4

  1. A’A=1 A1

  2. A’A=0 B1

  3. A jest dopełnieniem A’

  4. A’’=A Tw2.




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


©operacji.org 2019
wyślij wiadomość

    Strona główna