Захаров Основи на математичката логика и теорија на алгоритми. „Математичка логика и теорија на алгоритми

Книги. Преземете ги книгите за DJVU, PDF бесплатно. Бесплатна електронска библиотека
А.К. Цврсти, Математичка логика и теорија на алгоритми

Можеш (програмата ќе го означи со жолто)
Можете да го видите списокот со книги за виша математика подредени по азбучен ред.
Можете да го видите списокот со книги за повисока физика подредени по азбучен ред.

• Бесплатно преземање книга, волумен 556 Kb, формат .djvu (модерен учебник)

Дами и господа!! За да преземете датотеки со електронски публикации без „багови“, кликнете на подвлечената врска со датотеката ДЕСНО копче на глувчето, изберете команда "Зачувај цел како ..." („Зачувај цел како...“) и зачувајте ја датотеката e-pub на вашиот локален компјутер. Електронските публикации обично се во формати Adobe PDF и DJVU.

I. Логика
1. Класична логика
1.1. пропозициска логика
1.1.1. изреки
1.1.2. Основни закони на логиката
1.1.3. Раселовиот логичен парадокс
1.1.4. Алгебра (логика) на искази
1.1.5. Дијаграми на скалила
1.1.6. Еквивалентни формули
1.1.7. Булова алгебра
1.1.8. Вистински и валидни формули
1.1.9. Проблем со одлучување
1.1.10. логична последица
1.1.11. Силогизми
1.2. Предикатна логика
1.2.1. Предикати и формули
1.2.2. Толкувања
1.2.3. Вистината и задоволливоста на формулите. Модели, валидност, логичка последица
1.2.4. Готлоб Фреге
1.2.5. Функции на Сколем
и сколемизација на формули
1.3. Метод на резолуција
1.3.1. Метод на резолуции во пропозициска логика
1.3.2. Метод на резолуција во предикатната логика

2. Формални теории (калкулус)
2.1. Дефиниција на формална теорија, или пресметка
2.1.1. Доказ. Конзистентност на теоријата. Комплетност на теоријата
2.2. пропозиционо калкулус
2.2.1. Јазик и правила за заклучување на исказната пресметка
2.2.2. Пример за доказ за теорема
2.2.3. Комплетност и конзистентност на искажната пресметка
2.3. Пресметка на предикат
2.3.1. Јазик и правила за заклучување на пресметувањето на прирокот
2.3.2. Комплетност и конзистентност на пресметувањето на прирокот
2.4. Формална аритметика
2.4.1. Егалитарни теории
2.4.2. Јазик и правила за изведување на формална аритметика
2.4.3. Конзистентност на формалната аритметика. Генценова теорема
2.4.4. Теорема за нецелосност на Годел
2.4.5. Курт Гедел
2.5. Автоматско изведување на теорема
2.5.1. С.Ју. Маслов
2.6. Логичко програмирање
2.6.1. логичка програма
2.6.2. Логички програмски јазици

3. Некласични логики
3.1. интуиционистичка логика
3.2. нејасна логика
3.2.1. Нејасни подмножества
3.2.2. Операции на нејасни подмножества
3.2.3. Својства на множеството нејасни подмножества
3.2.4. Нејасна пропозициска логика
3.2.5. Дијаграми за нејасни скалила
3.3. Модални логики
3.3.1. Видови на модалитет
3.3.2. Калкулус 1 и Т (Фајс-фон Рајт)
3.3.3. Калкулус S4, S5 и Калкулус Wrouer
3.3.4. Формула вреднување
3.3.5. Семантика на Крипке
3.3.6. Други толкувања на модалните знаци
3.4. Георг фон Рајт
3.5. Временски логики
3.5.1. Тајминг логика на Прајор
3.5.2. Временската логика на Лемон
3.5.3. Временската логика на Фон Рајт
3.5.4. Примена на логики за тајминг при програмирање
3.5.5. Пнуели временска логика
3.6. Алгоритамски логики
3.6.1. Принципи на конструирање на алгоритамска логика
3.6.2. Чарлс Хоар
3.6.3. Алгоритамска логика на Хоаре

II. Алгоритми
4. Алгоритми
4.1. Концепт на алгоритам и пресметлива функција
4.2. Рекурзивни функции
4.2.1. Примитивни рекурзивни функции
4.2.2. Делумно рекурзивни функции
4.2.3. Тезата на црквата
4.3. Машина Turing-Post
4.3.1. Пресметки на функции на машина Туринг-пост
4.3.2. Примери за пресметка
4.3.3. Тјуринг теза
4.3.4. Универзална машина Туринг-пост
4.4. Алан Тјуринг
4.5. Емил Пост
4.6. Ефикасни алгоритми
4.7. Алгоритамски нерешливи проблеми

5. Сложеност на алгоритми
5.1. Концептот на сложеноста на алгоритмите
5.2. Класи на проблеми Р и НП
5.2.1. Класа на проблеми Р
5.2.2. Класа на проблеми НП
5.2.3. Недетерминистичка Тјуринг машина
5.3. За концептот на сложеност
5.3.1. Три типа на тежина
5.3.2. Четири категории на броеви според Колмогоров
5.3.3. тезата на Колмогоров
5.4. А.Н. Колмогоров

6. Алгоритми на реалноста
6.1. Генератор на виртуелна реалност
6.2. Тјуринг принцип
6.3. Логично можни средини на Кантготу

Кратко резиме на книгата

Учебникот е посветен на презентација на основите на математичката логика и теоријата на алгоритми. Учебникот се заснова на белешки за предавања дадени на студенти од втора година на Катедрата за компјутерски науки на Државниот универзитет во Омск во 2002 година. За студенти кои студираат во специјалитетот „Компјутерска безбедност“ и во специјалитетот „Компјутери, комплекси, системи и мрежи“.

Што е наука за логиката. Ова е теорија која учи како правилно да размислувате, правилно да извлекувате заклучоци и заклучоци, што резултира со точни (точни) изјави. Затоа, логиката како наука мора да содржи список на правила за добивање точни искази. Таков збир на правила, заклучоци се нарекува список на силогизми. Изјава е изјава за предметите што се проучуваат што има недвосмислено и точно дефинирано значење. На руски, исказот е декларативна реченица за која се моли да се каже дека ни кажува нешто точно или нешто сосема погрешно. Затоа, изјавата може да биде или вистинита или неточна.

Книги, преземај книги, преземај книга, книги онлајн, читај онлајн, преземај книги бесплатно, читај книги, читај книги онлајн, читај, библиотека онлајн, читани книги, читај онлајн бесплатно, читај книги бесплатно, е-книга, читај книги онлајн, најдобри книги математика и физика, интересни книги математика и физика, е-книги, книги бесплатно, книги за бесплатно симнување, бесплатно преземање книги математика и физика, преземање книги бесплатно целосно, онлајн библиотека, преземање книги бесплатно, читање книги онлајн бесплатно без регистрација математика и физика, читајте книги онлајн бесплатно математика и физика, електронска библиотека математика и физика, книги за читање онлајн математика и физика, светот на книгите математика и физика, читајте математика и физика бесплатно, библиотека онлајн математика и физика, читање математика и физика, книги онлајн бесплатни математика и физика , популарни книги математика и физика, библиотека со бесплатни книги математика и физика, преземете електр. бесплатна книга по математика и физика, бесплатна онлајн библиотека по математика и физика, преземање е-книги, онлајн учебници по математика и физика, библиотека е-книги по математика и физика, е-книги бесплатно преземање без регистрација математика и физика, добри книги по математика и физика, преземање целосни книги математика и физика, електронска библиотека чита бесплатно математика и физика, електронска библиотека бесплатно преземање математика и физика, сајтови за преземање книги математика и физика, паметни книги математика и физика, пребарување книги математика и физика, преземање е-книги бесплатно математика и физика, е-книга преземање математика и физика, најдобри книги за математика и физика, електронска библиотека за бесплатна математика и физика, читање онлајн бесплатни книги за математика и физика, страница за книги по математика и физика, електронска библиотека, онлајн книги до читај, книга по електронска математика и физика, сајт за симнување книги бесплатно и без регистрација , бесплатна онлајн библиотека за математика и физика, каде што можете бесплатно да преземате книги по математика и физика, бесплатно и без регистрација да читате книги по математика и физика, да преземате учебници по математика и физика, да преземате бесплатни е-книги по математика и физика, преземете бесплатни книги целосно, библиотека онлајн бесплатно, најдобрите е-книги математика и физика, онлајн библиотека со книги математика и физика, преземете е-книги бесплатно без регистрација, преземање онлајн библиотека бесплатно, каде да преземете бесплатни книги, е- библиотеки бесплатно, електронски книги бесплатно, бесплатни е-библиотеки, онлајн библиотека бесплатно, бесплатно читање книги, книги онлајн бесплатно за читање, читање бесплатно онлајн, интересни книги за читање онлајн математика и физика, читање книги онлајн математика и физика, електронска библиотека онлајн математика и физика, бесплатна библиотека на електронски книги математика и физика, библиотека онлајн за читање, читање бесплатно и без регистрација и математика и физика, најдете книга за математика и физика, каталог на книги по математика и физика, преземете книги онлајн бесплатно за математика и физика, онлајн библиотека за математика и физика, преземете бесплатни книги без регистрација математика и физика, каде што можете да преземете книги за бесплатна математика и физика, каде што можете да преземате книги, страници за бесплатно преземање книги, онлајн за читање, библиотека за читање, книги за читање онлајн бесплатно без регистрација, библиотека книги, бесплатна библиотека онлајн, онлајн библиотека за читање бесплатно , книги за читање бесплатно и без регистрација, електронска библиотека за преземање книги бесплатно, онлајн за читање е бесплатно.

,
Од 2017 година, ја продолжуваме мобилната верзија на веб-страницата за мобилни телефони (скратен дизајн на текст, WAP технологија) - горното копче во горниот лев агол на веб-страницата. Ако немате пристап до Интернет преку персонален компјутер или интернет терминал, можете да го користите вашиот мобилен телефон за да ја посетите нашата веб-страница (скратен дизајн) и, доколку е потребно, да зачувате податоци од веб-локацијата во меморијата на вашиот мобилен телефон. Зачувајте книги и написи на вашиот мобилен телефон (мобилен интернет) и преземете ги од телефонот на вашиот компјутер. Практично преземање книги преку мобилен телефон (во меморијата на телефонот) и на вашиот компјутер преку мобилен интерфејс. Брз интернет без непотребни ознаки, бесплатен (по цена на интернет услуги) и без лозинки. Материјалот е даден за преглед. Забранети се директни врски до датотеки со книги и написи на веб-страницата и нивна продажба од трети лица.

Забелешка. Удобен текстуален линк за форуми, блогови, цитирање материјали на веб-локации, html кодот може да се копира и едноставно да се залепи на вашите веб-страници кога се цитираат материјали од нашата веб-локација. Материјалот е даден за преглед. Исто така, зачувајте книги на вашиот мобилен телефон преку Интернет (постои мобилна верзија на страницата - врската е горе лево на страницата) и преземете ги од телефонот на вашиот компјутер. Директните врски до датотеките со книги се забранети.

КАЗАН ТЕХНИЧКИ УНИВЕРЗИТЕТ нив. А.Н.Туполева

Ш.И.Галиев

МАТЕМАТИЧКА ЛОГИКА И ТЕОРИЈА НА АЛГОРИТМИ

УПАТСТВО

Казан 2002 година

Галиев Ш. И. Математичка логика и теорија на алгоритми. - Казан: Издавачка куќа на КСТУ. А.Н. Туполев. 2002. - 270 стр.

ISBN 5-93629-031-X

Прирачникот ги содржи следните делови. Логиката на предлозите и предикатите со апликации, вклучувајќи го и методот на резолуција и елементите на неговата имплементација на јазикот PROLOG. Класична пресметка (на предлози и предикати) и елементи на некласичните логики: тривредностни и повеќевредносни логики, модални, временски и нејасни логики. Теорија на алгоритми: нормални алгоритми, Тјуринг машини, рекурзивни функции и нивните односи. Концептот на пресметковна сложеност, различни (по сложеност) класи на проблеми и примери на такви проблеми.

Сите поглавја се опремени со контролни прашања и вежби, дадени се опции за типични задачи и тестови за самоконтрола на совладување на материјалот.

Прирачникот е наменет за студенти на техничките универзитети од специјалитетот 2201 од насоката „Информатика и компјутерско инженерство“ и може да се користи за специјалитетот 2202 и други специјалности од оваа област.

ВОВЕД

Логиката обично се подразбира како наука за методите на докажување и побивање. Математичката логика е логика развиена со помош на математички методи.

Проучувајќи ги методите на докажување и побивање, логиката првенствено ја интересира формата на добивање вистински заклучоци, а не содржината на премиси и заклучоци во одредено расудување. Размислете, на пример, следните два излеза:

1. Сите луѓе се смртни. Сократ е човек. Затоа, Сократ е смртен.

2. Сите мачиња сакаат да играат. Моура е маче. Затоа, Моура сака да игра.

И двата заклучоци имаат иста форма: Сите A се B, C е A; затоа C е B. Овие заклучоци се вистинити врз основа на нивната форма, без разлика на содржината, без разлика дали премисите и заклучоците направени сами по себе се вистинити или лажни. Систематското формализирање и каталогизирање на правилните начини на расудување е една од главните задачи на логиката. Ако во овој случај се користи математичкиот апарат и истражувањето е посветено првенствено на проучување на математичкото расудување, тогаш оваа логика е математичка логика (формална логика). Оваа дефиниција не е строга (точна) дефиниција. За да го разберете предметот и методот на математичката логика, најдобро е да започнете да го проучувате.

Математичката логика почна да се обликува многу одамна. Потеклото на нејзините идеи и методи се случило во античка Грција, античка Индија и античка Кина од околу 6 век п.н.е. п.н.е д. Веќе во овој период, научниците се обидоа да го подредат синџирот на математички докази во таков синџир што преминот од една алка во друга нема да остави никакви сомнежи и да добие универзално признание. Веќе во најраните ракописи што дошле до нас, цврсто е воспоставен „канонот“ на математичкиот стил на прикажување. Последователно, тој го добива конечното завршување на големите класици: Аристотел, Евклид, Архимед. Концептот на доказ за овие автори не се разликува од нашиот.

Логиката како самостојна наука потекнува од студиите на Аристотел (384 - 322 п.н.е.). Големиот филозоф на антиката, Аристотел, изврши енциклопедиска систематизација на античкото знаење во сите области на тогашната наука. Логичките студии на Аристотел се претставени главно во неговите две дела „Прва анализа“ и „Втора аналитика“, обединети под општиот наслов „Органон“ (Инструмент на знаење).

Од особено значење е големото значење за формирањето и развојот на математичката логика на едно од најбрилијантните достигнувања во историјата на човештвото, имено, трансформацијата на геометријата во точен дедуктивен систем во делото на Евклид (330 - 275 п.н.е.) „Почетоци“. Токму овој дедуктивен пристап со јасна свест за целите и методите беше основа за развојот на филозофската и математичката мисла во следните векови.

Исто така, од големо значење за формирањето и развојот на логиката беа достигнувањата во алгебрата (Bule algebra) и во други математички дисциплини, вклучително и повторно во геометријата (создавање на неевклидова геометрија - геометрија Лобачевски-Гаус-Бољај). Краток преглед на формирањето на математичката логика може да се најде во.

Во формирањето и развојот на математичката логика учествувале многу и многу научници, од античко време, средниот век и последователните времиња.

Основно и применето значење на математичката логика

Основното значење на математичката логика е поткрепеноста на математиката (анализа на основите на математиката).

Применетата вредност на математичката логика моментално е многу висока. Математичката логика се користи за следните цели:

анализа и синтеза (конструкција) на дигитални компјутери и други дискретни автомати, вклучувајќи интелигентни системи;

анализа и синтеза на формални и машински јазици, за анализа на природен јазик;

анализа и формализирање на интуитивниот концепт на пресметливост;

откривање на постоење на механички постапки за решавање проблеми од одреден тип;

анализа на проблеми со пресметковната сложеност.

Исто така, се покажа дека математичката логика е тесно поврзана со голем број прашања од лингвистиката, економијата, психологијата и филозофијата.

Овој прирачник ги прикажува основните концепти на математичката логика и теоријата на алгоритми. Материјалот претставен во прирачникот

одговара на државниот образовен стандард за насоката „Информатика и компјутерско инженерство“ и може да се користи за студенти кои студираат во различни специјалности од оваа насока.

При пишувањето на прирачникот користена е литература, а секако се користени и други извори. Списокот на референци вклучува книги што е пожелно да се видат за испитувачки и баран студент.

Во прирачникот, секое поглавје содржи прашања за само-тестирање на теоретски материјал и вежби дизајнирани да развијат вештини за решавање проблеми и да го продлабочат знаењето за темата што се презентира. Покрај тоа, прирачникот дава опции за типични задачи и тестови за самоконтрола на асимилацијата на материјалот.

Федерална агенција за образование

ТОМСК ДРЖАВЕН УНИВЕРЗИТЕТ ЗА КОНТРОЛНИ СИСТЕМИ И РАДИО ЕЛЕКТРОНИКА (ТУСУР)

Одделение за автоматизација на обработка на информации

Одобрувам:

Глава кафуле АОИ

Професор

Да. Ехлаков

„__“ _____________2007 година

Насоки

до спроведување на практична работа на дисциплината

„Математичка логика и теорија на алгоритми“

за студенти од специјалност 230102 -

„Автоматски системи за обработка и контрола на информации“

Програмери:

чл. предавач на катедрата АОИ

ПОТОА. Перемитина

Томск - 2007 година

Практичен час бр.1 „Пропозициски алгебарски формули“ 3

Практичен час бр.2 „Еквивалентни трансформации на формули за пропозиција алгебра“ 10

Практичен час бр.3 „Нормални форми на формули“ 12

Практичен час бр.4 „Логичко расудување“ 14

Практичен час бр.5 „Формули на предикатна логика“ 18

Вежбајте бр. 6 Булови функции 23

Вежба бр. 7 Делумно рекурзивни функции 28

Вежба бр. 8 Туринг машини 34

Практичен час бр.1 „Пропозициски формули на алгебра“

Доктрината за предлози - алгебра на пропозиции или алгебра на логиката - е наједноставната логичка теорија. Атомскиот поим на исказната алгебра е изјава - декларативна реченица во однос на која има смисла изјавата за нејзината вистинитост или неточност.

Пример за вистинска изјава: „Земјата се врти околу сонцето“. Пример за лажна изјава: „3 > 5“. Не секоја реченица е изјава; изјавите не вклучуваат прашални и извични реченици. Реченицата: „Кашата е вкусно јадење“ не е изјава, бидејќи не може да има консензус дали е точно или неточно. Реченицата „Има живот на Марс“ треба да се смета за изјава, бидејќи објективно е или точно или неточно, иако никој сè уште не знае која.

Бидејќи предмет на проучување на логиката е само вистинитостите на предлозите, за нив се воведени ознаките на буквите A, B, ... или X, Y ....

Секоја изјава се смета за вистинита или неточна. За краткост, наместо вистинската вредност ќе напишеме 1, а наместо погрешната вредност 0. На пример, X= „Земјата се врти околу Сонцето“ и Y= „3 > 5“, и X=1 и Y= 0. Исказот не може да биде и вистинит и неточен.

Изјавите можат да бидат едноставни или сложени. Изјавите „земјата се врти околу сонцето“ и „3 > 5“ се едноставни. Сложените искази се формираат од едноставни со помош на природни (руски) јазични сврзници НЕ, И, ИЛИ, АКО-ТОГАШ, ТОГАШ-И-САМО-ТОГАШ. Кога се користи азбучна нотација за искази, овие сврзници се заменуваат со специјални математички симболи, кои може да се сметаат како симболи на логички операции.

Подолу, во табела 1, има варијанти на симболи за означување на врски и имиња на соодветните логички операции.

Негирање (инверзија) изјави Xе изјава која е вистинита ако и само ако Xнеточно (означено или , гласи „не X“ или „не е точно тоа X”).

сврзник
од два предлога се нарекува предлог што е точен ако и само ако двата предлога се вистинити Xи Y. Оваа логичка операција одговара на поврзувањето на изјавите со синдикатот „и“.

дисјункција
две реченици Xи YСе вели дека изјавата е лажна ако и само ако двете изјави Xи Yлажни. Во разговорниот говор, оваа логичка операција одговара на унијата „или“ (не ексклузивно „или“).

импликација две реченици X и Yе изјава која е неточна ако и само ако Xвистина, и Y- неточно (означено
; гласи " Xповлекува Y“, „ако X, тогаш Y”). Оперантите на оваа операција имаат посебни имиња: X- пакет, Y- заклучок.

Еквивалентност две реченици Xи Yсе нарекува изјава која е вистинита ако и само ако вистината вреднува Xи Yсе исти (симбол:
).

Табела 1. Логички операции

Операндите на логичките операции можат да земат само две вредности: 1 или 0. Затоа, секоја логичка операција , &, , ,  може лесно да се специфицира со помош на табелата, означувајќи ја вредноста на резултатот од операцијата во зависност од вредностите на операндите. Таквата табела се нарекува табела на вистината (Табела 2).

Табела 2. Табела на вистинитост на логички операции

Со помош на логичките операции дефинирани погоре, можно е да се изгради од едноставни предлози пропозициски логички формули претставувајќи различни сложени искази. Логичкото значење на сложената изјава зависи од структурата на исказот, изразена со формулата и логичките вредности на елементарните искази што го формираат.

За систематско проучување на формули кои изразуваат изјави, се воведуваат искази на променливи П, П 1 , П 2 , ..., П Н, земајќи вредности од множеството (0, 1).

Пропозициска логичка формула Ф (П 1 , П 2 ,..., П Н) се нарекува тавтологија или идентично точно ако неговата вредност за која било вредност П 1 , П 2 ,..., П Не 1 (точно). Се повикуваат формулите кои се оценуваат како точно за барем еден сет на списоци со променливи изводливо . Се повикуваат формулите што ја земаат вредноста „неточно“ за која било вредност на променливите противречности (идентично неточно, невозможно).

11.1. Концептот на алгоритмот и теоријата на алгоритми

Интуитивно, алгоритам се подразбира како процес на последователно решавање на проблем кој се одвива во дискретно време, така што во секој следен момент од времето, системот на објекти на алгоритмот се добива според одреден закон од системот на објекти кои биле достапни. во претходниот момент. Интуитивен затоа што, строго кажано, концептот на алгоритам е сличен на концептот на множество, кој е неопределен.

Во согласност со ГОСТ 19781-74 „Пресметувачки машини. Софтвер. Термини и дефиниции“ алгоритаме точен рецепт кој го дефинира пресметковниот процес кој води од променливи почетни податоци до посакуваниот резултат. Ова претпоставува присуство на извршител на алгоритам - објект што "знае како" да ги изврши овие дејства.

Зборот „алгоритам“ доаѓа од името на централноазискиот (узбекистански) математичар од XIII век Ал Хорезми (Абу Абдала Мухамед ибн Муса ал Хорезми ал Меџуси) - „Алгоритми“ во латинска транскрипција, кој прв ги формулирал правилата (постапка) за извршување на четири аритметички операции во декаден броен систем.

Сè додека пресметките беа едноставни, немаше посебна потреба од алгоритми. Кога имаше потреба од повеќе чекор-по-чекор процедури, тогаш се појави теоријата на алгоритми. Но, со уште поголема компликација на задачите, се покажа дека некои од нив не можат да се решат алгоритамски. Такви, на пример, се многу задачи што ги решава „вградениот компјутер“ на една личност - мозокот. Решението на ваквите проблеми се заснова на други принципи - овие принципи ги користи новата наука - невроматематиката и соодветните технички средства - неврокомпјутерите. Во овој случај се применуваат процесите на учење, обиди и грешки - односно она што моментално го работиме.

Квалитетот на алгоритам се одредува според неговите својства (карактеристики). Главните својства на алгоритмот се:

1. масовен карактер. Се претпоставува дека алгоритмот може да биде погоден за решавање на сите проблеми од овој тип. На пример, алгоритам за решавање на систем од линеарни алгебарски равенки треба да биде применлив за систем кој се состои од произволен број равенки.

2. Ефикасност. Ова својство значи дека алгоритмот мора да доведе до резултат во конечен број чекори.

3. Сигурност. Инструкциите вклучени во алгоритмот мора да бидат прецизни и разбирливи. Оваа карактеристика ја обезбедува единственоста на резултатот од пресметковниот процес за дадените првични податоци.

4. дискретност. Ова својство значи дека процесот опишан од алгоритам и самиот алгоритам може да се подели на посебни елементарни фази, можноста за која корисникот може да ја изврши на компјутер е несомнена.

Денес, „дигиталниот милениум“ е во дворот и можеби ќе добиете впечаток дека секоја задача е предмет на алгоритми. Излегува дека многу проблеми не можат да се решат алгоритамски. Тоа се таканаречените алгоритамски нерешливи проблеми.

За да се докаже алгоритамската решливост или нерешливост на проблемите, потребни се математички ригорозни и прецизни средства. Во средината на 30-тите години на минатиот век, беа направени обиди да се формализира концептот на алгоритам и беа предложени различни модели на алгоритми: рекурзивни функции; „машини“ - Тјуринг, Пост; нормални Марков алгоритми.

Последователно, беше откриено дека овие и други модели се еквивалентни во смисла дека класите на проблеми што ги решаваат се совпаѓаат. Овој факт се нарекува теза на Црквата. Сега ова е општо прифатено. Формалното дефинирање на концептот на алгоритам ги создаде предусловите за развој на теоријата на алгоритам уште пред развојот на првите компјутери. Напредокот на компјутерската технологија го стимулира понатамошниот развој на теоријата на алгоритми. Покрај утврдувањето на алгоритамската решливост на проблемите, теоријата на алгоритми се занимава и со проценка на сложеноста на алгоритмите во однос на бројот на чекори (временска сложеност) и потребната меморија (сложеност на просторот), а исто така развива и ефикасни алгоритми во оваа смисла.

За имплементација на некои алгоритми, под какви било разумни претпоставки од гледна точка на физиката за брзината на извршување на елементарните чекори, може да биде потребно повеќе време отколку, според современите гледишта, постои Универзумот или повеќе мемориски ќелии од атомите што ја сочинуваат планетата Земја.

Затоа, друга задача на теоријата на алгоритми е да го реши проблемот со елиминирање на набројувањето на опциите во комбинаторните алгоритми. Проценката на сложеноста на алгоритмите и создавањето таканаречени ефикасни алгоритми е една од најважните задачи на модерната теорија на алгоритми.

S. N. Pozdnyakov S. V. Rybin

Упатство

Министерство за образование и наука на Руската Федерација

Државниот електротехнички универзитет во Санкт Петербург „ЛЕТИ“

S. N. Pozdnyakov S. V. Rybin

МАТЕМАТИЧКА ЛОГИКА И ТЕОРИЈА НА АЛГОРИТМИ

Санкт Петербург СПбГЕТУ „ЛЕТИ“ издавачка куќа

UDC 510.6 BBK V12 P47

Pozdnyakov S. N., Rybin S. V. Математичка логика и теорија на алгоритми: Proc. додаток. Санкт Петербург: СПбГЕТУ „ЛЕТИ“, 2004. 64 стр.

Се разгледуваат главните идеи, концепти и методи на математичката логика, интересот за кој порасна поради новите апликации кои се појавија неодамна во врска со развојот на информатичката технологија.

Може да се користи и за редовни студенти и за вечерни и дописни факултети на техничките универзитети.

Рецензенти: Катедра за математичка анализа, Државен универзитет во Санкт Петербург; Доц. М. В. Дмитриева (државен универзитет во Санкт Петербург).

Одобрено од редакцискиот и издавачкиот одбор на универзитетот

како наставно помагало

Математичката логика, како и теоријата на алгоритми, се појави долго пред појавата на компјутерите. Нивната појава беше поврзана со внатрешните проблеми на математиката, со проучувањето на границите на применливоста на нејзините теории и методи.

AT Во моментов, двете од овие (меѓусебно поврзани) теории добија применет развој во таканаречената компјутерска математика (компјутерска наука). Еве неколку области на нивната употреба во применети области:

– користење на експертски системиформално-логички заклучоци за симулирање на активностите на експертите во различни области;

– при дизајнирање на микроциркути, се користи теоријата на Булови функции;

– тестирањето на програмите се заснова на логичка анализа на нивната структура;

– доказот за исправноста на програмите се заснова на теоријата на логичко заклучување;

– алгоритамските јазици поврзуваат два важни концепти на логика: концептот на јазик и концептот на алгоритам;

– автоматизацијата на докажувањето на теоремата се заснова на методот на резолуции изучуван во текот на логиката.

AT Овој учебник ги прикажува основните идеи, концепти и методи на математичката логика кои се во основата и на наведените и на другите негови примени.

1. Бинарни односи и графикони

1.1. Вовед. Формулирање на проблемот

Бинарни односи веќе се среќаваат на училишните курсеви по математика. Примери за такви односи се односите на нееднаквост, еднаквост, сличност, паралелизам, деливост итн. Бинарната релација на секој два објекта им ја доделува логичката вредност „да“ ако објектите се во оваа релација, а „не“ во спротивно. Со други зборови, множеството од парови објекти е поделено на две подмножества, паровите од првото подмножество се во оваа врска, а второто не. Ова својство може да се користи како основа за дефиниција на бинарна релација.

Дефиниција 1.1. Нека е дадено множество М. Размислете за декартов производ на ова множество и самиот M × M . Подмножество R од множество M ×M се нарекува бинарна релација R на множеството M . Ако парот (x; y) припаѓа на множеството R , се вели дека елементот x е во однос на елементот y и се запишува xRy.

Пример 1.1. Да ја воведеме релацијата за споредливост R: x е споредлива со cy модуло m ако и само ако x и y имаат ист модуло m. Тоа е, x ≡ y (мод m) .

Размислете за воведената релација R за случајот m = 3 на множеството M = (1; 2; 3; 4; 5; 6), тогаш

Релацијата R е дефинирана со множеството од такви парови:

Пример 1.2. Размислете како M = R множеството нешта

реални броеви или, со други зборови, множеството точки на реалната права. Тогаш M × M = R 2 е множеството точки во координатната рамнина. Релација на нееднаквост< определяется множеством парR = = {(x; y)|x < y} .

Вежба 1.1.

1. На множеството реални броеви е дадена релацијата: xRy тогаш

ако и само ако еден од броевите е двојно поголем од другиот. Нацртајте на рамнината множество точки што ја дефинираат оваа врска.

2. На множеството M = (1; 2; 3; 4; 5; 6) е дадена релацијата за деливост: xRy ако и само ако x е делив со y . Колку парови прави

дали е овој став? Наведете ги овие парови.

3. На множеството M = (1; 2; 3; 4; 5; 6) ја воведуваме релацијата со примарна порака, т.е. xRy ако и само ако x и y се сопрости: D(x; y) = 1 . Колку парови содржи оваа релација? Наведете ги овие

1.2. Својства на бинарни односи

Дефиниција 1.2. Се нарекува бинарна релација R на множество M

е рефлексивен ако секој елемент од ова множество е во врска со себе: xRx x M .

Пример 1.3.

1. Односот на споредливост е рефлексивен (за секое природно m и на кое било множество цели броеви).

2. Строгата релација на нееднаквост на множеството реални броеви не е рефлексивна.

3. Релацијата за деливост е рефлексивна (на кое било множество цели броеви што не содржат нула).

Дефиниција 1.3. Бинарна релација R на множеството М повикано

е антирефлексивен ако ниту еден елемент од ова множество не е во однос на самиот себе: x M не е точно дека xRx .

Пример 1.4.

1. Строгата релација на нееднаквост на множеството реални броеви е антирефлексивна.

2. Релацијата коприм е антирефлексивна на кое било множество цели броеви што не содржат 1 и −1 , е рефлексивен на множествата(1), (−1), (−1; 1) и не е ниту рефлексивен ниту антирефлексивен

во спротивно.

Дефиниција 1.4. Бинарна релација R на множество M се нарекува симетрична ако, заедно со секој пар (x; y), релацијата вклучува и симетричен пар (y; x) :x, y M xRy yRx.

Пример 1.5.

1. Односот на споредливост е симетричен за секое природно

2. Строгата релација на неравенство на множеството реални броеви не е симетрична.

3. Релацијата за деливост е симетрична само на множеството парни коприми цели броеви кои не содржат еден. На пример, на множеството прости броеви.

4. Релацијата коприм е симетрична на кое било множество цели броеви.

Дефиниција 1.5. Се нарекува бинарна релација R на множество M

е асиметричен ако ниту еден пар не влегува во релацијата заедно со неговата симетрична: x, y M , ако xRy , тогаш не е точно дека yRx .

Пример 1.6.

1. Строгата релација на неравенство на множеството реални броеви е асиметрична.

2. Релацијата за деливост не е асиметрична на ниту едно множество од цели броеви што не содржи нула.

Дефиниција 1.6. Се нарекува бинарна релација R на множество M

е антисиметричен ако ниту еден пар составен од различни елементи не влегува во релацијата заедно со неговата симетрична: x, y M , ако xRy и yRx тогаш x = y .

Пример 1.7.

1. Релацијата на нестриктна неравенка на множеството реални броеви е антисиметрична.

2. Релацијата за деливост е антисиметрична на кое било множество цели броеви што не содржат нула.

Вежба 1.2.

1. Дали е вистина дека асиметричната врска е секогаш антирефлексна? Докажи.

2. Дали е вистина дека симетричната врска е секогаш рефлексивна? Кажи ми.

3. Дали е вистина дека асиметричната врска е секогаш антисиметрична? Докажи.

4. Дали е вистина дека релацијата е асиметрична ако и само ако е антирефлексивна и антисиметрична? Докажи.

Дефиниција 1.7. Бинарната релација R е преодна ако, заедно со паровите (x; y), влегува и парот (x, z), т.е. x, y, x M ако xRy и

множество M, го нарекуваме u(y; z) во однос yRz , потоаxRz .

Забелешка 1.1. Својството на транзитивноста е добро илустрирано со релацијата достижливост: ако точката y е достапна од точката x, а точката z е достапна од точката y, тогаш точката z е достапна од точката x.

Пример 1.8.

1. Односот на споредливост е преоден за секое природно m и на кое било множество цели броеви.

2. Строгата (нестрога) релација на нееднаквост е преодна на кое било подмножество на реални броеви.

3. Релацијата за деливост е преодна на множеството цели броеви што не содржат нула.

4. Релацијата со примање не е преодна на ниту едно множество цели броеви. На пример, 2 е коприм за c3, 3 е коприм за c4, но 2 и 4 не се коприм.

Вежба 1.3. Дали е точно дека транзитивно и симетрично

ставот е секогаш рефлексивен? Докажи.

1.3. Начини за дефинирање на односите

Покрај експлицитното набројување на парови кои дефинираат бинарна релација, можни се следните начини на специфицирање на релации.

Специфицирање на постапката за верификација.

Пример 1.9.

1. Релацијата сопримерок се проверува со постапката за наоѓање на најголемиот заеднички делител: ако D(x; y) = 1, потоа (x; y) е вклучено во

односот на меѓусебната едноставност.

2. Односот на деливост се проверува со постапката на делење со остаток: ако x ≡ 0 (mod y) , тогаш (x; y) се вклучува во релацијата за деливост.

3. Истата постапка ја проверува врската на еднаквост на остатоците кога се дели со m : if(x−y)≡0 (mod m) , тогаш (x; y) е во релацијата.

За односите на конечни множества (кои се основни за дискретна математика), се користат и следните методи за специфицирање и опишување на релациите.

Одредување матрица за соседство. Дозволете ни да дефинираме матрица А со големина

|М| × |M |, каде што |M | е бројот на елементи од множеството М. Ги нумерираме елементите на множеството М. Тогаш aij = 1 ако елементот со број i е во врска со елементот со број j (iRj) и aij = 0 во спротивно.

Пример 1.10. Матрицата на соседност за односот на деливост на множеството M = (1; 2; 3; 4; 5; 6) изгледа вака:

Доделување графикони. Елементите на множеството се претставени со точки на рамнината и формираат множество темиња на графикот. Релацијата е претставена со лакови (рабови) на графикот: ако во релацијата е вклучена (x; y), тогаш од темето x до y се извлекува ориентиран лак.

Пример 1.11. Графикон за односот на споредливост модуло три на

Одредување листа на соседства. За секој елемент од множеството се наведени елементите кои се во оваа врска со него.

Пример 1.12. Списокот на соседство за копримерната релација на множеството M = (1; 2; 3; 4; 5; 6) изгледа вака:

Дозволете ни да дадеме интерпретација на својствата на бинарните односи на графиконите и матриците што ги опишуваат.

Теорема 1.1. Следниве тврдења се вистинити.

1. Дијагоналата на матрицата на соседството на рефлексивна релација се состои од едни.

2. Симетрична релација има симетрична матрица на соседство

3. Графикот на рефлексивни односи има јамки на секое теме.

4. График на симетрична релација заедно со лак што се поврзува x

со y , содржи лак што го поврзува y со x.

5. График на преодна релација го има следното својство: ако од теме x, движејќи се по лаците, можете да стигнете до темето y, тогаш мора да има лак во графикот што директно го поврзува x со y.

Забелешка 1.2. За симетрични

јамките обично не се цртаат, а паровите ориентирани лаци што ги поврзуваат дадените темиња се заменуваат со еден, ненасочен лак.

На пример, графикот во Пример 1.11 би изгледал како оној прикажан на Слика 1.11. 1.2.

и рефлексивни односи

Вежба 1.4.

1. Опишете ги својствата на матрицата на соседството: а) антирефлексивна врска; б) асиметрична врска; в) антисиметрична врска; г) преодна врска.

2. Опиши ги својствата на графикот: а) антирефлексивна врска; б) асиметрична врска; в) антисиметрична врска.

1.4. Релација на еквивалентност

Дефиниција 1.8. Бинарна релација која има својства на ре

нефлексивноста, симетријата и транзитивноста се нарекуваат еквивалентна врска.

Пример 1.13. Односот на споредливост (по кој било модул) е

се дава со еквивалентна релација.

Со секој елемент од множеството M да ги поврземе сите елементи што се со него во дадената еквивалентна релација: Mx = (y M | xRy). Следната теорема е вистинита.

Теорема 1.2. Множествата M x и M y или не се сечат или

Доказ. Сите елементи од иста класа се еквивалентни еден на друг, т.е. ако x, y Mz, тогаш xRy. Навистина, нека x, y Mz , па оттука и xRz и yRz. Според симетријата на R, имаме zRy. Потоа, поради транзитивноста, од xRz и zRy добиваме xRy.