Wstęp.
Zamiar.
Nowe sekcje kursu matematyki dyskretnej, choć realizowane w formie programów edukacyjnych i serii wykładów, nie istnieją jeszcze w formie monografii, przynajmniej w języku rosyjskim, ponieważ kurs matematyki dyskretnej dla uczelni technicznych koncentruje się na starych stosowanych problemach, które inżynierowie musieli rozwiązać. W szczególności w logice matematycznej była to minimalizacja obwody logiczne, która dziś straciła na aktualności.
Warto zauważyć, że teoria syntezy obwodów logicznych, która przeszła niemal pełny „cykl biologiczny” na oczach jednego pokolenia badaczy, jest bardzo pouczającym przykładem tego, jak słabo powiązane z podstawowymi gałęziami nauk technicznych nauki są bardzo podatne na starzenie się. 10 lat temu wszystko czasopisma techniczne zostały wypełnione artykułami na temat minimalizacji i syntezy obwodów logicznych. Większość metod minimalizacji opracowanych przez naukowców jest obecnie zapomniana i nie jest pożądana w praktyce. A te idee, które wówczas uważano za czysto teoretyczne, znalazły praktyczne zastosowanie w nowoczesna technologia. Na przykład logika rozmyta, sieci Petriego i teoria algorytmów przetrwały próbę czasu i są szeroko stosowane w różnych dziedzinach cybernetyki i programowania, takich jak programowanie systemów, złożoność obliczeniowa i sztuczna inteligencja.
A teoria algorytmów stała się centralną sekcją matematyki dyskretnej. Jednak w odróżnieniu od większości monografii w języku rosyjskim, w toku wykładów zagadnienia te prezentowane są jako sposób rozwiązywania praktycznych, inżynierskich problemów.
Jak wiadomo, po każdej dekadzie elementy sprzętowe komputerów, systemy operacyjne, narzędzia dostępu i same programy zmieniają się radykalnie. Jednak struktury i algorytmy leżące u ich podstaw pozostają niezmienione znacznie dłużej. Podstawy te zaczęto kłaść tysiące lat temu, kiedy opracowano logikę formalną i opracowano pierwsze algorytmy.
Logika matematyczna i teoria algorytmów tradycyjnie należą do nauk podstawowych i uważa się, że mają niewielki związek z praktyką i są trudne do zrozumienia. Rzeczywiście, kiedy J. Boole stworzył aparat matematyczny algebry Boole'a, przez długi czas nie znalazł on praktycznego zastosowania, ale w XX wieku to właśnie ten aparat matematyczny umożliwił zaprojektowanie wszystkich komponentów komputera. W konsekwencji pierwsze z tych uprzedzeń zostaje skutecznie obalone przez rozwój technologii komputerowej.
Jeśli chodzi o uprzedzenia dotyczące trudności zrozumienia tej dyscypliny, to w dużej mierze wynikają one z faktu, że książki z zakresu logiki matematycznej i teorii algorytmów pisali matematycy dla matematyków.
Teraz, gdy możliwości technologii obliczeniowej wielokrotnie wzrosły, a samych komputerów osobistych jest znacznie więcej niż ludzi, którzy wiedzą, jak efektywnie z nich korzystać, zrozumienie, co można, a czego nie można zrobić przy pomocy nowoczesnej technologii komputerowej, staje się niezwykle istotne wyjątkowe znaczenie.
To właśnie ogólna teoria algorytmów pokazała, że istnieją problemy nierozwiązywalne bez względu na to, jak potężna jest moc obliczeniowa, a jej dynamicznie rozwijająca się gałąź – teoria złożoności obliczeniowej – stopniowo prowadzi do zrozumienia, że istnieją problemy, które można rozwiązać, ale obiektywnie złożone, a ich złożoność może okazać się poniekąd w sensie absolutnym, tj. praktycznie niedostępne dla współczesnych komputerów.
Kurs ten postawił sobie następujące cele:
1. Przedstaw wszystkie rozważane zagadnienia w sposób możliwie najprostszy, ale nie prostszy niż jest to wymagane od wysoko wykwalifikowanego specjalisty.
2. Problemy praktyczne punktem wyjścia jest projektowanie i analiza systemów informatycznych, a środkiem jest aparat formalny rozwiązanie systematyczne te problemy. Jesteśmy głęboko przekonani, że uczeń nie jest naczyniem, które należy napełnić, ale pochodnią, którą należy zapalić.
3. Każda część kursu zawiera pytania testowe. Do asymilacji ten kurs uczeń ma obowiązek odpowiedzieć na wszystkie te pytania.
W wyniku opanowania przedmiotu student, w oparciu o dobre zrozumienie odpowiednich części teoretycznych, powinien potrafić:
Zaimplementuj najprostszy rodzaj logicznej transformacji informacji w dowolnej podstawie funkcji logicznych;
Podkreśl argumentację dowodową język naturalny strukturę logiczną, zbuduj formalne schematy dowodowe i sprawdź ich poprawność.
1.2 Reprezentacje logiczne
Reprezentacje logiczne - opis badanego systemu, procesu, zjawiska w formie zbioru złożone wypowiedzi składa się z proste (elementarne) stwierdzenia I łączniki logiczne
między nimi. Reprezentacje logiczne i ich składowe charakteryzują się określonymi właściwościami i zbiorem dopuszczalnych przekształceń na nich (operacje, reguły wnioskowania itp.), realizując te opracowane w języku formalnym (matematycznym) logika prawidłowe metody rozumowanie - prawa logiki.
Badane są metody (zasady) formalnej prezentacji twierdzeń, konstruowanie nowych zdań z istniejących przy użyciu logicznie poprawnych przekształceń, a także metody (metody) ustalania prawdziwości lub fałszywości twierdzeń. logika matematyczna. Współczesna logika matematyczna obejmuje dwie główne sekcje: logika wypowiedzi i zakrycie go Logika predykatów(Rys. 1.1), do budowy którego istnieją dwa podejścia (języki), tworzące dwa warianty logiki formalnej: algebra logiki I rachunek logiczny. Istnieje zgodność jeden do jednego pomiędzy podstawowymi pojęciami tych języków logiki formalnej. Ich izomorfizm ostatecznie zapewnia jedność leżących u ich podstaw dopuszczalnych przekształceń.
Ryż. 1.1
Głównymi przedmiotami tradycyjnych gałęzi logiki są twierdzenia.
Oświadczenie - zdanie deklaratywne (oświadczenie, wyrok), o co ma sens, aby to powiedzieć PRAWDA Lub FAŁSZ. Wszystko wiedza naukowa(prawa i zjawiska fizyki, chemii, biologii itp., twierdzenia matematyczne itp.), zdarzenia życia codziennego, sytuacje powstające w ekonomii i procesach zarządzania formułowane są w formie twierdzeń. Zdania rozkazujące i pytające nie są stwierdzeniami.
Przykładowe stwierdzenia: „Dwa razy dwa równa się cztery”, „Żyjemy w XXI wieku”, „Rubel to waluta rosyjska”, „Alosza to brat Olega”, „Operacje sumowania, przecięcia i dodawania są operacjami boolowskimi na zbiorach ”, „Człowiek jest śmiertelny”, „Przestawienie miejsc wyrazów nie zmienia sumy”, „Dzisiaj poniedziałek”, „Jeśli pada deszcz, warto zabrać ze sobą parasol”.
Aby dalej posługiwać się tymi zdaniami jako stwierdzeniami, musimy dla każdego z nich wiedzieć, czy jest ono prawdziwe, czy fałszywe, tj. znam ich wartość prawdy (prawda). Należy pamiętać, że w niektórych przypadkach prawdziwość lub fałszywość stwierdzenia zależy od tego, jaką konkretną rzeczywistość (system, proces, zjawisko) staramy się za jego pomocą opisać. W tym przypadku mówi się, że dane stwierdzenie jest prawdziwe (lub fałszywe) w danej interpretacji (kontekście). Zakładamy ponadto, że kontekst jest podany, a stwierdzenie ma określoną wartość prawdziwości.
1.3 Historia rozwiniętej logiki matematycznej
Logika jako nauka powstała w IV wieku. PNE. Został stworzony przez greckiego naukowca Arystotelesa.Słowo „logika” pochodzi od greckiego „logos”, które z jednej strony oznacza „słowo” lub „ekspozycja”, a z drugiej myślenie. W słownik objaśniający Ozhegova S.I. Mówi się: „Logika jest nauką o prawach myślenia i jego formach”. W XVII wieku Niemiecki naukowiec Leibniz planował stworzyć nową naukę, którą byłaby „sztuka obliczania prawdy” . W tej logice, zdaniem Leibniza, każdemu twierdzeniu miałby odpowiedni symbol, a rozumowanie miałoby formę obliczeń. Ta idea Leibniza, nie spotkała się ze zrozumieniem współczesnych, nie została rozpowszechniona ani rozwinięta i pozostała genialnym przypuszczeniem.
Dopiero w połowie XIX w. Irlandzki matematyk George Boole ucieleśniał ideę Leibniza. W 1854 roku napisał dzieło „Badanie praw myślenia”, które położyło podwaliny pod algebrę logiczną, w której obowiązują prawa podobne do praw algebry zwykłej, ale litery tak. nie oznaczają liczb, ale stwierdzenia. W języku algebry Boole'a można opisać rozumowanie i „obliczyć” jego wyniki. Nie obejmuje jednak całego rozumowania, a jedynie jego pewien rodzaj. , Dlatego algebra Boole'a jest uważana za rachunek zdań.
Algebra logiczna Boole'a była zalążkiem nowej nauki - logiki matematycznej. Natomiast logikę Arystotelesa nazywa się tradycyjną logiką formalną. Nazwa „logika matematyczna” odzwierciedla dwie cechy tej nauki: po pierwsze, logika matematyczna to logika posługująca się językiem i metodami matematyki; po drugie, logika matematyczna jest powoływana do życia przez potrzeby matematyki.
Pod koniec XIX wieku. Stworzona przez Georga Cantora teoria mnogości wydawała się solidną podstawą całej matematyki, w tym logiki matematycznej, przynajmniej dla rachunku zdań (algebra Boole’a), gdyż Okazało się, że algebra Cantora (teoria mnogości) jest izomorficzna z algebrą Boole'a.
Sama logika matematyczna stała się gałęzią matematyki, jak się początkowo wydawało najwyższy stopień abstrakcyjne i nieskończenie dalekie od praktycznych zastosowań. Jednak dziedzina ta nie pozostała długo domeną „czystych” matematyków. Na początku XX wieku. (1910) Rosyjski naukowiec Ehrenfest P.S. wskazał na możliwość wykorzystania aparatu algebry Boole'a w łączności telefonicznej do opisu obwodów przełączających. W latach 1938–1940 niemal jednocześnie ukazały się prace radzieckiego naukowca V.I. Szestakowa, amerykańskiego naukowca Shannona oraz japońskich naukowców Nakashimy i Hakazawy na temat zastosowania logiki matematycznej w technologii cyfrowej. Pierwszą monografię poświęconą zastosowaniu logiki matematycznej w projektowaniu sprzętu cyfrowego opublikował w ZSRR radziecki naukowiec M.A. Gavrilov. w 1950 r. Rola logiki matematycznej w rozwoju nowoczesnej technologii mikroprocesorowej jest niezwykle ważna: wykorzystuje się ją przy projektowaniu sprzętu komputerowego, przy rozwoju wszystkich języków programowania oraz przy projektowaniu dyskretnych urządzeń automatyki.
Naukowcy wnieśli ogromny wkład w rozwój logiki matematycznej różne kraje: Profesor Uniwersytetu Kazańskiego Poretsky P.S., de-Morgan, Pierce, Turing, Kołmogorow A.N., Heidel K. i in.
1.4 Pytania do samodzielnego sprawdzenia.
1. Sformułuj cele zajęć
Uniwersytet Wołżski nazwany imieniem. Tatiszczewa.
Wykłady z logiki matematycznej i teorii algorytmów.
Opracował: profesor nadzwyczajny S.V. Kawerin.
Rozdział I. Algebra logiki.
§1.1. Definicja funkcji logicznej.
Funkcja logiczna y=f(x 1 ,x 2 ,…,x n)od P zmienne x 1 , x 2 ,...,x n to dowolna funkcja, w której argumenty i funkcja mogą przyjmować wartość 0 lub 1, tj. funkcja logiczna to reguła, według której dowolny zbiór zer i jedynek
(x 1 ,x 2 ,...,x n) przypisuje się wartość 0 lub 1.
Funkcje logiczne nazywane również funkcje algebry logicznej, funkcje binarne i funkcje przełączające.
Funkcja logiczna z N zmienne można określić za pomocą tabeli prawdy, w której zestawy wartości argumentów są ułożone w kolejności rosnącej według ich liczb : najpierw trwa rekrutacja, reprezentujący binarne rozwinięcie 0 (ten zbiór jest ponumerowany 0); potem przychodzi zbiór, który jest binarnym rozwinięciem 1, potem 2, 3 itd. Ostatni zestaw składa się z N jednostek i jest binarnym rozwinięciem liczby 2 N-1 (ta kolejność uporządkowania zbiorów będzie nazywana porządek leksykograficzny). Biorąc pod uwagę, że licznik zaczyna się od 0, a wartość funkcji logicznej może wynosić 0 lub N
1, dochodzimy do wniosku, że istnieją tylko 22 różne funkcje logiczne N zmienne. Zatem istnieje na przykład 16 funkcji boolowskich dwóch zmiennych, 256 funkcji trzech itd.
Przykład 1.1.1.(głosować) . Rozważmy urządzenie rejestrujące przyjęcie określonej uchwały przez „komitet trzech”. Każdy członek komisji przy zatwierdzaniu uchwały naciska swój własny przycisk. Jeżeli większość członków zagłosuje za przyjęciem uchwały. Jest to rejestrowane przez urządzenie rejestrujące. Zatem urządzenie realizuje funkcję f(x,y,z ) , którego tablica prawdy ma postać
| X | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| y | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
| z | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| f(x,y,z) | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
Funkcja boolowska jest również jednoznacznie określona poprzez wyliczenie wszystkich krotek, w których przyjmuje wartość 0, lub poprzez wyliczenie wszystkich krotek, w których przyjmuje wartość 1. Funkcja uzyskana w przykładzie F można również określić za pomocą następującego układu równości: f(0,0,0) = f(0,0,1) = f(0,1,0) = f(1,0,0) =0.
Wektor wartości funkcji Boole’a y=f(x 1 ,x 2 ,…,x n) jest uporządkowanym zbiorem wszystkich wartości funkcji f, w którym wartości są uporządkowane w porządku leksykograficznym. Przykładowo, niech funkcja trzech zmiennych f będzie określona wektorem wartości (0000 0010) i trzeba znaleźć zbiór, w którym f przyjmuje wartość 1. Ponieważ 1 jest na 7. miejscu i zajmuje pierwsze miejsce porządek leksykograficzny zaczyna się od 0, wówczas musimy znaleźć rozwinięcie binarne liczby 6. Zatem funkcja f przyjmuje wartość 1 w zbiorze (110).
§1.2. Elementarne funkcje logiczne.
Wśród funkcji boolowskich wyróżniają się tzw. elementarne funkcje boolowskie, za pomocą których można opisać dowolną funkcję boolowską o dowolnej liczbie zmiennych.
1. Funkcja boolowska f(x 1 ,x 2 ,…,x n) przyjmująca wartość 1 we wszystkich zbiorach zer i jedynek nazywa się stała 1 lub identyczna jednostka. Przeznaczenie : 1 .
2. Funkcja boolowska f(x 1 ,x 2 ,…,x n) przyjmująca wartość 0 we wszystkich zbiorach zer i jedynek nazywa się stała 0 lub identyczne zero. Przeznaczenie : 0 .
3. Odmowa jest funkcją boolowską jednej zmiennej zdefiniowaną w poniższej tabeli prawdy
Inne nazwy : mnożenie logiczne (iloczyn); logiczne „i”.
Oznaczenia : x&y, xÿy, x⁄y, min(x,y).
5. Dysjunkcja
Inna nazwa : logiczna konsekwencja. Oznaczenia : xŘy, xfly, xy.
7. Równorzędność jest funkcją logiczną dwóch zmiennych zdefiniowaną w poniższej tabeli prawdy
Inna nazwa : antyrównoważność. Oznaczenia : x∆y, x+y.
9. Udar Schaeffera jest funkcja logiczna dwóch zmiennych zdefiniowana w poniższej tabeli prawdy
Inna nazwa : negacja alternatywy, logiczne „nie-lub”, funkcja Webba.
Przeznaczenie : x∞y ; dla funkcji Webba - x±y.
Komentarz. Symbole Ÿ, ⁄, ¤, Ø, ~, ∆, |, ∞ stosowane w notacji funkcje elementarne nazwiemy je połączeniami lub operacjami.
§1.3. Określanie funkcji boolowskich za pomocą funkcji elementarnych.
Jeśli zastąpisz niektóre funkcje logiczne funkcją logiczną zamiast zmiennych, wynikiem będzie nowa funkcja boolowska nałożenie funkcje podstawione (funkcja złożona). Stosując superpozycję, można uzyskać bardziej złożone funkcje, które mogą zależeć od dowolnej liczby zmiennych. Pisanie funkcji boolowskich będziemy nazywać w kategoriach elementarnych funkcji boolowskich formuła realizując tę funkcję.
Przykład 1.3.1. Niech będzie dana elementarna funkcja boolowska x¤y. Zastąpmy funkcję x 1 ∞x 2 zamiast x. Otrzymujemy funkcję trzech zmiennych (x 1 ∞x 2)¤y. Jeśli zamiast zmiennej y podstawimy np. x 3 ∆x 4, to otrzymamy nową funkcję czterech zmiennych: (x 1 ∞x 2)¤(x 3 ∆x 4). Oczywiście w ten sposób otrzymamy funkcje boolowskie, które wyrazimy poprzez elementarne funkcje boolowskie.
Patrząc w przyszłość, zauważamy to każdy funkcję boolowską można przedstawić jako superpozycję funkcji elementarnych.
Aby pisać złożone funkcje w bardziej zwięzły sposób, wprowadzamy następujące konwencje: : 1) pominięto nawiasy zewnętrzne; 2) w pierwszej kolejności wykonywane są operacje w nawiasach; 3) przyjmuje się, że pierwszeństwo łączników maleje w następującej kolejności : Ÿ, ⁄, ¤, Ø, ~. Dla spójników równoważnych i pozostałych spójników (∆,|,∞) należy na razie umieścić nawiasy.
Przykłady 1.3.2. We wzorze x⁄y¤z nawiasy umieszcza się następująco: ((x⁄y)¤z), ponieważ operacja ⁄ jest silniejsza niż operacja ¤ zgodnie z naszą umową.
1. We wzorze x¤y~zŘx nawiasy umieszcza się następująco: ((x¤y)~(zŘx))
2. We wzorze (x∆y)~zŘxy¤Ÿz nawiasy umieszcza się następująco: ((x∆y)~(zŘ((xy)¤(Ÿz)))).
3. Wzór xŘyŘz, zgodnie z naszą umową, nie jest zapisany poprawnie, ponieważ umieszczenie nawiasów daje dwa różne funkcje: ((xŘy)Řz) i (xŘ(yŘz)).
§1.4. Zmienne istotne i nieistotne.
Funkcja boolowska y=f(x 1 ,x 2 ,…,x n) zależy znacząco ze zmiennej X k jeśli taki zbiór wartości istnieje A 1 ,A 2 ,…,A k - 1, A k+1, A k + 2 ,…, A Nże f (A 1, za 2,…,a k-1 , 0 ,A k+1,a k+2,…,a N) π F (A 1, za 2,…,a k-1 , 1 ,A k+1,a k+2,…,a N).
W tym przypadku X k nazywa się zmienną istotną , W przeciwnym razie X k nazywa się zmienną nieistotną (fikcyjną). . Innymi słowy, zmienna jest nieistotna, jeśli jej zmiana nie powoduje zmiany wartości funkcji.
Przykład 1.4.1. Niech funkcje logiczne f 1 (x 1 , x 2) i f 2 (x 1 , x 2) zostaną określone przez poniższą tablicę prawdy:
| x 1 | x 2 | fa 1 (x 1,x 2) | f 2 (x 1, x 2) |
| 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 |
Dla tych funkcji zmienna x 1 - jest istotna, a zmienna x 2 nie jest istotna.
Oczywiście funkcje logiczne nie zmieniają swoich wartości poprzez wprowadzenie (lub usunięcie) nieistotnych zmiennych. Dlatego w dalszej części rozważamy funkcje logiczne aż do zmiennych nieistotnych (w przykładzie możemy zapisać: f 1 (x 1 , x 2) = x 1 , f 2 (x 1 , x 2) = Ÿx 1 ).
§1.5. Tablice prawdy. Funkcje równoważne.
Znając tablice prawdy dla funkcji elementarnych, możesz obliczyć tablicę prawdy funkcji, którą implementuje ten wzór.
Przykład 1.5.1. F1=x 1 ⁄x 2 ¤(x 1 ⁄Ÿx 2 ¤Ÿx 1 ⁄x 2)
Zatem wzór F1 realizuje alternatywę. Przykład 1.5.2. F2=x 1 ⁄x 2 Řx 1
Zatem wzór F3 realizuje alternatywę.
Wywoływane są funkcje logiczne f1 i f2 równowartość, jeśli na każdym zestawie ( A 1 ,A 2 ,…, jakiś) zera i jedynek, wartości funkcji pokrywają się. Zapis funkcji równoważnych jest następujący : f1=f2.
Na podstawie podanych przykładów 1-3 możemy pisać
X 1 ⁄x 2 ¤(x 1 ⁄Ÿx 2 ¤Ÿx 1 ⁄x 2)=x 1 ¤x 2 ;
X 1 ⁄x 2 Řx 1 =1;
((x 1 ⁄x 2)∆x 1)∆x 2 =x 1 ¤x 2.
§1.6. Podstawowe równoważności.
Podane równoważności są często przydatne podczas pracy z funkcjami boolowskimi.
Poniżej H, H1, H2,... oznaczają niektóre funkcje logiczne.
1. Prawo podwójnej negacji: H = H.
2. Idempotencja
3. Przemienność:
H1*H2=H2*H1, gdzie symbol * oznacza jeden z łączników &, ¤, ∆,
4. Łączność:
H1*(H2*H3)=(H1*H2)*H3, gdzie symbol * oznacza jeden ze łączników &, ¤, ∆, ~.
5. Dystrybutywność:
H1&(H2¤H3)=(H1&H2)¤(H1&H3); H1¤(H2&H3)=(H1¤H2)&(H1¤H3); H1&(H2∆H3)=(H1&H2)∆(H1&H3).
6. Prawa De Morgana:
H1 i H2 = H1 ∨ H2, H1∨ H2 = H1 i H2.
7. Zasady przejęć:
H1¤(H2&H3)=H1, H1&(H2¤H3)=H1
8. Prawa klejenia:
H1 i H2 ∨ H1 i H2 = H1, (H1∨ H2) & (H1∨ H2) = H1.
9. Prawa inwersji: H ∨ H = 1, H i H = 0.
10. Zasady operacji na stałych:
H¤1=1, H&1=H, H¤0=H, H&0=0.
Aby sprawdzić prawdziwość powyższych równoważności, wystarczy skonstruować odpowiednie tablice prawdy.
Należy zauważyć, że właściwość skojarzenia operacji umożliwia rozszerzenie tej operacji na dowolną liczbę zmiennych. Na przykład zapis x¤у¤z¤w jest poprawny, ponieważ dowolne ustawienie nawiasów daje tę samą funkcję. Przemienny charakter operacji umożliwia zamianę zmiennych w formule. Na przykład x⁄y⁄z⁄w=w⁄y⁄x⁄z.
§1.7. Kompletność funkcjonalna.
W typowym nowoczesnym komputerze cyfrowym liczby to 0 i 1. Dlatego instrukcje wykonywane przez procesor są funkcjami boolowskimi. Poniżej pokażemy, że dowolna funkcja boolowska jest realizowana poprzez koniunkcję, alternatywę i negację. Dzięki temu możliwe jest zbudowanie wymaganego procesora, mając do dyspozycji elementy realizujące koniunkcję, alternatywę i negację. Ten rozdział poświęcony jest odpowiedzi na pytanie: czy istnieją (a jeśli tak, to jakie) inne systemy funkcji boolowskich, które mają tę właściwość, że można je wykorzystać do wyrażenia wszystkich innych funkcji.
Wprowadźmy kilka klas funkcji.
1. Klasa funkcji zachowujących stałą 0, tj. takie funkcje
2. Klasa funkcji zachowujących stałą 1, tj. takie funkcje
3. Klasa funkcji samodualnych, tj. takie funkcje y=f(x 1 ,x 2 ,…,x n) takie, że f(x 1 , x 2 ,… , x n) = f(x 1 , x 2 ,… , x n) .
4. Klasa funkcji liniowych, tj. takie funkcje y=f(x 1 ,x 2 ,…,x n), które można przedstawić jako f(x 1 ,x 2 ,…,x n)=c 0 ∆c 1 x 1 ∆c 2 x 2 ∆… ∆ c n x n, gdzie c 0, c 1, c 2 ...współczynniki, które mogą przyjmować wartość 0 lub 1.
5. Klasa funkcji monotonicznych. Na zbiorze zer i jedynek Bn =((x 1 ,x 2 ,…,x n):x i œ(0,1),i=1,2,…,n) wprowadzamy porządek częściowy następująco:
(A 1 ,a 2 ,...,n)§( B 1 ,b 2 ,...,b n) wtedy i tylko wtedy gdy A 1 § B 1 , 2 § b 2 ,…,a N § B N. Funkcję f(x 1, x 2,..., x n) nazywamy monotoniczną, jeżeli dla dowolnych dwóch elementów z B n takich, że
(A 1 ,a 2 ,...,n)§( B 1 ,b 2 ,...,b n) wynika, że f( A 1 ,a 2 ,...,n)§F( B 1 ,b 2 ,...,b n).
Nazywa się układ S funkcji boolowskich, którego superpozycja może reprezentować dowolną funkcję boolowską funkcjonalnie kompletny . Mówi się, że tworzy się funkcjonalnie kompletny system S funkcji boolowskich podstawa w przestrzeni logicznej. Baza S nazywa się minimalny , jeśli usunięcie z niego jakiejkolwiek funkcji sprawi, że system ten stanie się niekompletny.
Kryterium kompletności (Twierdzenie Posta) . Układ S funkcji boolowskich jest kompletny wtedy i tylko wtedy, gdy zawiera co najmniej jedną funkcję: niezachującą stałą 0, niezachującą stałą 1, niesamodualną, nieliniową i niemonotoniczną.
W tabeli 1.7 przedstawiono właściwości elementarnych funkcji boolowskich (symbol * oznacza właściwość, jaką posiada dana funkcja).
Korzystając z twierdzenia Posta i tabeli 1.7, można budować bazy z funkcji elementarnych zgodnie z następującą zasadą. Wybierając dowolną elementarną funkcję Boole'a i uzupełniając ją w razie potrzeby innymi funkcjami, tak aby wszystkie razem spełniały twierdzenie o kompletność funkcjonalna. Poprzez funkcje tej podstawy możemy wyrazić Wszystko inne funkcje logiczne.
Skonstruujmy kilka często używanych baz w aplikacjach.
Tabela 1.7
| Nazwa | Przeznaczenie | Nieprzechowalność stałe |
Nieprzechowalność stałe |
Samodwoje ważność |
||
| Stała 0 | 0 | * | * | |||
| Konstytucja 1 | 1 | * | * | |||
| Negatywny | Ÿ | * | * | * | ||
| Kongyuna. | & | * | * | |||
| Dysjunkcja. | ¤ | * | * | |||
| domniemane. | Ø | * | * | * | * | |
| Równowartość. | ~ | * | * | * | ||
| Suma według mod_2 | ∆ | * | * | * | ||
| | | * | * | * | * | * | |
| Strzała Pierce'a | ∞ | * | * | * | * | * |
1. Podstawą jest układ funkcji S1=(Ÿ,⁄,¤). Aby sprowadzić funkcję boolowską do postaci zawierającej tylko łączniki z bazy S1, przydatne mogą być następujące równoważności: x → y = x ∨ y , x ↔ y = (x ∨ y)(x ∨ y) , x ⊕ y = xy ∨ xy , xy = x ∨ y , x ↓ y = x i y .
2. Podstawą jest system S2=(Ÿ,&). Funkcja arbitralna można najpierw sprowadzić do postaci zawierającej łączniki z S1, a następnie
skorzystaj z zależności x ∨ y = x ⋅ y.
3. Podstawą jest system S3=(Ÿ,¤). Dowolną funkcję można najpierw sprowadzić do postaci zawierającej łączniki z S1, a następnie
skorzystaj z zależności x ⋅ y = x ∨ y.
4. Podstawą jest układ S4=(1,&,∆). Dowolną funkcję można najpierw sprowadzić do postaci zawierającej spójniki z S1, a następnie skorzystać z zależności x = 1⊕ x, x ∨ y = x ⊕ y ⊕ x ⋅ y.
5. Podstawą jest system S5=(|). Dowolną funkcję można najpierw sprowadzić do postaci zawierającej spójniki z S2, a następnie skorzystać z relacji x ⋅ y = x y , x = xx .
6. Podstawą jest układ S6=(∞). Dowolną funkcję można najpierw sprowadzić do postaci zawierającej łączniki z S3, a następnie
skorzystaj z zależności x ∨ y = x ↓ y, x = x ↓ x.
7. Podstawą jest układ S7=(Ř,0).
Przykład 1.7.1. Zapisz funkcję x¨(y∆z) w bazie S1=(Ÿ,⁄,¤). x ↔ (y ⊕ z) = (x ∨ y ⊕ z) ⋅(x ∨ (y ⊕ z)) = (x ∨ y ⋅ z ∨ y ⋅ z) ⋅(x ∨ y ⋅ z ∨ y ⋅ z)
Rozdział II. Algebra Boole’a.
Zbiór wszystkich wartości logicznych w bazie S1=( ÿ, &, ⁄} formularz Algebra Boole’a. Zatem w algebrze Boole'a wszystkie formuły zapisuje się trzema łącznikami: Ÿ, &, ¤. Częściowo zbadaliśmy właściwości tej algebry w rozdziale I (patrz np. podstawowe równoważności). Ten rozdział dotyczy właściwości specyficznych dla algebry Boole'a, dlatego w tym rozdziale zajmiemy się tylko trzema funkcjami: ÿ, &, ⁄.
§2.1. Normalne formy.
Formy normalne to syntaktycznie jednoznaczny sposób zapisu formuły realizującej daną funkcję.
Jeśli x jest zmienną logiczną, a σœ(0,1) to wyrażenie x σ = x jeśli σσ == 10 lub x σ = 10 jeśli x x =≠σσ , x nazywa się literą . Litery x i Ÿx nazywane są przeciwieństwami. Połączony rozłączny zwane dysjunkcją liter. Na przykład wzory x ⋅ y ⋅ z i x ⋅ y ⋅ x ⋅ x są koniunkcjami, wzory x ∨ y ∨ z i x ∨ y ∨ x są rozłączeniami, a wzór z jest zarówno koniunkcją, jak i alternatywną.
Rozłączna postać normalna (DNF) nazywa się alternatywną skończoną liczbą spójników .
Łączna postać normalna (CNF) nazywa się koniunkcją skończonej liczby zdań .
Mówiąc prościej: DNF to suma produktów, a CNF to iloczyn sum logicznych.
1. xÿy¤yÿz¤x to DNF (suma produktów).
2. (x ∨ y ∨ z)⋅(x ∨ y)⋅z to CNF (iloczyn sum).
3. x ∨ y ∨ z ∨ w to DNF i CNF (jednocześnie).
4. x ⋅ y ⋅ z ⋅ w to DNF i CNF (jednocześnie).
5. (x¤x¤y)·(y¤z¤x)·z to CNF.
6. x⋅y⋅z i x⋅y⋅x⋅x to DNF.
7. x ⋅(x ∨ yz)⋅ x ⋅ y ⋅ z nie jest formą normalną (nie DNF ani CNF).
Niech funkcja f zostanie zapisana w bazie S1. Funkcja ta jest zredukowana do postaci normalnej w następujący sposób:
1) korzystając z praw De Morgana przekształcamy wzór do postaci, w której znaki ujemne odnoszą się tylko do poszczególnych zmiennych;
2) stosujemy zasadę usuwania podwójnych negatywów: ŸŸx=x;
H1&(H2¤H3)=(H1&H2)¤(H1&H3) i drugie prawo rozdzielności dla redukcji do CNF. H1¤(H2&H3)=(H1¤H2)&(H1¤H3).
Każda funkcja boolowska może mieć nieskończoną liczbę reprezentacji DNF i CNF. Przykładowo, korzystając dodatkowo z praw inwersji i zasad działania na stałych, można zapewnić, że w każdej pojedynczej koniunkcji lub alternatywie dowolna zmienna pojawi się nie więcej niż raz (albo sama, albo jej negacja).
Przykład 2.1.1. Aby zredukować do DNF, używamy pierwszej zasady rozdzielności.
x⋅y⋅x⋅y⋅z⋅(y∨z)=x⋅y⋅(x∨y∨z)⋅(y∨z)=(x⋅y⋅x∨x⋅y⋅y∨x⋅y ⋅z)⋅(y∨z)= to CNF
= (0∨ x⋅y∨ x⋅y⋅z)⋅(y∨ z) = (x⋅y∨ x⋅y⋅z)⋅(y∨ z) = - to jest kolejny CNF
X ⋅ y⋅у ∨ x ⋅ y⋅z⋅ y ∨ x ⋅y⋅z ∨ x ⋅ y⋅z⋅z = 0∨ 0∨ x ⋅y⋅z ∨ x ⋅ y⋅z =
X ⋅ y ⋅ z ∨ x ⋅ y ⋅ z jest DNF
Przykład 2.1.2. Aby zredukować do CNF, konieczne jest skorzystanie z drugiej zasady rozdzielności.
x ∨ y ⋅ x ⋅ y ∨ z = x ∨ y ⋅ (x ⋅ y ⋅ z) = x ∨ y ⋅ (x ∨ y) ⋅ z =
X∨y⋅z⋅(x∨y)=(x∨y⋅z)⋅(x∨x∨y)=(x∨y)⋅(x∨z)⋅(1∨y)=
= (x ∨ y) ⋅ (x ∨ z) to CNF
§2.2. Idealne normalne formy.
Jeśli w każdym wyrazie formy normalnej są reprezentowane wszystkie zmienne (same lub ich negacje), a w każdej indywidualnej koniunkcji lub alternatywie dowolna zmienna pojawia się dokładnie raz (sama lub jej negacja), wówczas postać tę nazywamy doskonała postać normalna (SDNF lub SCNF). Przykłady: Niech będzie dana funkcja trzech zmiennych f(x,y,z).
1. x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z jest doskonałym DNF.
2. (x ∨ y ∨ z)⋅(x ∨ y ∨ z)⋅(x ∨ y ∨ z) jest doskonałym CNF.
3. (x ∨ y) ⋅ (x ∨ z) nie jest idealną CNF, ponieważ na przykład pierwsza suma nie uwzględnia zmiennej z.
4. xÿyÿz to doskonały DNF. Twierdzenie 2.2.1.
1. Każda funkcja logiczna, która nie jest identyczna z zerem, ma tylko jeden SDNF, aż do lokalizacji warunków.
2. Każda funkcja logiczna, która nie jest identyczna z 1, ma tylko jeden SCNF, aż do lokalizacji warunków.
Twierdzenie udowodnimy konstruktywnie, jako rozwiązanie następującego problemu: Korzystając z tej tabeli prawdy, skonstruuj SDNF.
Rozważmy rozwiązanie na przykładzie funkcji f(x,y,z) podanej w tabeli (tabela 2.2) dla n=3.
Przykład 2.2.1. Korzystając z tej tabeli prawdy (Tabela 2.2), skonstruuj SDNF.
Tabela 2.2
| X | y | z | podstawowy spójniki |
f(x,y,z) |
| 0 | 0 | 0 | x ⋅ y ⋅ z | 0 |
| 0 | 0 | 1 | x ⋅ y ⋅ z | 1 |
| 0 | 1 | 0 | x ⋅ y ⋅ z | 1 |
| 0 | 1 | 1 | x ⋅ y ⋅ z | 0 |
| 1 | 0 | 0 | x ⋅ y ⋅ z | 0 |
| 1 | 0 | 1 | x ⋅ y ⋅ z | 1 |
| 1 | 1 | 0 | x ⋅ y ⋅ z | 1 |
| 1 | 1 | 1 | x ⋅ y ⋅ z | 1 |
Podstawowe spójniki (lub składniki_1) zawarte w tabeli odpowiadają konkretnemu zbiorowi zer i jedynek, jakie przyjmują zmienne x,y,z. Składniki są w trakcie tworzenia_ 1 zgodnie z następującą zasadą: zmienna jest zawarta w samym iloczynie, jeśli w danym zbiorze przyjmuje wartość 1, w przeciwnym razie jej negacja jest zawarta w iloczynie. I tak np. na zbiorze (0,0,1) zmienne x,y przyjmują wartość 0 i dlatego ich negacje są uwzględniane w iloczynie, a zmienna z przyjmuje wartość 1 i dlatego jest zawarta w samym iloczynie . Dla danego zbioru (0,0,1) składnik_1 jest równy x ⋅ y ⋅ z .
Oczywiście koniunkcja x ⋅ y ⋅ z jest równa 1 tylko na zbiorze
(0,0,0), a x ⋅ y ⋅ z wynosi 1 w zbiorze (0,0,1) itd. (patrz tabela). Następnie zauważmy, że dysjunkcja dwóch podstawowych spójników jest równa 1 dokładnie na dwóch zbiorach, które odpowiadają tym podstawowym spójnikom. Przykładowo funkcja x ⋅ y ⋅ z¤x ⋅ y ⋅ z jest równa 1 tylko na dwóch zbiorach - (0,0,0) i (0,0,1), a na wszystkich pozostałych zbiorach jest równa 0. Podobnie dysjunkcja trzech podstawowych spójników jest równa 1 na dokładnie trzech zbiorach, które odpowiadają tym podstawowym spójnikom, itd.
To. dostajemy zasada: do budowy SDNF należy wybrać wiersze, w których funkcja jest równa 1, a następnie dokonać alternatywy odpowiednich spójników głównych, otrzymamy pożądany SDNF. W naszym przykładzie mamy x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z .
Zadanie. Korzystając z tej tabeli prawdy, skonstruuj SCNF.
Konstytucja_0 dla zbioru zer i jedynek (które przyjmują zmienne x,y,z) konstruuje się następująco: zmienna jest uwzględniana w samej alternatywie, jeżeli przyjmuje wartość z tego zbioru 0 , w przeciwnym razie praca zawiera jej zaprzeczenie.
Zasada konstruowania SKNF: należy wybrać linie, w których funkcja jest równa 0 , a następnie weź koniunkcję odpowiednich składników_0. Rezultatem będzie pożądany SCNF. Zatem w naszym przykładzie mamy f = (x ∨ y∨ z)⋅(x ∨ y∨ z)⋅(x ∨ y∨ z) .
Komentarz. Aby skonstruować idealną funkcję CNF f, wystarczy skonstruować doskonałą funkcję DNF dla funkcji f, a następnie
Skonstruujmy SCNF dla naszego przykładu w oparciu o uwagę. 1. Budujemy SDNF do negacji.
x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z
2. Korzystamy z praw de Morgana f = f = x ⋅ y⋅ z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅ z = x ⋅ y⋅ z&x ⋅ y⋅z&x ⋅ y⋅ z == (x ∨ y ∨ z ) ⋅(x ∨ y ∨ z)⋅(x ∨ y ∨ z) .
Opisana metoda znajdowania SDNF (i SCNF) przy użyciu tabeli prawdy jest często bardziej pracochłonna niż poniższy algorytm.
1. Aby znaleźć SDNF Najpierw redukujemy tę formułę do DNF.
2. Jeżeli jakaś koniunkcja K (tj. K jest iloczynem pewnej liczby zmiennych lub ich negacji) nie zawiera np. zmiennej y, to tę koniunkcję zastępujemy równoważnym wzorem K&(y ∨ y) i stosując prawo rozdzielności, wynikowy wzór przedstawiamy DNF; jeżeli brakujących zmiennych jest kilka, to dla każdej z nich do spójnika dodajemy odpowiednią formułę postaci (y ∨ y).
3. Jeżeli powstały DNF zawiera kilka identycznych składników jednostki, wówczas pozostawiamy tylko jeden z nich. Rezultatem jest SDNF.
Komentarz: Aby skonstruować SCNF w klauzulę niezawierającą, powiedzmy, zmiennej Na dodajemy formułę w postaci y⋅ y, tj. Zastępujemy tę alternatywę równoważnym wzorem D ∨ y⋅ y i, stosując 2. zasadę rozdzielności.
Przykład 2. 2. 2. Skonstruuj SDNF dla funkcji f, używając równoważnych transformacji.
f = x ∨ y ⋅ z = x ⋅ (y ∨ y) ⋅ (z ∨ z) ∨ y ⋅ z ⋅ (x ∨ x) == x ⋅ y ⋅ z x ⋅ y ⋅ z x ⋅ y ⋅ z x ⋅ y ⋅ z y ⋅ z ⋅ x y ⋅ z ⋅ x =
WYCOFAĆ SIĘ.
Obliczanie SDNF ma nie tylko charakter teoretyczny, ale ma także ogromne znaczenie praktyczne. Na przykład w wielu nowoczesne programy za pomocą interfejsu graficznego do tworzenia złożonych warunków logicznych stosuje się formę wizualną w postaci tabeli: warunki są zapisywane w komórkach, a komórki jednej kolumny uważa się za połączone spójnikiem, a kolumny uważa się za połączone przez rozłączenie, to znaczy tworzą DNF (lub odwrotnie, w tym przypadku uzyskuje się CNF). W szczególności tak zaprojektowany jest interfejs graficzny QBE (Query-byExample), służący do formułowania warunków logicznych podczas odpytywania systemu DBMS.
Algorytm 2.2.1. Budowa SDNF
Wejście: wektor X: tablica stringów - identyfikatory zmiennych, macierz V: tablica 0..1 wszystkich różnych zbiorów wartości zmiennych,
wektor F: tablica 0..1 odpowiednich wartości funkcji.
Wyjście: ciąg symboli tworzący zapis wzoru SDNF dla danej funkcji.
f:= FAŁSZ(znak obecności lewego operandu alternatywy) Do I z 1Do 2n Do
Jeśli F[i] = 1 a następnie, jeśli F Następnie
dawa愤” (dodanie znaku alternatywy do wzoru; operator dawać drukuje m
symbol m) w przeciwnym razie f:= PRAWDA
koniec, jeśli g:= FAŁSZ(znak obecności lewego operandu koniunkcji) Do J z 1Do N zrobić, jeśli G Następnie
dawać„⁄” (dodanie znaku spójnika do wzoru)
w przeciwnym razie g: = prawda
koniec, jeśli V (dodanie identyfikatora zmiennej do formuły
§2.3. Minimalizacja DNF metodą Quine’a.
Każda formuła ma ostateczny numer wystąpienia zmiennych. Wystąpienie zmiennej odnosi się do miejsca, jakie zmienna zajmuje we wzorze. Zadanie polega na znalezieniu dla danej funkcji logicznej f DNF reprezentującego tę funkcję i mającego najmniejszą liczbę wystąpień zmiennych.
Jeśli x jest zmienną logiczną, a σœ(0,1) to wyrażenie x σ =xx if if σσ== 10 .
zwany list . Połączony zwane połączeniem liter. Na przykład wzory x ⋅ y ⋅ z i x ⋅ y ⋅ x ⋅ x są spójnikami . Iloczyn elementarny to koniunkcja, w której dowolna zmienna występuje nie więcej niż raz (sama lub jej zaprzeczenie).
Nazywa się Formuła f1 niejawne formuły f , jeśli f1 jest iloczynem elementarnym i f 1 ⁄ f = f 1, tj. to znaczy dla funkcji odpowiadających wzorom zachodzi nierówność f 1 § f. Implikant f1 wzoru f nazywa się prosty , jeśli po odrzuceniu dowolnej litery z f1 nie otrzyma się wzoru będącego implikacją wzoru f.
Przykład 2.3.1 . Znajdźmy wszystkie implikanty i implikanty proste dla wzoru f=xŘy . Istnieje w sumie 8 produktów elementarnych ze zmiennymi X I ty Poniżej dla przejrzystości podano ich tablice prawdy:
| X | y | xŘy | x ⋅ y | x ⋅ y | x ⋅ y | x ⋅ y | X | y | X | y | |||||||
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | |||||||
| 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | |||||||
| 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | |||||||
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | |||||||
Z tablic prawdy wnioskujemy, że wzory x ⋅ y , x ⋅ y , x ⋅ y , x ,y - wszystkie implikanty wzoru xŘy, a z tych implikantów wzory x i y są proste (na przykład wzór x ⋅ y nie jest prostym implikantem, ponieważ odrzucając literę y, otrzymujemy implikant x).
W skrócie DNF nazywa się dysjunkcją wszystkich implikantów pierwszych danej formuły (funkcji) .
Twierdzenie 2.3.1. Dowolną funkcję boolowską, która nie jest stałą 0, można przedstawić jako skrót DNF.
W przykładzie 2.3.1 funkcję odpowiadającą wzorowi xŘy przedstawiono za pomocą wzoru x ∨ y, który jest jej skrótem DNF.
Zredukowany DNF może zawierać dodatkowe implikacje, których usunięcie nie zmienia tabeli prawdy. Jeśli usuniemy wszystkie niepotrzebne implikanty ze zredukowanego DNF, otrzymamy DNF o nazwie ślepy zaułek.
Należy zauważyć, że reprezentacja funkcji jako ślepego zaułka DNF jest w ogólnym przypadku niejednoznaczna. Wybierając spośród wszystkich form ślepych uliczek, otrzymujemy formę z najmniejszą liczbą wystąpień zmiennych minimalny DNF (MDNF).
Rozważ metodę Quina, aby znaleźć MDNF reprezentujący daną funkcję boolowską. Definiujemy następujące trzy operacje:
1. pełna operacja wiązania : fa ⋅ x ∨ fa ⋅ x = fa ⋅ (x ∨ x) = fa ;
2. operacja częściowego klejenia:
fa ⋅ x ∨ fa ⋅ x = fa ⋅ (x ∨ x) ∨ fa ⋅ x ∨ fa ⋅ x = fa ∨ fa ⋅ x ∨ fa ⋅ x ;
3. działanie absorpcji elementarnej f ⋅ x σ ∨ f = f , σ ∈ (0,1) .
Twierdzenie 2.3.2(Twierdzenie Quine'a). Jeśli w oparciu o funkcję SDNF wykonamy wszystkie możliwe operacje niepełnego sklejenia, a następnie elementarnej absorpcji, to efektem będzie zredukowany DNF, czyli alternatywna wszystkich implikantów prostych.
Przykład 2.3.2. Niech funkcja f(x,y,z) będzie dana przez doskonały DNF f = x ⋅ y⋅ z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅ z ∨ x ⋅ y⋅z . Następnie wykonując w dwóch etapach wszystkie możliwe operacje niepełnego sklejenia, a następnie elementarnego wchłonięcia, mamy
F 
Zatem skrócony DNF funkcji f jest wzorem y¤x·z.
W praktyce, wykonując na każdym etapie operacje klejenia niepełnego, można nie pisać terminów związanych z tymi operacjami, a jedynie zapisywać wyniki wszystkich możliwych klejeń całkowitych i połączeń, które nie biorą udziału w żadnym klejeniu.
Przykład 2. 3. 3. Niech funkcja f(x,y,z) będzie dana przez doskonały DNF f = x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z .
Następnie wykonując operacje sklejania a następnie elementarnej absorpcji mamy
fa = x ⋅ y ⋅(z ∨ z) ∨ y ⋅ z ⋅(x ∨ x) ∨ x ⋅ z ⋅(y ∨ y) = x ⋅ y ∨ y ⋅ z ∨ x ⋅ z
Aby uzyskać minimalny DNF ze zredukowanego DNF, stosuje się macierz Quine'a , który jest skonstruowany w następujący sposób. Nagłówki kolumn tabeli zawierają składniki idealnej jednostki DNF, a nagłówki wierszy zawierają proste implikacje powstałego skróconego DNF. W tabeli gwiazdkami zaznaczono te przecięcia wierszy i kolumn, dla których koniunkcja w nagłówku wiersza wchodzi w składową jednostki, jaką jest nagłówek kolumny.
Na przykład 2.3.3. Macierz Quine’a ma postać
W ślepym zaułku DNF wybierana jest minimalna liczba prostych implikantów, których rozłączenie zachowuje wszystkie składniki jednostki, tj. każda kolumna macierzy Quine'a zawiera gwiazdkę na przecięciu z wierszem odpowiadającym jednemu z wybrane implikanty. Jako minimalny DNF wybierany jest ślepy zaułek DNF, który ma najmniejszą liczbę wystąpień zmiennych.
W przykładzie 2.3.3, korzystając z macierzy Quine'a, stwierdzamy, że minimalny DNF danej funkcji wynosi x ⋅ y ¤ x ⋅ z.
Komentarz.
użyj f = f i praw De Morgana.
§ 2.4. mapy Carnota.
Innym sposobem uzyskania prostych formuł implikowanych z małą liczbą zmiennych (a co za tym idzie znalezienia minimalnego DNF) jest wykorzystanie tzw. map Carnota.
Mapa Carnota jest specjalny typ tabela upraszczająca proces wyszukiwania form minimalnych i z powodzeniem stosowana, gdy liczba zmiennych nie przekracza sześciu. Mapy Karnaugha dla funkcji zależnych od n zmiennych to prostokąt podzielony na 2 n komórek. Każda komórka diagramu jest powiązana z binarnym n-wymiarowym zbiorem. W wymagane kwadraty wpisuje się wartości danej funkcji f z tabeli prawdy, ale jeśli komórka odpowiada 0, to zwykle pozostaje pusta.
W tabeli 2.4.1. pokazuje przykład zaznaczenia mapy Karnaugha dla funkcji zależnej od trzech zmiennych. Dolne cztery komórki mapy odpowiadają zbiorom binarnym, w których zmienna X przyjmuje wartość 1, cztery górne komórki odpowiadają zbiorom, w których zmienna X przyjmuje wartość 0. Cztery komórki tworzące prawą połowę mapy odpowiadają zbiorom, w których zmienna y; przyjmuje wartość 1 itd. W tabeli 2.4.2. Pokazano oznaczenie mapy Karnaugha dla n=4 zmiennych.
Aby skonstruować minimalny DNF, wykonujemy procedura klejenia „1”. Sklejające się wartości „1” odpowiadają sąsiadującym komórkom, tj. komórki różniące się tylko wartością jednej zmiennej (na obrazie graficznym oddzielone linią pionową lub poziomą, z uwzględnieniem bliskości przeciwległych komórek skrajnych).
Proces wklejania „1” sprowadza się do łączenia pojedynczych komórek mapy Karnaugh w grupy i należy przestrzegać następujących zasad:
1. Liczbę komórek wchodzących w skład jednej grupy należy wyrazić jako wielokrotność liczby 2, tj. 2 m gdzie m=0,1,2,...
2. Każda komórka w grupie 2 m komórek musi mieć m sąsiadujących komórek w grupie.
3. Każda komórka musi należeć do co najmniej jednej grupy.
4. Każda grupa powinna zawierać maksymalną liczbę komórek, tj. żadna grupa nie powinna należeć do innej grupy.
5. Liczba grup powinna być minimalna.
Przeczytaj funkcję f według grupy klejenia odbywa się w następujący sposób: zmienne, które zapisują te same wartości w komórkach grupy klejenia wchodzą w koniunkcję, a wartości 1 odpowiadają samym zmiennym, a wartości 0 odpowiadają ich negacjom.
Przedstawiamy szablony pomagające w budowaniu pokrycia 1 (uważamy, że zmienne są takie same, ale nie będziemy ich pisać). Dla uproszczenia zapisu nie będziemy oznaczać zmiennych, choć zachowamy ich oznaczenia jak w tabelach 2.4.1, 2.4.2.
| 1 | 1 |
| 1 | 1 |
| F=Ÿy&x | |
| 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 |
| 1 | 1 | 1 |
| 1 |
F=Ÿz&Ÿy f=Ÿx&y
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | ||||
| 1 | 1 | 1 | 1 | ||||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
F=Ÿx&z f=y&w F=Ÿx&Ÿy
| 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | ||
| 1 | 1 |
F=Ÿy&Ÿw f=Ÿy&Ÿz F=Ÿz&Ÿx
| 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | ||||
| 1 | 1 | 1 | 1 |
F=y&z&w f=Ÿy&Ÿz&Ÿw F=x&y&Ÿz
| 1 | ||
| 1 | ||
| 1 | 1 | 1 |
| 1 |
Przykład 2.4.1. Zbuduj MDNF.
Najpierw sprawdzamy, czy są jakieś powłoki_ 1 z 16 komórek obejmujących co najmniej jedną odkrytą 1. Nie ma takich osłon. Przechodzimy do pokrycia 8 komórek. Zobaczmy, czy w 1 z 8 komórek znajdują się osłony zakrywające przynajmniej jedną odkrytą 1. Nie ma takich osłon. Przechodzimy do pokrycia 4 komórek. Zobaczmy, czy istnieją osłony 1 z 4 komórek zakrywające co najmniej jedną odkrytą 1. Istnieją dwa takie osłony. Przechodzimy do pokrycia 2 komórek. Jest tylko jedna taka powłoka. W ten sposób wszystkie 1 zostały zakryte. Następnie zobaczmy, czy uda nam się usunąć część pokrycia, tak aby wszystkie jednostki pozostały zakryte. Na koniec zapisujemy MDNF: f =x⋅z∨y⋅w∨y⋅z⋅w.
Komentarz. Aby skonstruować minimalną CNF funkcji f, wystarczy skonstruować minimalną DNF dla funkcji f, a następnie
użyj f = f i praw De Morgana.
Rozdział III. Algebra Zhegalkina.
Zbiór funkcji boolowskich zdefiniowany w bazie Zhegalkina S4=(∆,&,1) nazywany jest algebrą Zhegalkina.
Podstawowe właściwości.
1. przemienność
H1∆H2=H2∆H1, H1&H2=H2
2. skojarzenie
H1∆(H2∆H3)=(H1∆H2)∆H3, H1&(H2&H3)=(H1&H2)
3. rozdzielność
H1&(H2∆H3)=(H1&H2)∆(H1&H3);
4. własności stałych H&1=H, H&0=0, H∆0=H;
5. H∆H=0, H&H=H.
Oświadczenie 3.1.1. Wszystkie inne funkcje logiczne można wyrazić za pomocą operacji algebry Zhegalkina:
Ÿx=1∆x, x¤y=x∆y∆xy, x~y=1∆x∆y, xŘy=1∆x∆xy, x∞y=1∆x∆y∆xy, x|y= 1∆xy.
Definicja. Wielomian Zhegalkina (wielomian modulo 2) n zmiennych x 1 ,x 2 ,…,x n jest wyrażeniem postaci c0∆с1x1∆c2x2∆…∆cnxn∆c12x1x2∆…∆c12…nx1x2…xn, gdzie stałe z k może przyjmować wartości 0 lub 1.
Jeżeli wielomian Zhegalkina nie zawiera iloczynów poszczególnych zmiennych, wówczas nazywa się go liniowym (funkcją liniową).
Na przykład f=x∆yz∆xyz i f1=1∆x∆y∆z są wielomianami, przy czym drugi jest funkcją liniową.
Twierdzenie 3.1.1. Każda funkcja boolowska jest reprezentowana w postaci wielomianu Zhegalkina w unikalny sposób.
Przedstawmy główne metody konstruowania wielomianów Zhegalkina z danej funkcji.
1. Metoda niepewnych współczynników . Niech P(x 1 ,x 2 ,…,x n) będzie pożądanym wielomianem Zhegalkina realizującym zadaną funkcję f(x 1 ,x 2 ,…,xn). Zapiszmy to w formularzu
P= do 0 ∆c 1 x 1 ∆c 2 x 2 ∆…∆c n x n ∆c 12 x 1 x 2 ∆…∆c12… n x 1 x 2 …x n .
Znajdźmy współczynniki za pomocą k. W tym celu przypisujemy kolejno zmiennym x 1 , x 2 ,…, x n wartości z każdego wiersza tabeli prawdy. W rezultacie otrzymujemy układ 2 n równań z 2 n niewiadomymi, który ma jednoznaczne rozwiązanie. Po jego rozwiązaniu znajdujemy współczynniki wielomianu P(x 1 ,x 2 ,…,xn).
2. Metoda polegająca na przekształcaniu formuł na zbiorze spójników ( ÿ,&}. Skonstruuj wzór Ф na zbiorze spójników (Ÿ,&), realizując zadaną funkcję f(x 1 ,x 2 ,…,x n). Następnie zamień wszędzie podformuły postaci A na A∆1, otwórz nawiasy korzystając z prawa rozdzielności (patrz własność 3), a następnie zastosuj własności 4 i 5.
Przykład 3.1.1. Skonstruuj wielomian Zhegalkina dla funkcji f(x,y)=xŘy.
Rozwiązanie. 1 . (metoda nieokreślonych współczynników). Zapiszmy wymagany wielomian w postaci
P(x,y)= c 0 ∆c 1 x∆c 2 y∆c 12 xy Korzystanie z tabeli prawdy
| X | 0 | 0 | 1 | 1 |
| y | 0 | 1 | 0 | 1 |
| xŘy | 1 | 1 | 0 | 1 |
stwierdzamy, że f(0,0)=P(0,0)= c 0 =1, f(0,1)=P(0,1)= c 0 ∆ c 2 =1, f(1,0) =P(1,0)= do 0 ∆c 1 =0, f(1,1)=P(1,1)= do 0 ∆c 1 ∆c 2 ∆c 12 =1
Z tego, co konsekwentnie stwierdzamy, c 0 =1, c 1 =1, c 2 =0, c 12 =1. Zatem xŘy=1∆x∆xy (porównaj ze stwierdzeniem 3.1).
2. (Metoda konwersji formuły.) Mamy
x → y = x ∨ y = x ⋅ y = (x ⋅ (y ⊕ 1)) ⊕ 1 = 1 ⊕ x ⊕ x ⋅ y .
Należy zauważyć, że zaletą algebry Zhegalkina (w porównaniu do innych algebr) jest arytmetyka logiki, która umożliwia w prosty sposób przeprowadzanie transformacji funkcji Boole'a. Jego wadą w porównaniu z algebrą Boole'a jest uciążliwość formuł.
Rozdział IV. Sprawozdania. Predykaty.
§4.1. Sprawozdania.
Konstruując algebrę logiczną, zastosowaliśmy podejście funkcjonalne. Jednakże możliwe byłoby konstruktywne skonstruowanie tej algebry. Najpierw zdefiniuj obiekty badań (stwierdzenia), wprowadź operacje na tych obiektach i zbadaj ich właściwości. Podajmy formalne definicje.
Mówiąc Nazwijmy zdanie oznajmujące, co do którego można jednoznacznie stwierdzić, czy w określonym momencie jest ono prawdziwe (wartość I lub 1), czy fałszywe (wartość L lub 0). Na przykład „5 to liczba pierwsza”, „Naciśnięto klawisz Esc” itp. Stosowanie łączników „nie”, „i”, „lub”, „jeśli,... to”, „wtedy i tylko wtedy, gdy” (odpowiadają one operacjom „Ÿ”, „&”, „¤”, „Ř” , „~” » odpowiednio), można konstruować bardziej złożone wypowiedzi (zdania). W ten sposób zbudowana jest algebra zdań.
Aby uprościć zapis zdań złożonych, wprowadzono pierwszeństwo spójników: „Ÿ”, „&”, „¤”, „Ř”, „~”, co pomaga ominąć niepotrzebne nawiasy.
Proste stwierdzenia nazywamy zmiennymi zdaniowymi.
Wprowadźmy pojęcie formuły.
1. Zmienne zdaniowe są formułami.
2. Jeżeli A, B są wzorami, to wyrażenia ŸA, A⁄B, A¤B, AŘB, A~B są wzorami.
3. Wzory to wyłącznie wyrażenia skonstruowane zgodnie z ust. 1 i 2.
Nazywa się formuła, która przyjmuje wartość ORAZ dla wszystkich wartości zmiennych zdaniowych tautologia (lub ogólnie obowiązująca), i nazywa się formułę, która przyjmuje wartość A dla wszystkich wartości zmiennych zdaniowych sprzeczne (lub niemożliwe)
Opis właściwości algebry zdań jest podobny do opisu odpowiednich funkcji w algebrze Boole'a i pomijamy je.
§4.2. Predykaty. Operacje logiczne na predykatach.
Przedmiotem badań w tym rozdziale będą predykaty – mapowanie dowolnych zbiorów na zbiór instrukcji. Właściwie dokonujemy przejścia na nowy poziom abstrakcji, przejścia tego samego typu, jakie dokonano w szkole - od arytmetyki liczb rzeczywistych do algebry funkcji numerycznych.
Definicja 2.1 Niech x 1 ,x 2 ,…,xn będą symbolami zmiennych o charakterze dowolnym. Nazwiemy te zmienne zmiennymi podmiotowymi. Niech zbiory zmiennych (x 1 ,x 2 ,…,x n) należą do zbioru M=(M1,M2,…Mn), który nazwiemy obszarem przedmiotowym (tzn. x i œM i, gdzie Mi nazywane są dziedziną definicji zmiennej xi). Predykat lokalizacji n (predykat o n-miejscach), zdefiniowany w obszarze tematycznym M, jest funkcją logiczną, która przyjmuje wartość AND lub wartość L.
Przykład 4.2.1. D(x1,x2) = „Liczba naturalna x1 jest dzielona (bez reszty) przez liczbę naturalną x2.” - predykat dwumiejscowy zdefiniowany na zbiorze par liczby naturalne M=NäN. Oczywiście D(4,2) = I, D(3,5) = 0.
Przykład 4.2.2. Q(x) ==„x 2<-1, хœR» - одноместный предикат, определенный на множестве liczby rzeczywiste M=R. Jasne jest, że Q(1) = А, Q(5) = А i w ogóle predykat Q(x) jest identycznie fałszywy, tj.
Q(x) = А dla wszystkich xœR.
Przykład 4.2.3. B(x,y,z) = „x 2 + y 2 Predykat P zdefiniowany na M nazywa się identycznie prawdziwym, jeśli przyjmuje wartość ORAZ dla dowolnych wartości zmiennych podmiotowych; Predykat P nazywany jest identycznie fałszywym, jeśli przyjmuje wartość A dla dowolnych wartości zmiennych podmiotowych. Predykat Q z przykładu 4.2.2. jest identycznie fałszywe. Ponieważ predykaty są funkcjami z wartościami w zestawie instrukcji, w których wprowadzane są operacje logiczne, operacje te są naturalnie definiowane dla predykatów. Niech P i Q będą predykatami zdefiniowanymi na M. Następnie 1. ¬P(x, x,…, x n) = P(x, x,…, x) ∧ 1 2 n 1 2 n ∧ 1 2 n 3. (P ∨ Q)(x 1 ,x 2 ,…,x n) = P(x 1 ,x 2 ,…,x n) ∨ Q(x 1 ,x 2 ,…,x n) 4. (P → Q)(x 1 ,x 2 ,…,x n) = P(x 1 ,x 2 ,…,x n) → Q(x 1 ,x 2 ,…,x n) Predykaty P i Q, zdefiniowane na M nazywamy równoważnymi (zapisz P=Q) jeśli P(x 1 ,x 2 ,…,xn)=Q(x 1 ,x 2 ,…,xn) dla dowolnego zbioru (x 1 ,x 2 ,…, x n )
zmienne przedmiotowe z M .
Twierdzenie 4.2.1 Zbiór n-arnych predykatów zdefiniowanych na M tworzy algebrę predykatów Boole'a. Zatem obowiązują dla nich podstawowe równoważności (patrz §1.6). Niech P(x 1 ,x 2 ,…,xn) będzie n-argumentowym predykatem zdefiniowanym na M. Ustalmy x i = A. Zdefiniujmy (n-1)-ary predykat Q(x 1 ,x 2 ,…,xk-1, xk+1,xn) następująco: Q(x 1 ,x 2 ,…,xk-1,xk +1, xn)=P(x 1 ,x 2 ,…,xk1, A,xk+1,xn). Mówią, że predykat Q(x 1 ,x 2 ,…,xk-1, xk+1,xn) otrzymuje się z predykatu P(x 1 ,x 2 ,…,xn) poprzez ustalenie wartości i- zmienna: x i = A
. Definicja
4.3.1
. Niech P(x) będzie predykatem jednoargumentowym. Skojarzmy z nim zdanie oznaczone „xP(x) (czytaj „dla dowolnego x P(x)”), które jest prawdziwe wtedy i tylko wtedy, gdy P(x) jest identycznie prawdziwym predykatem. mówi się, że jest , że jest uzyskiwany z predykatu P poprzez dołączenie uniwersalnego kwantyfikatora do zmiennej x. Definicja 4.3.2. Niech P(x) będzie predykatem jednoargumentowym. Powiążmy to ze stwierdzeniem oznaczonym $xP(x) (czytaj: „istnieje x P(x)”), które jest fałszywe wtedy i tylko wtedy, gdy P(x) jest identycznie fałszywym predykatem. Mówi się, że stwierdzenie $xP(x) uzyskuje się z predykatu P poprzez dołączenie kwantyfikatora egzystencjalnego do zmiennej x. Notatka 1. Symbole " i $ dla kwantyfikatorów są odpowiednio odwróconymi literami łacińskimi A i E, które są pierwszymi literami angielskich słów Wszystko- Wszystko, Istnieć- istnieć. Uwaga 2. Instrukcje można uznać za predykaty niezawierające zmiennych, czyli predykaty zerowe (lub predykaty dowolnej lokalizacji). Niech P(x 1 ,x 2 ,…,xn) będzie n-argumentowym predykatem zdefiniowanym na M. Ustalmy w nim wartości zmiennych x 1 ,x 2 ,…,x k-1 ,x k +1,x n. Do otrzymanego predykatu jednoargumentowego Q(x k) dołączamy kwantyfikator uniwersalny (istnienia) i otrzymujemy stwierdzenie. Zatem ustalony zbiór wartości zmiennych x 1 ,x 2 ,…,x k-1 ,x k+1 ,x n jest powiązany ze stwierdzeniem wykorzystującym kwantyfikator uniwersalności (istnienia). Mówi się, że ten (n-1)-arny predykat zmiennych x 1 ,x 2 ,…,x k-1 ,x k+1 ,x n jest otrzymywany z pierwotnego predykatu P(x 1 ,x 2 ,…, x n) poprzez dodanie uniwersalności kwantyfikatora (istnienia) w k-tej zmiennej. Predykat ten oznaczamy: „x do P(x 1 ,x 2 ,…,x n) ($x do P(x 1 ,x 2 ,…,x n)). mówią, że jest ona związana kwantyfikatorem powszechności (istnienia). Przykład 4.3.1. Niech D(x1,x2) = „Liczba naturalna x1 jest podzielna (bez reszty) przez liczbę naturalną x2.” - predykat dwumiejscowy. Przypiszmy kolejno kwantyfikatory do jego zmiennych. Jest oczywiste, że 1) "x1"x2D(x1,x2)=0 2) "x2"x1D(x1,x2)=0 3) $x1$x2D(x1,x2)=1 4) $x2$x1D(x1,x2)=1 5) "x1$x2D(x1,x2)=1 6) $x2"x1D(x1,x2)=1 7) $x1"x2D(x1,x2) =0 8) "x1$x2D(x1,x2)=1. Zatem (porównując 7 i 8 w ostatnim przykładzie) udowodniliśmy twierdzenie: Zazwyczaj łączniki i kwantyfikatory są uporządkowane według priorytetu w następujący sposób: Ÿ, ", $, &, ¤, Ø, ~. Twierdzenie 4.3.1. Kwantyfikatory przeciwne, ogólnie rzecz biorąc, nie dojeżdżają. Twierdzenie 4.3.2.(podstawowe równoważności zawierające kwantyfikatory) Mają miejsce następujące równoważności: 1. Prawa De Morgana ∀ xP (x) = ∃x P(x) , ∃xP (x) = ∀ x P(x) 2. Przemienność ∀x∀yP(x,y) =∀y∀xP(x,y) , ∃x∃yP(x,y) =∃y∃xP(x,y) 3. Dystrybutywność ∀x(P(x)&Q(x)) =∀xP(x)&Q(x) , ∃x(P(x)∨ Q(x))=∃xP(x)∨ Q(x) 4. Ograniczenia działania kwantyfikatorów ∀x(P(x)∨Q(y))=∀xP(x)∨∀xQ(y) , ∃x(P(x)&Q(y) =∃xP(x)&∃xQ(y) 5. Dla dowolnego predykatu dwumiejscowego ∃y∀xP(x,y) →∀x∃yP(x,y) =1 Teoria formalna(Lub rachunek różniczkowy)
Y- Ten: 1 zestaw A
formowanie się postaci alfabet
;
1.
pęczek F
słowa w alfabecie A, F
à A
które nazywają się formuły
;
3. podzbiór B
formuły, B
à F
,
które nazywają się aksjomaty; 4. wiele relacji R
na zestawie formuł tzw reguły wnioskowania. Mnóstwo symboli A
może być skończony lub nieskończony. Zwykle do tworzenia symboli używa się skończonego zestawu liter, do których w razie potrzeby przypisane są liczby naturalne jako indeksy. Wiele formuł F
zwykle podawane w drodze definicji indukcyjnej, na przykład za pomocą gramatyki formalnej. Z reguły zbiór ten jest nieskończony. Zestawy A
I F
wspólnie ustalić język
,
Lub podpis
,
teoria formalna. Wiele aksjomatów B
może być skończony lub nieskończony. Jeżeli zbiór aksjomatów jest nieskończony, to z reguły określa się go za pomocą skończonego zbioru schematów aksjomatów i reguł generowania określonych aksjomatów ze schematu aksjomatów. Wiele reguł wnioskowania R
oczywiście, co do zasady. Zatem rachunek Y jest czwórka (A, F, B, R)
. Przez wyprowadzenie w rachunku różniczkowym Y jest ciągiem wzorów F 1 , F 2 ,…, Fn takim, że dla dowolnego k (1§k§n) wzór Fk jest albo aksjomatem rachunku Y, albo bezpośrednią konsekwencją dowolnych poprzednich wzorów uzyskanych na podstawie reguły wnioskowania . Wzór G nazywa się twierdzeniem rachunku różniczkowego Y (wyprowadzonym w Y lub dowodliwym w Y), jeśli istnieje wniosek F 1 , F 2 ,…,F n ,G, który nazywa się wyprowadzeniem wzoru G lub dowodem twierdzenia twierdzenie G. Zapisuje się to następująco: F 1, F 2,…, F n + G. Rachunek różniczkowy Y zwany spójny, jeśli nie wszystkie jego formuły można udowodnić. Można podać inną definicję spójności: Rachunek różniczkowy nazywa się niesprzecznym, jeśli nie można w nim jednocześnie wyprowadzić wzorów F i ŸF (negacja F). Rachunek różniczkowy Y zwany kompletny(lub adekwatne), jeśli każde prawdziwe stwierdzenie M odpowiada twierdzeniu teorii Y
. Teoria formalna Y zwany rozstrzygalny, jeśli istnieje algorytm, który dla dowolnej formuły teorii określa, czy wzór ten jest twierdzeniem teorii Y albo nie. Korzystając z pojęcia rachunku formalnego, definiujemy rachunek zdań (PS). Alfabet IW składa się z 1. listy A, B, Q, R, P i inne, ewentualnie z indeksami (które nazywane są zmiennymi zdaniowymi), 2. symbole logiczne(więzadła) Ÿ, &, ¤, Ø, 3. pomocnicze postacie
(,). Wiele formuł IV wyznacza się indukcyjnie: 1. wszystkie zmienne zdaniowe są wzorami IV; 2. jeśli A, B są wzorami IV ,
toŸA, A⁄B, A¤B, AŘB - wzoryIV ;
3. wyrażenie jest wzorem IV wtedy i tylko wtedy, gdy można to ustalić na podstawie punktów „1” i Zatem każda formuła IV jest konstruowana ze zmiennych zdaniowych przy użyciu łączników Ÿ, ⁄, ¤, Ø. W przyszłości przy pisaniu formuł będziemy pomijać niektóre nawiasy, stosując tę samą konwencję, co w poprzednim rozdziale. Aksjomaty IV to następujące wzory (dla dowolnych wzorów A,B,C) 2. (AŘB)Ř((AŘ(BŘC))Ř(AŘC)); 5. (AŘB)Ř((AŘC)Ř(AŘ(B⁄C))); 8. (AŘC)Ř((BŘC)Ř((A¤B)ŘC)); 9. (AŘB)Ř((AŸB)ŸA); Formuły te nazywane są schematami aksjomatów IV .
Podstawiając określone formuły do dowolnego schematu, uzyskuje się szczególny przypadek schematu aksjomatu. Reguła wnioskowania w IE obowiązuje zasada wnioskowania (modus ponens): jeśli A i AŘB są formułami wyprowadzalnymi, to B również jest wyprowadzalne Symbolicznie jest to napisane tak: A, A B →
B
. Na przykład, jeśli twierdzenia A⁄B i A⁄BŘ(AŘC) są dedukcyjne, to twierdzenie AŘC również można wyprowadzić zgodnie z regułą wnioskowania. Mówi się, że wzór G daje się wyprowadzić ze wzorów F 1 , F 2 ,…, F n (oznaczonych jako F 1 , F 2 ,…, F n +G), jeśli istnieje ciąg wzorów F 1 , F 2 ,… ,F k ,G , w którym dowolny wzór jest albo aksjomatem, albo należy do listy wzorów F 1,F 2,...,F n (zwanych hipotezami), albo jest otrzymywany z poprzednich wzorów zgodnie z regułą wnioskowanie. Wyprowadzenie wzoru G z „ (oznaczonego przez +G) jest równoważne temu, że G jest twierdzeniem IV. Przykład 5.2.1. Pokażemy, że wzór AŘA można wyprowadzić z IV. W tym celu skonstruujemy wyprowadzenie tego wzoru: 1) w aksjomacie 2 zamień B na AŘA, C na A. Otrzymujemy aksjomat (AŘ(AŘA))Ř((AŘ((AŘA)ŘA))Ř(AŘA)); 2) w aksjomacie 1 zastępujemy B przez A. Otrzymujemy AŘ(AŘA); 3) z 1 i 2 zgodnie z modus ponens wnioskujemy (AŘ((AŘA)ŘA))Ř(AŘA); 4) w aksjomacie 1 zastępujemy B przez AŘA. Otrzymujemy AŘ((AŘA)ŘA); 5) z ust. 3 i 4, zgodnie z regułą wnioskowania, +AŘA jest prawdziwe. Twierdzenie 5.2.1. 1. Jeżeli F 1 ,F 2 ,…,Fn,A,B są wzorami IV, Г=(F 1 ,F 2 ,…,Fn), Г+A, to Г,B+A. (można zwiększyć liczbę hipotez). 2. Wtedy i tylko wtedy, gdy F 1 ,F 2 ,…,F n +A, gdy F 1 ⁄F 2 ⁄…⁄F n +A (redukcja wielu hipotez do jednej). Twierdzenie 5.3.1. (twierdzenie o dedukcji) Jeśli Г,B+A, to Г+BøA, gdzie Г jest zbiorem pewnych formuł Г=(F 1 ,F 2 ,…,F n ). Wniosek 5.3.1. Wtedy i tylko wtedy, gdy F 1 , F 2 ,…,F n +A, kiedy Dowód. Niech F 1 , F 2 ,…,F n +A. Następnie, stosując twierdzenie o dedukcji, mamy F 1 , F 2 ,…,F n-1 +F n ØA. Podobnie F 1 ,F 2 ,…,F n-2 +F n 1Ř(F n ŘA) itd. Kontynuując proces wymaganą liczbę razy, otrzymujemy F 1 Ř(F 2 Ř…Ř(F n-1 Ř(F n ŘA))…) Aby udowodnić wystarczalność, załóżmy, że +B, gdzie B=F 1 Ø(F 2 Ø… Ø(F n-1 Ø(F n ØA))…). Skorzystajmy z Twierdzenia 5.2.1., punkt 1: F1+B .
Zgodnie z zasadą konkluzji otrzymujemy F 1 + (F 2 Ø… Ø(F n-1 Ø(F n ØA))…), Następnie po n krokach mamy F 1 ,F 2 ,…,F n +A . Zatem, dzięki Wnioskowi 5.3.1. sprawdzenie wyprowadzalności wzoru A ze wzorów F 1, F 2,…, F n sprowadza się do sprawdzenia dowodliwości wzoru F 1 Ř(F 2 Ř…Ř(F n-1 Ř(F n ŘA))…). Przypomnijmy, że wzór A nazywa się identycznie prawdziwym (lub tautologią), jeśli wartość wzoru A jest równa jedności dla dowolnego zestawu wartości zmiennych zdaniowych. Poniższe twierdzenie sprowadza weryfikację udowodnialności wzoru do sprawdzenia jego tożsamej prawdziwości. Twierdzenie 5.3.2. (o kompletności). Formułę A można udowodnić wtedy i tylko wtedy, gdy A jest identycznie prawdziwe (tautologia): +A ‹ A-tautologia. Aby więc stwierdzić, czy wzór jest dowodliwy, wystarczy sporządzić jego tablicę prawdy. Jak wiadomo, istnieje skuteczny algorytm konstruowania tabeli prawdy, a co za tym idzie, IV rozpuszczalny. Przykład 5.3.1. Udowodnimy, że P+P. Zgodnie z twierdzeniem o dedukcji jest to równoważne +(PŘP). Z kolei zgodnie z twierdzeniem o zupełności wystarczy udowodnić, że (РŘР) jest tautologią. Kompilowanie tabeli prawdy dla wzoru (РŘР) ,
Jesteśmy przekonani, że (РŘР) jest identycznie prawdziwe, a zatem możliwe do udowodnienia. Twierdzenie 5.3.3. (o spójności). Rachunek IW jest spójny. Dowód. Zgodnie z twierdzeniem o zupełności, żadna formuła, która nie jest identycznie prawdziwa, nie jest możliwa do udowodnienia w IW. Na przykład taką formułą jest formuła A⁄(ŸA). Zbiór formuł Г nazywa się kontrowersyjny
,
jeśli Г+А⁄(ŸА) .
Jeżeli Г jest sprzecznym zbiorem formuł, fakt ten będziemy oznaczać przez Г+. Oświadczenie
5.3.1.
Formuła A jest wyprowadzalna ze zbioru formuł Г wtedy i tylko wtedy, gdy zbiór Г(ŸA) jest sprzeczny. Automatyczne dowodzenie twierdzeń jest podstawą programowania logicznego, sztucznej inteligencji i innych współczesnych trendów w programowaniu. Ogólnie rzecz biorąc, może nie istnieć algorytm, dzięki któremu, mając dowolną formułę A, po skończonej liczbie kroków można określić, czy A można wyprowadzić w rachunku Y, czy nie. Jednakże dla niektórych prostych teorii formalnych (na przykład rachunku zdań) i niektórych prostych klas formuł (na przykład stosowanego rachunku predykatów z jednym predykatem jednoargumentowym) znane są algorytmy automatycznego dowodzenia twierdzeń. Poniżej, na przykładzie rachunku zdań, zarysowujemy podstawy metody rozstrzygającej – klasycznej i jednocześnie popularnej metody automatycznego dowodzenia twierdzeń. Przypomnijmy, że jeśli x jest zmienną logiczną, a σœ(0,1), to wyrażenie x σ = xx jeśli jeśli σσ == 10 lub x σ = 10 jeśli jeśli x x =≠σσ , nazywa się list. Nazywa się litery x i Ÿx przeciwnik.
Połączony zwane połączeniem liter. rozłączny zwane dysjunkcją liter. Niech D 1 = B 1 ∨ A, D 2 = B 2 ∨ A będą klauzulami. Nazywa się klauzulę B 1 ¤B 2 rozpuszczalnik klauzule D 1 i D 2 literą A i są oznaczone res A (D 1 , D 2). Rozwiązanie klauzul D 1 i D 2 oznacza rozwiązanie przez jakąś literę i jest oznaczone przez res(D 1 , D 2). Oczywiście res(A,ŸA)=0. Rzeczywiście, ponieważ A=A¤0 i ŸA=ŸA¤0, wówczas res(A,ŸA)=0¤0=0. Jeśli klauzule D 1 i D 2 nie zawierają kontrastujących znaków, to nie mają rozwiązań. Przykład 5.5.1. Jeśli re 1 =A¤B¤C, re 2 = ZA ∨ B ∨ Q, wtedy res A (D 1 ,D 2)=B¤C¤ B ¤Q, res B (D 1 ,D 2)=A¤C¤A¤Q, resC(D 1 ,D 2) nie istnieje. Oświadczenie 5.5.1. Jeśli res(D 1 , D 2) istnieje, to D 1 , D 2 + res(D 1 , D 2). Niech S=(D 1 ,D 2 ,…,Dn) będzie zbiorem klauzul. Ciąg wzorów F 1 , F 2 ,…, F n nazywa się zdecydowanym wyprowadzeniem z S, jeśli dla każdego wzoru F k spełniony jest jeden z warunków: 2. są j, k
Twierdzenie 5.5.1.
(o kompletności metody rozstrzygania). Zbiór klauzul S jest sprzeczny wtedy i tylko wtedy, gdy istnieje rozstrzygający wniosek z S, który kończy się na 0. Należy zauważyć, że metodę rozwiązywania można zastosować do sprawdzenia możliwości wyprowadzenia wzoru F z danego zbioru wzorów F 1, F 2,…, F n. Rzeczywiście, warunek F 1 ,F 2 ,…,F n +F jest równoważny warunkowi F 1 ,F 2 ,…,F n ,ŸF+ (wiele wzorów jest sprzecznych), co z kolei jest równoważne warunkowi Q+, gdzie Q=F 1 ⁄F 2 ⁄…⁄F n ⁄(ŸF). Sprowadźmy wzór Q do CNF: Q=D 1 ⁄D 2 ⁄...⁄Dm, następnie Q+ ‹D 1 ⁄D 2 ⁄...⁄Dm+ ‹ D 1 ,D 2 ,...,D m + . Zatem zadanie sprawdzenia wyprowadzalności F 1 , F 2 ,...,F n +F sprowadza się do sprawdzenia niespójności zbioru zdań S=(D 1 ,D 2 ,...,D m ) , co jest równoznaczne z istnieniem zadeklarowanego wniosku 0 z S. Przykład 5.5.2. Sprawdź stosunek AŘ(BŸC), CDŘE, ŸFŘD&(Ÿ)E + AŘ(BŸF) stosując metodę rozdzielczości. Zgodnie ze stwierdzeniem 5.3.1. muszę sprawdzić niespójność wielu formuł S = (AŘ(BŸC), CDŘE, ŸFŘD&(Ÿ)E, Ÿ(AŘ(BŸF))). Przedstawiamy wszystkie formuły z. S do KNF: S = (A ∨ B ∨ C,C ⋅ D ∨ E, F ∨ D ⋅ E, A ∨ B ∨ F) == (A ∨ B ∨ C, C ∨ D ∨ E, (F ∨ D) ⋅ (F ∨ E), ZA ⋅ B ⋅ F) . W ten sposób otrzymujemy zbiór klauzul S = (A ∨ B ∨ C, C ∨ D ∨ E,F ∨ D,F ∨ E,A,B, F) Skonstruujmy rozstrzygający wniosek z S kończącego się na 0: 1. res A (A ∨ B ∨ C,A) = B ∨ C ; 2. res B (B ∨ C,B) = C ; 3. res re (C ∨ re ∨ E,F ∨ re) = do ∨ mi ∨ fa ; 4. res E (C ∨ E ∨ F, F ∨ E) = C ∨ F ; 5. res C (C, C ∨ F) = F ; 6. res(F, F) = 0 . Zatem dochodzimy do wniosku, że wzór AŘ(BŘF) można wyprowadzić ze zbioru wzorów AŘ(BŸC), CDŘE, ŸFŘD&(Ÿ)E. Należy zauważyć, że metoda rozstrzygająca jest wystarczająca do odkrycia możliwej spełnialności danego zbioru klauzul S. W tym celu uwzględnimy w zbiorze S wszystkie klauzule otrzymane w wyniku rozwiązujących dedukcji z S. Z twierdzenia o kompletności metody rozstrzygającej wynika Wniosek 5.5.1. Jeśli zbiór klauzul S zawiera rozwiązania wszystkich swoich elementów, to S jest spełnialne wtedy i tylko wtedy, gdy 0–S. Cechą charakterystyczną nowoczesności jest powszechne wykorzystanie komputerów w rozwiązywaniu problemów (zadań) w różnych obszarach działalności człowieka. Najpierw jednak problem należy rozwiązać algorytmicznie, tj. należy podać formalną receptę, po której można uzyskać końcowy wynik rozwiązania wszystkich problemów danego typu (jest to intuicyjna, a nie ścisła koncepcja algorytmu). Na przykład algorytm znajdowania największego wspólnego dzielnika dwóch liczb naturalnych a, b w następujący sposób: 1) rozwiń numer A według czynników pierwszych; 2) powtórz krok 1 dla B
I przejdź do kroku 3; 3) skomponować iloczyn wspólnych czynników pierwszych z rozwinięć A I B o wskaźnikach równych najmniejszemu ze wskaźników włączenia do rozwinięć. Po przeanalizowaniu tego przykładu zwracamy uwagę na najważniejsze cechy (właściwości) algorytmu: 1.
Masowy charakter- możliwość zastosowania algorytmu nie do jednego problemu, ale do klasy problemów. 2.
Dyskrecja- przejrzysty podział na poszczególne etapy (kroki) algorytmu. 3.
Determinizm- taka organizacja etapów realizacji, w której zawsze wiadomo, jak dokonać przejścia z jednego etapu do drugiego. 4.
Kończyna- aby uzyskać wynik przy zastosowaniu algorytmu do rozwiązania konkretnego problemu, wykonywana jest skończona sekwencja kroków algorytmu: Należy zauważyć, że jeśli obecność algorytmu sama w sobie jest dowodem na istnienie algorytmu, to aby udowodnić jego nieobecność, konieczna jest ścisła matematyczna definicja algorytmu. Próby sformalizowania koncepcji algorytmu doprowadziły do powstania Maszyny Turinga, jako jakieś wyimaginowane urządzenie implementujące algorytm. Kolejnym krokiem w definiowaniu pojęcia algorytmu był jego wygląd funkcje rekurencyjne ,
jako funkcje formalizujące koncepcję algorytmu i realizujące intuicyjną koncepcję obliczalności. Wkrótce odkryto, że zbiór funkcji rekurencyjnych pokrywa się ze zbiorem funkcji obliczalnych na maszynach Turinga. Pojawiające się wówczas nowe koncepcje, mające na celu wyjaśnienie pojęcia algorytmu, okazały się równoznaczne z funkcjami obliczalnymi na maszynach Turinga, a więc z funkcjami rekurencyjnymi. Wynikiem toczącej się dyskusji na temat tego, czym jest algorytm, było stwierdzenie zwane obecnie tezą Churcha. Teza Churcha. Pojęcie algorytmu, czyli obliczalności przez jakieś urządzenie mechaniczne, pokrywa się z koncepcją obliczalności na maszynach Turinga (a zatem z koncepcją funkcji rekurencyjnej). Innymi słowy, algorytm to proces, który można przedstawić za pomocą diagramu funkcjonalnego i zaimplementować na jakiejś maszynie Turinga. Maszyna Turinga to (abstrakcyjne) urządzenie składające się z taśmy, urządzenia sterującego i głowicy odczytującej. Taśma jest podzielona na komórki. Każda komórka zawiera dokładnie jeden znak z alfabet zewnętrzny
A=(
0,
1,…,
jakiś ). Jakiś symbol (oznaczymy to Ÿ
) alfabetu A nazywa się pustą, a każda komórka zawierająca obecnie pusty znak nazywana jest pustą komórką (w tym momencie). Zakłada się, że taśma jest potencjalnie nieograniczona w obu kierunkach. Urządzenie sterujące w każdym momencie czasu znajduje się w pewnym stanie q j należącym do zbioru Q=(q 0 , q 1 ,..., q m )(m=l). Zbiór Q nazywa się alfabet wewnętrzny
.
Jeden z tych warunków (zwykle q 0) nazywa się final, a inny (zwykle q 1) - wstępny. Głowica czytająca przesuwa się wzdłuż taśmy tak, że w dowolnym momencie skanuje dokładnie jedną komórkę taśmy. Głowa może odczytać zawartość obserwowanej komórki i wpisać do niej zamiast obserwowanego symbolu jakiś nowy symbol z zewnętrznego alfabetu A(prawdopodobnie ten sam). Podczas pracy urządzenie sterujące w zależności od stanu w jakim się znajduje oraz symbolu widzianego przez głowę zmienia swój stan wewnętrzny Q. Następnie wydaje szefowi polecenie wydrukowania określonego znaku z zewnętrznego alfabetu w monitorowanej komórce A, a następnie nakazuje głowie, aby albo pozostała na miejscu, albo przesunęła się o jedną komórkę w prawo, albo przesunęła się o jedną komórkę w lewo. Po osiągnięciu stanu końcowego maszyna przestaje działać. Konfiguracja na taśmie (lub słowie maszynowym) nazywa się zbiorem utworzonym przez: 1) sekwencja A
ja (1)
, A
ja (2)
,...,A
Jest) znaków z alfabetu zewnętrznego A, nagrany w komórkach taśmowych, gdzie A
I
(1)
.- symbol zapisany w pierwszej komórce po lewej stronie itp. (każda taka sekwencja nazywa się jednym słowem), 2) stan pamięci wewnętrznej q r ; 3) numer k postrzegana komórka. Konfigurację maszyny napiszemy w następujący sposób: a , a , ..., a a i(r) a , a , ..., a i(1) i(2) i(r−1) q r i(r+1) i(r+2) i(s) Tutaj R- postrzegana komórka jest podświetlona jako ułamek. Jeśli maszyna jest w stanie wewnętrznym qi, akceptuje komórkę z symbolem ty, zapisuje symbol do tej komórki w następnym momencie r, przechodzi w stan wewnętrzny pytanie i przesuwa się po taśmie, po czym mówią, że maszyna wykonuje polecenie q ja i ty
Æ
q s a r S, gdzie symbol S może przyjmować jedną z następujących wartości: -1 – przesunięcie głowy w lewo; +1 - przesunięcie głowy w prawo; 0 – głowa pozostaje na miejscu. Wywoływana jest lista wszystkich poleceń (kwintów), które określają działanie maszyny Turinga program ten samochód. Program maszyny jest często podawany w formie tabeli. Czyli dla sytuacji opisanej powyżej w tabeli na skrzyżowaniu linie A
ty i kolumna qi będzie stać q s a r S(patrz tabela 6.2.1) Tabela 6.2.1. Jeśli program obejmuje samochody dla pary (
q ja, a ty
)
brakuje pięciu, następnie w tabeli na przecięciu linii ty i kolumna qi dodaje się myślnik. Więc, Maszyna Turinga jest z definicji, zestaw M=(A,Q,P), Gdzie A- alfabet zewnętrzny, Q— alfabet stanów wewnętrznych, P- programu. Jeżeli maszyna po rozpoczęciu pracy z zapisanym na taśmie słowem P osiągnie stan końcowy, wówczas zostaje wywołana dotyczy tego słowa. Efektem jego pracy jest słowo zapisane na taśmie w stanie ostatecznym. W przeciwnym razie mówi się, że maszyna nie ma zastosowania do słowa R. Przykład 6.2.1. Zbudujmy maszynę Turinga, która dodaje liczby naturalne zapisane w systemie liczb jednoargumentowych (czyli zapisane za pomocą jednego symbolu). |.
Na przykład 5=|||||.). Rozwiązanie. Weź pod uwagę alfabet A
= {|, +, ⁄}. Maszynę wyznacza następujący program: Zapiszmy konfiguracje, które powstają sekwencyjnie podczas pracy tej maszyny na słowie początkowym ||+ ||| , tj. 2+3. Tutaj zapisując konfigurację zastosujemy następującą konwencję: stan w jakim znajduje się maszyna zapisywany jest w nawiasie po prawej stronie za obserwowaną literą. Przykład 6.2.2. Zbuduj maszynę Turinga, która podwaja liczby naturalne zapisane w systemie liczb jednoargumentowych. Rozwiązanie. Skonstruujemy wymaganą maszynę w alfabecie A=(|, α, ⁄). Program dla takiej maszyny mógłby wyglądać następująco: Zastosujmy powstałą maszynę do słowa ||
. Wprowadzenie nowej litery α i zastąpienie oryginalnych |
na α pozwala odróżnić oryginał |
i nowy (przypisany) |
. Państwo q 1 zapewnia wymianę |
na α ,
państwo q 2 zapewnia wyszukiwanie α ,
przeznaczone do wymiany |
, oraz zatrzymanie maszyny w przypadku nie wykrycia α, q 3 zapewnia ukończenie |
w przypadku, gdy α zostało zastąpione przez |.
Umówmy się co do tego w tym akapicie 1. zbiór N liczb naturalnych zawiera 0 (zero), tj. N=(0,1,2,3,...); 2. Rozważane funkcje f=f(x 1 ,x 2 ,…,x n) są zdefiniowane tylko wtedy, gdy zmienne przyjmują wartości z N, tj. xiœN; 3. zakres wartości funkcji DŒN; 4. rozpatrywane funkcje f=f(x 1 ,x 2 ,…,x n) można częściowo zdefiniować, tj. nie jest zdefiniowany dla wszystkich zbiorów liczb naturalnych. Wprowadźmy pod uwagę proste funkcje o(x)=0, s(x)=x+1,
Jestem m n (x 1 ,..., x n)
=
x m Funkcje te można obliczyć za pomocą odpowiedniego urządzenia mechanicznego (na przykład maszyny Turinga). Zdefiniujmy operatory konstruujące nowe funkcje na podstawie jednej lub większej liczby podanych funkcji. Operator superpozycji. Niech funkcja f(x 1 ,x 2 ,…,x k) k zmiennych i k funkcji f 1 (x 1 ,x 2 ,…,x n),…,f k (x 1 ,x 2 ,…,x n) będzie równa biorąc pod uwagę n zmiennych. Superpozycją funkcji f,f 1 ,…,f k jest funkcja j(x 1 ,x 2 ,…,x n)= f(f 1 (x 1 ,x 2 ,…,x n),…,f k (x 1 ,x 2 ,…,x n)) Mówimy, że funkcję j otrzymujemy stosując operator superpozycji S k+1 do funkcji f,f 1 ,…,f k i zapisujemy j=S k+1 (f,f 1 ,…,f k) Na przykład S 2 (s, o)=s(o(x)), tj. funkcja identycznie równa 1, a S 2 (s,s)=s(s(x)) jest funkcją y(x)=x+2. Pierwotny operator rekurencji. Niech zostaną podane funkcje g(x 1 ,x 2 ,…,x n) i h(x 1 ,x 2 ,…,x n+2). Skonstruujmy funkcję f(x 1 ,x 2 ,…,x n+1) Niech wartości x 1 ,x 2 ,…,x n zostaną ustalone. Następnie zakładamy: f(x 1 ,x 2 ,…,x n ,0)= g(x 1 ,x 2 ,…,x n) fa 1 (x 1 ,x 2 ,…,x n ,y+1)= h(x 1 ,x 2 ,…,x n ,y, f(x 1 ,x 2 ,…,x n ,y)) Równości te definiują funkcję f(x 1 ,x 2 ,…,x n+1) jednoznacznie. Funkcję f nazywa się funkcją uzyskaną za pomocą pierwotnego operatora rekurencji R. Stosuje się zapis f=R(g,h). Indukcyjna definicja funkcji (zademonstrowana za pomocą prymitywnego operatora rekurencji) nie jest rzadkością w matematyce. Na przykład 1) stopień z wykładnikiem naturalnym wyznacza się indukcyjnie: A
0
=1, A n+ 1
= rz
ÿ A
; 2) silnia: 0!=1, (n+1)!= n!ÿ(n+1) itd. Definicja. Funkcje, które można otrzymać z najprostszych o(x)=0, s(x)=x+1, I m n (x 1 ,..., x n) = x m stosując operatory superpozycji i pierwotną rekurencję skończoną liczbę razy są nazywane pierwotnie rekurencyjne. Sprawdźmy, czy funkcja u(x,y)=x+y jest funkcją rekurencyjną pierwotną. Rzeczywiście mamy: u(x,0)=0, u(x,y+1)=x+y+1=u(x,y)+1. Jest to prymitywny schemat rekurencji, ponieważ x= I 1 1 (x) i u(x,y)+1=s(u(x,y))=S 2 (s,u). Tutaj g(x)= I 1 1 (x) i h(x,y,u)=s(u)=S 2 (s, I 3 3). Podobnie udowodniono, że funkcje m(x,y)=xÿy, d(x,y)=x y (zakładamy z definicji 0 0 =1), fakt(x)=x! i wiele innych jest prymitywnie rekurencyjnych. Notatka; że pierwotnie funkcje rekurencyjne są wszędzie zdefiniowane (to znaczy zdefiniowane dla wszystkich wartości ich argumentów). Rzeczywiście najprostsze funkcje o, s, I m n są wszędzie zdefiniowane, a zastosowanie operatorów superpozycji i prymitywnej rekurencji do wszędzie zdefiniowanych funkcji daje również wszędzie zdefiniowane funkcje. A więc funkcja taka jak = x - y, jeśli x ≥ y< y f(x,y) nie istnieje, jeśli x nie może być pierwotnie rekurencyjny. Nie mamy prawa rozważać tutaj funkcji f(x,y)=x-y, ponieważ wartości funkcji muszą być liczbami naturalnymi (a więc nie ujemnymi). Można jednak rozważyć funkcję ÷ y = 0x − y jeśli x x<≥y.y Sprawdźmy, czy jest to prymitywnie rekurencyjne. Udowodnimy najpierw, że funkcja j(x)=xπ1 jest funkcją rekurencyjną pierwotną. Rzeczywiście, j(0)=0. j(y+1)=(y+1)π1=y, co służy jako prymitywny schemat rekurencji dla funkcji xπ1. Wreszcie, xπ0=x, xπ(y+1)=(xπy)π1=j(xπy) to prymitywny schemat rekurencji dla xπy. Znacznie szerszą klasą funkcji niż pierwotne funkcje rekurencyjne jest klasa funkcji rekurencyjnych (patrz definicja poniżej). W literaturze funkcje te nazywane są również częściowo rekurencyjne .
Aby je wyznaczyć, wprowadzamy jeszcze jednego operatora. Operator minimalizacji. Niech będzie dana funkcja f(x 1 ,x 2 ,… ,x n ,x n+1). Ustalmy pewne wartości x 1 ,x 2 ,… ,x n pierwszych n zmiennych i obliczmy f(x 1 ,x 2 ,… ,x n ,0), f(x 1 ,x 2 ,… ,x n ,1 ), f(x 1 ,x 2 ,… ,x n ,2) itd. Jeśli y jest najmniejszą liczbą naturalną, dla której f(x 1 ,x 2 ,… X n ,y)=x n+1 (czyli wartości f(x 1 ,x 2 ,… ,x n ,0), f(x 1 ,x 2 ,… ,x n ,1),…,f( x 1, x 2,… X n ,y-1) wszystkie istnieją i nie są równe xn +1), wówczas dodajemy g(x 1 ,x 2 ,… X n,x n+1)=y. Zatem g(x 1 ,x 2 ,… ,x n ,x n+1)=min(y|f(x 1 ,x 2 ,…,x n ,y)=x n+1). Jeżeli taki y nie, wówczas uważamy, że f(x 1 ,x 2 ,… ,x n ,x n+1) nie jest zdefiniowane. Możliwe są zatem trzy przypadki: 1. f(x 1 ,x 2 ,… ,x n ,0), f(x 1 ,x 2 ,… ,x n ,1),…,f(x 1 ,x 2 ,… ,x n ,y-1) istnieją i nie są równe xn +1, oraz f(x 1 ,x 2 ,…,x n ,y)=x n+1 ; 2. f(x 1 ,x 2 ,… ,x n ,0), f(x 1 ,x 2 ,… ,x n ,1),…,f(x 1 ,x 2 ,… ,x n ,y-1) istnieją i nie są równe xn +1, ale f(x 1 ,x 2 ,…,x n ,y) nie istnieje; 3. f(x 1 ,x 2 ,… ,x n ,i) istnieją dla wszystkich i–N i są różne od xn +1. Jeżeli zachodzi przypadek 1, to g(x 1 ,x 2 ,… ,x n ,x n+1)=y, a jeśli przypadek 2 lub 3, to g(x 1 ,x 2 ,… ,x n , x n +1) nie jest zdefiniowane. Mówi się, że otrzymaną w ten sposób funkcję g uzyskuje się z f przy użyciu operatora minimalizacji M. Piszemy g= Mf. Operator minimalizacji jest oczywistym uogólnieniem operatora funkcji odwrotnej. Uogólnienie jest dość głębokie, gdyż funkcja f nie musi być różnowartościowa (w zmiennej x n+1) Definicja. Funkcje, które można wyprowadzić z najprostszych o(x)=0, s(x)=x+1,
Jestem m n (x 1 ,..., x n)
= x m wywoływanie operatorów superpozycji, rekurencji pierwotnej i operatorów minimalizacji skończoną liczbę razy rekurencyjne. Klasa funkcji rekurencyjnych jest szersza niż klasa pierwotnych funkcji rekurencyjnych, choćby dlatego, że zawiera nie tylko funkcje, które są wszędzie zdefiniowane. Udowodnimy na przykład, że funkcja = x - y, jeśli x ≥ y< y f(x,y) nie istnieje, jeśli x jest rekurencyjny. Rzeczywiście, f(x,y)=min(z| y+z=x), a wcześniej ustalono, że funkcja u(x,y)=x+y jest pierwotnie rekurencyjna. Funkcje rekurencyjne odzwierciedlają nasze intuicyjne zrozumienie funkcji, które może obliczyć jakieś urządzenie mechaniczne. W szczególności można je obliczyć na maszynach Turinga (patrz poprzedni akapit). Wręcz przeciwnie, każda funkcja, którą można obliczyć na maszynie Turinga, jest rekurencyjna. Nie będziemy tego sprawdzać, bo zajęłoby to zbyt dużo czasu i miejsca. Kompletny dowód można znaleźć na przykład w książce A.I. Maltseva „Algorithms and Recursive Functions”. Należy zauważyć, że nie każda funkcja argumentów naturalnych jest rekurencyjna, nawet nie każda funkcja pojedynczego argumentu. Istnienie funkcji nierekurencyjnych jest „matematycznym powodem” występowania problemów nierozwiązywalnych algorytmicznie. W różnych gałęziach matematyki istnieją problemy nierozwiązywalne algorytmicznie, tj. problemów, dla których nie ma algorytmu rozwiązania, i to nie dlatego, że jeszcze go nie wynaleziono, ale dlatego, że jest to w zasadzie niemożliwe. Algorytm należy oczywiście rozumieć w sensie maszyn Turinga i funkcji rekurencyjnych. Sformułujmy jeden z tych problemów Problem z zatrzymaniem maszyny Turinga. Maszyna Turinga to obiekt zdefiniowany przez skończoną liczbę parametrów. Wszystkie częściowe odwzorowania z jednego skończonego zbioru na inny można skutecznie przenumerować. Dlatego każdej maszynie Turinga można przypisać liczbę (liczbę naturalną). Niech T(n) będzie maszyną Turinga o liczbie n. Niektóre maszyny, które zaczynają pracować na pustym pasku, w końcu się zatrzymują, a inne działają przez czas nieokreślony. Powstaje problem: mając liczbę naturalną n, określ, czy maszyna Turinga T(n) uruchomiona na pustej taśmie zatrzyma się, czy nie. To zadanie algorytmicznie nierozstrzygalny. Oznacza to, że nie ma automatycznej procedury ,
dla każdego n decyduje, czy maszyna T(n) zatrzyma się, czy nie. Nie wyklucza to faktu, że dla konkretnej maszyny ustalimy, czy się zatrzyma, czy nie. Nie ma metody, która rozwiązałaby ten problem dla wszystkich maszyn jednocześnie .
Biorąc pod uwagę problem, jak znaleźć skuteczny algorytm, aby go rozwiązać? A jeśli zostanie znaleziony algorytm, jak można go porównać z innymi algorytmami, które rozwiązują ten sam problem? Jak ocenić jego jakość? Pytania tego typu interesują zarówno programistów, jak i osoby zajmujące się teoretycznymi badaniami informatyki. Istnieje wiele kryteriów oceny algorytmów. Najczęściej będzie nas interesować kolejność narastania czasu i pojemności pamięci potrzebnej do rozwiązania problemu wraz ze wzrostem ilości danych wejściowych. Chcielibyśmy powiązać z każdym konkretnym zadaniem liczbę, zwaną jej rozmiarem ,
co wyrażałoby miarę ilości danych wejściowych. Na przykład rozmiar problemu mnożenia macierzy może być największym rozmiarem macierzy czynnikowych. Nazywa się czas potrzebny algorytmowi jako funkcję wielkości problemu złożoność czasu ten algorytm. Nazywa się zachowanie tej złożoności w granicy wraz ze wzrostem rozmiaru problemu asymptotyczna złożoność czasowa
.
Podobnie możemy zdefiniować złożoność pojemnościowa i asymptotyczną złożoność pojemnościową. To asymptotyczna złożoność algorytmu ostatecznie determinuje rozmiar problemów, które można rozwiązać za pomocą tego algorytmu. Jeśli algorytm przetwarza dane wejściowe o rozmiarze n w czasie cÿn 2 , gdzie c -
pewną stałą, wówczas mówią, że złożoność czasowa tego algorytmu wynosi O(n 2) (czytaj „porządku en kwadrat”). Można by pomyśleć, że ogromny wzrost szybkości obliczeń spowodowany jest przez obecną generację cyfrową komputery, zmniejszy znaczenie wydajnych algorytmów. Dzieje się jednak odwrotnie. Ponieważ maszyny liczące stają się coraz szybsze i możemy rozwiązywać większe problemy, to złożoność algorytmu determinuje wzrost rozmiaru problemu, który można osiągnąć wraz ze wzrostem szybkości maszyny. Załóżmy, że mamy pięć algorytmów A1, A2,…, A5 z następującą złożonością czasową: Tutaj złożoność czasowa to liczba jednostek czasu wymaganych do przetworzenia danych wejściowych o rozmiarze n. Niech jednostką czasu będzie jedna milisekunda (1 sekunda = 1000 milisekund). Następnie algorytm A1 może przetworzyć dane wejściowe o rozmiarze 1000 w ciągu jednej sekundy, podczas gdy A5 może przetworzyć dane wejściowe o rozmiarze nie większym niż 9. W tabeli. 6.5.1. Podano rozmiary problemów, które można rozwiązać w ciągu jednej sekundy, minuty i godziny za pomocą każdego z tych pięciu algorytmów. Tabela 6.5.3. Załóżmy, że następna generacja komputerów będzie 10 razy szybsza od obecnej. W tabeli 6.5.2. pokazuje, jak wzrośnie rozmiar problemów, które możemy rozwiązać dzięki temu wzrostowi prędkości. Należy zauważyć, że dla algorytmu A5 dziesięciokrotne zwiększenie prędkości zwiększa rozmiar problemu, który można rozwiązać tylko o trzy jednostki (patrz ostatnia linia w tabeli 6.5.2.), podczas gdy dla algorytmu A3 rozmiar problemu jest ponad trzykrotny . Tabela 6.5.4. Zamiast efektu zwiększenia prędkości rozważmy teraz efekt zastosowania wydajniejszego algorytmu. Wróćmy do tabeli 6.5.1. Jeżeli za podstawę porównania przyjmiemy 1 minutę, to zastępując algorytm A4 algorytmem A3, możemy rozwiązać problem 6 razy większy, a zastępując A4 algorytmem A2 ,
możesz rozwiązać problem 125 razy większy. Wyniki te są znacznie bardziej imponujące niż 2-krotna poprawa osiągnięta dzięki 10-krotnemu zwiększeniu prędkości. Jeśli za podstawę porównania przyjmiemy 1 godzinę, różnica okaże się jeszcze bardziej znacząca. Z tego wnioskujemy, że asymptotyczna złożoność algorytmu służy jako ważna miara jakości algorytmu i miara, która może stać się jeszcze ważniejsza wraz z późniejszym wzrostem szybkości obliczeń. Pomimo tego, że główną uwagę zwraca się tutaj na porządek wzrostu wielkości, należy zrozumieć, że duży rząd wzrostu złożoności algorytmu może mieć mniejszą stałą multiplikatywną (stała C w definicji O(f(x))), niż niewielki rząd wzrostu złożoności innego algorytmu. W tym przypadku algorytm o szybko rosnącej złożoności może być preferowany w przypadku małych problemów - być może nawet w przypadku wszystkich problemów, które nas interesują. Załóżmy na przykład, że złożoność czasowa algorytmów A1, A2, A3, A4, A5 wynosi w rzeczywistości odpowiednio 1000n, 100nÿlog(n), 10n2, n3 i 2. n Wtedy A5 będzie najlepszy dla problemów o rozmiarze 2§n§9, A2 - dla problemów o rozmiarze 10§n§58, A1 – pod adresem 59§n§1024, oraz A1- przy n>1024.- 1. F.A. Novikov. Matematyka dyskretna dla programistów./ St. Petersburg: Peter, 2001, 304С. 2. S.V. Sudoplatow, E.V. Ovchinnikova. Elementy matematyki dyskretnej./ M., INFRA-M, Nowosybirsk, Wydawnictwo NSTU, 3. Y.M.Erusalimsky. Matematyka dyskretna / M., „Książka uniwersytecka”, 2001, 279 s. 4. A. Aho, J. Hopcroft, J. Ullman. Budowa i analiza algorytmów obliczeniowych. / M., Mir, 1979, 536С. 5. V.N.Nefedov, V.A.Osipova Kurs matematyki dyskretnej./ M., Wydawnictwo MAI, 1992, 264P.§4.3. Kwantyfikatory i ich własności.
Rozdział V. Teorie formalne.
§5.1. Definicja teorii formalnej.
§5.2. Rachunek zdań.
§5.3. Twierdzenie o dedukcji. Kompletność IV.
§5.4. Automatyczny dowód twierdzeń.
§5.5. Metoda rozwiązywania w IW.
Rozdział VI. Elementy teorii algorytmów.
§6.1. Definicja algorytmu.
§6.2. Maszyna Turinga.
q 0
…
qi
…
q m
…
ty
Q
S
A
rS
…
§6.3. Funkcje rekurencyjne
§6.4. Problemy nierozwiązywalne algorytmicznie.
§6.5. Algorytmy i ich złożoność.
LITERATURA.