Książki. Pobierz książki DJVU w formacie PDF za darmo

UNIWERSYTET TECHNICZNY KAZANIA im. A. N. Tupoleva

Sh. I. GALIEV

LOGIKA MATEMATYCZNA I TEORIA ALGORYTMÓW

INSTRUKTAŻ

Kazań 2002

Galiew Sz. I. Logika matematyczna i teoria algorytmów. – Kazań: Wydawnictwo KSTU im. A. N. Tupolew. 2002. - 270 s.

ISBN 5-93629-031-X

Podręcznik zawiera następujące sekcje. Logika zdań i predykatów z zastosowaniami, łącznie ze sposobem rozwiązywania i elementami jej realizacji w języku PROLOG. Rachunek klasyczny (zdania i predykaty) oraz elementy logik nieklasycznych: logika trójwartościowa i wielowartościowa, logika modalna, temporalna i rozmyta. Teoria algorytmów: algorytmy normalne, maszyny Turinga, funkcje rekurencyjne i ich zależności. Pojęcie złożoności obliczeniowej, różne (ze złożoności) klasy problemów i przykłady takich problemów.

Wszystkie rozdziały są dostępne pytania kontrolne i ćwiczenia, podane są opcje typowe zadania oraz testy do samokontroli opanowania materiału.

Podręcznik przeznaczony jest dla studentów uczelni technicznych specjalności 2201 na kierunku „Informatyka i Informatyka” i może być stosowany na specjalności 2202 oraz innych specjalnościach z tego zakresu.

WSTĘP

Logikę zwykle rozumie się jako naukę o metodach dowodzenia i obalania. Logika matematyczna to logika opracowana przy użyciu metod matematycznych.

Badając metody dowodu i obalania, logikę interesuje przede wszystkim forma uzyskania prawdziwych wniosków, a nie treść przesłanek i wniosków w konkretnym argumencie. Rozważmy na przykład następujące dwa wyniki:

1. Wszyscy ludzie są śmiertelni. Sokrates jest mężczyzną. Dlatego Sokrates jest śmiertelny.

2. Wszystkie kocięta uwielbiają się bawić. Mura jest kotkiem. Dlatego Mura uwielbia się bawić.

Obydwa wnioski mają tę samą postać: wszystkie A to B, C to A; dlatego C jest B. Wnioski te są prawdziwe ze względu na swoją formę, niezależnie od treści, niezależnie od tego, czy przyjęte przez nie przesłanki i wnioski są prawdziwe, czy fałszywe. Systematyczna formalizacja i katalogowanie właściwe sposoby rozumowanie jest jednym z głównych zadań logiki. Jeśli w tym przypadku zostanie zastosowany aparat matematyczny, a badania poświęcone będą przede wszystkim badaniu rozumowania matematycznego, to logika ta jest logiką matematyczną (logiką formalną). Ta definicja nie jest ścisłą (precyzyjną) definicją. Aby zrozumieć przedmiot i metodę logiki matematycznej, najlepiej zacząć ją studiować.

Logika matematyczna zaczęła nabierać kształtu dawno temu. Początki jej pomysłów i metod miały miejsce w Starożytna Grecja, Starożytne Indie I Starożytne Chiny z około VI wieku. pne mi. Już w tym okresie naukowcy próbowali ułożyć łańcuch dowodów matematycznych w taki łańcuch, aby przejście z jednego ogniwa do drugiego nie pozostawiało wątpliwości i zyskało powszechne uznanie. Już w najwcześniejszych rękopisach, jakie do nas dotarły, „kanon” matematycznego stylu prezentacji jest mocno ugruntowany. Następnie otrzymuje ostateczne uzupełnienie od wielkich klasyków: Arystotelesa, Euklidesa, Archimedesa. Pojęcie dowodu u tych autorów nie różni się od naszego.

Logika jako samodzielna nauka wywodzi się z badań Arystotelesa (384 – 322 p.n.e.). Wielki starożytny filozof Arystoteles dokonuje encyklopedycznej systematyzacji starożytna wiedza we wszystkich obszarach ówczesnej nauki. Badania logiczne Arystotelesa prezentowane są głównie w jego dwóch dziełach „Pierwsza analityka” i „Druga analityka”, zebranych pod wspólnym hasłem: Nazwa zwyczajowa„Organon” (instrument wiedzy).

Na szczególną uwagę bardzo ważne za powstanie i rozwój logiki matematycznej jedno z najwspanialszych osiągnięć w historii ludzkości, a mianowicie przekształcenie geometrii w dokładny system dedukcyjny w dziele Euklidesa (330–275 pne) „Principia”. To właśnie to podejście dedukcyjne, z jasną świadomością celów i metod, stworzyło podstawę rozwoju myśli filozoficznej i matematycznej w kolejnych stuleciach.

Duże znaczenie dla powstania i rozwoju logiki miały także osiągnięcia w algebrze (algebra Boole'a) i innych dyscyplinach matematycznych, w tym ponownie w geometrii (tworzenie geometrii nieeuklidesowej - geometria Łobaczewskiego - Gaussa - Bolyai). Krótka recenzja Tworzenie logiki matematycznej można znaleźć w.

W powstaniu i rozwoju logiki matematycznej uczestniczyło wielu, wielu naukowców, zarówno od czasów starożytnych, od średniowiecza, jak i czasów późniejszych.

Podstawowe i stosowane znaczenie logiki matematycznej

Zasadniczym znaczeniem logiki matematycznej jest uzasadnienie matematyki (analiza podstaw matematyki).

Wartość stosowana logiki matematycznej jest obecnie bardzo wysoka. Logika matematyczna jest wykorzystywana do następujących celów:

analiza i synteza (konstrukcja) komputerów cyfrowych i innych automatów dyskretnych, w tym systemów inteligentnych;

analiza i synteza języków formalnych i maszynowych, do analizy języka naturalnego;

analiza i formalizacja intuicyjnej koncepcji obliczalności;

wyjaśnienie istnienia mechanicznych procedur rozwiązywania problemów określonego typu;

analiza problemów złożoności obliczeniowej.

Również logika matematyczna okazała się ściśle powiązana z szeregiem zagadnień z zakresu językoznawstwa, ekonomii, psychologii i filozofii.

W podręczniku tym przedstawiono podstawowe pojęcia logiki matematycznej i teorii algorytmów. Materiał przedstawiony w instrukcji

odpowiada stanowi standard edukacyjny dla kierunku „Informatyka i Informatyka” i może być wykorzystany dla studentów studiujących na różnych specjalnościach na tym kierunku.

Przy pisaniu podręcznika korzystano z literatury i oczywiście korzystano także z innych źródeł. Na liście literatury znajdują się książki, z którymi warto zapoznać się dociekliwym i wymagającym studentem.

Podręcznik w każdym rozdziale zawiera pytania do samodzielnego sprawdzenia materiału teoretycznego oraz ćwiczenia mające na celu rozwinięcie umiejętności rozwiązywania problemów i pogłębienie wiedzy na prezentowany temat. Ponadto podręcznik zawiera opcje typowych zadań i testów umożliwiających samokontrolę opanowania materiału.

Proponowany podręcznik (wyd. 2, stereotyp) stanowi podstawę zestawu do zajęć z logiki matematycznej i teorii algorytmów, który zawiera także zbiór problemów (Igoshin V.I. Zagadnienia i ćwiczenia z logiki matematycznej i teorii algorytmów).

Szczegółowo zarysowano podstawy teorii, pokazano kierunki penetracji logiki w podstawy algebry, analizy, geometrii, przedstawiono czerpiąc z materiału kurs szkolny matematyka pod kątem jej analizy logicznej, scharakteryzowano związek logiki matematycznej z komputerami, informatyką, systemami sztuczna inteligencja.

Wstęp. Logika matematyczna w systemie współczesnej edukacji.
Logika i intuicja. Logika tradycyjna i logika matematyczna. Trochę historii. Logika matematyczna - logika czy matematyka? Logika matematyczna w nauczaniu matematyki. Logika matematyczna i współczesne komputery.
Rozdział I. Algebra zdań.
§ 1. Wyciągi i operacje na nich.
Pojęcie wypowiedzi. Negacja stwierdzenia. Połączenie dwóch zdań. Rozdzielenie dwóch zdań. Implikacja dwóch stwierdzeń. Równoważność dwóch stwierdzeń. Związki języka i operacji logicznych (język i logika). Ogólna perspektywa dla operacji logicznych.
§2. Wzory algebry zdań.
Budowa zdań złożonych. Pojęcie wzoru algebry zdań. Logiczne znaczenie zdania złożonego. Kompilacja tabel prawdy dla formuł. Klasyfikacja wzorów algebry zdań. Myślenie i logika matematyczna
§ 3. Tautologie algebry zdań.
O znaczeniu tautologii. Podstawowe tautologie. Podstawowe zasady otrzymywania tautologii.
§ 4. Równoważność logiczna wzorów.
Pojęcie równoważności wzorów. Znak równoważności formuł. Przykłady równoważnych wzorów. Transformacje równoważne wzorów. Równoważności w logice i tożsamości w algebrze.
§ 5. Formy normalne wzorów algebry zdań.
Pojęcie form normalnych. Idealne normalne formy. Reprezentacja wzorów algebry zdań za pomocą doskonałych rozłącznych form normalnych (PDN). Reprezentacja wzorów algebry zdań za pomocą doskonałych koniunkcyjnych form normalnych (PCN). Dwa sposoby zredukowania wzoru algebry zdań do doskonałej postaci normalnej
§ 6. Ciąg logiczny formuł.
Pojęcie konsekwencji logicznej. Znaki konsekwencji logicznej. Dwie właściwości o konsekwencji logicznej. Spójność i równoważność formuł. Zasady wnioskowania logicznego. Inny sposób sprawdzenia implikacji logicznych. Znajdowanie konsekwencji z danych przesłanek. Znalezienie przesłanek dla danej konsekwencji.
§ 7. Zastosowanie algebry zdań w praktyce logiczno-matematycznej.
Twierdzenia bezpośrednie i odwrotne. Warunki konieczne i wystarczające. Przeciwieństwo i odwrotność twierdzenia przeciwnego. Prawo kontrapozycji. Modyfikacja struktury twierdzenia matematycznego. Metody dowodzenia twierdzeń matematycznych. Rozumowanie dedukcyjne i indukcyjne. Prawidłowe i błędne rozumowanie dedukcyjne. Rozwiązywanie problemów logicznych. Zasada całkowitej dysjunkcji. Jedno uogólnienie zasady całkowitej alternatywy.
Rozdział II. Funkcje logiczne.
§8. Zbiory, relacje, funkcje.
Pojęcie zestawu. Inkluzja i równość zbiorów. Operacje na zbiorach. Relacje i funkcje binarne. Pojęcie relacji larowej.
§ 9. Funkcje logiczne jednego i dwóch argumentów.
Pochodzenie funkcji boolowskich. Funkcje logiczne z jednego argumentu. Funkcje logiczne z dwóch argumentów. Własności alternatywy, koniunkcji i negacji. Własności równoważności, implikacji i negacji. Wyrażanie niektórych funkcji logicznych za pomocą innych
§ 10. Funkcje logiczne n argumentów.
Pojęcie funkcji boolowskiej. Liczba funkcji logicznych. Wyrażanie funkcji boolowskich poprzez koniunkcję, alternatywę i negację. Funkcje logiczne i wzory algebry zdań. Formy normalne funkcji boolowskich.
§ 11. Układy funkcji boolowskich.
Kompletne układy funkcji boolowskich. Specjalne klasy funkcji boolowskich. Twierdzenie Posta o zupełności układu funkcji boolowskich
§ 12. Zastosowanie funkcji boolowskich w obwodach przekaźnikowo-stykowych.
Pomysł na aplikację. Dwa główne problemy teorii obwodów przekaźnikowych.
§ 13. Obwody styków przekaźnikowych w komputerach.
Binarny półsumator. Jednobitowy dodatek binarny. Szyfrator i deszyfrator.
§ 14. O niektórych innych zastosowaniach teorii funkcji boolowskich.
Diagnoza (rozpoznawanie) chorób. Rozpoznawanie wzorców.
Rozdział III. Sformalizowany rachunek zdań.
§ 15. System aksjomatów i teoria wnioskowania formalnego.
Początki aksjomatycznej teorii zdań: pojęcia początkowe, system aksjomatów, reguła wnioskowania. Pojęcie wnioskowania i jego właściwości. Twierdzenie o dedukcji i jego konsekwencjach. Zastosowanie twierdzenia o dedukcji. Wyprowadzone reguły wnioskowania
§ 16. Kompletność i inne właściwości sformalizowanego rachunku zdań
Dowodliwość wzoru i jego prawdziwość identyczna (składnia i semantyka). Lemat o dedukcyjności. Kompletność sformalizowanego rachunku zdań. Twierdzenie o adekwatności. Spójność sformalizowanego rachunku zdań. Rozstrzygalność sformalizowanego rachunku zdań
§ 17. Niezależność systemu aksjomatów sformalizowanego rachunku zdań.
Pojęcie niepodległości. Niezależność aksjomatu (A1). Niezależność aksjomatu (A2). Niezależność aksjomatu (A3). Niezależność układu aksjomatów
Rozdział IV. Logika predykatów.
§ 18. Podstawowe pojęcia związane z predykatami.
Pojęcie predykatu. Klasyfikacja predykatów. Zbiór prawdy predykatu. Równoważność i następstwo predykatów
§ 19. Operacje logiczne na predykatach.
Negacja predykatu. Koniunkcja dwóch predykatów. Zaprojektuj przejście do strony dikats. Własności negacji, koniunkcji i alternatywy. Implikacja i równoważność dwóch predykatów.
§ 20. Operacje kwantyfikatorowe na predykatach.
Kwantyfikator ogólny. Kwantyfikator istnienia. Kwantyfikatory numeryczne. Ograniczone kwantyfikatory. Kwadrat logiczny
§ 21. Formuły logiki predykatów.
Pojęcie formuły logicznej predykatu. Klasyfikacja formuł logicznych predykatów. Tautologie logiki predykatów
§ 22. Przekształcenia równoważne formuł i konsekwencja logiczna formuł w logice predykatów
Pojęcie równoważności wzorów. Zredukowana forma formuł logicznych predykatów. Wstępnie uwarunkowana postać normalna dla formuł logicznych predykatów. Logiczne następstwo formuł logicznych predykatów
§ 23. Problemy rozwiązania ogólnej ważności i spełnialności wzorów.
Stwierdzenie problemu i jego nierozwiązywalności w ogólna perspektywa. Rozwiązanie zadania dla wzorów na zbiorach skończonych. Przykład wzoru, który jest wykonalny na nieskończonym zbiorze i niemożliwy do zrealizowania na żadnym skończonym zbiorze. Problem rozwiązywania spełnialności: wpływ liczności zbioru i struktury formuły. Rozwiązanie problemu dla formuł zawierających tylko jednomiejscowe zmienne predykatowe. Problem rozwiązania ważności i liczności zbioru, na którym rozważana jest formuła. Rozwiązanie problemu dla formuł V i 3
§ 24. Zastosowanie logiki predykatów w praktyce logiczno-matematycznej.
Zapisywanie w języku logiki orzeczeń różnych zdań. Porównanie logiki predykatów i logiki zdań. Struktura twierdzeń matematycznych. Metody wnioskowania: Sylogistyka arystotelesowska. Sylogistyka arystotelesowska i logika predykatów. Teoretyczna interpretacja sylogistyki arystotelesowskiej. O innych sposobach rozumowania. Zasada całkowitej alternatywy w formie predykatu. Metoda (pełna) Indukcja matematyczna Warunki konieczne i wystarczające. Orzekaj logikę i ustawiaj algebrę.
§ 25. Sformalizowany rachunek predykatów.
Pojęcia początkowe (język sformalizowanego rachunku predykatów). System aksjomatów rachunku predykatów. Zasady wypłaty. Teoria wnioskowania formalnego.
Rozdział V. Nieformalne teorie aksjomatyczne.
§ 26. Metoda aksjomatyczna w matematyce i teoriach aksjomatycznych.
Pojęcie teorii aksjomatycznej. Jak powstają teorie aksjomatyczne. Przykłady teorii aksjomatycznych. Interpretacje i modele teorii aksjomatycznej.
§ 27. Właściwości teorii aksjomatycznych.
Konsystencja. Kategoryczny. Niezależność układu aksjomatów. Kompletność.
Rozdział VI. Formalne teorie aksjomatyczne.
§ 28. O formalnych teoriach aksjomatycznych.
O historii idei formalnej teorii aksjomatycznej. Pojęcie formalnej teorii aksjomatycznej. Język i metajęzyk, twierdzenia i metatwierdzenia teorii formalnej. Interpretacje i modele teorii formalnej. Wnioskowanie semantyczne. Metamatematyka (właściwości formalnych teorii aksjomatycznych). Sformalizowany rachunek zdań jako formalna teoria aksjomatyczna Formalizacja teorii sylogizmów arystotelesowskich.
§ 29. Właściwości sformalizowanego rachunku predykatów.
Uzasadnienie aksjomatyzacji Spójność sformalizowanego rachunku predykatów. Twierdzenie Gödla o istnieniu modelu. Kompletność i adekwatność sformalizowanego rachunku predykatów. Niekompletność sformalizowanego rachunku predykatów w sensie absolutnym i wąskim.Twierdzenie o zwartości.
§ 30. Teorie formalne pierwszego rzędu.
Teorie pierwszego rzędu z równością. O formalnych teoriach mnogości. O arytmetyce formalnej. O formalnych teoriach systemów liczbowych.O geometrii formalnej. O formalnych Analiza matematyczna. Ogólny pogląd na proces formalizacji teorii matematyki.Na granicach metody aksjomatycznej, metody formalizacji i logiki.
Rozdział VII. Elementy teorii algorytmów.
§31. Intuicyjne zrozumienie algorytmów.
Algorytmy są wszędzie wokół nas. Nieformalna koncepcja algorytmu. Konieczność wyjaśnienia pojęcia algorytmu.
§ 32. Maszyny Turinga.
Definicja maszyny Turinga.Zastosowanie maszyn Turinga do słów. Budowa maszyn Turinga. Funkcje obliczeniowe Turinga. Właściwa obliczalność funkcji na maszynie Turinga. Skład maszyn Turinga. Teza Turinga (główna hipoteza teorii algorytmów). Maszyny Turinga i nowoczesne komputery elektroniczne.
§ 33. Funkcje rekurencyjne.
Geneza funkcji rekurencyjnych. Podstawowe pojęcia teorii funkcji rekurencyjnych i tezy Churcha. Pierwotne funkcje rekurencyjne. Pierwotna rekursywność predykatów. Obliczalność Turinga prymitywnych funkcji rekurencyjnych. Funkcje Ackermanna. Operator minimalizacji. Ogólne funkcje rekurencyjne i częściowo rekurencyjne. Obliczalność Turinga funkcji częściowo rekurencyjnych. Częściowa rekursywność funkcji obliczalnych Turinga.
§34. Normalne algorytmy Markowa.
Podstawienia Markowa. Algorytmy normalne i ich zastosowanie do słów. Funkcje normalnie obliczalne i zasada normalizacji Markowa. Zbieżność klasy wszystkich funkcji obliczalnych normalnie z klasą wszystkich funkcji obliczalnych Turinga. Równoważność różnych teorii algorytmów.
§ 35. Rozwiązywalność i przeliczalność zbiorów.
§ 36. Nierozwiązywalne problemy algorytmiczne.
Numerowanie algorytmów. Numeracja maszyn Turinga. Istnienie funkcji nieobliczalnych Turinga. Problemy uznania samostosowalności i stosowalności. Problemy nierozwiązywalne algorytmicznie w ogólnej teorii algorytmów. Twierdzenie Raisa. Inne przykłady nierozstrzygalności algorytmicznej.
§ 37. Twierdzenie Gödla o niezupełności arytmetyki formalnej.
Formalne teorie aksjomatyczne i liczby całkowite. Arytmetyka formalna i jej własności. Twierdzenie Gödla o niezupełności. Gödel i jego rola w logice matematycznej XX wieku. .
Rozdział VIII. Logika matematyczna i informatyka, informatyka, sztuczna inteligencja.
* § 38. Logika matematyczna i oprogramowanie komputery.
Podstawą programowania jest teoria algorytmów i logika matematyczna. Opis programów komputerowych wykorzystujących logikę matematyczną. Opisz programowanie i przeanalizuj jego koncepcje za pomocą logiki matematycznej. Weryfikacja (dowód poprawności) programów z wykorzystaniem logiki matematycznej.
§ 39. Wykorzystanie komputerów do dowodzenia twierdzeń logiki matematycznej.
Program „Teoretyk logiki” i programy mu bliskie. Metoda rozwiązywania dowodzenia twierdzeń w rachunku zdań i rachunku predykatów.
§ 40. Od logiki matematycznej do programowania logicznego.
Powstanie języka PROLOG i jego rozwój. ogólna charakterystyka PROLOG Język Krótki opis PROLOG Język i przykłady. Obszary zastosowań języka PROLOG.
§41. Logika matematyczna i informatyka.
Ogólna koncepcja o bazie danych. Relacyjna baza danych i logika zapytań w niej zawarta.
§ 42. Logika matematyczna i systemy sztucznej inteligencji Historia rozwoju i przedmiot sztucznej inteligencji jako nauki. Reprezentacja wiedzy w systemach sztucznej inteligencji. Systemy eksperckie. Język PROLOG w systemach sztucznej inteligencji. Czy maszyna może myśleć?
Wniosek: Czy logika jest wszechmocna w znajomości praw myślenia?
Bibliografia.

Logika i intuicja.
Aktywność umysłowa człowieka jest złożonym i wieloaspektowym procesem zachodzącym zarówno na poziomie świadomym, jak i nieświadomym (podświadomym). Jest to najwyższy poziom poznania człowieka, umiejętność adekwatnego odzwierciedlania obiektów i zjawisk rzeczywistości, tj. do znalezienia prawdy.

Logika i intuicja to dwie przeciwstawne i nierozerwalnie powiązane właściwości ludzkiego myślenia. Myślenie logiczne (dedukcyjne) różni się tym, że zawsze prowadzi od prawdziwych przesłanek do prawdziwego wniosku, bez polegania na doświadczeniu, intuicji i innych. czynniki zewnętrzne. Intuicja (od łacińskiego intuitio – „dokładne badanie”) to umiejętność zrozumienia prawdy poprzez bezpośrednie jej obserwowanie bez uzasadnienia przy użyciu logicznie rygorystycznego dowodu. Intuicja jest więc swego rodzaju antypodą, przeciwwagą dla logiki i rygoru.

Logiczna część procesu myślowego zachodzi na poziomie świadomości, część intuicyjna – na poziomie podświadomości.
Rozwój nauki, a zwłaszcza matematyki, jest nie do pomyślenia bez intuicji. W wiedzy naukowej istnieją dwa rodzaje intuicji1: intuicja-osąd i intuicja-zgadywanie. Sąd-intuicja (lub filozoficzny sąd-intuicja) charakteryzuje się tym, że w tym przypadku bezpośrednie poznanie prawdy, obiektywne powiązanie rzeczy odbywa się nie tylko bez logicznie ścisłego dowodu, ale taki dowód dla danej prawdy nie istnieje i w zasadzie nie może istnieć. Ocena intuicji dokonywana jest jako pojedynczy (jednorazowy) syntetyczny akt integralny o charakterze uogólniającym. Taka właśnie jest natura logicznie nieudowadnialnych twierdzeń w tezach Turinga, Churcha i Markowa rozpatrywanych w teorii algorytmów.

Pobierz e-book za darmo w wygodnym formacie, obejrzyj i przeczytaj:
Pobierz książkę Logika matematyczna i teoria algorytmów, Igoshin V.I., 2008 - fileskachat.com, szybkie i bezpłatne pobranie.

Federalna Agencja Edukacji

TOMSK PAŃSTWOWY UNIWERSYTET SYSTEMÓW KONTROLI I ELEKTRONIKI RADIOWEJ (TUSUR)

Katedra Automatyzacji Przetwarzania Informacji

Potwierdzam:

Głowa dział IDF

Profesor

Tak. Echłakow

„__” _____________2007

Wytyczne

do wdrożenia praktyczna praca przez dyscyplinę

„Logika matematyczna i teoria algorytmów”

dla studentów specjalności 230102 -

„Zautomatyzowane systemy przetwarzania i kontroli informacji”

Twórcy:

Sztuka. wykładowca na wydziale IDF

TO. Peremityna

Tomsk – 2007

Lekcja praktyczna nr 1 „Wzory algebry zdań” 3

Lekcja praktyczna nr 2 „Przekształcenia równoważne wzorów algebry zdań” 10

Lekcja praktyczna nr 3 „Formy normalne formuł” 12

Lekcja praktyczna nr 4 „Logiczne rozumowanie” 14

Lekcja praktyczna nr 5 „Wzory logiki predykatów” 18

Praktyka nr 6 Funkcje logiczne 23

Praktyka nr 7 Funkcje częściowo rekurencyjne 28

Ćwiczenie nr 8 Maszyny Turinga 34

Lekcja praktyczna nr 1 „Wzory algebry zdań”

Doktryna zdań - algebra zdań, czyli algebra logiki - jest najprostszą teorią logiczną. Atomowe pojęcie algebry zdań jest oświadczenie - zdanie oznajmujące, w stosunku do którego stwierdzenie o jego prawdziwości lub fałszywości ma sens.

Przykład prawdziwego stwierdzenia: „Ziemia kręci się wokół słońca”. Przykład fałszywego stwierdzenia: „3 > 5”. Nie każde zdanie jest stwierdzeniem; zdania nie obejmują zdań pytających i wykrzyknikowych. Zdanie „Owsianka to smaczne danie” nie jest stwierdzeniem, ponieważ nie można osiągnąć konsensusu co do tego, czy jest ono prawdziwe, czy fałszywe. Zdanie „Na Marsie jest życie” należy uznać za stwierdzenie, ponieważ obiektywnie jest ono albo prawdziwe, albo fałszywe, chociaż nikt jeszcze nie wie, które.

Ponieważ przedmiotem badań logiki są tylko wartości logiczne zdań, wprowadzono dla nich oznaczenia literowe A, B, ... lub X, Y....

Każde stwierdzenie jest uważane za prawdziwe lub fałszywe. Dla zwięzłości zamiast wartości prawdziwej napiszemy 1, a zamiast wartości fałszywej 0. Na przykład X = „Ziemia kręci się wokół Słońca” i Y = „3 > 5”, gdzie X = 1 i Y = 0. Zdanie nie może być jednocześnie prawdziwe i fałszywe.

Instrukcje mogą być proste lub złożone. Stwierdzenia „Ziemia krąży wokół Słońca” i „3 > 5” są proste. Zdania złożone tworzy się z prostych przy użyciu spójników języka naturalnego (rosyjskiego) NIE, I, LUB, JEŚLI-WTEDY, WTEDY-I-TYLKO-WTEDY. W przypadku stosowania oznaczeń literowych w instrukcjach łączniki te są zastępowane specjalnymi symbolami matematycznymi, które można uważać za symbole operacje logiczne.

Poniżej Tabela 1 przedstawia opcje symboli oznaczających łączniki oraz nazwy odpowiednich operacji logicznych.

Odmowa (inwersja). X jest stwierdzeniem, które jest prawdziwe wtedy i tylko wtedy, gdy X fałsz (oznaczony przez lub , brzmi: „nie X” lub „To nieprawda, że X”).

Spójnik
dwa zdania to zdanie, które jest prawdziwe wtedy i tylko wtedy, gdy oba zdania są prawdziwe X I Y. Ta operacja logiczna odpowiada łączeniu zdań spójnikiem „i”.

Dysjunkcja
dwa stwierdzenia X I Y Zdanie nazywa się fałszywym wtedy i tylko wtedy, gdy obydwa stwierdzenia są fałszywe X I Y FAŁSZ. W mowie potocznej ta operacja logiczna odpowiada spójnikowi „lub” (a nie wyłącznemu „lub”).

Przez implikację dwa stwierdzenia X I Y jest zdaniem fałszywym wtedy i tylko wtedy, gdy X prawda, ale Y– fałsz (oznaczone
; czyta „ X pociąga za sobą Y", "Jeśli X, To Y„). Operandy tej operacji mają specjalne nazwy: X- pakiet, Y- wniosek.

Równorzędność dwa stwierdzenia X I Y jest stwierdzeniem, które jest prawdziwe wtedy i tylko wtedy, gdy wartości prawdy są prawdziwe X I Y są takie same (oznaczenie:
).

Tabela 1. Operacje logiczne

Operandy operacji logicznych mogą przyjmować tylko dwie wartości: 1 lub 0. Dlatego każdą operację logiczną , &, , ,  można łatwo określić za pomocą tabeli, wskazując wartość wyniku operacji w zależności od wartości operandów. Ta tabela nazywa się tabela prawdy (Tabela 2).

Tabela 2. Tabela prawdy operacji logicznych

Za pomocą zdefiniowanych powyżej operacji logicznych można budować na podstawie prostych zdań formuły logiki zdań , reprezentujące różne instrukcje złożone. Logiczne znaczenie instrukcji złożonej zależy od struktury instrukcji wyrażonej wzorem i wartości logicznych tworzących ją instrukcji elementarnych.

W celu systematycznego badania formuł wyrażających stwierdzenia wprowadzono instrukcje zmienne P., P 1 , P 2 , ..., P N, przyjmując wartości ze zbioru (0, 1).

Formuła logiki zdań F (P 1 , P 2 ,..., P N) nazywa się tautologią lub identyczne z prawdą , jeśli jego wartość ma dowolne wartości P 1 , P 2 ,..., P N jest 1 (prawda). Wywoływane są formuły, których wartość jest prawdziwa dla co najmniej jednego zestawu zmiennych wykonalny . Wywoływane są formuły, których wartość jest fałszywa dla dowolnej wartości zmiennej sprzeczności (identycznie fałszywe, niemożliwe).

Autor: Guts A.K.
Wydawca: O.: Dziedzictwo
Rok wydania: 2003
Strony: 108
ISBN 5-8239-0126-7
Czytać:
Pobierać: matematicheskayalogika2003.djvu

WYDZIAŁ INFORMATYKI UNIWERSYTETU PAŃSTWOWEGO W OMSK
CYBERNETYKA
AK Wnętrzności
Logika matematyczna i teoria algorytmów
Omsk 2003
VVK 60 UDC 53:630.11
Guts A.K. Logika matematyczna i teoria algorytmów: Instruktaż. -
Omsk: Wydawnictwo Heritage. Dialog-Syberia, 2003. - 108 s.
ISBN 5 - 8239 - 0126 - 7
Podręcznik poświęcony jest prezentacji podstaw logiki i teorii matematycznej
algorytmy. Podstawą podręcznika są wygłoszone notatki z wykładów
studenci drugiego roku wydziału informatyki w Omsku
Uniwersytet stanowy w 2002.
Dla studentów studiujących na specjalności 075200 – „Komputer
bezpieczeństwo” i specjalność 220100 – „Komputery,
kompleksy, systemy i sieci.”
ISBN 5 - 8239 - 0126 - 7
(c) Uniwersytet Państwowy w Omsku, 2003
Spis treści
Logika 7
1 Logika klasyczna 8
1.1. Logika zdań............................................ 8
1.1.1. Oświadczenia............................................ 8
1.1.2. Podstawowe prawa logiki............................ 9
1.1.3. Paradoks logiczny Russella........... 10
1.1.4. Algebra (logika) zdań .................. 11
1.1.5. Schematy przekaźników............................ 12
1.1.6. Wzory równoważne............................ 14
1.1.7. Algebra Boole’a........................... 15
1.1.8. Wzory prawdziwe i powszechnie obowiązujące.............. 15
1.1.9. Problem rozwiązywalności............................ 15
1.1.10. Logiczna konsekwencja............................ 16
1.1.11. Sylogizmy.................................. 17
1.2. Logika predykatowa............................................ 17
1.2.1. Predykaty i formuły............................ 18
1.2.2. Interpretacje .................................. 19
1.2.3. Prawdziwość i spełnialność wzorów. Modele,
ważność ogólna, konsekwencja logiczna............ 20
1.2.4. Gottlob Frege........................... 21
1.2.5. Funkcje Skolemova
i skolemizacja formuł............................ 22
1.3. Metoda rozstrzygania............................................ 25
1.3.1. Metody rozwiązań w logice
oświadczenia............................ 25
1.3.2. Metody rozwiązań w logice
predykaty............................................ 29
3
4
Spis treści
2 Teorie formalne (rachunek różniczkowy) 31
2.1. Definicja teorii formalnej, czyli rachunku różniczkowego. . 32
2.1.1. Dowód. Spójność teorii.
Kompletność teorii........................................... 32
2.2. Rachunek zdań........................... 33
2.2.1. Zasady języka i derywacji rachunku zdań
............................................. 33
2.2.2. Przykład dowodu twierdzenia............................ 35
2.2.3. Kompletność i spójność
Rachunek zdań............................ 36
2.3. Rachunek predykatów .................................. 37
2.3.1. Język i zasady wnioskowania rachunku predykatów 37
2.3.2. Kompletność i spójność
rachunek predykatów........................... 39
2.4. Arytmetyka formalna............................ 39
2.4.1. Teorie egalitarne........................... 39
2.4.2. Język i zasady wyprowadzania arytmetyki formalnej
.............................................. 39
2.4.3. Spójność formalna
arytmetyka. Twierdzenie Gentzena........... 40
2.4.4. Twierdzenie Gödla o niezupełności........................... 41
2.4.5. Kurt Gödel........................... 42
2.5. Automatyczne wyprowadzanie twierdzeń............................ 43
2.5.1. S.Yu. Masłow........................... 43
2.6. Programowanie logiczne............................ 45
2.6.1. Program logiczny........................... 46
2.6.2. Logiczne języki programowania.... 49
3 Logiki nieklasyczne 50
3.1. Logika intuicjonistyczna........................... 50
3.2. Logika rozmyta........................... 51
3.2.1. Podzbiory rozmyte........................... 51
3.2.2. Operacje na rozmytych
podzbiory............................................ 52
3.2.3. Właściwości zbioru rozmytego
podzbiory............................................ 53
3.2.4. Rozmyta logika zdań............................ 54
3.2.5. Rozmyte obwody przekaźników........... 56
3.3. Logiki modalne.................................. 56
3.3.1. Rodzaje modalności .................................. 57
Spis treści
5
3.3.2. Rachunek 1 i T (Feis-von Wright)............ 57
3.3.3. Rachunek S4, S5
i rachunek Brouwera........................... 58
3.3.4. Znaczenie wzorów............................ 59
3.3.5. Semantyka Kripkego........................... 60
3.3.6. Inne interpretacje modałów
znaki............................ 62
3.4. Georg von Wright........................... 62
3.5. Logika czasowa............................ 62
3.5.1. Logika temporalna Pryora........................... 63
3.5.2. Logika temporalna Lemmona........................... 64
3.5.3. Logika temporalna von Wrighta........... 64
3.5.4. Aplikacja logiki rozrządu
do programowania............................ 65
3.5.5. Logika temporalna Pnuelego................. 67
3.6. Logiki algorytmiczne.................................. 70
3.6.1. Zasady konstrukcyjne
1 >

Książki. Pobierz książki DJVU w formacie PDF za darmo. Bezpłatny Biblioteka Cyfrowa
AK Guts, Logika matematyczna i teoria algorytmów

Można (program zaznaczy żółty)
Możesz zobaczyć listę książek o wyższej matematyce posortowaną alfabetycznie.
Możesz zobaczyć listę książek o wyższej fizyce, posortowaną alfabetycznie.

• Pobierz książkę za darmo, tom 556 KB, format djvu (nowoczesny podręcznik)

Panie i Panowie!! Aby pobrać pliki publikacji elektronicznych bez „błędów” należy kliknąć na podkreślony link z plikiem Prawy przycisk myszy wybierz polecenie "Zapisz cel jako..." („Zapisz obiekt jako…”) i zapisz plik publikacji elektronicznej na komputerze lokalnym. Publikacje elektroniczne są zwykle prezentowane w formatach Adobe PDF i DJVU.

I. Logika
1. Logika klasyczna
1.1. Logika zdań
1.1.1. Sprawozdania
1.1.2. Podstawowe prawa logiki
1.1.3. Paradoks logiczny Russella
1.1.4. Algebra zdań (logika)
1.1.5. Schematy przekaźników
1.1.6. Równoważne formuły
1.1.7. Algebra Boole’a
1.1.8. Prawdziwe i ogólnie obowiązujące formuły
1.1.9. Problem rozwiązywalności
1.1.10. Logiczna konsekwencja
1.1.11. Sylogizmy
1.2. Logika predykatów
1.2.1. Predykaty i formuły
1.2.2. Interpretacje
1.2.3. Prawdziwość i spełnialność wzorów. Modele, ważność ogólna, konsekwencja logiczna
1.2.4. Gottloba Frege’a
1.2.5. Funkcje Skolemova
i skolemizacja formuł
1.3. Metoda rozwiązywania
1.3.1. Metoda rozstrzygania w logice zdań
1.3.2. Metoda rozwiązywania w logice predykatów

2. Teorie formalne (rachunek różniczkowy)
2.1. Definicja teorii formalnej, czyli rachunku różniczkowego
2.1.1. Dowód. Spójność teorii. Kompletność teorii
2.2. Rachunek zdań
2.2.1. Zasady języka i derywacji rachunku zdań
2.2.2. Przykład dowodu twierdzenia
2.2.3. Kompletność i spójność rachunku zdań
2.3. Rachunek predykcyjny
2.3.1. Język i zasady wnioskowania rachunku predykatów
2.3.2. Kompletność i spójność rachunku predykatów
2.4. Arytmetyka formalna
2.4.1. Teorie egalitarne
2.4.2. Język i zasady wyprowadzania arytmetyki formalnej
2.4.3. Spójność arytmetyki formalnej. Twierdzenie Gentzena
2.4.4. Twierdzenie Gödla o niezupełności
2.4.5. Kurta Gödla
2.5. Automatyczne wyprowadzanie twierdzeń
2.5.1. S.Yu. Masłow
2.6. Programowanie logiczne
2.6.1. Program logiczny
2.6.2. Języki programowania logicznego

3. Logiki nieklasyczne
3.1. Logika intuicjonistyczna
3.2. Logika rozmyta
3.2.1. Rozmyte podzbiory
3.2.2. Operacje na podzbiorach rozmytych
3.2.3. Własności zbioru rozmytych podzbiorów
3.2.4. Rozmyta logika zdań
3.2.5. Rozmyte schematy przekaźników
3.3. Logika modalna
3.3.1. Rodzaje modalności
3.3.2. Rachunek 1 i T (Feis-von Wright)
3.3.3. Rachunek S4, S5 i rachunek Wrauera
3.3.4. Znaczenie formuł
3.3.5. Semantyka Kripkego
3.3.6. Inne interpretacje modałów
3.4. Georga von Wrighta
3.5. Logika temporalna
3.5.1. Temporalna logika Priora
3.5.2. Temporalna logika Lemmona
3.5.3. Temporalna logika von Wrighta
3.5.4. Zastosowanie logiki taktowania w programowaniu
3.5.5. Logika temporalna Pnuelego
3.6. Logika algorytmiczna
3.6.1. Zasady konstrukcji logiki algorytmicznej
3.6.2. Charlesa Hoare’a
3.6.3. Logika algorytmiczna Hoare’a

II. Algorytmy
4. Algorytmy
4.1. Pojęcie algorytmu i funkcji obliczeniowej
4.2. Funkcje rekurencyjne
4.2.1. Pierwotne funkcje rekurencyjne
4.2.2. Funkcje częściowo rekurencyjne
4.2.3. Teza Churcha
4.3. Maszyna Turinga-Posta
4.3.1. Obliczenia funkcji na maszynie Turinga-Posta
4.3.2. Przykłady obliczeń
4.3.3. Teza Turinga
4.3.4. Uniwersalna maszyna Turing-Post
4.4. Alana Turinga
4,5. Emil Post
4.6. Wydajne algorytmy
4.7. Problemy nierozwiązywalne algorytmicznie

5. Złożoność algorytmów
5.1. Pojęcie złożoności algorytmów
5.2. Klasy problemów P i NP
5.2.1. Klasa problemowa P
5.2.2. Klasa problemu NP
5.2.3. Niedeterministyczna maszyna Turinga
5.3. O pojęciu złożoności
5.3.1. Trzy rodzaje trudności
5.3.2. Cztery kategorie liczb według Kołmogorowa
5.3.3. Teza Kołmogorowa
5.4. JAKIŚ. Kołmogorow

6. Algorytmy rzeczywistości
6.1. Generator Wirtualna rzeczywistość
6.2. Zasada Turinga
6.3. Logicznie możliwe środowiska Cantgoutou

Krótkie streszczenie książki

Podręcznik poświęcony jest prezentacji podstaw logiki matematycznej i teorii algorytmów. Podstawą podręcznika są notatki z wykładów, które zostały rozdane studentom drugiego roku Wydziału Informatyki Uniwersytetu Państwowego w Omsku w 2002 roku. Dla studentów studiujących na specjalności „Bezpieczeństwo Informatyki” oraz na specjalności „Komputery, zespoły, systemy i sieci”.

Czym jest nauka logiki. Jest to teoria, która uczy prawidłowego rozumowania, prawidłowego wyciągania wniosków i wniosków, czego efektem są poprawne (poprawne) stwierdzenia. Dlatego logika jako nauka musi zawierać listę reguł uzyskiwania poprawnych twierdzeń. Taki zbiór reguł, wniosków, nazywany jest listą sylogizmów. Wypowiedź to wypowiedź na temat badanych obiektów, posiadająca jednoznaczne i precyzyjnie określone znaczenie. W języku rosyjskim stwierdzenie to zdanie oznajmujące, o którym można powiedzieć, że mówi nam coś prawdziwego lub coś całkowicie fałszywego. Dlatego stwierdzenie może być prawdziwe lub fałszywe.

Książki, pobieranie książek, pobieranie książek, książki online, czytaj online, pobieraj książki za darmo, czytaj książki, czytaj książki online, czytaj, biblioteka online, książki czytane, czytaj online za darmo, czytaj książki za darmo, e-book, czytaj online książki, najlepsze książki matematyka i fizyka, interesujące książki matematyka i fizyka, e-booki, książki za darmo, książki do pobrania za darmo, pobierz książki za darmo matematyka i fizyka, pobierz książki za darmo w całości, biblioteka internetowa, pobierz książki za darmo, czytaj książki online za darmo bez rejestracji matematyka i fizyka, czytaj książki online za darmo matematyka i fizyka, elektroniczna biblioteka matematyki i fizyki, książki do przeczytania matematyka w internecie i fizyki, świat książek o matematyce i fizyce, czytaj matematykę i fizykę za darmo, internetowa biblioteka matematyki i fizyki, czytanie książek o matematyce i fizyce, książki o matematyce i fizyce online za darmo, popularne książki o matematyce i fizyce, biblioteka bezpłatnej matematyki i fizyki książki, pobierz e-booki matematyka i fizyka, bezpłatna biblioteka online matematyka i fizyka, pobierz e-booki, podręczniki online matematyka i fizyka, biblioteka e-booki matematyka i fizyka, e-booki do pobrania za darmo bez rejestracji matematyka i fizyka, dobre książki matematyka i fizyka, pobierz pełne książki matematyka i fizyka, biblioteka elektroniczna czytaj za darmo matematyka i fizyka, elektroniczna biblioteka do pobrania za darmo matematyka i fizyka, strony do pobierania książek matematycznych i fizycznych fizyka, inteligentne książki matematyka i fizyka, szukaj książek matematyka i fizyka, pobierz e-booki darmowa matematyka i fizyka, pobierz e-booki matematyka i fizyka, najlepsze książki matematyka i fizyka, elektroniczna biblioteka darmowa matematyka i fizyka, czytaj darmowe książki online matematyka i fizyka, strona internetowa książek matematyczno-fizycznych, biblioteka elektroniczna, książki online do czytania, książka elektronicznej matematyki i fizyki, strona do bezpłatnego i bez rejestracji pobierania książek, bezpłatna biblioteka internetowa matematyki i fizyki, z której można pobrać matematykę i fizykę książki do fizyki za darmo, czytaj książki za darmo i bez rejestracji matematyka i fizyka, podręczniki do pobrania matematyki i fizyki, pobierz darmowe e-booki z matematyki i fizyki, pobierz darmowe książki całkowicie, biblioteka online za darmo, najlepsze e-booki z matematyki i fizyki , internetowa biblioteka książek matematycznych i fizycznych, pobierz e-booki za darmo bez rejestracji, biblioteka online do pobrania za darmo, skąd pobrać darmowe książki, darmowe e-biblioteki, darmowe e-booki, darmowe e-biblioteki, biblioteka internetowa za darmo, czytaj książki za darmo, czytaj książki online za darmo, czytaj bezpłatnie online, ciekawe książki czytaj online matematykę i fizykę, czytaj książki online matematyka i fizyka, elektroniczna biblioteka online matematyka i fizyka, bezpłatna biblioteka elektronicznych książek matematyka i fizyka, biblioteka online czytaj, czytaj za darmo i bez rejestracji matematyka i fizyka, znajdź książkę matematyka i fizyka, katalog książek matematyka i fizyka, pobierz książki online darmowa matematyka i fizyka, internetowa biblioteka matematyki i fizyki, pobierz darmowe książki matematyki i fizyki bez rejestracji, skąd możesz pobrać książki do bezpłatnej matematyki i fizyki, gdzie można pobrać książki, strony do bezpłatnego pobierania książek, czytanie online, czytanie biblioteki, książki czytaj online za darmo bez rejestracji, książki biblioteczne, bezpłatna biblioteka online, biblioteka online do bezpłatnego czytania, książki do czytaj za darmo i bez rejestracji, biblioteka elektroniczna do pobierania książek za darmo, online do czytania za darmo.

,
Od 2017 roku wznawiamy mobilną wersję serwisu na telefony komórkowe (projekt tekstu skróconego, technologia WAP) - górny przycisk w lewym górnym rogu strony. Jeśli nie masz dostępu do Internetu za pośrednictwem komputera osobistego lub terminala internetowego, możesz skorzystać z telefonu komórkowego, aby odwiedzić naszą stronę internetową (skrócona wersja) i w razie potrzeby zapisać dane z witryny w pamięci swojego telefonu komórkowego. Zapisuj książki i artykuły w swoim telefon komórkowy (Internet mobilny) i pobierz je z telefonu na komputer. Wygodne pobieranie książek poprzez telefon komórkowy (do pamięci telefonu) oraz do komputera poprzez interfejs mobilny. Szybki Internet bez zbędnych tagów, za darmo (w cenie usług internetowych) i bez haseł. Materiał udostępniany jest wyłącznie w celach informacyjnych. Zabrania się umieszczania bezpośrednich linków do plików książek i artykułów znajdujących się w serwisie oraz ich sprzedaży osobom trzecim.

Notatka. Wygodny link tekstowy do forów, blogów, cytujący materiały z serwisu, kod html można skopiować i po prostu wkleić na swoje strony internetowe podczas cytowania materiałów z naszego serwisu. Materiał udostępniany jest wyłącznie w celach informacyjnych. Książki możesz także zapisywać na swoim telefonie komórkowym poprzez Internet (jest tam wersja mobilna site - link w lewym górnym rogu strony) i pobierz je z telefonu na komputer. Bezpośrednie linki do plików książek są zabronione.