Zacharowa Podstawy logiki matematycznej i teorii algorytmów. „Logika matematyczna i teoria algorytmów

Książki. Pobierz książki DJVU w formacie PDF za darmo. Bezpłatna biblioteka elektroniczna
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”, kliknij 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. Algorytmiczna logika Hoare’a

II. Algorytmy
4. Algorytmy
4.1. Pojęcie algorytmu i funkcji obliczeniowej
4.2. Funkcje rekurencyjne
4.2.1. Funkcje prymitywnie 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. Zrozumienie 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 otrzymali studenci drugiego roku Wydziału Informatyki Uniwersytetu w Omsku Uniwersytet stanowy w 2002. 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ł i 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. Zatem zdanie 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 matematyka i fizyka, czytaj bezpłatnie matematykę i fizykę, biblioteka online matematyka i fizyka, czytaj książki matematyka i fizyka, książki online darmowa matematyka i fizyka, popularne książki matematyka i fizyka, biblioteka bezpłatnych książek matematyka i fizyka, pobierz e-book matematyka i fizyka, bezpłatna biblioteka matematyka i fizyka online, pobieranie e-booków, podręczniki matematyki i fizyki online, biblioteka e-booki matematyka i fizyka, pobierz e-booki za darmo bez rejestracji matematyka i fizyka, dobre książki matematyka i fizyka, pobierz książki w pełnej matematyce i fizyce, elektroniczna biblioteka czytaj za darmo matematykę i fizykę, elektroniczna biblioteka pobierz darmową matematykę i fizykę, strony do pobrania książki matematyczne i fizyczne, inteligentne książki matematyczne i fizyczne, szukaj książek matematycznych i fizycznych, pobierz e-booki z matematyki i fizyki, pobierz e-booki z matematyki i fizyki, najlepsze książki z matematyki i fizyki, elektroniczna biblioteka darmowa matematyka i fizyka, czytaj online darmowe książki matematyka i fizyka, strona z książkami do matematyki i fizyki, biblioteka elektroniczna, książki online do czytania, książka elektroniczna do matematyki i fizyki, strona do pobierania książek za darmo i bez rejestracji, bezpłatna biblioteka online do matematyki i fizyki, gdzie pobrać książki do matematyki i 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 do matematyki i fizyki, pobierz bezpłatnie książki w całości, biblioteka online za darmo, najlepsze e-książki do matematyki i fizyki fizyka, internetowa biblioteka książek matematyka i fizyka, pobierz e-booki za darmo bez rejestracji, biblioteka internetowa do pobrania za darmo, skąd pobrać darmowe książki, darmowe biblioteki elektroniczne, darmowe e-booki, darmowe biblioteki elektroniczne, biblioteka internetowa za darmo, bezpłatnie czytaj książki, książki online za darmo do czytania, czytaj za darmo online, ciekawe książki do czytania online matematyka i fizyka, czytanie książek online matematyka i fizyka, elektroniczna biblioteka online matematyka i fizyka, bezpłatna biblioteka elektronicznych książek matematyka i fizyka, internetowa biblioteka do czytania, czytaj matematykę i fizykę za darmo i bez rejestracji, znajdź książkę matematyka i fizyka, katalog książek matematyka i fizyka, pobierz książki online za darmo matematyka i fizyka, biblioteka internetowa matematyka i fizyka, pobierz darmowe książki matematyczne i fizyka bez rejestracji, gdzie możesz można pobrać książki za darmo z matematyki i fizyki, gdzie można pobrać książki, strony do bezpłatnego pobierania książek, czytanie online, czytanie bibliotek, książki czytane online za darmo bez rejestracji, biblioteka książek, bezpłatna biblioteka online, biblioteka online czytaj za darmo, czytaj książki za darmo i bez rejestracji, biblioteka elektroniczna pobierz książki za darmo, czytaj online za darmo.

,
Od 2017 roku wznawiamy mobilną wersję serwisu na telefony komórkowe (skrócony tekst, 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.

UNIWERSYTET TECHNICZNY KAZANIA im. A. N. Tupolewa

Sh. I. GALIEV

LOGIKA MATEMATYCZNA I TEORIA ALGORYTMÓW

INSTRUKTAŻ

Kazań 2002

Galiev Sh. 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żeli stosuje się aparat matematyczny, a badania skupiają się przede wszystkim na 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 istniejącej 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ść zastosowana logiki matematycznej jest obecnie bardzo duża. 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.

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. nauczyciel wydziału 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

Lekcja praktyczna nr 6 „Funkcje logiczne” 23

Lekcja praktyczna nr 7 „Funkcje częściowo rekurencyjne” 28

Lekcja praktyczna 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

Korzystając z zdefiniowanych powyżej operacji logicznych, można konstruować proste instrukcje 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 stwierdzenia 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).

11.1. Pojęcie algorytmu i teoria algorytmów

Intuicyjnie algorytm jest rozumiany jako proces sekwencyjnego rozwiązywania problemu, który następuje w dyskretnym czasie, tak że w każdym kolejnym momencie system obiektów algorytmu jest otrzymywany według pewnego prawa z układu obiektów, który istniał w poprzedni moment w czasie. Intuicyjnie, bo ściśle rzecz biorąc, pojęcie algorytmu jest zbliżone do pojęcia zbioru, który jest niedefiniowalny.

Zgodnie z GOST 19781-74 „Maszyny liczące. Oprogramowanie. Warunki i definicje" algorytm- jest to dokładna recepta, która określa proces obliczeniowy prowadzący od zmiany danych początkowych do pożądanego wyniku. Zakłada się w tym przypadku obecność wykonawcy algorytmu – obiektu, który „wie jak” wykonać te działania.

Uważa się, że słowo „algorytm” pochodzi od imienia środkowoazjatyckiego (uzbeckiego) matematyka z XIII wieku Al Khorezmi (Abu Abdullah Muhammad ibn Musa al Khorezmi al Medjusi) - „Algorithmi” w transkrypcji łacińskiej, który jako pierwszy sformułował zasady (procedura) wykonywania czterech operacji arytmetycznych w systemie dziesiętnym.

Dopóki obliczenia były proste, nie było szczególnej potrzeby stosowania algorytmów. Kiedy pojawiła się potrzeba stosowania wielu procedur krok po kroku, pojawiła się teoria algorytmów. Kiedy jednak problemy stały się jeszcze bardziej złożone, okazało się, że niektórych z nich nie da się rozwiązać algorytmicznie. To na przykład wiele problemów, które rozwiązuje ludzki „komputer pokładowy” – mózg. Rozwiązanie takich problemów opiera się na innych zasadach - zasady te wykorzystuje nowa nauka - neuromatematyka i odpowiadające jej środki techniczne - neurokomputery. W tym przypadku stosowane są procesy uczenia się, prób i błędów – czyli to, co robimy teraz.

O jakości algorytmu decydują jego właściwości (cechy). Do głównych właściwości algorytmu należą:

1. Masowy charakter. Zakłada się, że algorytm może nadawać się do rozwiązywania wszystkich problemów tego typu. Na przykład algorytm rozwiązywania układu liniowych równań algebraicznych musi mieć zastosowanie do układu składającego się z dowolnej liczby równań.

2. Efektywność. Ta właściwość oznacza, że ​​algorytm musi generować wynik w skończonej liczbie kroków.

3. Pewność. Instrukcje zawarte w algorytmie muszą być precyzyjne i zrozumiałe. Cecha ta zapewnia jednoznaczność wyniku procesu obliczeniowego przy zadanych danych początkowych.

4. Dyskrecja. Właściwość ta oznacza, że ​​proces opisywany przez algorytm oraz sam algorytm można podzielić na odrębne, elementarne etapy, których możliwość bez wątpienia użytkownik może wykonać na komputerze.

Dziś żyjemy w „cyfrowym tysiącleciu” i wydawać by się mogło, że algorytmy poradzą sobie z każdym zadaniem. Okazuje się, że wielu problemów nie da się rozwiązać algorytmicznie. Są to tak zwane problemy nierozwiązywalne algorytmicznie.

Aby udowodnić algorytmiczną rozwiązywalność lub nierozwiązywalność problemów, wymagane są matematycznie rygorystyczne i precyzyjne środki. W połowie lat 30. ubiegłego wieku podjęto próby sformalizowania pojęcia algorytmu i zaproponowano różne modele algorytmów: funkcje rekurencyjne; „maszyny” – Turing, Post; normalne algorytmy Markowa.

Następnie stwierdzono, że te i inne modele są równoważne w tym sensie, że klasy problemów, które rozwiązują, są takie same. Fakt ten nazywany jest tezą Churcha. Jest to obecnie powszechnie akceptowane. Formalna definicja pojęcia algorytmu stworzyła przesłanki do rozwoju teorii algorytmu jeszcze przed pojawieniem się pierwszych komputerów. Postęp techniki komputerowej stał się impulsem do dalszego rozwoju teorii algorytmów. Oprócz ustalenia algorytmicznej rozwiązywalności problemów, teoria algorytmów zajmuje się także szacowaniem złożoności algorytmów pod względem liczby kroków (złożoność czasowa) i wymaganej pamięci (złożoność przestrzenna), a także zajmuje się rozwojem algorytmów wydajne algorytmy w tym sensie.

Zaimplementowanie niektórych algorytmów, przy jakichkolwiek rozsądnych z fizycznego punktu widzenia założeniach dotyczących szybkości wykonywania elementarnych kroków, może zająć więcej czasu, niż według współczesnych poglądów istnieje Wszechświat lub więcej komórek pamięci niż atomów tworzących planetę Ziemia.

Dlatego kolejnym zadaniem teorii algorytmów jest rozwiązanie problemu eliminacji wyliczania opcji w algorytmach kombinatorycznych. Ocena złożoności algorytmów i tworzenie tzw. wydajnych algorytmów to jedno z najważniejszych zadań współczesnej teorii algorytmów.

S. N. POZDNYAKOV S. V. RYBIN

Instruktaż

Ministerstwo Edukacji i Nauki Federacji Rosyjskiej

Państwowy Uniwersytet Elektrotechniczny w Petersburgu „LETI”

S. N. POZDNYAKOV S. V. RYBIN

LOGIKA MATEMATYCZNA I TEORIA ALGORYTMÓW

Wydawnictwo w Petersburgu Uniwersytet Elektrotechniczny „LETI” w Petersburgu

UDC 510.6 BBK V12 P47

Pozdnyakov S. N., Rybin S. V. Logika matematyczna i teoria algorytmów: Podręcznik. dodatek. St. Petersburg: Wydawnictwo Petersburskiego Uniwersytetu Elektrotechnicznego „LETI”, 2004. 64 s.

Rozważane są główne idee, koncepcje i metody logiki matematycznej, których zainteresowanie wzrosło dzięki nowym zastosowaniom, które pojawiły się w przeszłości Ostatnio w związku z rozwojem technologii informatycznych.

Może być stosowany zarówno dla studentów studiów stacjonarnych, jak i dla wydziałów wieczorowych i korespondencyjnych uczelni technicznych.

Recenzenci: wydział Analiza matematyczna Uniwersytet Państwowy w Petersburgu; doc. M. V. Dmitrieva (Uniwersytet Państwowy w Petersburgu).

Zatwierdzone przez Radę Redakcyjną i Wydawniczą Uniwersytetu

jako pomoc dydaktyczna

Logika matematyczna, podobnie jak teoria algorytmów, pojawiła się na długo przed pojawieniem się komputerów. Ich pojawienie się było związane z wewnętrznymi problemami matematyki, z badaniem granic stosowalności jej teorii i metod.

W Obecnie obie te (powiązane ze sobą) teorie doczekały się rozwoju stosowanego w tak zwanej matematyce komputerowej (informatyka). Oto kilka obszarów ich zastosowania w obszarach zastosowań:

– wykorzystania systemów ekspertowych formalne wnioskowania logiczne do symulacji działań ekspertów z różnych dziedzin;

– przy projektowaniu mikroukładów wykorzystuje się teorię funkcji boolowskich;

– testowanie programów opiera się na logicznej analizie ich struktury;

– dowód poprawności programów opiera się na teorii wnioskowania logicznego;

– języki algorytmiczne łączą dwa ważne pojęcia logiki: pojęcie języka i pojęcie algorytmu;

– automatyzacja dowodzenia twierdzeń opiera się na metodzie rozwiązywania, poznanej na kursie logiki.

W dany podręcznik przedstawiono podstawowe idee, koncepcje i metody logiki matematycznej leżące u podstaw zarówno wymienionych, jak i innych jej zastosowań.

1. Relacje binarne i wykresy

1.1. Wstęp. Sformułowanie problemu

Relacje binarne napotkano już w kurs szkolny matematyka Przykładami takich relacji są relacje nierówności, równości, podobieństwa, równoległości, podzielności itp. Relacja binarna wiąże każde dwa obiekty z wartością logiczną „tak”, jeśli obiekty są w tej relacji, lub „nie” w przeciwnym razie. Innymi słowy, zbiór par obiektów dzieli się na dwa podzbiory, pary pierwszego podzbioru są w danej relacji, ale pary drugiego nie. Właściwość ta może służyć jako podstawa do zdefiniowania relacji binarnej.

Definicja 1.1. Niech będzie dany zbiór M. Rozważmy iloczyn kartezjański tego zbioru sam w sobie M × M . Podzbiór R zbioru M × M nazywany jest relacją binarną R na zbiorze M. Jeżeli para (x; y) należy do zbioru R, mówimy, że element x pozostaje w relacji R z elementem y i zapisujemy xRy.

Przykład 1.1. Wprowadźmy relację porównywalności R: x jest porównywalne z y modulo m wtedy i tylko wtedy, gdy x i y mają takie same reszty przy dzieleniu przez m. Oznacza to, że x ≡ y (mod m) .

Rozważmy wprowadzoną relację R dla przypadku m = 3 na zbiorze M = (1; 2; 3; 4; 5; 6), wówczas

Relację R definiujemy poprzez zbiór takich par:

Przykład 1.2. Rozważmy jako M = R – zbiór rzeczy

liczby rzeczywiste, czyli inaczej zbiór punktów prostej rzeczywistej. Wtedy M × M = R 2 jest zbiorem punktów płaszczyzny współrzędnych. Relacja nierówności< определяется множеством парR = = {(x; y)|x < y} .

Ćwiczenie 1.1.

1. Na zbiorze liczb rzeczywistych dana jest następująca zależność: xRy zatem

wtedy i tylko wtedy, gdy jedna z liczb jest dwa razy większa od drugiej. Narysuj na płaszczyźnie zbiór punktów definiujących tę zależność.

2. Na zbiorze M = (1; 2; 3; 4; 5; 6) dana jest relacja podzielności: xRy wtedy i tylko wtedy, gdy x jest podzielne przez y. Ile par zawiera?

czy to jest postawa? Wypisz te pary.

3. Wprowadźmy na zbiorze M = (1; 2; 3; 4; 5; 6) relację względności pierwszej, czyli xRy wtedy i tylko wtedy, gdy x i y są względnie pierwsze: D(x; y) = 1 . Ile par zawiera ta relacja? Wymień je

1.2. Własności relacji binarnych

Definicja 1.2. Nazywa się relację binarną R na zbiorze M

jest zwrotny, jeśli każdy element tego zbioru jest w relacji sam ze sobą: xRx x M .

Przykład 1.3.

1. Relacja porównywalności jest zwrotna (dla dowolnego naturalnego m i na dowolnym zestawie liczb całkowitych).

2. Ścisła relacja nierówności na zbiorze liczb rzeczywistych nie jest zwrotna.

3. Relacja podzielności jest zwrotna (na dowolnym zbiorze liczb całkowitych, który nie zawiera zera).

Definicja 1.3. Nazywa się relację binarną R na zbiorze M

jest antyrefleksyjna, jeśli ani jeden element tego zbioru nie jest w relacji sam ze sobą: x M nie jest prawdą, że xRx .

Przykład 1.4.

1. Ścisła relacja nierówności na zbiorze liczb rzeczywistych jest antyrefleksyjna.

2. Wzajemna relacja pierwsza jest antyrefleksyjna na dowolnym zestawie liczb całkowitych, który nie zawiera 1 i −1, zwrotne na zbiorach (1), (−1), (−1; 1) i nie są ani zwrotne, ani antyrefleksyjne

W przeciwnym razie.

Definicja 1.4. Relację binarną R na zbiorze M nazywamy symetryczną, jeżeli obok każdej pary (x; y) relacja ta zawiera także parę symetryczną (y; x): x, y M xRy yRx .

Przykład 1.5.

1. Relacja porównywalności jest symetryczna dla dowolnej liczby naturalnej

2. Ścisła relacja nierówności na zbiorze liczb rzeczywistych nie jest symetryczna.

3. Relacja podzielności jest symetryczna tylko na zbiorze liczb całkowitych względnie pierwszych parami, które nie zawierają ani jednej. Na przykład na zbiorze liczb pierwszych.

4. Relacja względnie pierwsza jest symetryczna na dowolnym zbiorze liczb całkowitych.

Definicja 1.5. Nazywa się relację binarną R na zbiorze M

jest asymetryczna, jeśli w relacji razem z jej symetryczną nie ma pary: x, y M , jeśli xRy , to nie jest prawdą, że yRx .

Przykład 1.6.

1. Relacja ścisłej nierówności na zbiorze liczb rzeczywistych jest asymetryczna.

2. Relacja podzielności nie jest asymetryczna na żadnym zbiorze liczb całkowitych, który nie zawiera zera.

Definicja 1.6. Nazywa się relację binarną R na zbiorze M

jest antysymetryczna, jeśli w relacji z jej symetryczną nie jest zawarta żadna para składająca się z różnych elementów: x, y M ifxRy i yRx tox = y.

Przykład 1.7.

1. Nieścisła relacja nierówności na zbiorze liczb rzeczywistych jest antysymetryczna.

2. Relacja podzielności jest antysymetryczna na dowolnym zbiorze liczb całkowitych, który nie zawiera zera.

Ćwiczenie 1.2.

1. Czy to prawda, że ​​relacja asymetryczna jest zawsze antyrefleksyjna? Udowodnij to.

2. Czy prawdą jest, że relacja symetryczna jest zawsze zwrotna? Pokaż mi wcześniej.

3. Czy prawdą jest, że relacja asymetryczna jest zawsze antysymetryczna? Udowodnij to.

4. Czy prawdą jest, że relacja jest asymetryczna wtedy i tylko wtedy, gdy jest antyrefleksyjna i antysymetryczna? Udowodnij to.

Definicja 1.7. Relacja binarna R jest przechodnia, jeśli para (x; y) zawiera także parę (x, z), tj. x, y, x M, jeśli xRy i

zbiór M nazywa się u(y; z) w relacji yRz , toxRz .

Uwaga 1.1. Właściwość przechodniości dobrze ilustruje relacja osiągalności: jeśli pointy jest osiągalny z punktówx, a pointz jest osiągalny z pointy, to pointz jest osiągalny z punktówx.

Przykład 1.8.

1. Relacja porównywalności jest przechodnia dla dowolnego naturalnego m i na dowolnym zbiorze liczb całkowitych.

2. Ścisła (nieścisła) relacja nierówności jest przechodnia w dowolnym podzbiorze liczb rzeczywistych.

3. Relacja podzielności jest przechodnia na zbiorze liczb całkowitych, który nie zawiera zera.

4. Relacja względnie pierwsza nie jest przechodnia na żadnym zbiorze liczb całkowitych. Na przykład, 2 jest względnie pierwsze do c3, 3 jest względnie pierwsze do c4, ale 2 i 4 nie są względnie pierwsze.

Ćwiczenie 1.3. Czy to prawda, że ​​przechodnie i symetryczne

Czy postawa zawsze jest refleksyjna? Udowodnij to.

1.3. Metody definiowania relacji

Oprócz wyraźnego wyszczególnienia par definiujących relację binarną jest to możliwe następujące metody zadania związane z relacjami.

Ustalenie procedury weryfikacji.

Przykład 1.9.

1. Relację wzajemnej pierwszości sprawdza się metodą znajdowania największej wspólny dzielnik: Jeśli D(x; y) = 1, to(x; y) jest zawarte w

relacja wzajemnej prostoty.

2. Relację podzielności sprawdzamy metodą dzielenia z resztą: if x ≡ 0 (mod y) , wtedy (x; y) jest zawarte w relacji podzielności.

3. Ta sama procedura sprawdza relację równości reszt przy dzieleniu przez m : jeśli (x−y)≡0 (mod m) , to (x; y) jest zawarte w relacji.

W przypadku relacji na zbiorach skończonych (które są podstawą matematyki dyskretnej) stosuje się również następujące metody określania i opisywania relacji.

Określanie macierzy sąsiedztwa. Zdefiniujmy macierz A o rozmiarze

|M | × |M |, gdzie |M | – liczba elementów zbioru M. Ponumerujmy elementy zbioru M. Wtedy aij = 1, jeśli numer elementu i jest w związku z elementem o numerze j (iRj), a aij = 0 w przeciwnym razie.

Przykład 1.10. Macierz sąsiedztwa relacji podzielności na zbiorze M = (1; 2; 3; 4; 5; 6) wygląda następująco:

Przypisanie według wykresu. Elementy zbioru reprezentowane są przez punkty na płaszczyźnie i tworzą zbiór wierzchołków grafu. Relacje reprezentują łuki (krawędzie) grafu: jeśli w relacji uwzględnimy (x; y), to od wierzchołka x do y rysowany jest łuk zorientowany.

Przykład 1.11. Wykres relacji porównywalności modulo trzy na

Określanie listy sąsiedztwa. Dla każdego elementu zbioru wyszczególnione są elementy pozostające z nim w danej relacji.

Przykład 1.12. Lista przylegań relacji względnie pierwszej na zbiorze M = (1; 2; 3; 4; 5; 6) wygląda następująco:

Podajmy interpretację właściwości relacji binarnych na wykresach i macierzach je opisujących.

Twierdzenie 1.1. Poniższe stwierdzenia są prawdziwe.

1. Przekątna macierzy sąsiedztwa relacji zwrotnej składa się z jedynek.

2. Relacja symetryczna ma symetryczną macierz sąsiedztwa

3. Wykres relacji zwrotnej ma pętle w każdym wierzchołku.

4. Wykres zależności symetrycznej wraz z łukiem łączącym X

z y, zawiera łuk łączący y z x.

5. Wykres relacji przechodniej ma następującą właściwość: jeśli od góry x, poruszając się po łukach, można dojść do wierzchołka y, wtedy wykres musi mieć łuk bezpośrednio łączący x z y.

Uwaga 1.2. Dla symetrycznych

pętle zwykle nie są przedstawiane, a pary zorientowanych łuków łączących te wierzchołki są zastępowane jednym – nieorientowanym – łukiem.

Przykładowo wykres z przykładu 1.11 będzie wyglądał jak ten pokazany na ryc. 1.2.

i refleksyjne relacje

Ćwiczenie 1.4.

1. Opisz właściwości macierzy sąsiedztwa: a) postawa antyrefleksyjna; b) zależność asymetryczna; c) zużycie antysymetryczne; d) relacja przechodnia.

2. Opisz właściwości wykresu: a) postawa antyrefleksyjna; b) zależność asymetryczna; c) zależność antysymetryczna.

1.4. Relacja równoważności

Definicja 1.8. Relacja binarna, która ma właściwości re

brak elastyczności, symetria i przechodniość nazywana jest relacją równoważności.

Przykład 1.13. Relacja porównywalności (według dowolnego modułu) wynosi

jest relacją równoważności.

Powiążmy z każdym elementem zbioru M wszystkie elementy, które są z nim w danej relacji równoważności: Mx = (y M | xRy). Poniższe twierdzenie jest prawdziwe.

Twierdzenie 1.2. Zbiory M x i M y albo się nie przecinają, albo są takie same

Dowód. Wszystkie elementy tej samej klasy są sobie równoważne, czyli jeśli x, y Mz, to xRy. Rzeczywiście, niech x, y Mz, zatem xRz i yRz. Z symetrii stosunku R mamy zRy. Następnie, ze względu na przechodniość, z xRz i zRy otrzymujemy xRy.