Вовед.
Цел.
Нови делови од дискретниот курс по математика, иако имплементирани во форма наставни програмии серија предавања, сè уште не постојат во форма на монографии, барем на руски јазик, бидејќи текот на дискретната математика за техничките универзитетифокусирани на старите применети проблеми, што инженерите мораа да го решат. Конкретно во математичка логикатоа беше минимизирање логички кола, кој денес ја изгуби својата важност.
Интересно е да се забележи дека теоријата за синтеза на логички кола, која помина низ речиси целосен „биолошки циклус“ пред очите на една генерација истражувачи, е многу поучен пример за тоа како индустриите се многу подложни на застареност. техничките науки, слабо поврзан со фундаменталната наука. Пред 10 години се технички списанијабеа исполнети со написи за минимизирање и синтеза на логички кола. Повеќето од методите за минимизирање развиени од научниците сега се заборавени и не се барани во пракса. И оние идеи кои во тоа време се сметаа за чисто теоретски најдоа практична примена во модерна технологија. На пример, нејасната логика, петриевите мрежи и теоријата на алгоритам го поминаа тестот на времето и се широко користени во различни областикибернетика и програмирање, како на пр системско програмирање, компјутерска сложеност и вештачка интелигенција.
И теоријата на алгоритми стана централен дел на дискретната математика. Меѓутоа, за разлика од повеќето монографии на руски, во текот на предавањата овие прашања се претставени како средство за решавање на практични, инженерски проблеми.
Како што е познато, по секоја деценија, составната база на компјутерите, ОС, средствата за пристап и самите програми радикално се менуваат. Сепак, структурите и алгоритмите што стојат во основата на нив остануваат непроменети многу подолго. Овие основи почнаа да се поставуваат пред илјадници години, кога беше развиена формалната логика и беа развиени првите алгоритми.
Традиционално припаѓаат математичката логика и теоријата на алгоритми фундаментална наукаи се смета дека се од мала практична важност и тешко разбирливи. Навистина, кога J. Bull создаде математички апаратБулова алгебра, му требаше долго време да ја пронајде практична примена, сепак, во 20 век, токму овој математички апарат овозможи дизајнирање на сите компјутерски компоненти. Следствено, првата од овие предрасуди е успешно побиена со развојот компјутерска технологија.
Што се однесува до предрасудите за тешкотијата да се разбере оваа дисциплина, таа во голема мера произлегува од фактот дека книгите за математичката логика и теоријата на алгоритми биле напишани од математичари за математичари.
Сега, кога можностите на компјутерската технологија се зголемија многукратно, и на персонални компјутериИма многу повеќе луѓе од луѓе кои знаат како ефективно да ги користат, разбирањето што може и што не може да се направи со модерната компјутерска технологија е од најголема важност.
Точно општа теоријаалгоритмите покажаа дека постојат проблеми кои се нерешливи без разлика колку е моќна компјутерската моќ, а нејзината гранка која брзо се развива, теоријата на пресметковна сложеност, постепено води до разбирање дека постојат проблеми кои можат да се решат, но се објективно сложени, и нивната сложеност може да испадне дека е во некоја смисла апсолутна, тие. практично недостапни за современите компјутери.
Овој курс ги постави следните цели:
1. Претставете ги сите прашања што се разгледуваат што е можно поедноставно, но не поедноставно отколку што е потребно за високо квалификуван специјалист.
2. Практични проблемидизајн и анализа информациски системисе почетната точка, а формалниот апарат е средството систематско решениеовие проблеми. Наше длабоко убедување е дека студентот не е сад што треба да се наполни, туку факел што треба да се запали.
3. Секој дел од курсот содржи прашања за самотестирање. За асимилација овој курсод ученикот се бара да одговори на сите овие прашања.
Како резултат на совладувањето на овој курс, студентот, врз основа на јасно разбирање на релевантните теоретски делови, треба да биде способен:
Спроведување наједноставна форма логичка конверзијаинформации во произволна основа на логички функции;
Истакнете во доказното расудување природен јазиклогичка структура, конструирајте формални шеми за докажување и проверете ја нивната исправност.
1.2 Логички претстави
Логички претстави -опис на системот, процес, феномен што се проучува во форма на множество сложени изјависоставена од едноставни (елементарни) исказиИ логички врски
помеѓу нив. Логичките претстави и нивните компоненти се карактеризираат со одредени својства и збир на дозволени трансформации над нив (операции, правила за заклучување итн.), имплементирајќи ги оние развиени во формални (математички) логика правилни методирасудување - законите на логиката.
Се изучуваат методи (правила) на формално прикажување на искази, изградба на нови искази од постојните со помош на логички правилни трансформации, како и методи (методи) за утврдување на вистинитоста или неточноста на исказите. математичка логика.Современата математичка логика вклучува два главни дела: логика на изјавитеи покривајќи го предикатна логика(Сл. 1.1), за чија конструкција постојат два пристапи (јазици), кои формираат две варијанти на формалната логика: алгебра на логикатаИ логички пресметки.Постои кореспонденција еден на еден помеѓу основните концепти на овие јазици на формалната логика. Нивниот изоморфизам на крајот е обезбеден со единството на основните дозволени трансформации.
Ориз. 1.1
Главните објекти на традиционалните гранки на логиката се изјавите.
Изјава - декларативна реченица (изјава, пресуда), ошто има смисла да се каже дека тоа вистинаили лажни.Сите научни сознанија(закони и феномени на физиката, хемијата, биологијата итн., математички теореми итн.), настани Секојдневниот живот, ситуациите кои произлегуваат во економијата и процесите на управување се формулирани во форма на изјави. Императивните и прашалните реченици не се изјави.
Примери на изјави: „Двапати два е четири“, „Живееме во 21 век“, „Рубљата е руска валута“, „Аљоша е брат на Олег“, „Операциите на спојување, пресек и собирање се Булови операции на множества “, „Човекот е смртен“, „Преуредувањето на местата на термините не ја менува сумата“, „Денес е понеделник“, „Ако врне, треба да земеш чадор“.
За понатаму да работиме со овие реченици како искази, мора да знаеме за секоја од нив дали е точно или неточно, т.е. познај ги вистина вредност (вистината).Забележете дека во некои случаи вистинитоста или неточноста на изјавата зависи од тоа каква конкретна реалност (систем, процес, феномен) се обидуваме да ја опишеме со нејзина помош. Во овој случај, дадената изјава се вели дека е точно (или неточно) во дадено толкување (контекст). Понатаму претпоставуваме дека контекстот е даден и изјавата има одредена вистинита вредност.
1.3 Историја на развиена математичка логика
Логиката како наука е формирана во IV век. п.н.е. Создаден е од грчкиот научник Аристотел.Зборот „логика“ доаѓа од грчкиот „логос“, што од една страна значи „збор“ или „излагање“, а од друга, размислување. ВО објаснувачки речникОжегова С.И. Се вели: „Логиката е наука за законите на размислувањето и неговите форми“. Во 17 век Германскиот научник Лајбниц планирал да создаде нова наука, која би била „уметност на пресметување на вистината“. . Во оваа логика, според Лајбниц, секоја изјава би имала соодветен симбол, а расудувањето би имало облик на пресметки. Оваа идеја на Лајбниц, бидејќи не го исполни разбирањето на неговите современици, не беше раширена или развиена и остана брилијантна претпоставка.
Само во средината на 19 век. Ирскиот математичар Џорџ Бул ја отелотвори идејата на Лајбниц.Во 1854 година, тој го напиша делото „Истражување на законите на мислата“, кое ги постави темелите за алгебрата на логиката, во која важат законите слични на законите на обичната алгебра, но буквите важат. не означуваат бројки, туку искази. На јазикот на Буловата алгебра, може да се опише расудувањето и да се „пресметат“ неговите резултати. Сепак, тоа не ги опфаќа сите расудувања, туку само одредено нивниот тип, Затоа, Буловата алгебра се смета за исказна пресметка.
Алгебрата на Буловата логика беше ембрионот нова наука– математичка логика. Спротивно на тоа, логиката на Аристотел се нарекува традиционална формална логика. Името „математичка логика“ одразува две карактеристики на оваа наука: прво, математичката логика е логика која го користи јазикот и методите на математиката; второ, математичката логика ја оживуваат потребите на математиката.
На крајот на 19 век. Теоријата на множества создадена од Георг Кантор се чинеше дека е сигурна основа за целата математика, вклучително и математичката логика, барем за исказната пресметка (Бул алгебра), бидејќи Се покажа дека Канторската алгебра (теорија на множества) е изоморфна на Буловата алгебра.
Самата математичка логика стана гранка на математиката која на почетокот изгледаше многу апстрактно и бескрајно далеку од практични апликации. Сепак, оваа област не остана долго време во доменот на „чистите“ математичари. На почетокот на 20 век. (1910) Рускиот научник Еренфест П.С. укажа на можноста за користење на апаратот на Буловата алгебра во телефонските комуникации за опишување на прекинувачки кола. Во 1938-1940 година, речиси истовремено, делата на советскиот научник В.И. Шестаков, американскиот научник Шенон и јапонските научници Накашима и Хаказава се појавија за примената на математичката логика во дигиталната технологија. Првата монографија посветена на употребата на математичка логика во дизајнот на дигитална опрема беше објавена во СССР од советскиот научник М.А. Гаврилов. во 1950 година. Улогата на математичката логика во развојот на модерната микропроцесорска технологија е исклучително важна: се користи во дизајнот на компјутерски хардвер, во развојот на сите програмски јазици и во дизајнот на дискретни уреди за автоматизација.
Научниците дадоа голем придонес во развојот на математичката логика различни земји: Професор на Казанскиот универзитет Поретски П.С., де-Морган, Пирс, Тјуринг, Колмогоров А.Н., Хајдел К. и др.
1.4 Прашања за самотестирање.
1. Формулирајте ги целите на курсот
Испратете ја вашата добра работа во базата на знаење е едноставна. Користете ја формата подолу
Студентите, дипломираните студенти, младите научници кои ја користат базата на знаење во нивните студии и работа ќе ви бидат многу благодарни.
Сè уште нема HTML верзија на делото.
Можете да ја преземете архивата на делото со кликнување на врската подолу.
Слични документи
Основни дефиниции за математичка логика, Булови и еквивалентни функции. Општи концептиБулова алгебра. Жегалкин алгебра: изјави и предикати. Дефиниција формална теорија. Елементи на теоријата на алгоритми, рекурзивни функции, Турингова машина.
курс на предавања, додаден 08/08/2011
Основни форми на размислување: концепти, судови, заклучоци. Есеј од Џорџ Бул кој детално ја истражува логичката алгебра. Вистинската вредност (т.е. вистинитост или неточност) на изјавата. Логички операции на инверзија (негација) и сврзник.
презентација, додадена на 14.12.2016 година
Графичко толкување на множества и операции на нив. Математичка логика, Булова алгебра. Совршена конјунктивна нормална форма. Еквивалентни формули и нивно докажување. Комплетност на системот Булова функции. Логика на предикати, теорија на графикони.
предавање, додадено на 12.01.2009
Историја на појавата на Буловата алгебра, развој на пропозиционен калкулусен систем. Методи за утврдување на вистинитоста или неточноста на сложените логички искази користејќи алгебарски методи. Дисјункција, сврзник и негација, табели на вистинитост.
презентација, додадена на 22.02.2014 година
Квадратни матриции детерминанти. Координација на линеарен простор. Системско истражување линеарни равенки. Алгебра на матрици: нивно собирање и множење. Геометриска слика сложени броевии нив тригонометриска форма. Лапласова теорема и основа.
прирачник за обука, додаден на 02.03.2009 година
Основниот концепт на теоријата на позитивни (природни) броеви. Изработка на стенографија за аритметички операции. Симболичен јазик за деливост. Својства и алгебра на споредбите. Подигнување на споредби со моќи. Повторно квадратирање. Малата теорема на Ферма.
презентација, додадена на 04.06.2014 година
Системи дигитална обработкаинформации. Концептот на Буловата алгебра. Ознаки на логички операции: дисјункција, сврзник, инверзија, импликација, еквиваленција. Законите и идентитетите на Буловата алгебра. Логички основиКОМПЈУТЕР. Конверзија на структурни формули.
презентација, додадена на 11.10.2014 година
Книгата е напишана врз основа на материјали од предавања и семинари спроведени од авторите за помлади студенти на Механичко-математичкиот факултет на Московскиот државен универзитет. Зборува за основните концепти на математичката логика (пропозициска логика, јазици од прв ред, изразливост, пресметување на исказот, теории што може да се решаваат, теорема за комплетноста, принципи на теоријата на модели). Презентацијата е наменета за студенти математички училишта, студенти по математика и сите заинтересирани математичка логика. Книгата вклучува околу 200 проблеми со различна тежина.
Логика на изјавите.
Изреки и операции
„Ако бројот n е рационален, тогаш n - алгебарски број. Но, тоа не е алгебарски. Значи, п не е рационално“. Не мора да знаеме што е бројот n, кои броеви се нарекуваат рационални, а кои алгебарски, за да препознаеме дека ова расудување е точно во смисла дека заклучокот всушност произлегува од двете наведени премиси. Ваквата ситуација - кога одредена изјава е вистинита без оглед на значењето на исказите вклучени во неа - претставува предмет на пропозициската логика.
Овој почеток (особено ако се земе предвид дека логичкиот курс беше дел од програмата на Филозофскиот факултет, каде се изучуваше и „дијалектичка логика“) е алармантен, но всушност нашите размислувања ќе имаат сосема прецизна математичка природа, иако ќе започнеме со неформални мотивации.
Содржина
Предговор
1. Пропозициска логика
1.1. Изреки и операции
1.2. Комплетни лигаментни системи
1.3. Шеми на функционални елементи
2. Пропозиција пресметка
2.1. Пропозиционен Калкулус (ПЦ)
2.2. Втор доказ за теоремата за комплетноста
2.3. Наоѓање контрапример и последователна пресметка
2.4. Интуиционистичка пропозициска логика
3. Јазици од прв ред
3.1. Формули и толкувања
3.2. Дефиниција на вистината
3.3. Изразливи предикати
3.4. Изразливост во аритметиката
3.5. Неискажливи предикати: автоморфизми
3.6. Елиминација на квантификатори
3.7. Пресбургер аритметика
3.8. Теорема Тарски-Зајденберг
3.9. Елементарна еквивалентност
3.10. Играта на Еренфехт
3.11. Намалување на моќноста
4. Пресметување на предикат
4.1. Општо валидни формули
4.2. Аксиоми и правила за заклучување
4.3. Исправност на пресметувањето на прирокот
4.4. Заклучоци во пресметување на предикати
4.5. Комплетност на пресметувањето на прирокот
4.6. Преименување на променливи
4.7. Нормална форма со префикс
4.8. Хербрандова теорема
4.9. Функции на Сколемов
5. Теории и модели
5.1. Аксиоми на еднаквост
5.2. Зголемување на моќноста
5.3. Целосни теории
5.4. Нецелосни и нерешливи теории
5.5. Дијаграми и екстензии
5.6. Ултрафилтри и компактност
5.7. Нестандардна анализа
Литература
Индекс на тема
Индекс на имиња.
Бесплатно преземање е-книгаво пригоден формат, гледајте и читајте:
- fileskachat.com, брзо и бесплатно преземање.
Преземете pdf
Подолу можете да ја купите оваа книга по најдобра цена со попуст со испорака низ цела Русија.Купете ја оваа книга
Преземете ја книгата Предавања за математичка логика и теорија на алгоритми, Дел 2, Јазици и пресметка, Верешчагин Н.К., Шен А., 2012 година - pdf - датотеки со депозити.
Универзитетот Волжски именуван по. Татишчева.
Предавања по математичка логика и теорија на алгоритми.
Составил: вонреден професор С.В. Каверин.
Поглавје I. Алгебра на логиката.
§1.1. Дефиниција на Булова функција.
Булова функција y=f(x 1,x 2,…,x n)од Ппроменливи x 1 , x 2 ,...,x n е која било функција во која аргументите и функцијата можат да ја земат вредноста или 0 или 1, т.е. Буловата функција е правило според кое произволно множество од нули и единици
(x 1 , x 2 ,..., x n) се доделува на вредноста 0 или 1.
Булова функцииисто така се нарекува Функции на логичка алгебра, бинарни функции и преклопни функции.
Булова функција од n променливите може да се специфицираат со табела на вистинитост во која множества на вредности на аргументи се распоредени по растечки редослед на нивните броеви : прво регрутирањето е во тек, претставувајќи го бинарното проширување од 0 (ова множество е нумерирано со 0); потоа доаѓа множеството, кое е бинарно проширување на 1, потоа 2, 3 итн. Последниот сет се состои од n единици и е бинарно проширување на бројот 2 n-1 (овој редослед на распоред на множества ќе се вика лексикографски ред). Имајќи предвид дека броењето започнува од 0, а вредноста на Буловата функција може да биде или 0 или n
1, заклучуваме дека има само 22 различни Булови функции на n променливи. Така, има, на пример, 16 Булови функции од две променливи, 256 од три итн.
Пример 1.1.1.(гласање) . Да разгледаме уред кој го снима усвојувањето на одредена резолуција од страна на „комитетот на тројца“. Секој член на комисијата го притиска своето копче кога одобрува резолуција. Доколку мнозинството членови гласаат за, резолуцијата се усвојува. Ова е снимено од уред за снимање. Така, уредот ја имплементира функцијата f(x,y,z ) , чија табела на вистинитост има форма
| x | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| y | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
| z | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| f(x,y,z) | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
Буловата функција е исто така уникатно специфицирана со набројување на сите торки на кои ја зема вредноста 0, или со набројување на сите торки на кои ја зема вредноста 1. Функцијата добиена во примерот ѓможе да се специфицира и со следниот систем на еднаквости: f(0,0,0) = f(0,0,1) = f(0,1,0) = f(1,0,0) =0.
Вектор на вредности на Буловата функција y=f(x 1,x 2,…,x n) е подредено множество од сите вредности на функцијата f, во кое вредностите се подредени по лексикографски редослед. На пример, нека функција од три променливи f биде одредена со вектор на вредности (0000 0010) и треба да најдете множество на кое f ја зема вредноста 1. 1 е на 7-мо место, а нумерира лексикографски редзапочнува на 0, тогаш треба да го најдеме бинарното проширување на 6. Така, функцијата f ја зема вредноста 1 на множеството (110).
§1.2. Елементарни Булови функции.
Меѓу Буловите функции се издвојуваат таканаречените елементарни Булови функции, со помош на кои може да се опише која било Булова функција од кој било број на променливи.
1. Буловата функција f(x 1 , x 2 ,..., x n) земајќи ја вредноста 1 на сите множества нули и единици се нарекува константа 1, или идентична единица. Означување : 1 .
2. Булова функција f(x 1 , x 2 ,..., x n) земајќи ја вредноста 0 на сите множества нули и единици се нарекува константа 0, или идентична нула. Означување : 0 .
3. Негирањее Булова функција на една променлива која е дефинирана со следната табела на вистинитост
Други имиња : логичко множење (производ); логично „и“.
Ознаки : x&y, xÿy, x⁄y, min(x,y).
5. Дисјункција
Друго име : логична последица. Ознаки : xØy, xfly, xy.
7. Еквивалентносте Булова функција од две променливи што е дефинирана со следната табела на вистинитост
Друго име : анти-еквивалентност. Ознаки : x∆y, x+y.
9. Мозочниот удар на Шефер еБулова функција од две променливи што е дефинирана со следната табела за вистинитост
Друго име : негација на дисјункција, логично „не-или“, функција Webb.
Означување : x∞y ; за функцијата Webb - x±y.
Коментар.Симболите Ÿ, ⁄, ¤, Ø, ~, ∆, |, ∞ вклучени во ознаката елементарни функцииќе ги наречеме врски или операции.
§1.3. Одредување Булова функции со помош на елементарни.
Ако замените некои Булова функции со логичка функција наместо променливи, резултатот е нова Булова функција наречена суперпозицијазаменети функции (комплексна функција). Користејќи суперпозиција, можете да добиете посложени функции кои можат да зависат од кој било број на променливи. Пишувањето ќе го наречеме Булови функции во смисла на елементарни Булови функции формуласпроведувањето оваа функција.
Пример 1.3.1.Нека е дадена елементарна Булова функција x¤y. Да ја замениме функцијата x 1 ∞x 2 наместо x. Добиваме функција од три променливи (x 1 ∞x 2)¤y. Ако наместо променливата y замениме, на пример, x 3 ∆x 4, тогаш добиваме нова карактеристикаод четири променливи: (x 1 ∞x 2)¤(x 3 ∆x 4). Очигледно, на овој начин ќе добиеме Булови функции, кои ќе бидат изразени преку елементарни Булови функции.
Гледајќи напред, го забележуваме тоа било којБуловата функција може да се претстави како суперпозиција на елементарни функции.
За покомпактно снимање сложени функциида ги воведеме следните конвенции : 1) надворешните загради се испуштени; 2) прво се вршат операции во загради; 3) се смета дека приоритетот на приклучоците се намалува по следниот редослед : Ÿ, ⁄, ¤, Ø, ~. За еквивалентни сврзници и преостанатите сврзници (∆,|,∞), треба да ставите загради засега.
Примери 1.3.2.Во формулата x⁄y¤z се поставени заградите на следниот начин: ((x⁄y)¤z), бидејќи операцијата ⁄ е посилна од операцијата ¤ според нашиот договор.
1. Во формулата x¤y~zØx заградите се поставени на следниов начин: ((x¤y)~(zØx))
2. Во формулата (x∆y)~zØxy¤Ÿz заградите се поставени на следниов начин: ((x∆y)~(zØ((xy)¤(Ÿz)))).
3. Формулата xØyØz, по нашиот договор, не е правилно напишана, бидејќи ставањето загради резултира во две различни функции: ((xØy)Øz) и (xØ(yØz)).
§1.4. Значајни и незначајни променливи.
Булова функција y=f(x 1 , x 2 ,…, x n) зависи значителноод променлива x k ако постои таков сет на вредности а 1 ,а 2 ,…,а k - 1, а k+1, а k + 2,…, а nдека ѓ (а 1, а 2,…,а k-1 , 0 , а k+1,a k+2,…,а н) π ѓ (а 1, а 2,…,а k-1 , 1 , а k+1,a k+2,…,а n).
Во овој случај x k се нарекува суштинска променлива , В во спротивно x k се нарекува незначителна (кукла) променлива . Со други зборови, променливата е ирелевантна ако нејзиното менување не ја менува вредноста на функцијата.
Пример 1.4.1.Нека Буловите функции f 1 (x 1 , x 2) и f 2 (x 1 , x 2) се дефинирани со следнава табела за вистинитост:
| x 1 | x 2 | f 1 (x 1 , x 2) | f 2 (x 1 , x 2) |
| 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 |
За овие функции променливата x 1 - е значајна, а променливата x 2 не е значајна.
Очигледно, Буловите функции не ги менуваат своите вредности со воведување (или отстранување) ирелевантни променливи. Затоа, во следново, Буловите функции се сметаат до неважни променливи (во примерот можеме да напишеме: f 1 (x 1 , x 2) = x 1 , f 2 (x 1 , x 2) = Ÿx 1 ).
§1.5. Табели на вистината. Еквивалентни функции.
Знаејќи ги табелите на вистинитост за елементарните функции, можете да ја пресметате табелата на вистинитост на функцијата што ја спроведува оваа формула.
Пример 1.5.1. F1=x 1 ⁄x 2 ¤(x 1 ⁄Ÿx 2 ¤Ÿx 1 ⁄x 2)
Така, формулата F1 ја спроведува дисјункцијата. Пример 1.5.2. F2=x 1 ⁄x 2 Øx 1
Така, формулата F3 ја спроведува дисјункцијата.
Се повикуваат Буловите функции f1 и f2 еквивалент, ако на секој сет ( а 1 ,а 2 ,…, n) нули и единици, вредностите на функциите се совпаѓаат. Ознаката за еквивалентни функции е како што следува : f1=f2.
Според дадените примери 1-3, можеме да пишуваме
X 1 ⁄x 2 ¤(x 1 ⁄Ÿx 2 ¤Ÿx 1 ⁄x 2)=x 1 ¤x 2 ;
X 1 ⁄x 2 Øx 1 =1;
((x 1 ⁄x 2)∆x 1)∆x 2 =x 1 ¤x 2.
§1.6. Основни еквиваленции.
Дадените еквиваленции често се корисни кога се работи со Булови функции.
Под H, H1, H2,... значат некои Булови функции.
1. Закон за двојна негација: H = H.
2. Идемпотенција
3. Комутативност:
H1*H2=H2*H1, каде што симболот * значи едно од сврзниците &, ¤, ∆,
4. Асоцијативност:
H1*(H2*H3)=(H1*H2)*H3, каде што симболот * значи едно од сврзниците &, ¤, ∆, ~.
5. Дистрибутивноста:
H1&(H2¤H3)=(H1&H2)¤(H1&H3); H1¤(H2&H3)=(H1¤H2)&(H1¤H3); H1&(H2∆H3)=(H1&H2)∆(H1&H3).
6. Законите на Де Морган:
H1& H2 = H1 ∨ H2, H1∨ H2 = H1 & H2.
7. Правила за преземање:
H1¤(H2&H3)=H1, H1&(H2¤H3)=H1
8. Закони за лепење:
H1&H2 ∨ H1&H2 = H1, (H1∨ H2) & (H1∨ H2) = H1.
9. Закони за инверзија: H ∨ H = 1, H & H = 0.
10. Правила за операции со константи:
H¤1=1, H&1=H, H¤0=H, H&0=0.
За да се провери вистинитоста на горенаведените еквиваленции, доволно е да се конструираат соодветните табели на вистинитост.
Забележете дека својството на асоцијативност на операцијата дозволува оваа операција да се прошири на кој било број на променливи. Така, на пример, ознаката x¤у¤z¤w е точна, бидејќи секое распоредување на загради резултира со истата функција. Комутативната природа на операцијата ви овозможува да замените променливи во формула. На пример, x⁄y⁄z⁄w=w⁄y⁄x⁄z.
§1.7. Функционална комплетност.
Во типичен модерен дигитален компјутер, броевите се 0 и 1. Според тоа, инструкциите што ги извршува процесорот се Булови функции. Подолу ќе покажеме дека која било Булова функција се имплементира преку конјункција, дисјункција и негација. Следствено, можно е да се изгради потребниот процесор, имајќи на располагање елементи кои имплементираат сврзување, дисјункција и негација. Овој дел е посветен на одговорот на прашањето: дали има (и ако има, какви) други системи на Булови функции кои имаат својство дека можат да се користат за изразување на сите други функции.
Дозволете ни да воведеме неколку класи на функции.
1. Класата на функции кои ја зачувуваат константата 0, т.е. таквите функции
2. Класата на функции кои ја зачувуваат константата 1, т.е. таквите функции
3. Класата на само-двојни функции, т.е. такви функции y=f(x 1 ,x 2 ,…,x n) такви што f(x 1 , x 2 ,… , x n) = f(x 1 , x 2 ,… , x n) .
4-то одделение линеарни функции, т.е. такви функции y=f(x 1 ,x 2 ,…,x n), кои можат да се претстават како f(x 1 ,x 2 ,…,x n)=c 0 ∆c 1 x 1 ∆c 2 x 2 ∆… ∆ c n x n, каде што c 0, c 1, c 2 ...коефициенти кои можат да ја земат вредноста 0 или 1.
5. Час монотони функции. На множеството од нули и единици Bn =((x 1 ,x 2 ,…,x n):x i œ(0,1),i=1,2,…,n) воведуваме делумен редослед како што следува:
(а 1 ,а 2 ,...,а н)§( б 1 ,б 2 ,...,б н) ако и само ако а 1 § б 1 , а 2 § б 2,…,а n § б n. Функцијата f(x 1, x 2,..., x n) се нарекува монотона ако за кои било два елементи од B n таква што
(а 1 ,а 2 ,...,а н)§( б 1 ,б 2 ,...,б н) следува дека f( а 1 ,а 2 ,...,а н)§f( б 1 ,б 2 ,...,б н).
Се нарекува систем S на Булови функции, чија суперпозиција може да претставува која било Булова функција функционално комплетен . Велат дека е функционален комплетен системСе формираат S Булови функции основаво логички простор. Се нарекува основата S минимална , ако отстранувањето на која било функција од неа го претвори овој систем во нецелосен.
Критериум за комплетност (Теорема на пост) . Систем S од Булови функции е комплетен ако и само ако вклучува барем една функција: незачувувачка константа 0, незачувувачка константа 1, несамо-двојна, нелинеарна и немонотона.
Табелата 1.7 ги прикажува својствата што ги имаат елементарните Булови функции (симболот * означува својство што го има дадена функција).
Користејќи ја теоремата на Пост и табела 1.7, можете да изградите основи од елементарни функции според следното правило. Со избирање на која било елементарна Булова функција и нејзино дополнување, доколку е потребно, со други функции, така што сите заедно ја задоволуваат теоремата за функционална комплетност. Преку функциите на оваа основа можеме да изразиме Сите други Булови функции.
Ајде да конструираме некои често користени основи во апликациите.
Табела 1.7
| Име | Означување | Нескладирање константи |
Нескладирање константи |
Самодвоји валидност |
||
| Конст.0 | 0 | * | * | |||
| Конст.1 | 1 | * | * | |||
| Негативни | Ÿ | * | * | * | ||
| Конгјун. | & | * | * | |||
| Дисјункција. | ¤ | * | * | |||
| Имплицитно. | Ø | * | * | * | * | |
| Еквивалент. | ~ | * | * | * | ||
| Збир по mod_2 | ∆ | * | * | * | ||
| | | * | * | * | * | * | |
| Стрела на Пирс | ∞ | * | * | * | * | * |
1. Системот на функции S1=(Ÿ,⁄,¤) формира основа. За да се намали Буловата функција на форма која содржи само сврзници од основата S1, следните еквиваленции може да бидат корисни: x → y = x ∨ y , x ↔ y = (x ∨ y)(x ∨ y), x ⊕ y = xy ∨ xy, xy = x ∨ y, x ↓ y = x & y.
2. Системот S2=(Ÿ,&) формира основа. Произволна функцијаможе прво да се сведе на форма која содржи сврзници од S1, а потоа
користете ја релацијата x ∨ y = x ⋅ y.
3. Системот S3=(Ÿ,¤) формира основа. Произволна функција најпрво може да се сведе на форма која содржи сврзници од S1, а потоа
користете ја релацијата x ⋅ y = x ∨ y.
4. Системот S4=(1,&,∆) формира основа. Произволна функција најпрво може да се сведе на форма што содржи сврзници од S1, а потоа да се користат релациите x = 1⊕ x, x ∨ y = x ⊕ y ⊕ x ⋅ y.
5. Системот S5=(|) формира основа. Произволна функција најпрво може да се сведе на форма што содржи сврзници од S2, а потоа да ги користи релациите x ⋅ y = x y, x = xx.
6. Системот S6=(∞) формира основа. Произволна функција најпрво може да се сведе на форма која содржи поврзувања од S3, а потоа
користете ги релациите x ∨ y = x ↓ y, x = x ↓ x.
7. Системот S7=(Ø,0) формира основа.
Пример 1.7.1.Запишете ја функцијата x¨(y∆z) во основата S1=(Ÿ,⁄,¤). x ↔ (y ⊕ z) = (x ∨ y ⊕ z) ⋅(x ∨ (y ⊕ z)) = (x ∨ y ⋅ z ∨ y ⋅ z) ⋅(x ∨ y ⋅ z ∨ y) y
Поглавје II. Булова алгебра.
Множество од сите булови во основата S1=( ÿ, &, ⁄} форма Булова алгебра. Така, во Буловата алгебра, сите формули се напишани со користење на три сврзници: Ÿ, &, ¤. Делумно ги испитавме својствата на оваа алгебра во Поглавје I (види, на пример, основни еквиваленции). Ова поглавје се занимава со својства специфични за Буловата алгебра и затоа во текот на ова поглавје ќе се занимаваме само со три функции: ÿ, &, ⁄.
§2.1. Нормални форми.
Нормалните форми се синтаксички недвосмислен начин на пишување формула што имплементира дадена функција.
Ако x е логичка променлива, а σœ(0,1) тогаш изразот x σ = x ако ако σσ == 10 или x σ = 10 ако x x =≠σσ , x се нарекува буква . Буквите x и Ÿx се нарекуваат спротивности. Спој дисјункцискинаречена дисјункција на буквите. На пример, формулите x ⋅ y ⋅ z и x ⋅ y ⋅ x ⋅ x се сврзници, формулите x ∨ y ∨ z и x ∨ y ∨ x се дисјунктни, а формулата z е и конјункт и дисјункнт.
Дисјунктивна нормална форма (DNF)се нарекува дисјункција на конечен број сврзници .
Конјунктивна нормална форма (CNF)се нарекува сврзник од конечен број реченици .
Поедноставно: DNF е збир на производи, а CNF е производ на логички суми.
1. xÿy¤yÿz¤x е DNF (збир на производи).
2. (x ∨ y ∨ z)⋅(x ∨ y)⋅z е CNF (производ на збирови).
3. x ∨ y ∨ z ∨ w е DNF и CNF (истовремено).
4. x ⋅ y ⋅ z ⋅ w е DNF и CNF (истовремено).
5. (x¤x¤y)·(y¤z¤x)·z е CNF.
6. x⋅y⋅z и x⋅y⋅x⋅x се DNF.
7. x ⋅(x ∨ yz)⋅ x ⋅ y ⋅ z не е нормална форма (не DNF или CNF).
Нека функцијата f е запишана во основата S1. Оваа функција е сведена во нормална форма како што следува:
1) ги користиме законите на Де Морган за да ја трансформираме формулата во форма во која негативните знаци се однесуваат само на поединечни променливи;
2) го применуваме правилото за отстранување на двојните негативи: ŸŸx=x;
H1&(H2¤H3)=(H1&H2)¤(H1&H3) и вториот дистрибутивен закон за редукција на CNF. H1¤(H2&H3)=(H1¤H2)&(H1¤H3).
Секоја Булова функција може да има бесконечен број на DNF и CNF претстави. На пример, користејќи ги дополнително законите за инверзии и правилата за операции со константи, можно е да се осигура дека во секоја поединечна сврзница или дисјункца која било променлива се појавува не повеќе од еднаш (или самата или нејзината негација).
Пример 2.1.1.За да се намали на DNF, го користиме првиот закон за дистрибутивноста.
x⋅y⋅x⋅y⋅z⋅(y∨z)=x⋅y⋅(x∨y∨z)⋅(y∨z)=(x⋅y⋅x∨x⋅y⋅y∨x⋅y ⋅z)⋅(y∨z)= е CNF
= (0∨ x⋅y∨ x⋅y⋅z)⋅(y∨ z) = (x⋅y∨ x⋅y⋅z)⋅(y∨ z) = - ова е уште еден CNF
X ⋅ y⋅у ∨ x ⋅ y⋅z⋅ y ∨ x ⋅y⋅z ∨ x ⋅ y⋅z⋅z = 0∨ 0∨ x ⋅y⋅z ∨ x ⋅z = y
X ⋅ y ⋅ z ∨ x ⋅ y ⋅ z е DNF
Пример 2.1.2. За да се намали на CNF потребно е да се користи вториот закон за дистрибутивноста.
x ∨ y ⋅ x ⋅ y ∨ z = x ∨ y ⋅ (x ⋅ y ⋅ z) = x ∨ y ⋅ (x ∨ y) ⋅ z =
X∨y⋅z⋅(x∨y)=(x∨y⋅z)⋅(x∨x∨y)=(x∨y)⋅(x∨z)⋅(1∨y)=
= (x ∨ y) ⋅ (x ∨ z) е CNF
§2.2. Совршени нормални форми.
Ако во секој член на нормална форма се претставени сите променливи (или тие самите или нивните негации), и во секоја поединечна сврзница или дисјункција која било променлива се појавува точно еднаш (или самата или нејзината негација), тогаш оваа форма се нарекува совршена нормална форма (SDNF или SCNF). Примери:Нека е дадена функција од три променливи f(x,y,z).
1. x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z е совршен DNF.
2. (x ∨ y ∨ z)⋅(x ∨ y ∨ z)⋅(x ∨ y ∨ z) е совршен CNF.
3. (x ∨ y) ⋅ (x ∨ z) не е совршен CNF, бидејќи на пример, првиот збир не ја вклучува променливата z.
4. xÿyÿz е совршен DNF. Теорема 2.2.1.
1. Секоја Булова функција која не е идентично нула има само еден SDNF, до локацијата на поимите.
2. Секоја Булова функција која не е идентична со 1 има само еден SCNF, до локацијата на термините.
Теоремата ќе ја докажеме конструктивно, како решение на следниот проблем: Користејќи ја оваа табела на вистинитост, конструирајте SDNF.
Да го разгледаме решението користејќи го примерот на функцијата f(x,y,z) дадена во табела (табела 2.2) за n=3.
Пример 2.2.1.Користејќи ја оваа табела на вистинитост (Табела 2.2), конструирајте SDNF.
Табела 2.2
| x | y | z | основни сврзници |
f(x,y,z) |
| 0 | 0 | 0 | x ⋅ y ⋅ z | 0 |
| 0 | 0 | 1 | x ⋅ y ⋅ z | 1 |
| 0 | 1 | 0 | x ⋅ y ⋅ z | 1 |
| 0 | 1 | 1 | x ⋅ y ⋅ z | 0 |
| 1 | 0 | 0 | x ⋅ y ⋅ z | 0 |
| 1 | 0 | 1 | x ⋅ y ⋅ z | 1 |
| 1 | 1 | 0 | x ⋅ y ⋅ z | 1 |
| 1 | 1 | 1 | x ⋅ y ⋅ z | 1 |
Основни сврзници (или конституенти_1) вклучени во табелата одговараат на одредено множество од нули и оние што земаат променливи x,y,z. Конституенти се градат_ 1 според следното правило: променливата се вклучува во самиот производ ако ја зема вредноста 1 на дадено множество, во спротивно нејзината негација се вклучува во производот. Така, на пример, во множеството (0,0,1) променливите x,y ја земаат вредноста 0 и затоа нивните негации се вклучени во производот, а променливата z ја зема вредноста 1 и затоа е вклучена во самиот производ. . За дадено множество (0,0,1), конституентот_1 е еднаков на x ⋅ y ⋅ z .
Очигледно, сврзникот x ⋅ y ⋅ z е еднаков на 1 само во множеството
(0,0,0), а x ⋅ y ⋅ z е 1 во множеството (0,0,1) итн. (види табела). Следно, забележете дека дисјункцијата на два основни сврзници е еднаква на 1 на точно две множества што одговараат на овие основни сврзници. На пример, функцијата x ⋅ y ⋅ z¤x ⋅ y ⋅ z е еднаква на 1 само во две множества - (0,0,0) и (0,0,1), а кај сите други множества е еднаква на 0. Слично на тоа, дисјункцијата на три основни сврзници е еднаква на 1 на точно три множества што одговараат на овие основни сврзници итн.
Тоа. добиваме правило: за конструирање SDNFтреба да ги изберете редовите во кои функцијата е еднаква на 1, а потоа да ја земете дисјункцијата на соодветните главни сврзници, го добиваме саканиот SDNF. Така, за нашиот пример, имаме x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z ¤ x ⋅ y ⋅ z .
Задача. Користејќи ја оваа табела на вистинитост, конструирајте го SCNF.
Уставот_0за множество од нули и единици (кои ги земаат променливите x,y,z) се конструира на следниов начин: променливата е вклучена во самата дисјункција ако ја земе вредноста на ова множество 0 , во спротивно делото ја вклучува и нејзината негација.
Правило за изградба на SKNF:треба да изберете линии во кои функцијата е еднаква на 0 , а потоа земете го сврзникот на соодветните конституенти_0. Резултатот ќе биде посакуваниот SCNF. Така, за нашиот пример, имаме f = (x ∨ y∨ z)⋅(x ∨ y∨ z)⋅(x ∨ y∨ z) .
Коментар. За да се конструира совршена CNF функција f, доволно е да се конструира совршена DNF за функцијата f, а потоа
Дозволете ни да го конструираме SCNF за нашиот пример врз основа на забелешката. 1. Градиме SDNF за негација.
x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z
2. Ги користиме законите на Де Морган f = f = x ⋅ y⋅ z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅ z = x ⋅ y⋅ z&x ⋅ y⋅z&x ⋅ y⋅ z ==x ( ) ⋅(x ∨ y ∨ z)⋅(x ∨ y ∨ z) .
Опишаниот метод за пронаоѓање на SDNF (и SCNF) со помош на табелата за вистинитост е често поинтензивен од следниот алгоритам.
1. Да се најде SDNF оваа формулаПрво се сведуваме на DNF.
2. Ако некој сврзник K (т.е. K е производ на одреден број променливи или нивни негации) не ја вклучува, на пример, променливата y, тогаш оваа врска ја заменуваме со еквивалентната формула K&(y ∨ y) и, применувајќи законот на дистрибутивноста, ја презентираме добиената формула на DNF; ако недостасуваат неколку променливи, тогаш за секоја од нив ја додаваме соодветната формула на формата (y ∨ y) на сврзникот.
3. Ако добиениот DNF содржи неколку идентични состојки на единицата, тогаш оставаме само една од нив. Резултатот е SDNF.
Коментар: Да се конструира SCNF во клаузула која не содржи, да речеме, променлива надодаваме формула од формата y⋅ y, т.е. Овој дисјункнт го заменуваме со еквивалентната формула D ∨ y⋅ y и, применувајќи го вториот закон за дистрибутивноста.
Пример 2. 2. 2.Конструирај SDNF за функцијата f користејќи еквивалентни трансформации.
f = x ∨ y ⋅ z = x ⋅ (y ∨ y) ⋅ (z ∨ z) ∨ y ⋅ z ⋅ (x ∨ x) == x ⋅ y ⋅ z x ⋅ y ⋅ z x ⋅y x ⋅y ⋅ z ⋅ x y ⋅ z ⋅ x =
ПОВЛЕКУВАЊЕ.
Пресметката на SDNF не е само теоретска, туку и од големо практично значење. На пример, во многу модерни програмисо графички интерфејс за составување комплекс логички условисе користи визуелна форма во форма на табела: условите се запишуваат во ќелиите, а ќелиите од една колона се сметаат за поврзани со сврзник, а колоните се сметаат за поврзани со дисјункција, односно тие формирајте DNF (или обратно, во овој случај, се добива CNF). Конкретно, вака е дизајниран графичкиот интерфејс QBE (Query-byExample), кој се користи за формулирање на логички услови при барање на DBMS.
Алгоритам 2.2.1.Изградба на SDNF
Влез: вектор X: низа од низа - идентификатори на променливи, матрица V: низа од 0..1 од сите различни множества на вредности на променливи,
вектор F: низа од 0..1 соодветни функциски вредности.
Излез:низа од симболи кои формираат запис на формулата SDNF за дадена функција.
f:= лажни(знак за присуство на левиот операнд на дисјункцијата) зајас од 1до 2n направи
ако F[i] = 1 тогаш акоѓ тогаш
принос„¤“ (додавање знак за дисјункција на формулата; оператор принос m отпечатоци
симбол m) друго f:= вистина
крај ако g:= лажни(знак за присуство на левиот операнд на сврзникот) зај од 1до n направи акое тогаш
принос„⁄“ (додавање на сврзнички знак во формулата)
друго g: =точно
крај ако ако V ( додавање идентификатор на променлива во формулата
§2.3. Минимизирање на DNF со методот на Квин.
Секоја формула има конечен бројпојави на променливи. Појавата на променлива се однесува на местото што променливата го зазема во формулата. Задачата е да се најде, за дадена Булова функција f, DNF што ја претставува оваа функција и има најмал бројпојави на променливи.
Ако x е логичка променлива, а σœ(0,1) тогаш изразот x σ =xx ако σσ== 10 .
повикани писмо . Спојнаречен сврзник на букви. На пример, формулите x ⋅ y ⋅ z и x ⋅ y ⋅ x ⋅ x се сврзници . Елементарен производ е сврзник во кој која било променлива се појавува не повеќе од еднаш (или самата или нејзината негација).
Формулата f1 се нарекува импликантформули ѓ , ако f1 е елементарен производ и f 1 ⁄ f = f 1, т.е. односно за функциите што одговараат на формулите важи неравенката f 1 § f. Импликантот f1 од формулата f се нарекува едноставно , ако, по отфрлање на која било буква од f1, не се добие формула која е импликант на формулата f.
Пример 2.3.1 . Да ги најдеме сите импликанти и едноставни импликанти за формулата f=xØy . Има вкупно 8 елементарни производи со променливи XИ u.Подолу, за јасност, се дадени нивните табели за вистинитост:
| x | y | xØy | x ⋅ y | x ⋅ y | x ⋅ y | x ⋅ y | x | y | x | y | |||||||
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | |||||||
| 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | |||||||
| 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | |||||||
| 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | |||||||
Од табелите за вистинитост заклучуваме дека формулите x ⋅ y , x ⋅ y , x ⋅ y , x ,y - сите импликанти од формулата xØy, а од овие импликанти формулите x и y се едноставни (формулата x ⋅ y, на пример, не е едноставна импликантна, бидејќи, отфрлајќи ја буквата y, ја добиваме импликантот x).
Скратено DNFсе нарекува дисјункција на сите прости импликанти на дадена формула (функција) .
Теорема 2.3.1.Секоја Булова функција која не е константа 0 може да се претстави како стенографски DNF.
Во Пример 2.3.1, функцијата што одговара на формулата xØy е претставена со формулата x ∨ y што е нејзиниот скратен DNF.
Намалениот DNF може да содржи дополнителни импликанти, чие отстранување не ја менува табелата на вистинитост. Ако ги отстраниме сите непотребни импликанти од намален DNF, добиваме наречен DNF ќорсокак.
Забележете дека претставувањето на функција како слепа DNF во општ случајдвосмислена. Избирајќи од сите слепи форми, дава формата со најмал број на појавувања на променливи минимален DNF (MDNF).
Размислете за методот Кина,да се најде MDNF што претставува дадена Булова функција. Ги дефинираме следните три операции:
1. целосна операција на сврзување : f ⋅ x ∨ f ⋅ x = f ⋅ (x ∨ x) = f ;
2. делумна операција на лепење:
f ⋅ x ∨ f ⋅ x = f ⋅ (x ∨ x) ∨ f ⋅ x ∨ f ⋅ x = f ∨ f ⋅ x ∨ f ⋅ x ;
3. операција на елементарна апсорпција f ⋅ x σ ∨ f = f , σ ∈ (0,1) .
Теорема 2.3.2(Квинова теорема). Ако, врз основа на функцијата SDNF, ги извршиме сите можни операции на нецелосно лепење, а потоа елементарна апсорпција, тогаш резултатот ќе биде намален DNF, т.е. дисјункција на сите едноставни импликанти.
Пример 2.3.2. Нека функцијата f(x,y,z) е дадена со совршен DNF f = x ⋅ y⋅ z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅z ∨ x ⋅ y⋅ z ∨ x ⋅ y⋅z . Потоа, изведувајќи ги во две фази сите можни операции на нецелосно лепење, а потоа и елементарна апсорпција, имаме
ѓ 
Така, скратениот DNF на функцијата f е формулата y¤x·z.
Во пракса, при извршување на нецелосни операции на лепење во секоја фаза, можно е да не се пишуваат термините вклучени во овие операции, туку да се запишат само резултатите од сите можни комплетни лепење и сврзници кои не се вклучени во никакво лепење.
Пример 2. 3. 3.Нека функцијата f(x,y,z) е дадена со совршен DNF f = x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z ∨ x ⋅ y ⋅ z .
Потоа, извршување на операциите на лепење, а потоа и елементарна апсорпција, имаме
f = x ⋅ y ⋅(z ∨ z) ∨ y ⋅ z ⋅(x ∨ x) ∨ x ⋅ z ⋅(y ∨ y) = x ⋅ y ∨ y ⋅ z ∨ x ⋅ z
За да се добие минималниот DNF од намалениот DNF, се користи матрицата Quine , кој е конструиран на следниов начин. Насловите на колоните од табелата ги содржат конституентите на совршената DNF единица, а насловите на редовите ги содржат едноставните импликанти од добиениот скратен DNF. Во табелата, ѕвездички ги означуваат оние пресеци на редови и колони за кои сврзникот во заглавието на редот е вклучен во конституентот на единицата, а тоа е насловот на колоната.
На пример 2.3.3. Quine матрицата ја има формата
Во ќорсокак DNF, се избира минималниот број на едноставни импликанти, чија дисјункција ги зачувува сите конституенти на единицата, т.е., секоја колона од матрицата Quine содржи ѕвездичка на пресекот со редот што одговара на една од избрани импликанти. За минимален DNF е избран ќорсокакот DNF кој има најмал број на појавувања на променливи.
Во примерот 2.3.3, користејќи ја матрицата Quine, откриваме дека минималната DNF на дадена функција е x ⋅ y ¤ x ⋅ z.
Коментар.
користете f =f и законите на Де Морган.
§ 2.4. Карно карти.
Друг начин да се добијат едноставни импликантни формули со мал број променливи (и, според тоа, да се најде минималниот DNF) се заснова на употребата на таканаречените карно мапи.
Карноовата карта е посебен типтабела која го поедноставува процесот на пронаоѓање минимални форми и успешно се користи кога бројот на променливи не надминува шест. Карно картите за функции во зависност од n променливи се правоаголник поделен на 2 n ќелии. Секоја ќелија од дијаграмот е поврзана со бинарно n-димензионално множество. Вредностите на дадената функција f од табелата за вистинитост се внесуваат во бараните квадрати, но ако ќелијата одговара на 0, тогаш таа обично останува празна.
Во табела 2.4.1. покажува пример за означување на карнауска карта за функција која зависи од три променливи. Долните четири ќелии на картата одговараат на бинарни множества во кои променливата xја зема вредноста 1, првите четири ќелии одговараат на множества во кои променливата xја зема вредноста 0. Четирите ќелии што ја сочинуваат десната половина од картата одговараат на множества во кои променливата y; ја зема вредноста 1 итн. Во табела 2.4.2. Прикажана е ознаката на карнауската карта за n=4 променливи.
За да конструираме минимален DNF, изведуваме постапка на лепење „1“.Вредностите „1“ што се држат заедно одговараат на соседните ќелии, т.е. ќелии кои се разликуваат само во вредноста на една променлива (од графички приказодвоени вертикално или хоризонтална линијаземајќи ја предвид близината на спротивните екстремни ќелии).
Процесот на лепење „1“ се сведува на комбинирање на единечни ќелии од карта Карно во групи и мора да се почитуваат следните правила;
1. Бројот на клетки вклучени во една група мора да се изрази како множител од 2, т.е. 2 m каде m=0,1,2,...
2. Секоја клетка вклучена во група од 2 m ќелии мора да има m соседни ќелии во групата.
3. Секоја ќелија мора да припаѓа на најмалку една група.
4. Секоја група треба да вклучи максимален бројклетки, т.е. ниту една група не треба да биде содржана во друга група.
5. Бројот на групи треба да биде минимален.
Функција за читање fспоред групата за лепење се врши на следниов начин: променливи кои штедат исти вредностиво ќелиите на групата за лепење, тие влегуваат во врска, а вредностите 1 одговараат на самите променливи, а вредностите 0 одговараат на нивните негации.
Презентираме шаблони кои помагаат да се изгради покриеност 1 (сметаме дека променливите се исти, но нема да ги пишуваме). За да ја поедноставиме ознаката, нема да ги означуваме променливите, иако ќе ги задржиме нивните ознаки како во табелите 2.4.1, 2.4.2.
| 1 | 1 |
| 1 | 1 |
| F=Ÿy&x | |
| 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 |
| 1 | 1 | 1 |
| 1 |
F=Ÿz&Ÿy f=Ÿx&y
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | ||||
| 1 | 1 | 1 | 1 | ||||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
F=Ÿx&z f=y&w F=Ÿx&Ÿy
| 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | ||
| 1 | 1 |
F=Ÿy&Ÿw f=Ÿy&Ÿz F=Ÿz&Ÿx
| 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | ||||
| 1 | 1 | 1 | 1 |
F=y&z&w f=Ÿy&Ÿz&Ÿw F=x&y&Ÿz
| 1 | ||
| 1 | ||
| 1 | 1 | 1 |
| 1 |
Пример 2.4.1.Изградба на МДНФ.
Прво гледаме да видиме дали има облоги_ 1 од 16 ќелии кои покриваат најмалку една непокриена 1. Нема такви покривки. Преминуваме на покривки од 8 ќелии. Ајде да видиме дали има корици од 1 од 8 ќелии што покриваат барем една непокриена 1. Нема такви корици. Преминуваме на покривки од 4 ќелии. Ајде да видиме дали има корици од 1 од 4 ќелии што покриваат барем една непокриена 1. Има две такви покривки. Поминуваме на покривки од 2 ќелии. Има само еден таков слој. Така, сите 1 станаа покриени. Следно, да видиме дали можеме да отстраниме некои од прекривките за сите единици да останат покриени. На крајот го запишуваме MDNF: f =x⋅z∨y⋅w∨y⋅z⋅w.
Коментар.За да се конструира минималната CNF на функцијата f, доволно е да се конструира минималната DNF за функцијата f, а потоа
користете f =f и законите на Де Морган.
Поглавје III. Жегалкин алгебра.
Множеството Булови функции дефинирани во Жегалкиновата основа S4=(∆,&,1) се нарекува Жегалкинова алгебра.
Основни својства.
1. комутативност
H1∆H2=H2∆H1, H1&H2=H2
2. асоцијативност
H1∆(H2∆H3)=(H1∆H2)∆H3, H1&(H2&H3)=(H1&H2)
3. дистрибутивноста
H1&(H2∆H3)=(H1&H2)∆(H1&H3);
4. својства на константите H&1=H, H&0=0, H∆0=H;
5. H∆H=0, H&H=H.
Изјава 3.1.1.Сите други Булови функции може да се изразат преку операциите на Жегалкин алгебра:
Ÿx=1∆x, x¤y=x∆y∆xy, x~y=1∆x∆y, xØy=1∆x∆xy, x∞y=1∆x∆y∆xy, x|y= 1∆xy.
Дефиниција.Жегалкиновиот полином (полином модул 2) од n променливи x 1 ,x 2 ,…,x n е израз на формата c0∆σ1x1∆c2x2∆…∆cnxn∆c12x1x2∆…∆c12…nx1x2…xn, каде што константите со k може да земе вредности 0 или 1.
Ако полиномот Жегалкин не содржи производи од поединечни променливи, тогаш тој се нарекува линеарен (линеарна функција).
На пример, f=x∆yz∆xyz и f1=1∆x∆y∆z се полиноми, а вториот е линеарна функција.
Теорема 3.1.1.Секоја Булова функција е претставена во форма на полином Жегалкин на единствен начин.
Да ги претставиме главните методи за конструирање на полиноми на Жегалкин од дадена функција.
1. Метод неизвесни коефициенти. Нека P(x 1 ,x 2 ,…,x n) е посакуваниот полином на Жегалкин кој ја имплементира дадената функција f(x 1 ,x 2 ,…,xn). Ајде да го напишеме во форма
P= c 0 ∆c 1 x 1 ∆c 2 x 2 ∆…∆c n x n ∆c 12 x 1 x 2 ∆…∆c12… n x 1 x 2 …x n .
Ајде да ги најдеме коефициентите со k. За да го направите ова, ние последователно ги доделуваме променливите x 1 , x 2 ,…, x n вредности од секој ред од табелата за вистинитост. Како резултат на тоа, добиваме систем од 2 n равенки со 2 n непознати, кои имаат единствена одлука. Откако го решивме, ги наоѓаме коефициентите на полиномот P(x 1 ,x 2 ,…,xn).
2. Метод заснован на трансформација на формули преку збир на сврзувачки елементи ( ÿ,&}. Конструирај некоја формула Ф над множеството сврзници (Ÿ,&), реализирајќи ја дадената функција f(x 1 ,x 2 ,…,x n). Потоа заменете ги насекаде подформулите од формата А со A∆1, отворете ги заградите користејќи го дистрибутивниот закон (види својство 3), а потоа примени ги својствата 4 и 5.
Пример 3.1.1.Конструирај полином на Жегалкин за функцијата f(x,y)=xØy.
Решение. 1 . (метод на неодредени коефициенти). Дозволете ни да го напишеме бараниот полином во форма
P(x,y)= c 0 ∆c 1 x∆c 2 y∆c 12 xy Користење на табелата за вистинитост
| x | 0 | 0 | 1 | 1 |
| y | 0 | 1 | 0 | 1 |
| xØy | 1 | 1 | 0 | 1 |
наоѓаме дека f(0,0)=P(0,0)= c 0 =1, f(0,1)=P(0,1)= c 0 ∆ c 2 =1, f(1,0) =P(1,0)= c 0 ∆c 1 =0, f(1,1)=P(1,1)= c 0 ∆c 1 ∆c 2 ∆c 12 =1
Од каде што постојано наоѓаме, c 0 =1, c 1 =1, c 2 =0, c 12 =1. Затоа xØy=1∆x∆xy (спореди со исказот 3.1).
2.(Метод на конверзија на формула.)Ние имаме
x → y = x ∨ y = x ⋅ y = (x ⋅ (y ⊕ 1)) ⊕ 1 = 1 ⊕ x ⊕ x ⋅ y .
Забележете дека предноста на Жегалкин алгебра (во споредба со другите алгебри) е аритметизацијата на логиката, што овозможува да се извршат трансформации на Буловите функции прилично едноставно. Неговиот недостаток во споредба со Буловата алгебра е гломазноста на формулите.
Поглавје IV. Искази. Предикати.
§4.1. Искази.
Кога ја конструиравме алгебрата на логиката, користевме функционален пристап. Сепак, би било можно конструктивно да се конструира оваа алгебра. Прво, дефинирајте ги објектите на студијата (изјави), воведете операции на овие објекти и проучете ги нивните својства. Да дадеме формални дефиниции.
Со кажувањеДа ја наречеме декларативна реченица за која недвосмислено може да се каже дали е точно (вредност I или 1) или неточно (вредност L или 0) во одреден момент во времето. На пример, „5 е прост број“, „притиснато е копчето Esc“ итн. Користење на врски „не“, „и“, „или“, „ако,... тогаш“, „ако и само ако“ (тие одговараат на операциите „Ÿ“, „&“, „¤“, „Ø“ , „~“ » соодветно), може да се конструираат посложени искази (реченици). Така е конструирана пропозициската алгебра.
За да се поедностави снимањето на сложени искази, се воведува предност на сврзувачките врски: „Ÿ“, „&“, „¤“, „Ø“, „~“, што помага да се испуштат непотребните загради.
Едноставните изјави ги нарекуваме пропозициски променливи.
Да го воведеме концептот на формула.
1. Пропозициските променливи се формули.
2. Ако A, B се формули, тогаш изразите ŸA, A⁄B, A¤B, AØB, A~B се формули.
3. Формулите се само изрази конструирани во согласност со ставовите 1 и 2.
Се нарекува формула која ја зема вредноста И за сите вредности на пропозициските променливи тавтологија (или општо валидна),и се нарекува формула која ја зема вредноста A за сите вредности на пропозициските променливи контрадикторно (или невозможно)
Описот на својствата на исказната алгебра е сличен на описот на соодветните функции во Буловата алгебра и ги испуштаме.
§4.2. Предикати. Логички операции на предикати.
Предмет на проучување во ова поглавје ќе бидат предикати - пресликувања на произволни множества во збир на искази. Всушност, ја правиме транзицијата кон ново нивоапстракции, премин од типот што се правел на училиште - од аритметика на реални броеви до алгебра на нумерички функции.
Дефиниција 2.1 Нека x 1 , x 2 ,…,xn се симболи на променливи од произволна природа. Овие променливи ќе ги наречеме предметни променливи. Нека множествата на променливи (x 1 , x 2 ,…, x n) припаѓаат на множеството M=(M1,M2,…Mn), кое ќе го наречеме предметна област (т.е. x i œM i, каде што Mi се нарекува домен на дефиниција на променливата xi). Локалитет прирок n (n-место прирок) дефиниран на предметна област M, е логичка функција која ја зема или вредноста И или вредноста L.
Пример 4.2.1. D(x1,x2) = „Природниот број x1 се дели (без остаток) со природниот број x2“. - двоместен прирок дефиниран на множество парови природни броеви M=NäN. Очигледно, D(4,2) = И, D(3,5) = 0.
Пример 4.2.2. Q(x) ==„x 2<-1, хœR» - одноместный предикат, определенный на множестве действительных чисел М=R. Ясно, что Q(1) = Л, Q(5) = Л, и вообще предикат Q(x) - тождественно ложен, т. е.
Q(x) = А за сите xœR.
Пример 4.2.3. B(x,y,z) = "x 2 +y 2 Предикатот P дефиниран на M се вели дека е идентично вистинит ако ја зема вредноста И за која било вредност на предметните променливи; Предикатот P се нарекува идентично неточен ако ја зема вредноста A за која било вредност на предметните променливи. Предикат Q од Пример 4.2.2. е идентично неточно. Бидејќи предикатите се функции со вредности во збир на искази каде се воведуваат логички операции, овие операции се природно дефинирани за предикати. Нека P и Q се предикати дефинирани на M. Потоа 1. ¬P(x, x,…, x n) = P(x, x,…, x) ∧ 1 2 n 1 2 n ∧ 1 2 n 3. (P ∨ Q)(x 1 ,x 2 ,…,x n) = P(x 1 ,x 2 ,…,x n) ∨ Q(x 1 ,x 2 ,…,x n) 4. (P → Q)(x 1 ,x 2 ,…,x n) = P(x 1 ,x 2 ,…,x n) → Q(x 1 ,x 2 ,…,x n) Предикати P и Q, дефинирани на M се нарекуваат еквивалентни (напиши P=Q) ако P(x 1 ,x 2 ,…,xn)=Q(x 1 ,x 2 ,…,xn) за кое било множество (x 1 ,x 2 ,…, x n )
предметни променливи од М .
Теорема 4.2.1Множеството n-ари предикати дефинирани на M формира Булова предикатна алгебра. Така, за нив важат основните еквиваленции (види §1.6). Нека P(x 1, x 2,…, xn) е n-арен прирок дефиниран на M. Да го поправиме x i = а. Дозволете ни да го дефинираме (n-1)-ариниот прирок Q(x 1 ,x 2 ,…,xk-1, xk+1, xn) на следниов начин: Q(x 1 ,x 2 ,…,xk-1,xk +1, xn)=P(x 1,x 2,…,xk1, а, xk+1, xn). Велат дека прирокот Q(x 1 ,x 2 ,…,xk-1, xk+1,xn) се добива од прирокот P(x 1 ,x 2 ,…,xn) со фиксирање на вредноста на i- та променлива: x i = а
. Дефиниција
4.3.1
. Нека P(x) е унарен прирок. Да го поврземе со него исказ означен „xP(x) (читај „за кој било x P(x)“), што е точно ако и само ако P(x) е идентично вистинит прирок. Исказот „xP(x) се вели дека е , дека се добива од прирокот P со прикачување на универзален квантификатор над променливата x. Дефиниција 4.3.2.Нека P(x) е унарен прирок. Дозволете ни да го поврземе со исказ означен $xP(x) (читај „има x P(x)“), што е неточно ако и само ако P(x) е идентично погрешен прирок. Исказот $xP(x) се вели дека е добиен од прирокот P со прикачување на егзистенцијален квантификатор на променливата x. Забелешка 1.Симболите " и $ за квантификатори се превртени латински букви A и E, соодветно, кои се првите букви во англиските зборови Сите- Сите, Постои- постојат. Забелешка 2.Изјавите може да се сметаат за предикати кои не содржат променливи, односно предикати од 0 места (или предикати на која било локација). Нека P(x 1,x 2,…,xn) е n-арен прирок дефиниран на M. Да ги поправиме во него вредностите на променливите x 1 , x 2 ,…,x k-1 ,x k +1, x n. Прикачуваме универзален (постоење) квантификатор на добиениот унарен предикат Q(x k) и добиваме исказ. Така, фиксен сет на вредности на променливи x 1 , x 2 ,…, x k-1 , x k+1 , x n е поврзан со изјава користејќи го квантификаторот на универзалност (постоење). Овој (n-1)-арински предикат на променливите x 1 ,x 2 ,…,x k-1 ,x k+1 ,x n се вели дека е добиен од оригиналниот предикат P(x 1 ,x 2 ,…, x n) со додавање на квантификатор универзалност (постоење) во k-тата променлива. Овој предикат се означува: „x до P(x 1 , x 2 ,…,x n) ($x до P(x 1 ,x 2 ,…,x n)). За k-тата променлива (која повеќе не постои) велат дека е врзана со квантификаторот на универзалноста (постоење). Пример 4.3.1.Нека D(x1,x2) = „Природниот број x1 е делив (без остаток) со природниот број x2“. - двоместен прирок. Дозволете ни да доделиме квантификатори последователно на неговите променливи. Јасно е дека 1) "x1"x2D(x1,x2)=0 2) "x2"x1D(x1,x2)=0 3) $x1$x2D(x1,x2)=1 4) $x2$x1D(x1,x2)=1 5) "x1$x2D(x1,x2)=1 6) $x2"x1D(x1,x2)=1 7) $x1"x2D(x1,x2) =0 8) "x1$x2D(x1,x2)=1. Така (со споредување на 7 и 8 во последниот пример) ја докажавме теоремата: Вообичаено, сврзниците и квантификаторите се подредени по приоритет на следниов начин: Ÿ, ", $, &, ¤, Ø, ~. Теорема 4.3.1.Спротивните квантификатори, генерално кажано, не патуваат. Теорема 4.3.2.(основни еквиваленции кои содржат квантификатори) Следниве еквиваленции се одвиваат: 1. Законите на Де Морган ∀ xP (x) = ∃x P(x) , ∃xP (x) = ∀ x P(x) 2. Комутативност ∀x∀yP(x,y) =∀y∀xP(x,y) , ∃x∃yP(x,y) =∃y∃xP(x,y) 3. Дистрибутивноста ∀x(P(x)&Q(x)) =∀xP(x)&Q(x) , ∃x(P(x)∨ Q(x))=∃xP(x)∨ Q(x) 4. Ограничувања на дејството на квантификаторите ∀x(P(x)∨Q(y))=∀xP(x)∨∀xQ(y) , ∃x(P(x)&Q(y) =∃xP(x)&∃xQ(y) 5. За кој било прирок од две места ∃y∀xP(x,y) →∀x∃yP(x,y) =1 Формална теорија(или калкулус)
Y- Ова: 1. сет А
формирање на ликови азбука
;
1.
еден куп Ф
зборови во азбуката А, Ф
à А
кои се нарекуваат формули
;
3. подмножество Б
формули, Б
à Ф
,
кои се нарекуваат аксиоми; 4. многу врски Р
на множество формули наречени правила за заклучување. Многу симболи А
може да биде конечна или бесконечна. Вообичаено, за да се формираат симболи, се користи конечен сет на букви, на кои, доколку е потребно, се доделуваат природни броеви како индекси. Многу формули Ф
обично се дава со индуктивна дефиниција, на пример со помош на формална граматика. Како по правило, овој сет е бесконечен. Сетови А
И Ф
колективно одредуваат јазик
,
или потпис
,
формална теорија. Многу аксиоми Б
може да биде конечна или бесконечна. Ако множеството аксиоми е бесконечно, тогаш, по правило, тоа се одредува со користење на конечна група шеми на аксиоми и правила за генерирање специфични аксиоми од шемата за аксиоми. Многу правила за заклучување Р
, како по правило, се разбира. Значи, пресметка Yима четири (А, Ф, Б, Р)
. Со изведување во пресметка Yе низа од формули F 1 , F 2 ,…,Fn таква што за кое било k (1§k§n) формулата Fk е или аксиома на пресметката Y или директна последица на која било претходна формула добиена со правилото за заклучување . Формулата G се нарекува теорема на пресметка Y (изводлива во Y или докажлива во Y) ако постои заклучок F 1 ,F 2 ,…,F n ,G кој се нарекува извод на формулата G или доказ за теорема Г. Ова е напишано на следниов начин: F 1, F 2,…,F n + G. Калкулус Yповикани конзистентна, ако не сите негови формули се докажливи. Може да се даде друга дефиниција за конзистентност: Калкулусот се нарекува конзистентен ако формулите F и ŸF (негацијата на F) не се истовремено дедуцирани во него. Калкулус Yповикани заврши(или адекватно) ако секоја вистинита изјава М одговара на теорема на теоријата Y
. Формална теорија Yповикани одлучувачки, ако постои алгоритам кој, за која било формула на теоријата, одредува дали оваа формула е теорема на теоријата Yили не. Користејќи го концептот на формално калкулус, го дефинираме пропозициското сметање (PS). Азбука IW се состои од 1. писма A, B, Q, R, P и други, евентуално со индекси (кои се нарекуваат пропозициски променливи), 2. логички симболи(лигаменти) Ÿ, &, ¤, Ø, 3. помошни ликови
(,). Многу формули IV се одредува индуктивно: 1. сите пропозициски променливи се IV формули; 2. ако A, B се формули IV ,
toŸA, A⁄B, A¤B, AØB - формулиIV ;
3. изразот е IV формула ако и само ако тоа може да се утврди со помош на точките „1“ и Така, секоја IV формула е конструирана од пропозициски променливи користејќи сврзници Ÿ, ⁄, ¤, Ø. Во иднина, кога пишуваме формули, ќе испуштиме некои загради, користејќи ги истите конвенции како во претходното поглавје. Аксиоми IV се следните формули (за која било формула A,B,C) 2. (AØB)Ø((AØ(BØC))Ø(AØC)); 5. (AØB)Ø((AØC)Ø(AØ(B⁄C))); 8. (AØC)Ø((BØC)Ø((A¤B)ØC)); 9. (AØB)Ø((AØŸB)ØŸA); Овие формули се нарекуваат шеми на IV аксиоми .
При замена на специфични формули во која било шема, се добива посебен случај на аксиомската шема. Правило за заклучувањево IE постои правило за заклучок (modus ponens): ако A и AØB се изводливи формули, тогаш и B е изводливо Симболично е напишано вака: А, АБ →
Б
. На пример, ако исказите A⁄B и A⁄BØ(AØC) се дедуктивни, тогаш и тврдењето AØC може да се изведе според правилото за заклучување. Се вели дека формулата G може да се изведе од формулите F 1 , F 2 ,…,F n (означена F 1 , F 2 ,…,F n +G) ако постои низа од формули F 1 , F 2 ,… ,F k ,G , во која која било формула е или аксиома, или припаѓа на листата на формули F 1,F 2,...,F n (наречени хипотези), или е добиена од претходните формули според правилото за заклучување. Изведливоста на формулата G од “ (означена со +G) е еквивалентна на фактот дека G е IV теорема. Пример 5.2.1. Да покажеме дека формулата AØA може да се изведе во IV. За да го направите ова, ќе ја конструираме изведбата на оваа формула: 1) во аксиома 2, заменете го B со AØA, C со A. Ја добиваме аксиомата (AØ(AØA))Ø((AØ((AØA)ØA))Ø(AØA)); 2) во аксиомата 1 го заменуваме B со A. Добиваме AØ(AØA); 3) од 1 и 2 според modus ponens заклучуваме (AØ((AØA)ØA))Ø(AØA); 4) во аксиома 1 го заменуваме B со AØA. Добиваме AØ((AØA)ØA); 5) од ставовите. 3 и 4, според правилото за заклучување, + AØA е точно. Теорема 5.2.1. 1. Ако F 1 ,F 2 ,…,Fn,A,B се IV формули, Г=(F 1 ,F 2 ,…,Fn), Г+А, тогаш Г,B+A. (можете да го зголемите бројот на хипотези). 2. Ако и само ако F 1 ,F 2 ,…,F n +A, кога F 1⁄F 2 ⁄…⁄F n +A (намалување на многу хипотези на една хипотеза). Теорема 5.3.1. (дедукција теорема) Ако Г,B+A, тогаш Г+BØA, каде Г е множество од некои формули Г=(F 1 ,F 2 ,…,F n ). Заклучок 5.3.1.Тогаш и само ако F 1 ,F 2 ,…,F n +A, кога Доказ. Нека F 1 ,F 2 ,…,F n +A. Потоа, применувајќи ја теоремата за дедукција, имаме F 1 ,F 2 ,…,F n-1 +F n ØA. Слично F 1 , F 2 ,…,F n-2 +F n 1Ø(F n ØA), итн. Продолжувајќи го процесот потребниот број пати, добиваме F 1 Ø(F 2 Ø…Ø(F n-1 Ø(F n ØA))…) За да се докаже доволноста, да се претпостави дека +B, каде што B=F 1 Ø(F 2 Ø…Ø(F n-1 Ø(F n ØA))…). Да ја користиме теорема 5.2.1., точка 1: F 1 +B .
Според правилото за заклучок, добиваме F 1 + (F 2 Ø…Ø(F n-1 Ø(F n ØA))…), Потоа по n чекори имаме F 1 ,F 2 ,…,F n +A . Така, благодарение на заклучокот 5.3.1., проверката на уводливоста на формулата А од формулите F 1, F 2,…, F n, се сведува на проверка на докажливоста на формулата F 1 Ø(F 2 Ø…Ø(F n-1 Ø(F n ØA))…). Потсетиме дека формулата А се нарекува идентично вистинита (или тавтологија) ако вредноста на формулата А е еднаква на една за кој било сет на вредности на пропозициските променливи. Следната теорема потврдувањето на докажливоста на формулата ја сведува на верификација на нејзината идентична вистина. Теорема 5.3.2. (за комплетноста). Формулата А е докажлива ако и само ако А е идентично точно (тавтологија): +A ‹ А-тавтологија. Така, за да се утврди дали формулата е докажлива, доволно е да се состави нејзината табела за вистинитост. Како што е познато, постои ефикасен алгоритам за конструирање табела на вистинитост, и затоа, IV решлив. Пример 5.3.1.Да докажеме дека P+P. Според теоремата за дедукција, ова е еквивалентно на +(PØP). За возврат, според теоремата за комплетност, доволно е да се докаже дека (РØР) е тавтологија. Составување табела на вистинитост за формулата (РØР) ,
Убедени сме дека (РØР) е идентично вистинито и, според тоа, докажливо. Теорема 5.3.3. (за конзистентноста).Пресметката на IW е конзистентна. Доказ. Според теоремата за комплетност, секоја формула што не е идентично вистинита не е докажлива во IW. На пример, таква формула е формулата A⁄(ŸA). Се нарекува множеството формули Г контроверзен
,
ако Г+А⁄(ŸА) .
Ако Г е контрадикторно збир на формули, овој факт ќе го означиме со Г+. Изјава
5.3.1.
Формулата А може да се изведе од множеството формули Г ако и само ако множеството Г»(ŸA) е контрадикторно. Автоматското докажување на теорема е камен-темелник на логичкото програмирање, вештачката интелигенција и другите модерни трендови во програмирањето. Општо земено, можеби нема да постои алгоритам со кој, со оглед на произволна формула А, може да се одреди, по конечен број чекори, дали А може да се изведе во пресметката Y или не. Меѓутоа, за некои едноставни формални теории (на пример, пропозициско сметање) и некои едноставни класи на формули (на пример, применета пресметка на предикат со еден унарен предикат), познати се алгоритми за автоматско докажување на теорема. Подолу, користејќи го примерот на пропозициско калкулус, ги наведуваме основите на методот на резолуција - класичен и во исто време популарен метод за автоматско докажување теореми. Потсетиме дека ако x е логичка променлива, а σœ(0,1) тогаш изразот x σ = xx ако ако σσ == 10 или x σ = 10 ако x x =≠σσ , се вика писмо. Се нарекуваат буквите x и Ÿx спротивно.
Спојнаречен сврзник на букви. дисјункцискинаречена дисјункција на буквите. Нека D 1 = B 1 ∨ A, D 2 = B 2 ∨ A се клаузули. Се нарекува клаузулата B 1 ¤B 2 растворливклаузули D 1 и D 2 со буквата A и се означува со res A (D 1 ,D 2). Резолуцијата на клаузулите D 1 и D 2 е растворувач со некоја буква и се означува со res(D 1 ,D 2). Очигледно res(A,ŸA)=0. Навистина, затоа што A=A¤0 и ŸA=ŸA¤0, потоа res(A,ŸA)=0¤0=0. Ако клаузулите D 1 и D 2 не содржат контрастни знаци, тогаш тие немаат растворувачи. Пример 5.5.1.Ако D 1 =A¤B¤C, D 2 = A ∨ B ∨ Q, потоа res A (D 1 ,D 2)=B¤C¤ B ¤Q, res B (D 1 ,D 2)=A¤C¤A¤Q, resC(D 1 ,D 2) не постои. Изјава 5.5.1.Ако постои res(D 1 ,D 2), тогаш D 1 ,D 2 + res(D 1 ,D 2). Нека S=(D 1 ,D 2 ,…,Dn) е множество од реченици. Низата од формулите F 1 , F 2 ,…,F n се нарекува резолутна изведба од S ако за секоја формула F k е исполнет еден од условите: 2. постојат j, k
Теорема 5.5.1.
(за комплетноста на методот на резолуција). Множеството од реченици S е контрадикторно ако и само ако постои резолутивен заклучок од S кој завршува на 0. Забележете дека методот на резолуција може да се користи за проверка на резултабилноста на формулата F од дадено множество формули F 1, F 2,…,F n. Навистина, условот F 1 ,F 2 ,…,F n +F е еквивалентен на условот F 1 ,F 2 ,…,F n ,ŸF+ (многу формули се контрадикторни), што пак е еквивалентно на условот Q+, каде Q=F 1 ⁄F 2 ⁄…⁄F n ⁄(ŸF). Да ја намалиме формулата Q на CNF: Q=D 1 ⁄D 2 ⁄...⁄Dm, потоа Q+ ‹D 1 ⁄D 2 ⁄...⁄Dm+ ‹ D 1 ,D 2 ,...,D m + . Така, задачата за проверка на дедуктивноста на F 1 ,F 2 ,…,F n +F се сведува на проверка на неусогласеноста на множеството од клаузули S=(D 1 ,D 2 ,...,D m ), што е еквивалентно на постоењето на решителен заклучок 0 од С. Пример 5.5.2.Проверете го соодносот AØ(BØC), CDØE, ŸFØD&(Ÿ)E + AØ(BØF) користејќи го методот на резолуција. Според изјавата 5.3.1. треба да се провери за недоследност многу формули S = (AØ(BØC), CDØE, ŸFØD&(Ÿ)E, Ÿ(AØ(BØF))). Ви ги претставуваме сите формули од. S до KNF: S = (A ∨ B ∨ C, C ⋅ D ∨ E, F ∨ D ⋅ E, A ∨ B ∨ F) == (A ∨ B ∨ C, C ∨ D ∨ E, (F ∨ D) ⋅ (F ∨ E), A ⋅ B ⋅ F) . Така, добиваме множество од клаузули S = (A ∨ B ∨ C, C ∨ D ∨ E, F ∨ D, F ∨ E, A, B, F) Ајде да конструираме резолутивен заклучок од S кој завршува со 0: 1. рез A (A ∨ B ∨ C, A) = B ∨ C ; 2. рез B (B ∨ C,B) = C; 3. рез D (C ∨ D ∨ E, F ∨ D) = C ∨ E ∨ F ; 4. рез E (C ∨ E ∨ F, F ∨ E) = C ∨ F ; 5. рез C (C, C ∨ F) = F; 6. res(F, F) = 0 . Значи, заклучуваме дека формулата AØ(BØF) е изводлива од множеството формули AØ(BØC), CDØE, ŸFØD&(Ÿ)E. Забележете дека методот на резолуција е доволен за да се открие можната задоволливост на дадено множество клаузули S. За да го направите ова, да ги вклучиме во множеството S сите клаузули добиени со резолутивни одбитоци од S. Од теоремата за комплетноста на методот на резолуција следи Заклучок 5.5.1.Ако множеството од клаузули S ги содржи растворувачите на сите негови елементи, тогаш S е задоволен ако и само ако 0–S. Карактеристична карактеристика на модерноста е широката употреба на компјутерите во решавањето проблеми (задачи) во различни области на човековата активност. Меѓутоа, проблемот прво мора да се реши алгоритамски, т.е. мора да се даде формален рецепт, по кој може да се добие конечниот резултат за решавање на сите проблеми од одреден тип (ова е интуитивен, а не строг концепт на алгоритам). На пример, алгоритам за наоѓање на најголемиот заеднички делител на два природни броја а, б, како што следи: 1) прошири го бројот аспоред основните фактори; 2) повторете го чекорот 1 за б
Иоди на чекор 3; 3) состави производ на заеднички прости фактори од проширувања АИ бсо индекси еднакви на најмалите од индексите на вклучување во проширувањата. Откако го анализиравме овој пример, ги забележуваме најважните карактеристики (својства) на алгоритмот: 1.
Масовен карактер- применливост на алгоритмот не на еден проблем, туку на класа на проблеми. 2.
Дискретност- јасно расчленување на поединечни фази (чекори) на алгоритмот. 3.
Детерминизам- таква организација на фази на извршување во кои секогаш е јасно како да се направи премин од една во друга фаза. 4.
Екстремитет- за да се добие резултат при примена на алгоритам за решавање на конкретен проблем, се врши конечна низа од чекори на алгоритмот: Забележете дека ако присуството на алгоритам само по себе служи како доказ за постоењето на алгоритам, тогаш за да се докаже неговото отсуство потребно е да се има строга математичка дефиниција за алгоритам. Обидите да се формализира концептот на алгоритам доведоа до создавање Тјуринг машини, како некој имагинарен уред кој го имплементира алгоритмот. Друг чекор во дефинирањето на концептот на алгоритам беше изгледот рекурзивни функции ,
како функции кои го формализираат концептот на алгоритам и го имплементираат интуитивниот концепт на пресметливост. Наскоро беше откриено дека множеството на рекурзивни функции се совпаѓа со множеството функции што се пресметуваат на машините на Тјуринг. Новите концепти кои потоа се појавија, тврдејќи дека го објаснуваат концептот на алгоритам, се покажаа еквивалентни на функциите што се пресметуваат на машините на Тјуринг, а со тоа и на рекурзивните функции. Резултатот од тековната дискусија за тоа што е алгоритам беше изјавата што сега се нарекува теза на Черч. Тезата на црквата.Концептот на алгоритам, или пресметливост со некој механички уред, се совпаѓа со концептот на пресметливост на машините на Тјуринг (а со тоа и со концептот на рекурзивна функција). Со други зборови, алгоритам е процес кој може да биде претставен со функционален дијаграм и имплементиран од некоја Тјуринг машина. Туринговата машина е (апстрактна) уред која се состои од лента, контролен уред и глава за читање. Лентата е поделена на ќелии. Секоја ќелија содржи точно еден знак од надворешна азбука
A=(
а 0,
а 1,…,
а н).Некој симбол (ќе го означиме Ÿ
) од азбуката А се нарекува празна, а секоја ќелија која моментално содржи празен знак се нарекува празна ќелија (во тој момент). Се претпоставува дека лентата е потенцијално неограничена во двете насоки. Контролен уредво секој момент од времето е во некоја состојба q j припаѓа на множеството Q=(q 0 , q 1 ,..., q m )(m=l). Се нарекува множеството Q внатрешна азбука
.
Еден од овие услови (обично q 0) се нарекува конечна, а некои други (обично q 1) - почетна. Главата за читање се движи по лентата така што во кое било време скенира точно една ќелија од лентата. Главата може да ја прочита содржината на набљудуваната ќелија и да напише во неа наместо набљудуваниот симбол некој нов симбол од надворешната азбука А(можеби истиот). За време на работата, контролниот уред, во зависност од состојбата во која се наоѓа и симболот што го гледа главата, ја менува својата внатрешна состојба q. Потоа на главата му издава наредба да отпечати одреден знак од надворешната азбука во ќелијата што се следи А,а потоа и наредува на главата или да остане на своето место, или да помести една ќелија надесно или да ја премести едната ќелија налево. Штом е во конечна состојба, машината престанува да работи. Конфигурација на лента (или машински збор)се нарекува множество формирано од: 1) низа а
јас (1)
, а
i(2)
,...,а
јас(и)знаци од надворешната азбука А, снимен во ќелии со лента, каде а
јас
(1)
.- симболот напишан во првата ќелија лево итн. (се вика која било таква низа со еден збор), 2) состојбата на внатрешната меморија q r ; 3) број ксогледана клетка. Конфигурацијата на машината ќе ја напишеме на следниов начин: a ,a ,..., a a i(r) a ,a ,..., a i(1) i(2) i(r−1) q r i(r+1) i(r+2) i(s) Еве р- воочената клетка е означена како дропка. Ако машината, да се биде во внатрешна состојба qi, прифаќа ќелија со симбол а у, пишува симбол на оваа ќелија во следниот момент во времето a r, оди во внатрешна состојба qsи се движи по лентата, потоа велат дека машината ја извршува командата q i a u
Æ
q s a r S, каде што симболот S може да земе една од следните вредности: -1 – поместување на главата налево; +1 - поместување на главата надесно; 0 – главата останува на своето место. Се повикува списокот на сите команди (квинтови) кои ја одредуваат работата на Тјуринговата машина програмаовој автомобил. Машинската програма често се одредува во форма на табела. Значи за ситуацијата опишана погоре во табелата на раскрсницата линии а
uи колона qiќе стои q s a r S(види табела 6.2.1) Табела 6.2.1. Ако програмата вклучува автомобили за двојка (
q i, a u
)
недостига пет, а потоа во табелата на пресекот на линијата а у, и колона qiсе додава цртичка. Значи, Тјурингова машина е, по дефиниција, комплет M=(A,Q,P), Каде А- надворешна азбука, П- азбука на внатрешните состојби, П- програма. Ако машината, откако почнала да работи со некој збор P напишан на лента, ја достигне конечната состојба, тогаш се нарекува применливо за овој збор. Резултатот од неговата работа е зборот снимен на лентата во неговата конечна состојба. Во спротивно, се вели дека машината не е применлива за зборот Р. Пример 6.2.1. Ајде да изградиме машина Тјуринг која собира природни броеви напишани во унарен броен систем (т.е. напишани со еден симбол |.
На пример 5=|||||.). Решение. Размислете за азбуката А
= {|, +, ⁄}. Машината се одредува со следнава програма: Дозволете ни да ги запишеме конфигурациите што се појавуваат последователно за време на работата на оваа машина на почетниот збор ||+ ||| , т.е. 2+3. Овде, при снимање на конфигурацијата, ќе ја користиме следнава конвенција: состојбата во која се наоѓа машината е запишана во загради десно зад буквата што се набљудува. Пример 6.2.2.Направете Тјурингова машина која ги удвојува природните броеви запишани во унарниот броен систем. Решение.Ќе ја конструираме потребната машина со азбука A=(|, α, ⁄). Програмата за таква машина може да изгледа вака: Ајде да ја примениме добиената машина на зборот ||
. Воведување на нова буква α и замена на оригиналните |
на α овозможува да се разликува оригиналот |
и ново (доделено) |
. држава q 1обезбедува замена |
на α ,
држава q 2обезбедува пребарување за α ,
наменет за замена |
, и запирање на машината во случај кога α не е откриен, q 3обезбедува завршување |
во случај кога α бил заменет со |.
Да се согласиме дека во овој став 1. множеството N природни броеви содржи 0 (нула), т.е. N=(0,1,2,3,...); 2. Функциите што се разгледуваат f=f(x 1 , x 2 ,…, x n) се дефинираат само кога променливите земаат вредности од N, т.е. xiœN; 3. опсег на вредности на функции DŒN; 4. функциите што се разгледуваат f=f(x 1 ,x 2 ,…,x n) можат делумно да се дефинираат, т.е. не е дефинирано за сите множества природни броеви. Да воведеме во предвид едноставни функции o(x)=0, s(x)=x+1,
I m n (x 1 ,..., x n)
=
x m Овие функции може да се пресметаат со помош на соодветен механички уред (на пример, машина Туринг). Дозволете ни да дефинираме оператори кои конструираат нови функции врз основа на една или повеќе дадени функции. Оператор за суперпозиција.Нека е функцијата f(x 1 ,x 2 ,…,x k) од k променливи и k функции f 1 (x 1 ,x 2 ,…,x n),…,f k (x 1 ,x 2 ,…,x n) дадени n променливи. Суперпозиција на функциите f,f 1 ,…,f k е функцијата j(x 1 ,x 2 ,…,x n)= f(f 1 (x 1 ,x 2 ,…,x n),…,f k (x 1 , x 2 ,…, x n)) Велиме дека функцијата j се добива со примена на операторот за суперпозиција S k+1 на функциите f,f 1 ,…,f k , и се запишува j=S k+1 (f,f 1,…,f k) На пример, S 2 (s, o)=s(o(x)), т.е. функција идентично еднаква на 1, а S 2 (s,s)=s(s(x)) е функција y(x)=x+2. Примитивен рекурзиски оператор.Нека се дадени функциите g(x 1 , x 2 ,…,x n) и h(x 1 ,x 2 ,…,x n+2). Ајде да конструираме функција f(x 1 , x 2 ,…,x n+1) Нека се фиксираат вредностите x 1 , x 2 ,…,x n. Тогаш претпоставуваме: f(x 1 , x 2 ,…,x n ,0)= g(x 1 , x 2 ,…, x n) f 1 (x 1 , x 2 ,…,x n ,y+1)= h(x 1 ,x 2 ,…,x n ,y, f(x 1 ,x 2 ,…,x n ,y)) Овие еднаквости ја дефинираат функцијата f(x 1 , x 2 ,…,x n+1) уникатно. Функција f се нарекува функција добиена со помош на примитивниот рекурзиски оператор R. Се користи ознаката f=R(g,h). Индуктивната дефиниција на функцијата (демонстрирана кај примитивниот рекурзиски оператор) не е невообичаена во математиката. На пример, 1) степен со природен експонент се одредува индуктивно: а
0
=1, а n+ 1
=a n
ÿ а
; 2) факторски: 0!=1, (n+1)!= n!ÿ(n+1) итн. Дефиниција.Функции кои може да се добијат од наједноставната o(x)=0, s(x)=x+1, I m n (x 1 ,..., x n) = x m со примена на оператори за суперпозиција и примитивна рекурзија конечен број пати се нарекуваат примитивно рекурзивен. Да провериме дали функцијата u(x,y)=x+y е примитивна рекурзивна. Навистина, имаме: u(x,0)=0, u(x,y+1)=x+y+1=u(x,y)+1. Ова е примитивна рекурзиска шема, бидејќи x= I 1 1 (x), и u(x,y)+1=s(u(x,y))=S 2 (s,u). Тука g(x)= I 1 1 (x), и h(x,y,u)=s(u)=S 2 (s, I 3 3). Слично е докажано дека функциите m(x,y)=xÿy, d(x,y)=x y (претпоставуваме по дефиниција 0 0 =1), факт(x)=x! и многу други се примитивно рекурзивни. Забелешка; дека примитивно рекурзивните функции се насекаде дефинирани (т.е. дефинирани за сите вредности на нивните аргументи). Навистина, наједноставните функции о, с, I m n се насекаде дефинирани, а примената на суперпозиција и примитивни рекурзивни оператори на секаде дефинираните функции, исто така, дава секаде дефинирани функции. Значи функција како = x − y, ако x ≥ y< y f(x,y) не постои ако x не може да биде примитивно рекурзивен. Немаме право овде да ја разгледуваме функцијата f(x,y)=x-y, бидејќи вредностите на функцијата мора да бидат природни броеви (затоа не негативни). Сепак, може да се разгледа функцијата ÷ y = 0x − y ако x x<≥y.y Да провериме дали е примитивно рекурзивен. Прво да докажеме дека функцијата j(x)=xπ1 е примитивна рекурзивна. Навистина, j(0)=0. j(y+1)=(y+1)π1=y, што служи како примитивна рекурзивна шема за функцијата xπ1. Конечно, xπ0=x, xπ(y+1)=(xπy)π1=j(xπy) е примитивна рекурзиска шема за xπy. Значително поширока класа на функции од примитивните рекурзивни функции е класата на рекурзивни функции (види дефиниција подолу). Во литературата овие функции се нарекуваат и делумно рекурзивен .
За да ги одредиме, воведуваме уште еден оператор. Оператор за минимизирање.Нека е дадена функцијата f(x 1 ,x 2 ,… ,x n ,x n+1). Ајде да поправиме некои вредности x 1 , x 2 ,… ,x n од првите n променливи и да пресметаме f(x 1 ,x 2 ,… ,x n ,0), f(x 1 ,x 2 ,… ,x n ,1 ), f(x 1 , x 2 ,… ,x n ,2) итн. Ако y е најмалиот природен број за кој f(x 1 , x 2 ,… X n ,y)=x n+1 (т.е. вредности f(x 1 , x 2 ,… ,x n ,0), f(x 1 ,x 2 ,… ,x n ,1),…,f( x 1, x 2,… X n ,y-1) сите постојат и не се еднакви на xn +1), тогаш ставаме g(x 1 ,x 2 ,… X n ,x n+1)=y. Така, g(x 1 ,x 2 ,… ,x n ,x n+1)=min(y|f(x 1 ,x 2 ,…,x n ,y)=x n+1). Доколку таквите yне, тогаш сметаме дека f(x 1 ,x 2 ,… ,x n ,x n+1) не е дефиниран. Значи, можни се три случаи: 1. f(x 1 , x 2 ,… ,x n ,0), f(x 1 ,x 2 ,… ,x n ,1),…,f(x 1 ,x 2 ,… ,x n ,y-1) постојат и не се еднакви на xn +1, и f(x 1 ,x 2 ,…,x n ,y)=x n+1 ; 2. f(x 1 , x 2 ,… ,x n ,0), f(x 1 ,x 2 ,… ,x n ,1),…,f(x 1 ,x 2 ,… ,x n ,y-1) постојат и не се еднакви на xn +1, но f(x 1 ,x 2 ,…,x n ,y) не постои; 3. f(x 1 ,x 2 ,… ,x n ,i) постојат за сите iœN и се различни од xn +1. Ако се појави првиот случај, тогаш g(x 1 , x 2 ,… ,x n ,x n+1)=y, а ако вториот или третиот случај, тогаш g(x 1 ,x 2 ,… ,x n , x n +1) не е дефинирано. Функција g добиена на овој начин се вели дека е добиена од f со помош на операторот за минимизирање М. Запишуваме g= Mf. Операторот за минимизирање е очигледна генерализација на операторот на инверзна функција. Генерализацијата е прилично длабока, бидејќи функцијата f не е потребно да биде еден на еден (во променливата x n+1) Дефиниција.Функции кои можат да се извлечат од наједноставните o(x)=0, s(x)=x+1,
I m n (x 1 ,..., x n)
= x mпримена на оператори за суперпозиција, примитивна рекурзија и оператори за минимизирање конечен број пати се нарекуваат рекурзивен. Класата на рекурзивни функции е поширока од класата на примитивни рекурзивни функции, само затоа што содржи не само функции кои се дефинирани насекаде. Да докажеме, на пример, дека функцијата = x − y, ако x ≥ y< y f(x,y) не постои ако x е рекурзивен. Навистина, f(x,y)=min(z| y+z=x), а претходно беше утврдено дека функцијата u(x,y)=x+y е примитивно рекурзивна. Рекурзивните функции го одразуваат нашето интуитивно разбирање на функциите што некои механички уреди може да ги пресметаат. Особено, тие се пресметливи на машините на Тјуринг (види претходниот став). Напротив, секоја функција што може да се пресмета на машината Туринг е рекурзивна. Ние нема да го провериме овој факт, бидејќи за тоа би било потребно премногу време и простор. Целосен доказ може да се најде, на пример, во книгата на А.И. Малцев „Алгоритми и рекурзивни функции“. Забележете дека не секоја функција од природни аргументи е рекурзивна, дури ни секоја функција од еден аргумент. Постоењето на нерекурзивни функции е „математичка причина“ за присуството на алгоритамски нерешливи проблеми. Во различни гранки на математиката постојат алгоритамски нерешливи проблеми, т.е. проблеми за кои не постои алгоритам за решение и тоа не затоа што сè уште не е измислен, туку затоа што во принцип е невозможно. Се разбира, алгоритмот мора да се разбере во смисла на Тјуринг машини и рекурзивни функции. Да формулираме еден од овие проблеми Проблем со запирање на машината Тјуринг.Тјуринг машина е објект дефиниран со конечен број параметри. Сите парцијални пресликувања од едно конечно множество во друго може ефикасно да се пренумерираат. Затоа, на секоја Тјуринг машина може да и се додели број (природен број). Нека T(n) е Турингова машина со број n. Некои машини кои почнуваат да работат на празен појас на крајот престануваат, а некои работат на неодредено време. Проблемот се јавува: со оглед на природен број n, одреди дали Туринговата машина Т(n) лансирана на празна лента ќе запре или не. Оваа задача алгоритамски нерешливи. Односно нема автоматска процедура ,
за секое n одлучува дали машината T(n) запира или не. Ова не нè спречува да одредиме за која било конкретна машина дали запира или не. Не постои метод што го решава ова за сите машини одеднаш .
Со оглед на проблем, како да се најде ефикасен алгоритам за негово решавање? И ако се најде алгоритам, како може да се спореди со други алгоритми кои го решаваат истиот проблем? Како да се оцени неговиот квалитет? Прашањата од овој вид се од интерес и за програмерите и за оние кои се вклучени во теоретското проучување на компјутерите. Постојат многу критериуми за оценување на алгоритмите. Најчесто, ќе нè интересира редоследот на раст на времето и капацитетот на меморијата потребни за решавање на проблемот како што се зголемуваат влезните податоци. Ние би сакале да поврземе број со секоја специфична задача, наречена нејзината големина ,
кој би изразил мерка за количината на влезните податоци. На пример, големината на проблемот со множење на матрицата може да биде најголемата големина на матриците на факторот. Времето потребно од алгоритам како функција од големината на проблемот се нарекува временска сложеностовој алгоритам. Однесувањето на оваа сложеност во границата како што се зголемува големината на проблемот се нарекува асимптотична временска сложеност
.
Слично можеме да дефинираме капацитивна сложености асимптотична капацитивна комплексност. Асимптотичната сложеност на алгоритмот е таа што на крајот ја одредува големината на проблемите што може да се решат со овој алгоритам. Ако алгоритам обработува влезови со големина n во време cÿn 2 , каде што в -
некоја константа, тогаш тие велат дека временската сложеност на овој алгоритам е O(n 2) (читај „од ред и квадрат“). Некој би помислил дека огромното зголемување на брзината на пресметување што го предизвикува сегашната генерација на дигитални компјутерски машини ќе ја намали важноста на ефикасните алгоритми. Меѓутоа, се случува спротивното. Бидејќи компјутерските машини стануваат сè побрзи и побрзи и можеме да решаваме поголеми проблеми, сложеноста на алгоритмот е таа што го одредува зголемувањето на големината на проблемот што може да се постигне како што се зголемува брзината на машината. Да речеме дека имаме пет алгоритми A1, A2,…, A5 со следните временски сложености: Овде, временската сложеност е бројот на временски единици потребни за обработка на влез со големина n. Единицата за време нека биде една милисекунда (1сек=1000 милисекунди). Тогаш алгоритмот А1 може да обработи влез со големина 1000 за една секунда, додека А5 може да обработи влез со големина не повеќе од 9. Во табелата. 6.5.1. Дадени се големини на проблеми кои можат да се решат за една секунда, една минута и еден час со секој од овие пет алгоритми. Табела 6.5.3. Да претпоставиме дека следната генерација на компјутери ќе биде 10 пати побрза од сегашната. Во табела 6.5.2. покажува како ќе се зголеми големината на проблемите што можеме да ги решиме поради ова зголемување на брзината. Забележете дека за алгоритмот А5, десеткратното зголемување на брзината ја зголемува големината на проблемот што може да се реши за само три единици (видете ја последната линија во Табела 6.5.2.), додека за алгоритмот А3 големината на проблемот повеќе од тројно . Табела 6.5.4. Наместо ефектот на зголемување на брзината, сега да го разгледаме ефектот од користење на поефикасен алгоритам. Да се вратиме на табелата 6.5.1. Ако земеме 1 минута како основа за споредба, тогаш со замена на алгоритамот А4 со алгоритам А3, можеме да решиме проблем 6 пати поголем, а со замена на А4 со А2 ,
можеш да решиш проблем 125 пати поголем. Овие резултати се многу поимпресивни од 2x подобрувањето постигнато со 10 пати поголема брзина. Ако земеме 1 час како основа за споредба, разликата се покажува уште позначајна. Од ова заклучуваме дека асимптотичната сложеност на алгоритам служи како важна мерка за квалитетот на алгоритмот и мерка која ветува дека ќе стане уште поважна со последователните зголемувања на брзината на пресметување. И покрај фактот што главното внимание овде се посветува на редот на раст на количините, мора да се разбере дека голем ред на раст во сложеноста на алгоритмот може да има помала мултипликативна константа (константа вво дефиницијата за O(f(x))), отколку мал ред на зголемување на сложеноста на друг алгоритам. Во овој случај, алгоритам со брзо растечка сложеност може да се претпочита за мали проблеми - можеби дури и за сите проблеми за кои сме заинтересирани. На пример, да претпоставиме дека временските сложености на алгоритмите A1, A2, A3, A4, A5 се всушност 1000n, 100nÿlog(n), 10n2, n3 и 2, соодветно. n Тогаш A5 ќе биде најдобар за проблеми со големина 2§n§9, A2 - за проблеми со големина 10§n§58, A1 - на 59§n§1024, и А1-со n>1024.- 1. Ф.А.Новиков. Дискретна математика за програмери./ Санкт Петербург: Петар, 2001, 304С. 2. С.В.Судоплатов, Е.В.Овчиникова. Елементи на дискретна математика./ М., ИНФРА-М, Новосибирск, Издавачка куќа НСТУ, 3. Y.M.Erusalimsky. Дискретна математика / М., „Универзитетска книга“, 2001 година, 279 стр. 4. А. Ахо, Ј. Хопкрофт, Џ. Улман. Изградба и анализа на пресметковни алгоритми. / М., Мир, 1979, 536С. 5. В.Н.Нефедов, В.А.Осипова Курс по дискретна математика./ М., Издавачка куќа МАИ, 1992 година, 264стр.§4.3. Квантификатори и нивните својства.
Поглавје V. Формални теории.
§5.1. Дефиниција на формална теорија.
§5.2. Предлог пресметка.
§5.3. Теорема за дедукција. Комплетност на IV.
§5.4. Автоматско докажување на теоремите.
§5.5. Метод на резолуција во IW.
Поглавје VI. Елементи на теоријата на алгоритми.
§6.1. Дефиниција на алгоритам.
§6.2. Тјуринг машина.
q 0
…
qi
…
q m
…
а у
q
с
а
rS
…
§6.3. Рекурзивни функции
§6.4. Алгоритамски нерешливи проблеми.
§6.5. Алгоритми и нивната сложеност.
ЛИТЕРАТУРА.