Изпращането на вашата добра работа в базата знания е лесно. Използвайте формата по-долу

добра работакъм сайта">

Студенти, докторанти, млади учени, които използват базата от знания в обучението и работата си, ще ви бъдат много благодарни.

Все още няма HTML версия на произведението.
Можете да изтеглите архива на работата, като кликнете върху връзката по-долу.

Подобни документи

Основни дефиниции на математическата логика, булеви и еквивалентни функции. Общи понятияБулева алгебра. Алгебра на Жегалкин: твърдения и предикати. Определение формална теория. Елементи от теорията на алгоритмите, рекурсивни функции, машина на Тюринг.

курс на лекции, добавен на 08.08.2011 г


Основни форми на мислене: понятия, съждения, изводи. Есе от Джордж Бул, което изследва логическата алгебра в детайли. Истинната стойност (т.е. истинност или неистинност) на дадено твърдение. Логически операцииинверсия (отрицание) и връзка.

презентация, добавена на 14.12.2016 г


Графична интерпретация на множества и операции върху тях. Математическа логика, булева алгебра. Перфектен конюнктив нормална форма. Еквивалентни формули и тяхното доказателство. Завършеност на системата Булеви функции. Предикатна логика, теория на графите.

лекция, добавена на 12/01/2009


История на възникването на булевата алгебра, развитие на системата на пропозиционалното смятане. Методи за установяване истинността или неистинността на комплекса логически твърдениячрез използване алгебрични методи. Дизюнкция, конюнкция и отрицание, таблици на истинност.

презентация, добавена на 22.02.2014 г


Квадратни матриции детерминанти. Координатно линейно пространство. Системни изследвания линейни уравнения. Алгебра на матриците: тяхното събиране и умножение. Геометрично изображение комплексни числаи тях тригонометрична форма. Теорема и основа на Лаплас.

ръководство за обучение, добавено на 03/02/2009


Основната концепция на теорията на положителните (естествени) числа. Разработване на стенография за аритметични операции. Символен език за делимост. Свойства и алгебра на сравненията. Повишаване на сравнения с правомощия. Повторна квадратура. Малката теорема на Ферма.

презентация, добавена на 04.06.2014 г


системи цифрова обработкаинформация. Концепцията за Булова алгебра. Обозначения на логическите операции: дизюнкция, конюнкция, инверсия, импликация, еквивалентност. Закони и тъждества на Булевата алгебра. Логически основиКОМПЮТЪР. Трансформация на структурни формули.

презентация, добавена на 11.10.2014 г

Волжски университет на име. Татищева.

Лекции по математическа логикаи теория на алгоритмите.

Съставител: доц. С.В. Каверин.

Глава 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.

Булеви функциинаричан още функции на логическата алгебра, двоични функции и превключващи функции.

Булева функция от п променливите могат да бъдат определени от таблица на истината, в която набори от стойности на аргументи са подредени във възходящ ред на техните номера : на първо време тече набиране на персонал, представляващо двоичното разширение на 0 (този набор е номериран с 0); след това идва наборът, който е двоичното разширение на 1, след това 2, 3 и т.н. Последният комплект се състои от п единици и е двоичното разширение на числото 2 п-1 (този ред на подреждане на комплекти ще бъде извикан лексикографски ред ). Като се има предвид, че броенето започва от 0 и стойността на булева функция може да бъде 0 или п

1, заключаваме, че има само 22 различни булеви функции на п променливи. Така има например 16 булеви функции на две променливи, 256 на три и т.н.

Пример 1.1.1.(гласуване) . Нека разгледаме устройство, което записва приемането на определена резолюция от „комитета на трима“. Всеки член на комисията натиска свой бутон, когато одобрява резолюция. Ако мнозинството от членовете гласуват „за“, решението е прието. Това се записва от записващо устройство. По този начин устройството изпълнява функцията f(x,y,z ) , чиято таблица на истинност има формата

х	0	0	0	0	0	1	1	1
г	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може също да се определи чрез следната система от равенства: 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, xлетят, 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) зависи значителноот променлива х k, ако съществува такъв набор от стойности а 1 ,а 2 ,…,а k - 1, а k+1, а k + 2 ,…, а пче f (а 1,а 2,…,а к-1 , 0 ,а k+1,a k+2,...,a н) π f (а 1,а 2,…,а к-1 , 1 ,а k+1,a k+2,...,a n).

В този случай х k се нарича съществена променлива , V иначе х k се нарича незначима (фиктивна) променлива . С други думи, една променлива е неуместна, ако нейната промяна не променя стойността на функцията.

Пример 1.4.1.Нека булевите функции f 1 (x 1 ,x 2) и f 2 (x 1 ,x 2) са дефинирани от следната таблица на истинност:

х 1	х 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 ,…, a 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 ,a 2 ,...,a n)§( b 1 ,b 2 ,...,b n) ако и само ако а 1 § b 1 , а 2 § b 2 ,…,a n § bп. Функция f(x 1, x 2,..., x n) се нарича монотонна, ако за всеки два елемента от B n, така че

(а 1 ,a 2 ,...,a n)§( b 1 ,b 2 ,...,b n) следва, че f( а 1 ,a 2 ,...,a n)§f( b 1 ,b 2 ,...,b n).

Извиква се система 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 ⋅ z)

Глава II. Булева алгебра.

Наборът от всички булеви стойности в основата S1=( ÿ, &, ⁄} форма Булева алгебра. По този начин в булевата алгебра всички формули се записват с помощта на три съединителя: Ÿ, &, ¤. Ние частично разгледахме свойствата на тази алгебра в глава I (вижте например основните еквивалентности). Тази глава се занимава със свойства, специфични за булевата алгебра и следователно в тази глава ще се занимаваме само с три функции: ÿ, &, ⁄.

§2.1. Нормални форми.

Нормалните форми са синтактично недвусмислен начин за писане на формула, която изпълнява дадена функция.

Ако x е логическа променлива и σœ(0,1), тогава изразът x σ = x if if σσ == 10 или x σ = 10 if if 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, използваме 1-вия закон на разпределението.

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 ⋅ y⋅z =

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) е перфектна КНФ.

3. (x ∨ y) ⋅ (x ∨ z) не е перфектна КНФ, тъй като например първата сума не включва променливата 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

х	г	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), constituent_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 ∨ y ∨ z ) ⋅(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. 2.Конструирайте SDNF за функцията f, като използвате еквивалентни трансформации.

f = x ∨ y ⋅ z = x ⋅ (y ∨ y) ⋅ (z ∨ z) ∨ y ⋅ z ⋅ (x ∨ x) == x ⋅ y ⋅ z x ⋅ y ⋅ z x ⋅ y ⋅ z x ⋅ y ⋅ z y ⋅ z ⋅ x y ⋅ z ⋅ x =

ОТСТЪПЛЕНИЕ.

Изчисляването на SDNF има не само теоретични, но и големи практическо значение. Например в много модерни програмис графичен интерфейс за композиране на комплекс логически условияизползва се визуална форма под формата на таблица: в клетките се записват условия, а клетките от една колона се считат за свързани с конюнкция, а колоните се считат за свързани с дизюнкция, т.е. образуват DNF (или обратно, в този случай се получава CNF). По-специално, така е проектиран графичният интерфейс QBE (Query-byExample), използван за формулиране на логически условия при запитване към СУБД.

Алгоритъм 2.2.1.Изграждане на SDNF

Вход: вектор X: масив от низове - идентификатори на променливи, матрица V: масив от 0..1 от всички различни набори от стойности на променливи,

вектор F: масив от 0..1 съответстващи стойности на функцията.

Изход:поредица от символи, формиращи запис на SDNF формулата за дадена функция.

f:= невярно(знак за наличието на левия операнд на дизюнкцията) зааз от 1към 2n направи

ако F[i] = 1 тогава ако f тогава

добив"¤" (добавяне на знак за дизюнкция към формулата; оператор добив m разпечатки

символ m) друго f:= вярно

край ако g:= невярно(знак за наличието на левия операнд на конюнкцията) зай от 1къмп направи акож тогава

добив"⁄" (добавяне на знак за връзка към формулата)

друго g: =вярно

край ако ако V ( добавяне на идентификатор на променлива към формулата

§2.3. Минимизиране на DNF по метода на Quine.

Всяка формула има крайно числопоявявания на променливи. Появата на променлива се отнася до мястото, което променливата заема във формулата. Задачата е да се намери за дадена булева функция f DNF, представляваща тази функция и притежаваща най-малкото числопоявявания на променливи.

Ако x е логическа променлива и σœ(0,1), тогава изразът x σ =xx if if σσ== 10 .

наречен писмо . Съединителнаречена връзка на букви. Например формулите x ⋅ y ⋅ z и x ⋅ y ⋅ x ⋅ x са връзки . Елементарният продукт е връзка, в която всяка променлива се появява не повече от веднъж (или самата тя, или нейното отрицание).

Формула f1 се нарича имплицитноформули f , ако 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	х	г		х		г
							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 . След това, извършвайки на два етапа всички възможни операции на непълно залепване и след това елементарна абсорбция, имаме

f

По този начин, съкратената 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. Матрицата на Куайн има формата

В задънена DNF се избира минималният брой прости импликанти, чиято дизюнкция запазва всички съставни части на единицата, т.е. всяка колона на матрицата на Quine съдържа звездичка в пресечната точка с реда, съответстващ на един от избрани импликанти. Задънената DNF, която има най-малък брой появявания на променливи, се избира като минимална DNF.

В пример 2.3.3, използвайки матрицата на Куайн, намираме, че минималната DNF на дадена функция е x ⋅ y ¤ x ⋅ z.

Коментирайте.

използвайте f =f и законите на De Morgan.

§ 2.4. Карти на Карно.

Друг начин за получаване на прости импликантни формули с малък брой променливи (и следователно за намиране на минималната DNF) се основава на използването на така наречените карти на Карно.

Картата на Карно е специален типтаблица, която опростява процеса на намиране на минимални форми и се използва успешно, когато броят на променливите не надвишава шест. Карта на Карно за функции, зависещи от n променливи, е правоъгълник, разделен на 2 n клетки. Всяка клетка от диаграмата е свързана с двоично n-измерно множество. Стойностите на дадена функция f от таблицата на истината се въвеждат в необходимите квадратчета, но ако клетката съответства на 0, тогава тя обикновено остава празна.

В таблица 2.4.1. показва пример за маркиране на карта на Карно за функция, която зависи от три променливи. Долните четири клетки на картата съответстват на двоични набори, в които променливата хприема стойност 1, горните четири клетки съответстват на набори, в които променливата хприема стойност 0. Четирите клетки, които съставляват дясната половина на картата, съответстват на набори, в които променливата y; приема стойност 1 и т.н. В таблица 2.4.2. Показано е маркирането на картата на Карно за n=4 променливи.

За да конструираме минимална DNF, изпълняваме процедура за залепване "1".Стойностите "1", които се слепват, съответстват на съседни клетки, т.е. клетки, различаващи се само по стойността на една променлива (по графично представянеразделени вертикално или хоризонтална линиякато се вземе предвид близостта на противоположни крайни клетки).

Процесът на залепване на "1" се свежда до комбиниране на отделни клетки от картата на Karnaugh в групи, като трябва да се спазват следните правила;

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.Изградете MDNF.

Първо гледаме дали има покрития_ 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 и законите на De Morgan.

Глава 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 с 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 Използване на таблицата на истината

х	0	0	1	1
г	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 .

Обърнете внимание, че предимството на алгебрата на Zhegalkin (в сравнение с други алгебри) е аритметизацията на логиката, което прави възможно извършването на трансформации на булеви функции доста просто. Неговият недостатък в сравнение с булевата алгебра е тромавостта на формулите.

Глава 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» - одноместный предикат, определенный на множестве реални числа M=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).

§4.3. Квантори и техните свойства.

Нека 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

Глава V. Формални теории.

§5.1. Дефиниция на формалната теория.

Формална теория(или смятане) Y- Това:

1. комплект А формиране на герои азбука ;

1. много Е думи в азбуката А, Е Ã А които се наричат формули ;

3. подмножество б формули, б Ã Е , които се наричат аксиоми;

4. много отношения Р върху набор от формули, наречени правила за умозаключение.

Много герои А може да бъде ограничен или безкраен. Обикновено за формиране на символи се използва краен набор от букви, към които, ако е необходимо, се присвояват естествени числа като индекси.

Много формули Е обикновено се дава чрез индуктивна дефиниция, например с помощта на формална граматика. По правило това множество е безкрайно. Комплекти А И Е колективно определят език , или подпис , формална теория.

Много аксиоми б може да бъде ограничен или безкраен. Ако наборът от аксиоми е безкраен, тогава, като правило, той се определя с помощта на краен набор от схеми на аксиоми и правила за генериране на конкретни аксиоми от схемата на аксиомите.

Много правила за извод Р , като правило, разбира се. И така, смятане Yима четворка (A, F, B, R) .

Чрез извеждане в смятането 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наречен пълен(или адекватно), ако всяко вярно твърдение M съответства на теорема от теорията Y .

Формална теория Yнаречен решим, ако има алгоритъм, който за всяка формула на теорията определя дали тази формула е теорема на теорията Yили не.

§5.2. Пропозиционално смятане.

Използвайки концепцията за формално смятане, ние дефинираме пропозиционално смятане (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 аксиомни схеми . При заместване на конкретни формули във всяка схема се получава частен случай на схемата на аксиомата.

Правило за умозаключениев IW има правило за заключение (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), Г+A, тогава Г,B+A. (можете да увеличите броя на хипотезите).

2. Ако и само ако F 1 ,F 2 ,…,F n +A, когато F 1 ⁄F 2 ⁄…⁄F n +A (свеждане на много хипотези до една хипотеза).

§5.3. Теорема за дедукция. Завършеност на IV.

Теорема 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., проверката на изводимостта на формула A от формулите F 1,F 2,…,F n, се свежда до проверка на доказуемостта на формулата

F 1 Ø(F 2 Ø…Ø(F n-1 Ø(F n ØA))…).

Спомнете си, че формула A се нарича идентично вярна (или тавтология), ако стойността на формулата A е равна на единица за всеки набор от стойности на пропозиционалните променливи. Следващата теорема свежда проверката на доказуемостта на формула до проверка на нейната идентична истинност.

Теорема 5.3.2. (относно пълнотата). Формула A е доказуема тогава и само ако A е идентично вярна (тавтология): +A ‹ A-тавтология.

По този начин, за да се определи дали една формула е доказуема, е достатъчно да се състави нейната таблица на истинност. Както е известно, има ефективен алгоритъм за конструиране на таблица на истината и следователно IV разрешими.

Пример 5.3.1.Нека докажем, че P+P. По теоремата за дедукцията това е еквивалентно на +(PØP). От своя страна, според теоремата за пълнотата е достатъчно да се докаже, че (РØР) е тавтология. Съставяне на таблица на истинност за формулата (РØР) , Ние сме убедени, че (РØР) е идентично вярно и, следователно, доказуемо.

Теорема 5.3.3. (относно последователността).Изчислението на IW е последователно.

Доказателство. Съгласно теоремата за пълнотата, всяка формула, която не е идентично вярна, не е доказуема в IW. Например, такава формула е формулата A⁄(ŸA).

Множеството от формули Г се нарича спорен , ако Г+А⁄(ŸА) . Ако Г е противоречив набор от формули, ще обозначим този факт с Г+.

Изявление 5.3.1. Формула A е изводима от множеството формули Г тогава и само тогава, когато множеството Г»(ŸA) е противоречиво.

§5.4. Автоматично доказателство на теореми.

Автоматичното доказване на теореми е крайъгълният камък на логическото програмиране, изкуствения интелект и други съвременни тенденции в програмирането. Най-общо казано, може да няма алгоритъм, чрез който, дадена произволна формула A, човек може да определи в краен брой стъпки дали A е изводим в изчислението Y или не. Въпреки това, за някои прости формални теории (например пропозиционално смятане) и някои прости класове формули (например приложено предикатно смятане с един унарен предикат) са известни алгоритми за автоматично доказване на теорема. По-долу, използвайки примера на пропозиционалното смятане, очертаваме основите на метода на разделителната способност - класически и в същото време популярен метод за автоматично доказване на теореми.

§5.5. Метод на разделителна способност в IW.

Спомнете си, че ако x е логическа променлива и σœ(0,1), тогава изразът

x σ = xx if if σσ == 10 или x σ = 10 if if 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. res A (A ∨ B ∨ C,A) = B ∨ C ;

2. res B (B ∨ C,B) = C ;

3. res D (C ∨ D ∨ E,F ∨ D) = C ∨ E ∨ F ;

4. res E (C ∨ E ∨ F,F ∨ E) = C ∨ F ;

5. res 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.

Глава VI. Елементи от теорията на алгоритмите.

§6.1. Дефиниране на алгоритъм.

Характерна особеност на съвременността е широкото използване на компютри при решаване на проблеми (задачи) в различни области на човешката дейност. Проблемът обаче първо трябва да се реши алгоритмично, т.е. трябва да се даде формално предписание, следвайки което може да се получи крайният резултат за решаване на всички проблеми от определен тип (това е интуитивно, а не строго понятие за алгоритъм). Например алгоритъм за намиране на най-голям общ делител на две естествени числа а, б, изглежда така:

1) разширете числото апо прости множители;

2) повторете стъпка 1 за b Иотидете на стъпка 3;

3) съставете произведението на общи прости множители от разширения АИ bс индекси, равни на най-малкия от индексите на включване в разширенията.

След като анализирахме този пример, отбелязваме най-важните характеристики (свойства) на алгоритъма:

1. Масов характер- приложимост на алгоритъма не към един проблем, а към клас проблеми.

2. Дискретност- ясна разбивка на отделни етапи (стъпки) на алгоритъма.

3. Детерминизъм- такава организация на етапите на изпълнение, при която винаги е ясно как да се направи преходът от един етап към друг.

4. Крайник- за получаване на резултат при прилагане на алгоритъм за решаване на конкретен проблем се изпълнява крайна последователност от стъпки на алгоритъма:

Обърнете внимание, че ако наличието на алгоритъм само по себе си служи като доказателство за съществуването на алгоритъм, то за да се докаже липсата му, е необходимо да има строга математическа дефиниция на алгоритъм.

Опитите да се формализира концепцията за алгоритъм доведоха до създаването Машини на Тюринг, като някакво въображаемо устройство, което изпълнява алгоритъма. Друга стъпка в дефинирането на концепцията за алгоритъм беше появата рекурсивни функции , като функции, които формализират концепцията за алгоритъм и прилагат интуитивната концепция за изчислимост. Скоро беше открито, че наборът от рекурсивни функции съвпада с набора от функции, изчислими на машини на Тюринг. Нови концепции, които се появиха тогава, претендирайки да обяснят концепцията за алгоритъм, се оказаха еквивалентни на функции, изчислими на машини на Тюринг, и следователно на рекурсивни функции. Резултатът от продължаващата дискусия за това какво е алгоритъм беше твърдение, което сега се нарича тезата на Чърч.

Тезата на Чърч.Концепцията за алгоритъм или изчислимост от някакво механично устройство съвпада с концепцията за изчислимост на машините на Тюринг (и следователно с концепцията за рекурсивна функция). С други думи, алгоритъмът е процес, който може да бъде представен чрез функционална диаграма и реализиран от някаква машина на Тюринг.

§6.2. Машина на Тюринг.

Машината на Тюринг е (абстрактно) устройство, състоящо се от лента, контролно устройство и четяща глава.

Лентата е разделена на клетки. Всяка клетка съдържа точно един знак от външна азбука A=( а 0, а 1,…, a n ).Някакъв символ (ще го обозначим Ÿ ) от азбуката A се нарича празна и всяка клетка, която в момента съдържа празен знак, се нарича празна клетка (в този момент). Предполага се, че лентата е потенциално неограничена и в двете посоки.

Контролно устройствовъв всеки момент от времето е в някакво състояние q j, принадлежащо на множеството Q=(q 0 , q 1 ,..., q m )(m=l). Множеството Q се нарича вътрешна азбука . Едно от тези състояния (обикновено q 0) се нарича окончателен, а някои други (обикновено р 1) - начален.

Четящата глава се движи по дължината на лентата, така че във всеки един момент да сканира точно една клетка от лентата. Главата може да прочете съдържанието на наблюдаваната клетка и да запише в нея вместо наблюдавания символ някакъв нов символ от външната азбука А(възможно е същият).

По време на работа контролното устройство, в зависимост от състоянието, в което се намира и символа, гледан от главата, променя вътрешното си състояние р. След това издава заповед на ръководителя да отпечата определен знак от външната азбука в наблюдаваната клетка а,и след това заповядва на главата или да остане на място, или да премести една клетка надясно, или да премести една клетка наляво. Веднъж в крайно състояние, машината спира да работи.

Конфигурация на лента (или машинна дума)се нарича множеството, образувано от:

1) последователност а аз (1) , а аз (2) ,...,а i(s)знаци от външната азбука А, записани в клетки на лента, където а аз (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)

тук r- възприетата клетка се маркира като дроб.

Ако машината е във вътрешно състояние q i, приема клетка със символ a u, записва символ в тази клетка в следващия момент от време a r, преминава във вътрешно състояние qsи се движи по лентата, тогава казват, че машината изпълнява командата q i a u Æ q s a r S, където символът S може да приема една от следните стойности: -1 – изместване на главата наляво; +1 - изместване на главата надясно; 0 – главата остава на мястото си. Извиква се списъкът с всички команди (quints), които определят работата на машина на Тюринг програматази кола. Машинната програма често се определя под формата на таблица. Така че за ситуацията, описана по-горе в таблицата на пресечката

линии а uи колона q iще стои q s a r S(виж таблица 6.2.1)

Таблица 6.2.1.

q 0	…	q i	…	q m
…
a u	р s а rS
…

Ако програмата включва автомобили за двойка ( q i ,a u ) пет липсва, след това в таблицата в пресечната точка на линията a u, и колона q iдобавя се тире.

така че Машината на Тюринг е по дефиниция, комплект M=(A,Q,P), Къде А- външна азбука, Q— азбука на вътрешните състояния, П- програма.

Ако една машина, започнала да работи с някаква дума P, написана на лента, достигне крайното състояние, тогава тя се извиква приложимо към тази дума. Резултатът от неговата работа е думата, записана на касетата в нейното крайно състояние. В противен случай се казва, че машината не е приложима към думата R.

Пример 6.2.1. Нека изградим машина на Тюринг, която събира естествени числа, записани в унарната бройна система (т.е. написани с помощта на един символ |. Например 5=|||||.).

Решение. Помислете за азбуката А = {|, +, ⁄}.

Машината се определя от следната програма:

Нека запишем конфигурациите, които възникват последователно по време на работата на тази машина върху оригиналната дума ||+ ||| , т.е. 2+3. Тук, когато записваме конфигурацията, ще използваме следната конвенция: състоянието, в което се намира машината, се изписва в скоби вдясно зад наблюдаваната буква.

Пример 6.2.2.Изградете машина на Тюринг, която удвоява естествени числа, записани в унарната бройна система.

Решение.Ще конструираме търсената машина в азбуката A=(|, α, ⁄). Програмата за такава машина може да изглежда така:

Нека приложим получената машина към думата || .

Въвеждане на нова буква α и замяна на оригиналните | на α позволява да се разграничи оригиналът | и нови (присвоени) | . състояние р 1осигурява замяна | на α , състояние р 2осигурява търсене на α , предназначени за замяна | и спиране на машината в случай, че α не се открие, р 3гарантира завършване | в случая, когато α беше заменено с |.

§6.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, Аз съм 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), fact(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, х 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).

Ако такива гне, тогава приемаме, че 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.

Ако възникне 1-ви случай, тогава g(x 1 ,x 2 ,… ,x n ,x n+1)=y, а ако 2-ри или 3-ти случай, тогава 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, Аз съм 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 е примитивно рекурсивна.

Рекурсивните функции отразяват нашето интуитивно разбиране за функциите, които някои механични устройства могат да изчислят. По-специално, те са изчислими на машини на Тюринг (вижте предишния параграф). Напротив, всяка функция, изчислима на машина на Тюринг, е рекурсивна. Няма да проверяваме този факт, тъй като ще отнеме твърде много време и място. Пълно доказателство може да се намери например в книгата на А. И. Малцев „Алгоритми и рекурсивни функции“.

Обърнете внимание, че не всяка функция на естествени аргументи е рекурсивна, дори не всяка функция на един аргумент. Съществуването на нерекурсивни функции е „математическата причина“ за наличието на алгоритмично неразрешими проблеми.

§6.4. Алгоритмично неразрешими проблеми.

В различни клонове на математиката има алгоритмично неразрешими задачи, т.е. проблеми, за които няма алгоритъм за решаване, и не защото все още не е измислен, а защото е невъзможен по принцип. Разбира се, алгоритъмът трябва да се разбира в смисъла на машините на Тюринг и рекурсивните функции.

Нека формулираме един от тези проблеми

Проблем със спирането на машината на Тюринг.Машината на Тюринг е обект, дефиниран от краен брой параметри. Всички частични преобразувания от едно крайно множество в друго могат да бъдат ефективно преномерирани. Следователно на всяка машина на Тюринг може да се присвои номер (естествено число). Нека T(n) е машина на Тюринг с номер n. Някои машини, които започват да работят на празна лента, в крайна сметка спират, а някои работят за неопределено време. Проблемът възниква: дадено естествено число n, определете дали машина на Тюринг T(n), стартирана на празна лента, ще спре или не. Тази задача

алгоритмично неразрешим. Тоест няма автоматична процедура , за всяко n решава дали машината T(n) спира или не. Това не ни пречи да определим за всяка конкретна машина дали спира или не. Няма метод, който решава това за всички машини наведнъж .

§6.5. Алгоритми и тяхната сложност.

При даден проблем, как да се намери ефективен алгоритъм за разрешаването му? И ако бъде намерен алгоритъм, как може да бъде сравнен с други алгоритми, които решават същия проблем? Как да оценим качеството му? Въпроси от този вид са от интерес както за програмистите, така и за тези, които се занимават с теоретично изучаване на изчисленията.

Има много критерии за оценка на алгоритмите. Най-често ще се интересуваме от реда на нарастване на времето и капацитета на паметта, необходими за решаване на задача, с увеличаване на входните данни. Бихме искали да свържем номер с всяка конкретна задача, наречена нейния размер , което би изразило мярка за количеството входни данни. Например, размерът на проблем с умножение на матрица може да бъде най-големият размер на фактор матриците.

Времето, необходимо на алгоритъм като функция от размера на проблема, се нарича времева сложносттози алгоритъм. Поведението на тази сложност в границата с увеличаване на размера на проблема се нарича асимптотична времева сложност . По подобен начин можем да определим капацитивна сложности асимптотична капацитивна сложност.

Това е асимптотичната сложност на алгоритъма, която в крайна сметка определя размера на проблемите, които могат да бъдат решени с този алгоритъм. Ако алгоритъм обработва входове с размер n за време cÿn 2, където c - някаква константа, тогава те казват, че времевата сложност на този алгоритъм е O(n 2) (да се чете „от ред на квадрат“).

Човек може да си помисли, че огромното увеличение на изчислителната скорост, предизвикано от сегашното поколение цифрови изчислителни машини, ще намали значението на ефективните алгоритми. Случва се обаче обратното. Тъй като изчислителните машини стават все по-бързи и по-бързи и ние можем да решаваме по-големи проблеми, сложността на алгоритъма е това, което определя увеличаването на размера на проблема, което може да бъде постигнато с увеличаване на скоростта на машината.

Да кажем, че имаме пет алгоритъма A1,A2,…,A5 със следните времеви сложности:

Тук времевата сложност е броят времеви единици, необходими за обработка на вход с размер n. Нека единицата за време е една милисекунда (1 сек=1000 милисекунди). Тогава алгоритъм A1 може да обработи вход с размер 1000 за една секунда, докато A5 може да обработи вход с размер не повече от 9. В табл. 6.5.1. Дадени са размерите на задачите, които могат да бъдат решени за една секунда, една минута и един час от всеки от тези пет алгоритъма.

Таблица 6.5.3.

Да приемем, че следващото поколение компютри ще бъде 10 пъти по-бързо от сегашното. В таблица 6.5.2. показва как ще се увеличи размерът на проблемите, които можем да разрешим поради това увеличение на скоростта. Обърнете внимание, че за алгоритъм A5 десетократното увеличение на скоростта увеличава размера на проблема, който може да бъде решен само с три единици (вижте последния ред в таблица 6.5.2.), докато за алгоритъм A3 размерът на проблема се увеличава повече от три пъти .

Таблица 6.5.4.

Вместо ефекта от увеличаване на скоростта, нека сега разгледаме ефекта от използването на по-ефективен алгоритъм. Да се ​​върнем към таблица 6.5.1. Ако вземем 1 минута като база за сравнение, тогава като заменим алгоритъм A4 с алгоритъм A3, можем да решим проблем 6 пъти по-голям и като заменим A4 с A2 , можете да решите проблем 125 пъти по-голям. Тези резултати са много по-впечатляващи от 2x подобрението, постигнато с 10x по-висока скорост. Ако вземем за база за сравнение 1 час, разликата се оказва още по-значима. От това заключаваме, че асимптотичната сложност на алгоритъма служи като важна мярка за качеството на алгоритъма и мярка, която обещава да стане още по-важна с последващо увеличаване на изчислителната скорост.

Въпреки факта, че основното внимание тук се обръща на реда на нарастване на количествата, трябва да се разбере, че голям ред на нарастване на сложността на алгоритъма може да има по-малка мултипликативна константа (константа cв дефиницията на 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, и A1-с n>1024.-

ЛИТЕРАТУРА.

1. Ф. А. Новиков. Дискретна математика за програмисти./ СПб.: Питър, 2001, 304С.

2. С. В. Судоплатов, Е. В. Овчинникова. Елементи на дискретната математика./ М., ИНФРА-М, Новосибирск, издателство NSTU,

3. Ю.М.Ерусалимски. Дискретна математика / М., “Университетска книга”, 2001, 279 стр.

4. А. Ахо, Дж. Хопкрофт, Дж. Улман. Конструиране и анализ на изчислителни алгоритми. / М., Мир, 1979, 536С.

5. V.N.Nefedov, V.A.Osipova Курс по дискретна математика./ М., Издателство MAI, 1992, 264P.

Математическа логика и теория на алгоритмите – Курс лекции
Въведение.

1. 
   Цел.

Този курс служи за развиване на знания и умения, които формират теоретичната основа, необходима за поставяне и решаване на проблеми в областта на компютърните науки, за правилно разбиране на ограниченията, които възникват при създаването на изчислителни структури, алгоритми и програми за обработка на информация.

Новите раздели на курса по дискретна математика, макар и реализирани под формата на образователни програми и поредици от лекции, все още не съществуват под формата на монографии, поне на руски език, тъй като курсът по дискретна математика за техническите университети е фокусиран върху стари приложни проблеми, които инженерите трябваше да решат. По-специално, в математическата логика минимизирането на логическите вериги е загубило своята релевантност днес.

Интересно е да се отбележи, че теорията за синтеза на логически вериги, преминала през почти пълен „биологичен цикъл“ пред очите на едно поколение изследователи, е много поучителен пример за това как клонове на техническите науки, които са слабо свързани с фундаменталните науката са силно податливи на остаряване. Само преди 10 години всички технически списания бяха пълни със статии за минимизиране и синтез на логически схеми. Повечето от методите за минимизиране, разработени от учените, вече са забравени и не се търсят на практика. И онези идеи, които по това време се смятаха за чисто теоретични, намериха практическо приложение в съвременните технологии. Например, размитата логика, мрежите на Петри и теорията на алгоритмите са издържали изпитанието на времето и се използват широко в различни области на кибернетиката и програмирането като системно програмиране, изчислителна сложност и изкуствен интелект.

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

Както знаете, след всяко десетилетие хардуерните компоненти на компютрите, операционните системи, инструментите за достъп и самите програми се променят радикално. Но структурите и алгоритмите, които са в основата им, остават непроменени много по-дълго. Тези основи са започнали да се полагат преди хиляди години, когато е разработена формалната логика и са разработени първите алгоритми.

Математическата логика и теорията на алгоритмите традиционно принадлежат към фундаменталната наука и се считат за слабо свързани с практиката и са трудни за разбиране. Наистина, когато Дж. Бул създава математическия апарат на булевата алгебра, той дълго време не намира практическо приложение, но през 20 век именно този математически апарат прави възможно проектирането на всички компютърни компоненти. Следователно, първият от тези предразсъдъци е успешно опроверган от развитието на компютърните технологии.

Що се отнася до предубеждението за трудността на разбирането на тази дисциплина, то до голяма степен произтича от факта, че книгите по математическа логика и теория на алгоритмите са написани от математици за математици.

Сега, когато възможностите на компютърната технология са се увеличили многократно и има много повече персонални компютри, отколкото има хора, които знаят как да ги използват ефективно, разбирането какво може и какво не може да се направи с помощта на съвременната компютърна технология изключително значение.

Именно общата теория на алгоритмите показа, че има проблеми, които са неразрешими, независимо колко мощна е изчислителната мощ, а нейният бързо развиващ се клон - теорията на изчислителната сложност - постепенно води до разбирането, че има проблеми, които могат да бъдат решени , но са обективно сложни, като сложността им може да се окаже донякъде в абсолютен смисъл, т.е. практически недостъпни за съвременните компютри.

Този курс си поставя следните цели:

1. Представете всички разглеждани въпроси възможно най-просто, но не по-просто, отколкото се изисква за висококвалифициран специалист.

2. Практическите проблеми на проектирането и анализа на информационните системи са отправна точка, а формалният апарат е средство за системно решаване на тези проблеми. Наше дълбоко убеждение е, че ученикът не е съд, който трябва да се напълни, а факла, която трябва да се запали.

3. Всеки раздел от курса съдържа въпроси за самопроверка. За да овладее този курс, студентът трябва да отговори на всички тези въпроси.

В резултат на усвояването на този курс студентът, въз основа на ясно разбиране на съответните теоретични раздели, трябва да може да:

Приложете най-простия тип логическа трансформация на информация в произволен базис от логически функции;

Идентифицирайте логическата структура в доказателственото разсъждение на естествен език, конструирайте формални схеми за доказателство и проверете тяхната коректност.

1.2 Логически представяния
Логически представяния -описание на изследваната система, процес, явление под формата на набор сложни твърдениясъставен от прости (елементарни) твърденияИ логически връзкимежду тях. Логическите представяния и техните компоненти се характеризират с определени свойства и набор от допустими трансформации върху тях (операции, правила за извод и т.н.), прилагащи тези, разработени във формални (математически) В логиката правилните методи на разсъждение са законите на логиката.

В математическа логика.Съвременната математическа логика включва два основни раздела: логика на твърдениятаи го покрива предикатна логика(фиг. 1.1), за чието изграждане има два подхода (езика), формиращи два варианта на формална логика: алгебра на логикатаИ логическо смятане.Съществува едно към едно съответствие между основните понятия на тези езици на формалната логика. Техният изоморфизъм в крайна сметка се осигурява от единството на лежащите в основата допустими трансформации.

ориз. 1.1
Основните обекти на традиционните клонове на логиката са твърденията.

Изявление -декларативно изречение (изявление, присъда), окоето има смисъл да се каже, че то вярноили невярно.Всички научни знания (закони и явления на физиката, химията, биологията и др., математически теореми и др.), събития от ежедневието, ситуации, възникващи в икономиката и процесите на управление, са формулирани под формата на твърдения. Повелителните и въпросителните изречения не са твърдения.

Примери за твърдения: „Два пъти две е четири“, „Живеем в 21 век“, „Рублата е руската валута“, „Альоша е брат на Олег“, „Операциите обединение, пресичане и събиране са булеви операции върху множества ”, „Човек е смъртен” , „Пренареждането на членовете не променя сбора”, „Днес е понеделник”, „Ако вали, трябва да вземете чадър.”

За да оперираме по-нататък с тези изречения като твърдения, трябва да знаем за всяко от тях дали е вярно или невярно, т.е. познавайте ги стойност на истината (истина).Обърнете внимание, че в някои случаи истинността или неверността на дадено твърдение зависи от това каква конкретна реалност (система, процес, явление) се опитваме да опишем с негова помощ. В този случай се казва, че даденото твърдение е вярно (или невярно) в дадена интерпретация (контекст). Освен това приемаме, че контекстът е даден и твърдението има определена стойност на истината.

1.3 История на развитата математическа логика

Логиката като наука се формира през 4 век. пр.н.е Създаден е от гръцкия учен Аристотел.

Думата „логика” произлиза от гръцкото „логос”, което от една страна означава „дума” или „изложение”, а от друга – мислене. В обяснителния речник на Ожегов С.И. Казано е: „Логиката е наука за законите на мисленето и неговите форми“. През 17 век Германският учен Лайбниц планира да създаде нова наука, която ще бъде „изкуството за изчисляване на истината“ . В тази логика, според Лайбниц, всяко твърдение би имало съответен символ, а разсъждението би имало формата на изчисления. Тази идея на Лайбниц, тъй като не е срещнала разбирането на съвременниците си, не е разпространена или развита и остава блестящо предположение.

Едва в средата на 19в. Ирландският математик Джордж Бул въплъщава идеята на Лайбниц. През 1854 г. той написва труда "Изследване на законите на мисълта", който полага основите на алгебрата на логиката, в която важат закони, подобни на законите на обикновената алгебра, но буквите важат. не означават числа, а твърдения. На езика на булевата алгебра човек може да опише разсъжденията и да „изчисли“ резултатите от тях. Той обаче не обхваща всички разсъждения, а само определен вид от тях. , Следователно Булевата алгебра се счита за пропозиционално смятане.

Логическата алгебра на Бул е ембрионът на нова наука - математическата логика. За разлика от това, логиката на Аристотел се нарича традиционна формална логика. Името "математическа логика" отразява две характеристики на тази наука: първо, математическата логика е логика, която използва езика и методите на математиката; второ, математическата логика се оживява от нуждите на математиката.

В края на 19в. Теорията на множествата, създадена от Георг Кантор, изглеждаше надеждна основа за цялата математика, включително математическата логика, поне за пропозиционалното смятане (Булова алгебра), тъй като Оказа се, че алгебрата на Кантор (теорията на множествата) е изоморфна на алгебрата на Бул.

Самата математическа логика се превърна в клон на математиката, който първоначално изглеждаше много абстрактен и безкрайно далеч от практически приложения. Тази област обаче не остава за дълго в сферата на „чистите“ математици. В началото на 20в. (1910) Руският учен Еренфест П.С. посочи възможността за използване на апарата на булевата алгебра в телефонните комуникации за описание на комутационни вериги. През 1938-1940 г. почти едновременно се появяват трудовете на съветския учен В. И. Шестаков, американския учен Шанън и японските учени Накашима и Хаказава за приложението на математическата логика в цифровата техника. Първата монография, посветена на използването на математическата логика при проектирането на цифрово оборудване, е публикувана в СССР от съветския учен М. А. Гаврилов. през 1950 г. Ролята на математическата логика в развитието на съвременната микропроцесорна технология е изключително важна: тя се използва при проектирането на компютърен хардуер, при разработването на всички езици за програмиране и при проектирането на дискретни устройства за автоматизация.

Учени от различни страни направиха голям принос за развитието на математическата логика: професорът от Казанския университет Порецки П.С., Де-Морган, Пърс, Тюринг, Колмогоров А.Н., Хайдел К. и др.

1.4 Въпроси за самопроверка.

1. Формулирайте целите на курса

Математическа логика и теория на алгоритмите

Лектор: А. Л. Семенов

Лекция 1

Въведение 1

Проблем на математическата логика и теория на алгоритмите 1

Математически резултати от математическата логика и теория на алгоритмите 2

Съвременната цивилизация и ролята на MLiTA 2

Изграждане на математиката. Теория на множествата 5

програма математически изследвания математическа дейност- Гилбърт 9

Обща идея 9

Резултати от програмата Хилбърт 12

Език и аксиоми на теорията на множествата. I. Примери 12

Логически символи и тяхното значение (семантика) 12

Примери за аксиоми за съществуване на множества 13

Въведение

Проблемът на математическата логика и теорията на алгоритмите

Проблемът, решен от математическата логика и теорията на алгоритмите, е да се изгради система от математически определения и теореми, които позволяват математически да се опишат и изследват следните видове човешка дейност:

• 
  Доказване на теореми и дефиниране на математически понятия
• 
  Описание на връзките между математическите обекти
• 
  Получаване на следствия от експериментално установени твърдения, от хипотези и др.
• 
  Проектиране на устройства (механични, електронни и др.) със зададени свойства и функции.
• 
  Създаване и прилагане на формални инструкции (описание и прилагане на алгоритми и програми)
• 
  Установяване на съответствие между описанието на искания резултат и алгоритъма, предназначен за постигане на този резултат (доказателство за коректност)

Математическата логика и теорията на алгоритмите предоставят (математически, точни) критерии за коректност на изброените дейности.

Математически резултати от математическата логика и теория на алгоритмите

Чрез провеждането на това изследване ще получим резултати, свързани с:

1. 
   Набори и отношения, които могат да бъдат описани на определен език
2. 
   Набори от доказуеми формули
3. 
   Набори от верни формули (има фундаментална разлика с точка 2)
4. 
   Набори от математически структури, в които формули от даден набор са верни
5. 
   Класове функции, които се изчисляват чрез алгоритми
6. 
   Наличието на алгоритъм, който определя истинността или доказуемостта на формулите
7. 
   Изчислителна сложност
8. 
   Сложност на обектите

и т.н.

Съвременната цивилизация и ролята на MLiTA

Значителният напредък в развитието на човечеството е свързан със създаването на машини за обработка на материални обекти, получаване и предаване на енергия (използвана от тези машини), транспортни средства, осветление и др.

От векове хората са имали идеята да създадат машини, които да работят не с материя и енергия, а с информационни обекти. Освен това такива машини са създадени и дори работят успешно, например машина, която ви позволява да извършвате аритметични операции - машина за добавяне (Б. Паскал).

През първата половина на 20-ти век беше дадено общо описание на възможните методи за формална обработка на информация от хората. До средата на 20-ти век са открити физически принципи, които правят възможно създаването на устройства, които могат да съхраняват много информация и да я обработват много бързо. Създадени са универсални устройства - компютри, които могат да правят всичко, което формално може да направи човек, но много по-бързо от човек.

Като вземем много общ поглед, можем да кажем, че математическата логика осигурява основата за теоретичната математика, а теорията на алгоритмите осигурява основата за изчислителната практика (използването на компютри). По-подробното разглеждане обаче показва, че много постижения на математическата логика са намерили приложение в развитието и прилагането на информационните технологии, а алгоритмичните съображения също са важни в различни раздели на чистата математика.

Важни камъни в историята

Важни моменти в развитието на съвременните идеи за това какво представляват математическите доказателства и изчисления бяха постиженията на немските математици края на XIX- началото на 20 век

От особено значение беше речта на Дейвид Хилберт (23.01.1862 - 14.01.1943) на II Международен конгрес на математиците (Париж, 1900 г.). Там той формулира 23 т.нар. Проблемите на Хилберт са най-важните за математиката от онова време и за развитието на математиката през 20 век. Някои от проблемите на Хилберт са били въпрос на определяне на истинността на определено математическо твърдение, други биха могли да се нарекат по-скоро предложение за извършване на някакъв вид изследователска програма.

Задачи I, II, X от списъка на Хилберт са свързани с предмета на математическата логика и теорията на алгоритмите.

От седемте математически проблема на Милениума, първият също е свързан с нашия предмет (той не беше сред проблемите на Хилберт).

В курса ще бъдат разгледани изброените по-горе проблеми в областта на математическата логика и теория на алгоритмите и съвременния поглед върху тях.

Организационни бележки

Авторите на курса вярват, че най-добрият начин да научите математика и да станете математик е сам да се занимавате с математика. Под математици тук разбираме всички, за които съществена част от професионалната им дейност (а за мнозина и целия им живот) е работа с математически обекти, използвайки математически методи на дейност. Значителна част от дейността в областта на информационните технологии например е структурирана по този начин. Под „правене на математика“ имаме предвид решаване на задачи и на първо място не тези, които най-често се решават в училище или в хода на математическия анализ през първата година на университета. Имаме предвид задачи, при които трябва да измислите нещо ново. Разбира се, когато овладявате нова област на математиката, много от тези проблеми трябва да са прости и отдавна решени, но те не се различават фундаментално от задачите, които професионалният математик и програмист трябва да реши.

Проблеми от типа, за които говорим сега, ще бъдат формулирани както в лекции, така и в курсови упражнения. Не всички формулирани задачи ще бъдат напълно прости. Освен това: някои от тях са решени в математиката съвсем наскоро, ще има такива, които все още не са решени, и други, които изобщо нямат решение (но които са полезни за решаване).

Насърчаваме ви да участвате в решаването на проблеми по време на курса и да ги обсъждате с вашия инструктор (и, разбира се, един с друг). това:

• 
  Ще ви помогне да разберете по-добре съдържанието на лекциите и цялата математическа област, към която се отнася курсът
• 
  По-добре е да се подготвите за изпита и да го „преминете“ частично (решаването на задачи по време на курса ще ви бъде „кредитирано“ на изпита, вашите учители ще ви кажат повече за това)
• 
  Опитайте се в обещаваща област на математиката и може би я изберете за вашата специализация в университета, което може да бъде полезно за вашата работа след университета.

Друго място, където се решават проблеми и се обсъждат решенията им, е Просеминарът по математическа логика и компютърни науки за младши ученици. Там, заедно с прости задачи, които ви позволяват да разберете същността на въпроса, веднага ще ви бъдат предложени както сложни, така и такива, които все още не са решени.

Материалите от следващата лекция ще бъдат публикувани в интернет на сайта http://lpcs.math.msu.su/vml2013/

Освен тях можете да се запознаете със съдържанието на курса от книгите:

• 
  Н. К. Верешчагин, А. Шен, Лекции по математическа логика и теория на алгоритмите, изд. MCCME (mccme.ru)
• 
  И. А. Лавров, Л. Л. Максимова, Проблеми на теорията на множествата, математическата логика и теорията на алгоритмите,

които също са достъпни в интернет.

И накрая, последното нещо. Един от приложните резултати на математическата логика и теорията на алгоритмите е автоматизацията на различни компоненти на математическата дейност. По-специално, проверката на определени видове математически доказателства може да бъде автоматизирана. Областта на такава автоматизация, естествено, непрекъснато се разширява поради развитието на самите алгоритми за автоматизация, по-доброто разбиране от математиците за това как да прилагат тези алгоритми, натрупването на опит и нарастването на изчислителните възможности. Днес най-популярната и ефективна компютърна рамка за автоматизиране на проверката на доказателства е Coq. Нашият отдел провежда семинар за Coq, където можете да научите как да използвате тази среда, да си представите нейните възможности и ограничения.

Изграждане на математиката. Теория на множествата

Съвременната структура на математиката, по-специално начинът, по който се преподава в университетите, се основава на теорията на множествата. Сега ще си припомним някои основни понятия на тази теория.

Къдравите скоби често се използват за дефиниране на множества. В тях можете да поставите всички елементи от даденото множество: (2, 14, 5.4) или да го опишете по специален начин: (x|x е реално число и sin(x)>0).

Използваме следната нотация за операции с множество: членство на елемент в множество ∊, включване на множества ⊂, обединение ∪, пресечна точка ∩, разлика \.

Нека имаме два обекта х,г. Подредена двойка x; г> наречен обект, от който уникално възстановен х, г, с други думи: x; г> = x′; г′> → ( х = х′ г = г′).

Работата х X гдва комплекта х И ге множеството от всички подредени двойки u; v>, къде u ∊ х И v ∊ г.

По същия начин, подредени п-ки обекти и пта степен х пкомплекти х. Може да се съгласи, че х 1 е х.

Връзка между множества х, г всяко подмножество на техния продукт се извиква х X г.

п-локална връзка на множеството хвсяко подмножество се извиква п-та степен на това множество.

Отношение fмежду х И гнаречена функция на х V г, ако от съвпадението на първите компоненти на всеки два елемента от релацията fследва съвпадението на последното.

Домейнът на функция е множеството от нейните първи компоненти.

Ако домейнът на функция е от х V гсъвпада с х, тогава се казва, че функцията се показва х V ги пиши f : х → г. Показване на множество всички функции х V г, обозначен с г х .

функция f : х → гнаречена биекция между х И г, или биекция от х V г, или изоморфизъм х И г, ако от съвпадението на вторите компоненти на елементите fследва, че първите елементи съвпадат, а освен това и вторите елементи fформират целия комплект г. Изоморфните множества се наричат ​​още еквивалентни множества.

Едно множество се нарича изброимо, ако е еквивалентно на естествения ред.

Задача. Докажете, че всяко подмножество на естествена серия е еквивалентно или на своя начален сегмент (който е същият като някои от нейните елементи), или на цялата естествена серия.

Формулирано в последната задача основно наблюдение– това, че една част може да бъде изоморфна на цялото, вероятно изглежда тривиално за второкурсниците. Но това беше едно от първите открития на теорията на множествата.

Крайните множества могат да се сравняват по размер. Ако едно е изоморфно на подмножество на друго, тогава то има по-малко елементи. В случай безкрайни множестватова е грешно. Тази ситуация е описана от Галилео Галилей в следния диалог, който представяме със съкращение:

Разговори Иматематическидоказателство, относно две новиклонове на науката,свързани домеханикаИместно движение

синьора Галилео ГалилейЛинчео, философ и първи математик Негово светло височество велик херцог на Тоскана

Салвиати. ...броят на всички числа заедно - квадрати и неквадрати - е по-голям от броя на квадратите поотделно; не е ли

Simplicio. Не мога да споря срещу това.

Салвиати. Има толкова квадрати, колкото и корени, тъй като всеки квадрат има свой собствен корен и всеки корен свой собствен квадрат; никой квадрат не може да има повече от един корен и нито един корен не може да има повече от един квадрат.

Сагредо. Какво трябва да се направи, за да се намери изход от тази ситуация?

Салвиати. Не виждам възможност за друго решение освен да призная, че свойствата на равенството, както и по-голямата и по-малка величина, не съществуват, когато имаме работа с безкрайност, и са приложими само за крайни количества. Затова, когато синьор Симплисио ми предлага неравни линии и ме пита как е възможно по-голямата от тях да не съдържа повечеточки, отколкото в по-малко, тогава му отговарям, че няма нито повече, нито по-малко и не еднакъв брой от тях, а безкраен брой във всяка.

Въпреки това, дори сред безкрайните множества все още има някакъв ред, както показва следната теорема, също обявена без доказателство от Кантор и скоро доказана от други немски математици.

Теорема на Кантор–Бернщайн. Нека има биекция между множеството Аи подмножество на множеството б, както и биекция между множеството би подмножество на множеството А. След това комплектите АИ б– равни по сила.

Задача. Докажете теоремата на Кантор–Бърнщайн.

Задача. Възможно ли е да се сравняват всякакви множества по отношение на мощността, т.е. вярно ли е, че за всяко АИ б, или Аеднакво мощно подмножество б, или беднакво мощно подмножество А?

Сред функциите, които подчертаваме свойства– функции, които приемат само стойностите 0 и 1. Всяко свойство определя релация – набор от елементи, на които неговата стойност е 1. Всяка функция f : х → B се извиква характеристика(на х). Обърнете внимание, че в нашите обозначения и конвенции B=(0,1)=2. По този начин наборът от всички характерни функции на хполучава наименованието Б хили 2 х .

Задача. Изграждане на изоморфизъм между набора от характеристични функции на хи много подмножества на множеството х.

Задача. Докажете, че множеството от подмножества на всяко множество не е изоморфно на него.

Идея за решение [Диагонал на Кантор]. Нека изоморфизъм Ж : х → 2 хсъществува. Нека разгледаме всеки елемент гот нашите много хсъответното му подмножество Ж(г). Можем ли от елементите хсъберете подмножество В, което би се различавало от комплекта Ж(г) "на елемент г» ? Или, което е същото, как да конструираме една характерна функция f В , което би се различавало от характерната функция на множеството Ж (г) "в точката г» във всеки случай г?

Ако хе набор от естествени числа, тогава доказателството става ясно графична форма. Ще се обадим на номера г, което влиза в характеристичната функция f, номер на функция f.

Аргумент Функция №	0	1	2	3	4	…
0	1	0	0	1	0
1	1	1	0	1	0
2	1	0	0	1	1
3	0	0	0	1	0
4	0	1	0	1	0

………

В тази таблица в реда с номер пизписани характерна функцияс номер п. Таблицата няма функция, получена от нейния диагонал чрез промяна на 1 на 0 и 0 на 1 (операция на отрицание).

Задача. Докажете, че множеството от реални числа е еквивалентно на множеството от подмножествата на естествения ред.

Програма за изследване на математическата дейност - Хилберт

Обща идея

Дейвид Хилбърт притежава идеята за математиката като област на математически описана дейност, осъзнаването на значението на изследването на математическата дейност чрез самата математика и представянето на програма за такова изследване - програмата Хилбърт.

Програмите на Хилберт за изучаване на математика могат да бъдат представени по следния начин:

• 
  Математиката може да бъде представена като система
  • 
    аксиоми - твърдения, които приемаме за верни и
  • 
    правила за доказване – получаване на нови твърдения.
• 
  Практиката на математическата дейност трябва да ни убеди, че избраната система ни позволява да конструираме всички необходими доказателства. В идеалния случай може да се случи всяко математическо твърдение да бъде доказано или опровергано с помощта на тази система. (Това свойство се нарича завършеност.)
• 
  Някои математически доказателства са „особено стабилни и убедителни“. Те включват напр. аритметични изчисления. Използвайки само тях, можете да се уверите, че избраната система за математика не ви позволява да получите противоречия. (Това свойство се нарича последователност.) Освен това може да се окаже, че пълнотата на математиката може да се докаже и с помощта на прости, разбираеми и убедителни разсъждения.

Полезността на свойството пълнота е ясна. Като правило, когато се опитваме да докажем математическо твърдение, ние едновременно търсим неговото опровержение. Бих искал да съм сигурен, че такава дейност в крайна сметка ще доведе до резултати и е „само“ въпрос на нашите способности и време. Хилберт вярва: „Това е вярата в разрешимостта на всеки математически проблеме голяма помощ за нас в нашата работа; чуваме постоянен призив в себе си: ето го проблемът, потърсете решение. Можете да го намерите чрез чисто мислене; тъй като в математиката няма Игнорабимус!“

Имайте предвид, че свойството последователност е много по-важно. Априори човек може да си представи научна теория, в който противоречието е разположено някъде в периферията и се отнася до някакви маловажни въпроси. Въпреки това, дизайнът на всички основни системи математическо доказателствое такава, че доказуемостта на едно противоречие (например, че произведението на някои две е много големи числаравно на някакво трето и друго четвърто) веднага води до доказуемостта на всяко математическо твърдение. Противоречието не може да бъде „локализирано“.

Първите стъпки към постигане на целите на Програмата Хилберт са направени още преди нейното формулиране. Още повече, че Програмата логично следваше от тях. Това са стъпките.

Доказателство. Логики.В края на 19 век става ясно как да се формализира системата на разсъждение. Тази формализация е завършена в трудовете на Готлоб Фреге (11/8/1848 - 07/26/1925).

Теория на множествата.Друго постижение на математиката в края на 19 век е разбирането, че цялата математика може да бъде представена еднакво по отношение на множества (както се прави в съвременния курсове по математикаи напомнихме по-горе). Това е направено в трудовете на Георг Кантор (3.03.1845 – 6.01.1918).

Така оставаше само изборът подходяща системааксиоми и продължаваме да следваме пътя на доказване на последователност и пълнота. Надеждата за получаване на такива доказателства с прости и надеждни средства беше свързана със следното. Използването на аксиоми и правила за доказателство изглежда доста прост процесработа с формули. Самите формули са прости обекти, вериги от символи. Математиката изглежда като игра, като шаха например. Да предположим, че трябва да докажем, че някаква позиция в шаха е невъзможна. По принцип - това, разбира се, може да стане, като се мине през всякакви игри на шах. Но можете да си представите повече просто разсъждение, въз основа например на факта, че фигурите не се добавят към полето, че епископите са със светло поле и тъмно поле и т.н. Такива разсъждения най-вероятно няма да използват реални числа, интеграли и дори по-сложни математически обекти.

система аксиоми за теория на множестватае построен основно през първите десетилетия на 20 век, като първата формулировка, близка до съвременната, принадлежи на Ернст Цермело (27.7.1871 ‒ 21.5.1953) и е публикувана от него през 1908 г.

Резултати от програмата Хилберт

Какво се случи с програмата Хилбърт по-късно? Сега ще формулираме това накратко, а в следващия курс ще го обясним по-подробно.

От една страна, програмата беше успешно изпълнена:

• 
  Аксиоматичната теория на множествата е основата съвременна математика.
• 
  По-специално, през тридесетте години се формира група от математици под колективния псевдоним Н. Бурбаки. Максимум от него творческа дейностнастъпили през 50-те и 60-те години. Тази група последователно и систематично представи значителна част от съвременната математика, изградена на основата на теорията на множествата.

В същото време Програмата фундаментално се провали:

• 
  Математиката не е пълна и не може да бъде пълна.
• 
  Последователността на математиката не може да бъде установена не само с някакви надеждни убедителни средства.

Това е установено от Kurt Gödel (04/28/1906 – 01/14/1978) през 30-те години на миналия век.

Език и аксиоми на теорията на множествата.аз. Примери

Започваме да формулираме система от доказателства в математиката (теория на множествата) с описание на логическия език.

Логически символи и тяхното значение (семантика)

Булеви стойности: символи I (вярно), L (невярно) или символи 1, 0.Ще обозначим множеството от два символа 0 и 1 като B.

Логически операции:(не, отрицание), (и, връзка), (или, дизюнкция), → (следва, импликация), ≡ (еквивалентност) се прилагат към символите 1 (I) и 0 (A) и резултатът от прилагането им е описани от следната таблица:

А	б	А	AB	AB	А → б	А ≡ б
0	0	1	0	0	1	1
0	1	1	0	1	1	0
1	0	0	0	1	0	0
1	1	0	1	1	1	1

Квантори, с които също, разбира се, сте запознати - х (съществува х ), г (за всякакви г )

Примери за аксиоми за съществуване на множества

Редица аксиоми на теорията на множествата са твърдения за съществуването на множества, включително тези, образувани от други множества.

За да говорим за множества, по-специално, за да формулираме аксиоми, свързани с тях, е необходимо към логическите символи да добавим символи, свързани с теорията на множествата. Как да запиша какво х – празен комплект, тоест множество, което няма елементи? Например така:

г (­ г ∊ х ) (за всички ­ г това не е вярно г принадлежи х )

Имахме нужда от символ за членство ∊. Нека го добавим към азбуката на нашия език.

За да има за какво да говорим, би било добре да сме сигурни в съществуването на поне един комплект. Да започнем с празното (Ø):

х г (­ г ∊ х ) [Аксиома на празното множество.]

Искаме да дефинираме някои специфични множества, свойства на множествата и т.н. Искаме да въведем обозначения за тях.

• 
  Ще считаме празното множество за нула.
• 
  Как да получите следващото числоизмежду п? Добавете към всички елементи пвсе още просто п. Тоест ще разгледаме елементите на следващия пномерира всички елементи от пи повече п. Всички получени елементи образуват набор Н:
  • 
    1 е (0)
  • 
    2 е (0,1)= (0,(0))

Задача. Колко елемента има в числото (множеството) 5? И то в изобилие п?

Съществуването на естествен ред, построен по този начин, се гарантира от следната аксиома. За по-лесно разбиране сме го разделили на части и го коментираме (в квадратни скоби) тези части:

s (u (u ∊ s v (v ∊ u )) [катоsможете да вземете естествената серияН; ще съдържаu - нула]

u (u ∊ s → [ За всякакви неща u от s ]

v (v ∊ s [ще имаv отs , ]

w (w ∊ v ≡ (w ∊ u w = u ))))) [доu ] [ Аксиома на безкрайността ]
Тази аксиома обаче може да бъде изпълнена не само от естествените серии, но и от други множества

Задача. Какъв например?

Задача. Как можем точно да опишем естествените серии, които сме изградили?

IN математически конструкциисе използват операции върху множества. Следвайки вече започнатия път, трябва да добавим аксиоми, които гарантират съществуването на резултатите от тези операции. Ето още един пример:

усв(w(w ∊ v →w ∊ u) ≡ v ∊ s) [Аксиома за степен]

Задача. Проверете дали последната формула смислено означава съществуването на множеството от всички подмножества на всяко дадено множество.

Разбира се, ще ни трябва например набор, който е пресечната точка на две данни и т.н.

По-горе започнахме постепенно да изграждаме комплекти. Ясно е как да продължим този път, например да конструираме набор от цели числа, след това рационални числа, като набор от двойки цели числа с някакво отношение на еквивалентност върху него, след това набор от реални числа и т.н.