Законы логики.

1.закон двойного отрицания:

2.законы идемпотентности:

3.законы коммутативности:

4.законы ассоциативности:

5.законы дистрибутивности:

6.законы поглощения:

7.законы де Моргана:

8.закон исключения импликации:

9.закон исключения эквиваленции:

10.закон контрапозиции:

11.законы исключенного третьего и противоречия:

12.законы нуля и единицы:

 

4.Пусть формула алгебры высказываний содержит только три операции: . Ф-лу F^* будем называть двойственной к ф-ле F, если она получена из F заменой каждой операции на двойственную, а именно: .

Закон двойственности. Пусть F-формула алгебры высказываний, не содержащая операции , , тогда имеет место след равносильность: .

Док-во: проведем используя ММИ по числу операций, входящих в заданную формулу: 1)Проверим, что указанная теорема вып-ся при n=1, т.е. если ф-ла содержит одну операцию: а)пусть ф-ла содержит только отрицание . б) в) вып-ся аналогично. 2)Предположим, что теорема выполнена для ф-л , содержащих не более k операций. 3)Покажем справедливость теоремы в случае, когда кол-во операций n=k+1 и формула F выражается через . Возможны 3 случая: а) . Док-во: а) ( . б) ( . в) ( .

Критерий двойственности. Две формулы титт, когда равносильны двойственные им формулы. Док-во: .Пусть , тогда согласно определению отрицания и понятию равносильности: , след-но, согласно теореме ( и ( и ( ( В последней равносильности переименуем переменные, а именно, заменим на саму переменную, от этого равносильность не изменится, а значит мы получим .

 

 

5.Рассмотрим мн-во М, содержащее конечное число элементов. Пусть М-мн-во особой природы. На указанном мн-ве введем алг унарную операцию «–» и две бинарные операции « » и « ».

Пусть указанные операции обладают след св-вами:

1.закон двойного отрицания:

2.законы идемпотентности:

3.законы коммутативности:

4.законы ассоциативности:

5.законы дистрибутивности:

6.законы поглощения:

7.законы де Моргана:

Мн-во М с введенными операциями, кот облад св-вами 1-7 называют булевой алгеброй.

Будем рассматривать понятие булевой алгебры в широком и узком смысле. В узком смысле понятие ф-ции Буля связано с понятием булевой алгебры.

Булевой ф-цией в узком смысле называют формулу алгебры высказываний, не содержащую операции эквиваленции и импликации.

N-местной булевой ф-цией в широком смысле будем называть n-местнуюф-цию, область определения которой , а мн-во значений также {0;1}.

Всего булевых ф-ций от n переменных .

Согласно комбинаторному правилу умножения булевых функций от 2-х переменных-16=2⁴.

x

y

1`

 

 

6.Пусть -мн-во всевозможных унарных и бинарных связок-их 20. Обозначим через мн-во основных связок. . Обозначим через Ф( )-мн-во формул, содержащих связки из . Ф )-мн-во формул, содержащих связки из .

Мн-во называют ПСС, если любая формула из Ф ) равносильна некоторой формуле из Ф( ): .

Св-ва ПСС: 1)Само мн-во СС явл-ся ПСС, поскольку любая формула из Ф ) равносильна сама с собой.

2)Пусть -ПСС, , то -ПСС. Т.к. -ПСС-любая формула из Ф ) равносильна некоторой формуле из , а значит и формуле из , а значит -ПСС.

3)Пусть ( ) , -ПСС и всякая формула из равносильна некоторой формуле из ,тогда -ПСС. Т.к. -ПСС, то , но любая формула из , а значит и g равносильна некоторой формуле h из , то используя транзитивность отношения равносильности получаем: -ПСС.

Теорема о связке отрицания. Мн-во М, содержащее лишь связку отрицание не явл-ся ПСС. Док-во: докажем методом от противного. Предположим, что М-ПСС. Рассмотрим произвольную формулу .Поэтому никакая тавтология из и никакое противоречие из не может быть равносильно ф-ции из Ф(М), след-но,М-не явл-ся ПСС (противоречие).

 

7. Мн-во называют ПСС, если любая формула из Ф ) равносильна некоторой формуле из Ф( ): .

Теорема о связке отрицания. Мн-во М, содержащее лишь связку отрицание не явл-ся ПСС. Док-во: докажем методом от противного. Предположим, что М-ПСС. Рассмотрим произвольную формулу .Поэтому никакая тавтология из и никакое противоречие из не может быть равносильно ф-ции из Ф(М), след-но,М-не явл-ся ПСС (противоречие).

Теорема. Следующие мн-ва явл-ся ПСС: 1)М₁={ } 2)M₂={ } 3)M₃={ } 4)M₄={ } 5)M₅={ }

Док-во: 1)для док-ва того, что М₁-ПСС достаточно выразить эквиваленцию через связки М₁: M₁-ПСС. 2)Используя 3-е св-во ПСС и то, что M₁-ПСС для док-ва утв2 достаточно выразить импликацию через связки из М₂: М₂-ПСС. 3)т.к. М₂-ПСС, то согласно св-ву3 ПСС выразим дизъюнкцию через связки из М₃: М₃-ПСС. 4)выразим конъюнкцию 5)т.к. М₄-ПСС, то выразим связки из М₅: М₅-ПСС.

 

8.Теорема. Мн-ва {},{ }-ПСС. Док-во: Для док-ва воспользуемся св-вом3 ПСС и тем, что { } и { } также явл-ся ПСС. 1){}-ПСС-? Для док-ва выразим через : 2) ){ }-ПСС-? след из св-во3 ПСС и M₄={ }-ПСС: .

Теорема.(о исключительности одноэлементных связок) Мн-во,содержащее {*} -ПСС . Других одноэлементных ПСС не сущ-ет.

 

9.Алгоритм построения СДНФ на основе построения таблицы истинности.

1.Построим таблицу истинности формулы.

2.Выделим те логические возможности формулы, на которых она принимает значение истина

3.Для выделенных логических возможностей составим истинные ЭК

4.Беря дизъюнкцию ЭК строим СДНФ.

Заметим, что формула и ее СДНФ, построенная по указанному алгоритму будут равносильными, т.к. на выделенных логических возможностях, одна из ЭК, входящих в СДНФ будет истинной, а значит и СДНФ также истинной, как и сама формула. В оставшихся логических возможностях каждая ЭК, входящая в СДНФ будет ложной, а значит ложной будет и СДНФ, как и сама формула.

Алгоритм построения СКНФ на основе таблицы истинности.

1.Построим таблицу истинности формулы.

2.Выделим те логические возможности формулы, на которых она принимает значение ложь

3.Для выделенных логических возможностей составим ложные ЭД

4.Беря конъюнкцию ЭД строим СКНФ.

Заметим, что формула и ее СКНФ, построенная по указанному алгоритму будут равносильными, т.к. на выделенных логических возможностях, одна из ЭД, входящих в СКНФ будет ложной, а значит и СКНФ также ложной, как и сама формула. В оставшихся логических возможностях каждая ЭД, входящая в СКНФ будет истинной, а значит истинной будет и СКНФ, как и сама формула.

 

10.Булевы ф-ции широко применяются приописании работы контактных схем, логических сетей и т.д., при исследовании некоторых электрических цепей, называемых релейно-контактных схем. Под РКС понимается устройство из проводников и двухпозиционных контактов. Контакты РКС могут быть 2-х типов: замыкающие и размыкающие. Каждый контакт подключен к некоторому реле. К одному реле может быть подключено несколько контактов, как замыкающих, так и размыкающих. Каждому реле ставится в соответствие своя булева переменная, которая принимает значение 1, когда реле срабатывает, и принимает значение 0 при отключении реле. На чертеже все замыкающие контакты, подключенные к реле x, обозначаются х, а все размыкающие контакты, подключенные к реле обозначаются . Каждая РКС, в которой занято n независимых реле определяет некоторую булеву ф-цию от n аргументов. Она принимает значение 1, когда данная схема проводит электрический ток. Схема последовательно соединенных контактов х и у проводит электрический ток титт, когда оба контакта х и у замкнуты, т.е. когда обе переменные принимают значение 1 и удовлетворяет условию . Схема, состоящая из 2-х параллельно соединенных контактов проводит электр ток в том и только в том случае, когда по меньшей мере один из контактов замкнут, т.е. когда хотя бы одна из булевых переменных принимает значение 1 и удовл условию . При решении задач используют анализ или синтез РКС: Анализ закл в след, для схемы составляется формула, которая на основании законов логики упрощается и для нее строится новая, более простая схема. Синтез схем заключается в построении схем с заданными электрическими св-вами. На основании заданных электр св-в строится формула алгебры высказываний, а по ней соответствующая схема.

 

11.ЭД от n переменных будем называть Д этих переменных или их отрицаний и обозначать: . ЭК от n переменных будем называть К этих переменных или их отрицаний и обозначать: .

КНФ формулы АВ будем называть равносильную ей формулу, представляющую собой К ЭД. ДНФ формулы АВ будем называть равносильную ей формулу, представляющую собой Д ЭК.

Теорема (о ЭД).ЭД от n переменных тождественно истинна титт, когда она содержит некоторую переменную одновременно с ее отрицанием.

Док-во: ( )докажем теорему методом от противного. Пусть ЭД тождественно истинна, но не содержит никакой переменной одновременно с ее отрицанием. Тогда придадим всем переменным, входящим в запись ЭД без знака отрицания значение 0, а со знаком отрицания значение 1. В рез-те получаем Д нулей, которая ложна. Противоречие. ( )Пусть ЭД содержит переменную одновременно с ее отрицанием, тогда эту ЭД можно, согласно законам ассоц и коммут представить в виде: ЭД

Теорема (о ЭК).ЭК от n переменных тождественно ложна титт, когда она содержит некоторую переменную одновременно с ее отрицанием.

Док-во: ( )докажем теорему методом от противного. Пусть ЭК тождественно ложна, но не содержит никакой переменной одновременно с ее отрицанием. Тогда придадим всем переменным, входящим в запись ЭК без знака отрицания значение 1, а со знаком отрицания значение 0. В рез-те получаем К единиц, которая истинна. Противоречие. ( )Пусть ЭК содержит переменную одновременно с ее отрицанием, тогда эту ЭК можно, согласно законам ассоц и коммут представить в виде: ЭК

 

12.Критерий тождественной истинности. Ф-ла АВ тождественно истинна титт, когда каждая ЭД, входящая в КНФ ф-лы содержит некоторую переменную одновременно с ее отрицанием.

Док-во: Пусть ф-ла АВ

Критерий тождественной ложности. Ф-ла АВ тождественно ложна титт, когда каждая ЭК, входящая в ДНФ ф-лы содержит некоторую переменную одновременно с ее отрицанием.

Док-во: Пусть ф-ла АВ

 

13.СДНФ будем называть ДНФ этой формулы, обладающую св-вами совершенства.

Св-ва совершенства. 1)Любая ЭК, входящая в ДНФ должна содержать все переменные, входящие в запись рассматриваемой формулы. 2)Все ЭК различны. 3)Ни одна из ЭК не содержит некоторой переменной одновременно с ее отрицанием. 4)Ни одна из ЭК не содержит никакую их переменных дважды.

СКНФ формулы будем называть КНФ этой формулы, обладающую св-вами совершенства. Св-ва совершенства для КНФ будут касаться ЭД. Их можно получить из записанных выше заменой фразы ЭК на ЭД.

 

14.Сложение по модулю 2 явл-ся бинарной операцией .

Св-ва операции сравнимости по модулю 2:

1) .

2) .

3)

4)

5) . .

6)

7)

8) .

 

15. -монотонна, если для каждых сравнимых логич возможностей выполняется. .

 

 

16.Полиномом Жегалкина от n переменных наз-ся булева ф-ция след вида:

Всего слагаемых в ПЖ от n переменных будет . Сущ-ет 2алгоритма построения ПЖ, кот основаны на след теореме.

Теорема. Любая булева ф-ция может быть представлена ПЖ и его представление единственно.

1способ получения ПЖ основанный на методе равносильных преобразований для БФ заданных в виде ДНФ:1)Найдем ДНФ формулы, учитывая, что и ; 2)Заменим Д в ДНФ используя закон де Моргана. При этом все отрицания переменных заменяем прибавлением 1; 3)Используем закон дистрибутивности К относительно , раскроем скобки в полученных выражениях, учитывая св-во4. В рез-те получим ф-цию в виде ПЖ.

2способ построения ПЖ основан на табл истинности для Д формы:1)Построим табл истинности для ф-ции; 2)Запишем ПЖ для указанной ф-ции через неопределенные коэф-ты; 3)Подставляя в полученный ПЖ все логические возможности ф-лы поочереди начиная с наименьшей и учитывая, что ф-ла и ПЖ равносильны найдем из полученных ур-й неизвестные коэф-ты.

; ; ; ; .

 

17. -класс линейных функций. БФ от называется линейной, если ее многочлен Жегалкина линеен, т.е имеет вид: . Построим полином Жегалкина для основных функций и выясним, какие из них принадлежат L.

Все аксиоматические теории можно разбить на 2 класса: содержательные и неформальные. В основу и тех и других положен аксиоматический метод, однако в содержательных теориях правила вывода новых утверждений из аксиом не постулируются, в формальных же теориях, правила вывода постулируются. Для построения формально-аксиоматической теории необходимо задать: язык теории, систему аксиом, правила вывода.

1)Язык ИВ. Алфавитом ИВ будем называть конечное мн-во символов-букв латинского алфавита, снабженных, быть может индексами, расширенного символами операций и скобками,т.е. . Формулой ИВ будем называть:1)всякую букву лат алфавита, возможно с индексами;2) если a и b-формулы, то ф-ми также явл-ся ;3)других формул, кроме определенных пунктами 1),2) не существует.

2)Система аксиом ИВ: А1. A2. A3.

3)Правила вывода ИВ.1.правило подстановки заключается в том, что указанная система аксиом в том смысле, что вместо a,b,c, входящих в запись А1,А2,А3 могут быть подставлены любые формулы ИВ. 2.modus ponens указанное правило может записать в виде двуместной ф-ции след вида: .

 

 

18.Т₁-класс БФ, сохраняющих единицу. Если . Т₂-класс БФ, сохраняющих ноль. Если .

-класс самосопряженных (самодвойственных) функций. Если .

.

f			S	L	M
	+	+	+	+	+
	-	-	+	+	-
	+	+	-	-	+
	+	+	-	-	+
	+	-	-	-	-
	+	-	-	+	-
	-	-	-	-	-
	-	-	-	-	-
	-	+	-	+	-
0	-	+	+	+	+
1	+	-	+	+	+

Теорема Поста. Система БФ является полной титт, когда для каждого из 5 введенных классов с системе найдется функция, не принадлежащая какому-либо классу. Иными словами, Система БФ является полной титт, когда в любом столбце таблицы Поста указанной системы стоит хотя бы один минус.

Выводом формулы F длины n будем называть посл-ть формул F₁,F₂,..,F_n, причем последняя формула этой посл-ти явл-ся формулой F.

Формула F наз-ся доказуемой, если сущ-ет вывод, оканчивающийся этой формулой, причем каждая формула вывода явл-ся либо аксиомой, либо получена из них по правилам вывода. Доказуемые формулы будем называть теоремами и обозначать: ├F.

Поскольку в выводе любой теоремы присутствуют аксиомы, поэтому определение доказуемых ф-л можно расширить след образом: ф-ла доказуема, если в ее выводе содержатся либо аксиомы, либо теоремы, либо ф-лы получены из них по правилам вывода.

Заметим, что аксиомы ИВ-это теоремы, длина которых n=1.

Пусть Н={H₁,H₂,..,H_n}-некот мн-во произвольных формул ИВ. Формулу F ИВ будем называть выводимой из мн-ва Н и записывать: Н├F,если сущ-ет вывод, оканчивающийся этой формулой, причем каждая формула вывода явл-ся либо аксиомой, либо теоремой, либо принадлежит мн-ву Н, либо получена из них по правилам вывода. Мн-во Н-мн-во гипотез, F выводима из мн-ва гипотез.

Выводимые из мн-ва гипотез ф-лы не явл-ся теоремами, поскольку в их выводе присутствуют произвольные ф-лы ИВ.

Теорема.(Критерий доказуемости) Формула F ИВ доказуема титт, когда она выводима из пустого мн-ва гипотез. Док-во: ( ) -аксиом или теорем, либо из них по правилам вывода . ( ) -аксиом или теорем, либо из них по правилам вывода .

 

 

19.Под проблемой разрешимости формул АВ понимают проблему отнесения формулы к определенному классу. Говорят, что проблема разрешимости алгоритмически разрешима, если существует алгоритм, позволяющий классифицировать формулы.

Теорема. Проблема разрешимости формул АВ разрешима. Для док-ва приведем алгоритм отнесения формулы к одному из 3-х классов: Алгоритм. 1)найдем КНФ формулы. Используя критерий тождественной истинности определим, явл-ся ли указанная формула тождественно истинной. Если ее КНФ . Если нет, то пункт2. 2)найдем ДНФ формулы. Используя критерий тождественной ложности определим, явл-ся ли формула тождественно ложной. Если ДНФ , если нет, то пункт3. 3)формула выполнима. Алгоритм. Основан на таблице и заключается в том, что в зависимости от вида столбца этой таблицы, отвечающего за значение истинности формулы можно сделать вывод о принадлежности ее к определенному классу, а именно, если этот столбец содержит только 1-тавтология, только 0-противоречие, во всех остальных случаях-формула выполнима-1 и 0.

Вывод формулы ├АА: 1)А1.(а=А, b=A) ├A (A A) 2)A2.(a=b=c=A) ├(A (A A)) ((A A) (A A)) 3)MP(2,3) ├(A A) (A A) 4)A1.(a=A, b=A A) ├A ((A A) A) 5)A2. (a=A, b=A A, c=A) ├(A ((A A) A)) ((A (A A)) (A A)) 6)MP(4,5) ├(A (A A)) (A A) 7)MP(1,6) ├А А.

Свойства выводимости из гипотез:

1) т.е мн-во гипотез можно расширять: Н-мн-во гипотез, W-либо ф-ла ИВ или некоторое мн-во формул, H,W=H W.

2) ,где H,W-мн-во формул, С-некотор ф-ла ИВ, А-некотор ф-ла ИВ. Данное свойство означает, что в выводе ф-лы А можно заменять некоторое мн-во формул одной из которых она выводится. Справедливость данного св-ва следует из определения доказуемых ф-л и выводимых из гипотез.

3) . . Тогда заменим в (1) ф-лу С ее выводом из Н, тогда в рез-те получим А₁,А₂,…,С₁,С₂,…С_m,…А_n=А(2), где (2)-вывод А из Н.

4) . Т.к. из

5) . сущ-ет вывод, оканчивающийся этой формулой В₁,В₂,…,В_n=C . Рассмотрим по св-ву 3 и добавим в него ф-лу С. В₁,В₂,…,В_n=C ,С, но по правилу МР получим, что из .

 

20.Теорема дедукции. H,A├B H├A B. Док-во: H,A├B B₁,B₂,…,B_n=B причем в этом выводе B_i либо аксиомы, либо теоремы, либо принадлежат мн-ву Н, либо получены из них по правилам вывода. Докажем ММИ по длине n вывода справедливость указанной теоремы:1)проверим справедливость при n=1. В этом случае формула может быть ; а) H,A├B₁; б)А1.(а=В₁, b=А)├В₁ (А В₁); в) H,A├А B₁ покажем, что если В₁ совпадает с А, то ,├А А . Т.о., при n=1 теорема вып-ся. 2)предположим, что условие теоремы вып-ся для всех n<k и покажем 3) вып-ся и для n=k. При n=k формула В_k может быть: а)B_n-аксиома или теорема; в)В_k=A; г) В_k по правилу вывода МР В_k получено из С и С₁, кот имеют след вид:С=В_j (j<k),C=B_j .Покажем, что из . Пусть -аксиома. 1)├ ; 2) ├ 3)МР(1,2): ├А . Пусть . 1) ; 2) ├ ; 3) МР(1,2): . Пусть В_k=A т.к.├А А . г)Пусть теперь формула получена из предыдущих по правилу вывода. Поскольку формулы С и С₁ стоят перед , а значит длина их вывода меньше k и для них справедлива данная теорема, а значит выводимой будет формула H├A Си H├A С₁ и поэтому будем использовать их при выводе формул : 1) ; 2) ; 3)А2..(а=А, b= )├( ) ) ; 4)MP(1,4)

 

21.Правило исключения промежуточной посылки (ПИПП): А (В С), В├А С. Рассмотрим мн-во гипотез след вида: Н={ А (В С),В,А}покажем, что ,т.е. А (В С),В,А├С=D, А (В С),В├А С. 1) А (В С) ; 2)В ; 3)А ; 4)МР(3,1) Н├В С;5)МР(2,4) ПИПП спр-во. Сформулируем ПИПП для вывода теорем ИВ: -ПИПП-ПВ.

Правило силлогизма (ПС): А В, В С├А С. Рассмотрим 3формулы:Н={А В, В С,А}, если А В, В С, А├С А В, В С├А С. 1) А В ; 2) В С ; 3)А ; 4)МР(3,1) ; 5)МР(4,2) ПС спр-во. -ПС.

Правило перестановки посылок (ППП): А (В С)├В (А С).Н={ А (В С),В,А}. А (В С),В,А А (В С),В├А А (В С)├В (А С).Строим вывод С: 1) А (В С) ; 2)В ; 3)А ;4)МР(3,1) С; 5)МР(2,4) ППП спр-во. -ППП.

 

22.Закон противоречивой посылки.├ ( В). Н={ ,А}.Покажем, что из : 1) ;2)А ;3)А1. ( ); 4)МР(1,3)├ ; 5)А3. )├ (( ) В); 6)МР(4,5)Н├( ) В; 7)А1.├А ( ); 8)МР(2,7) Н├( ); 9)МР(8,6) . Т.о. ,А├В В ├ ( В).

Закон контрапозиции. а)├ ( ) ( В). б)├(А В) ( ).Рассмотрим а) Н={ ,А}.Треб показать, что . Строим вывод. 1) ; 2)А ; 3)А3.├ ( ) ( ( В); 4)МР(1,3) ; 5)А1.├ ; 6)МР(2,5) ; 7)МР(6,4) .Мы получили ,А├В ( В) ├ ( ) ( В). А, ├В ( ) В )├А (( ) В).

Обобщенное правило противоречивой посылки (ОППП).├( В) (( В) В).Н={( В),( В)}.Треб показать, что . Строим вывод. 1) В ; 2) В ; 3)ЗК б)├(А В) ( ); 4)МР(1,3)Н├ ; 5)А3.├ ( ) ( ( В); 6)МР(4,5)Н├( В;7)ЗК ( ) ( ( ; 8)МР(2,7) Н├ . В, В├В ( В)├( В) ├( В) (( В) В).

 

23.Полнота. Пусть даны две теории Т,Т’, теория Т’ наз полной относительно теории Т, если все доказуемые формулы теории Т’ явл-ся теоремами теории Т. Указанное определение можно переформулировать по-другому, если считать, что Т-АВ, Т’-ИВ. ИВ-явл-ся полной отн-но АВ, если все доказуемые формулы ИВ явл-ся тавтологиями в АВ.

Теорема.(о полноте ИВ) ИВ-полная теория относительно АВ. Используя определение полноты указанную теорему можно сформулировать явно: формула Ив доказуема титт, когда она явл-ся тавтологией в АВ.

Док-во: ( )Пусть формула U доказуема в ИВ. Док-м, что эта формула доказуема в АВ, т.е. U 1 в АВ. Заметим, что любая формула ИВ явл-ся формулой АВ. Кроме того, U-доказуема, это означает, что сущ-ет вывод U₁,U₂,…,U_N=U,причем каждая формула вывода явл-ся либо аксиомой, либо получена из них по правилу МР, но все аксиомы тавтологии в АВ, МР: , но применим МР к тожд истин формула U также дает формулу тождественно истинную U-тавтология в АВ. ( )Пусть V V(x₁,x₂,…,x_n) в АВ, т.к. { , }-ПСС, то с помощью равносильных преобразований преобразуем ф-му V так, чтобы в ней содержались лишь опер , обознач получ ф-лу U: U V U(x₁,x₂,…,x_n); U ИВ. Используя следствие1 из т. О выводимости получаем: x₁’,x₂’,…x_n’├U (*);x₁’,x₂’,…x_n├U (1); x₁’,x₂’,… ├U (2); Согласно ТД (1)и(2)можно преобразовать след образом: x₁’,x₂’,…x_n’├ x_n U(3); x₁’,x₂’,…x_n-1’├ U(4). ОППП (А=х_n, B=U) ├( x_n U) (( U) U)(5). К (3),(5) применим прав МР. МР(3,5): x₁’,x₂’,…x_n-1’├( x_n U) ; MP(4,6): x₁’,x₂’,…x_n-1’├ (7). В рез-те мы избавились от одной гипотезы x_n из (*). Поступая аналогичным образом с оставшимися переменными окончательно получим, что ф-ла n выводима из пуст мн-ва гипотеза, а значит она доказуема.

 

24.Непротиворечивость. Теория Т” наз непротиворечивой, если для любой формулы этой теории не может выполняться одновременно доказуемость ее и ее отрицание. В противном случае теория наз противоречивой, а именно, теория Т’ наз противоречивой.

Теорема (о непротиворечивости). ИВ-непротиворечивая теория. Док-во:от противного. Предположим, что ИВ противоречива, значит найдется такая ф-а и ИВ, для которой будет вып-ся доказуемость U, и в то же время ее отриц: ├U (1); ├ (2). ЗПП(А=U), получим: ├ (3); MP(2,3)├ ; MP(1,4)├B. Т.о. получим, что любая произвольная формула В ИВ доказуема, что не так по т.о полноте ИВ получим противоречие.

Разрешимость. Теория Т’наз разрешимой, если сущ-ет алгоритм, позволяющий отнести любую формулу этой теории к определ классу формул, введенному на ней.

Теорема (о разрешимости).ИВ-разрешимая теория. Док-во:Согласно теории о полноте ф-ла ИВ доказуема титт, когда она тавтология в АВ, но не все формулы ИВ можно разбить на 2 класса:доказуемые и выводимые из Н.Поэтому для классифицир ф-л ИВ необходимо выяснить, явл-ся ли ф-ла тавтологией в АВ, а это можно сделать с помощью таблиц истинности.

 

28. Нуль местной высказывательной формой будем называть высказывание о эл-тах некоторого мн-ва М. (любое высказ-е – нуль-местная форма). Одноместной высказывательной формой будем называть высказывание, содержащее одну переменную о эл-тах неокоторого мн-ва М. n-местной высказывательной формой будем называть высказывание, содержащее n переменных о эл-тах некоторого мн-ва М.

Переменные, входящие в запись высказывательной формы будем называть предметными. Если в высказывательную форму вместо предметных переменных подставить их конкретные значения из мн-ва М, то высказывательная форма обратится в высказывание, которое может быть истинно или ложно. Т.о. на мн-ве М высказывательная форма задает отображение мн-ва М на мн-во {0,1}. Обозначается это отображение буквой Р: P: M {0;1}. Указанное отображение еще называют предикатом.

Т.о. n-местным предикатом, определенным на мн-ве М будем называть отображение М на мн-во {0;1}.

Мн-во М (область определения предиката) еще называют предметной областью, если в n-местном предикате каждая предметная переменная , то предметная область предиката есть декартовое произведение: . В общем случае, для n-местного предиката предм область М есть множество кортежей длины n.

Поскольку предикаты явл-ся отображениями, то для них справедливы все способы задания, что и для ф-ций, а именно: 1)словесный, с помощью высказывательной формы; 2)аналитический, с помощью формул; 3)графический, в случае, если мн-во М-числовое и местность предиката не больше 2-х; 4)табличный, с помощью таблицы истинности предиката, М-конечное, дискретное, местность предиката не превышает 1.

Пусть предикат Р(х) определен на предметной области М (х М).

Областью истинности предиката Р(х) будем называть подмножество предметной области , которое содержит только те значения предметной переменной, при которых Р(х) обращается в истинное высказывание.

n-местный предикат определенный на мн-ве М называется тождественно истинным на рассматриваемой области, если он принимает значение истина при всех значениях предметных переменных, входящих в запись предиката Р и отнесенных к рассматриваемой предметной области М. при этом пишут: .

n-местный предикат будем называть тождественно истинным, если он тождественно истинен на любой области. При этом пишут: .

n-местный предикат определенный на предметной области М называется тождественно ложным на области М, если он принимает значение ложь при всех значениях предметных переменных, входящих в запись предиката Р и отнесенных к рассматриваемой предметной области М. при этом пишут: .

n-местный предикат будем называть тождественно ложным, если он тождественно ложен на любой области. При этом пишут: .

 

29.Логические операции над предикатами. Поскольку предикат обращается в высказывание при подстановке в него вместо предметных переменных их значений из предметной области, то для любого предиката можно определить те же логические операции, что и для высказываний.

Дадим определение этим операциям, считая для простоты, что P(x), Q(x) одноместные предикаты, определенные на предметной области М.

1.Отрицанием предиката P(x) называется новый предикат , определенный на той же предметной области М и принимающий значение истина при тех и только тех значениях предметной переменной х М, при которых Р(х) принимает значение ложь.

2.Конъюнкцией 2-х предикатов P(x) и Q(x) называется новый предикат, обозначаемый P(x) Q(x) и принимающий значение истина при тех и только тех значениях предметной переменной х М, при которых оба предиката принимают значение ложь.

3.Дизъюнкцией 2-х предикатов P(x) и Q(x) называется новый предикат, обозначаемый P(x) Q(x) и принимающий значение ложь при тех и только тех значениях предметной переменной х М, при которых оба предиката принимают значение истина.

4.Импликацией 2-х предикатов P(x) и Q(x) называется новый предикат, обозначаемый P(x) Q(x) и принимающий значение ложь при тех и только тех значениях предметной переменной х М, при которых одновременно Р(х) принимает значение истина, а Q(х) – значение ложь.

5.Эквиваленцией 2-х предикатов P(x) и Q(x) называется новый предикат, обозначаемый P(x) Q(x) и принимающий значение истина при тех и только тех значениях предметной переменной х М, при которых оба предиката принимают одинаковые значения истинности.

Кванторные операции над предикатами.

Пусть P(x) и Q(x) определены на предметной области М. Рассмотрим две операции над предикатами, которые называются кванторными операциями.

1)Операция «навешивания» квантора общности. Квантором общности называется символ -любой, каждый, всякий.

Указанная операция определяется следующим образом: поставим в соответствие одноместному предикату P(x) высказывание , которое будет истинно титт, когда Р(х) тождеств истинен на предметной области М.

2)Операция «навешивания» квантора существования. Квантором существования называется символ -соотв слову существует.

Указанная операция определяется следующим образом: Поставим в соответствие одноместному предикату P(x) высказывание , которое будет ложно титт, когда P(x) тождественно ложен на предметной области М.

 

При навешивании квантора на одноместный предикат его местность уменьшается на единицу.

 

30.Теоремы о областях истинности. Рассмотрим P(x), Q(x), х М.

Т1. . Док-во: Пусть а М, а . Т.о. а

Т2. . Док-во: а М, а .

Т3. . Док-во: а М, а .

Т4. . Док-во: Для док-ва теоремы воспользуемся законами логики, которые очевидно справедливы для предикатов.

Т5. . Док-во: Для док-ва воспользуемся законами логики: .

 

31. Понятие формулы алгебры предиката.

Формулой алгебры предиката называют: 1)любой конкретный или переменный предикат 2)если P(x) и Q(x)-формулы, то формулами также являются: , 3)других формул, кроме 1) и 2) не существует.

Заметим: 1)В записи предиката P(x) и Q(x) в общем случае x=(x₁,…,x_n).

2)В случае n-местных предикатов P(x) и Q(x) запись вида: , : операция «навешивания» квантора может относиться не только к одной переменной, входящей в запись предиката, но квантор общности может быть «навешен» в общем случае на все переменные, входящие в запись предиката.

 

Кроме того, порядок «навешивания» кванторов-произвольный.

3)В случае отсутствия скобок порядок действия в формулах АП:1.кванторные операции(в том порядке, в каком в формуле) 2.логические операции.

Две формулы АП равносильны на предметной области М, если каждый предикат, входящий в запись формулы определен на рассматриваемой области и обе формулы принимают одинаковые значения истинности для любых наборов значений предметных переменных, входящих в запись формулы и рассматриваемой области: .

Если в формулу АП некоторая предметная переменная входит под знаком квантора, то она называется связанной, в противном случае-свободной.

Пусть М-область определения для формулы F(x), где F(x)-формула АП.

Формула F(x) АП называется выполнимой в области М, если существуют значения переменных, входящих в эту формулу и отнесенных к области М, при которых формула F(x) принимает истинные значения.

Формула F(x) АП называется выполнимой, если существует область, на которой эта формула выполнима.

Формула F(x) АП называется тождественно-истинной в области М, если она принимает значение истина для всех значений переменных, входящих в эту формулу и отнесенных к этой области.

Формула F(x) АП называется общезначимой, если она тождественно истина на всякой области.

Формула F(x) АП называется тождественно ложной в области М, если она принимает значение ложь для всех значений переменных, входящих в эту формулу и отнесенных к этой области.

Формула F(x) АП называется тождественно ложной (невыполнимой), если она тождественно ложна на всякой области.

Если результат не зависит от выбора предметной области, то формула является общезначимой.

Все формулы АП можно классифицировать как на предметной области, где они определены, так и вообще на любой предметной области.

Классификация формул на предметной области М: 1)тождественно истинны; 2)тождественно ложные; 3)выполнение. Классификация в широком смысле: 1)общезначимые формулы (тождественно истинные на любой области); 2)противоречие формул (тождественно ложные на любой области); 3) выполнимые.

Проблема разрешимости в узком смысле. Т.Проблема разрешимости формул в узком смысле, а именно, на конечных областях алгоритмически разрешима.

Док-во: поскольку на конечной области инвариантные операции можно представить через логические, то для любой формулы можно составить таблицу истинности, исключив кванторные операции согласно известной теореме. По полученной таблице истинности легко отнести формулу к определенному классу.

Однако ситуация существенно меняется в случае, когда область М-бесконечная. В широком смысле проблема разрешимости формул алгоритмически неразрешима. Т.Проблема разрешимости АП алгоритмически неразрешима.

 

 

32.Кванторные операции как обобщение логических св-в.

Рассмотрим одноместный предикат Р(х), определенный на конечной предметной области М. Пусть множество . Справедливы следующие равносильности: 1) .

Докажем (1), предположим, что . Согласно определению операции навешивания квантора общности , а это означает, что , а из этого следует, что ;

 

Докажем (2): предположим, что , тогда по определению «навешивания» квантора существования:

 

33. Пусть P(x), Q(x), R(x,y), S(x,y); P(x),Q(x)- произвольные предикаты, определенные на произвольных предметных областях. Тогда имеют место следующие равносильности:

3)Правила вынесения квантора-правила де Моргана.

а) ;б)

Док-во: а)Пусть .

б) Пусть .

8)Правила переименования связанной переменной.

а)

б)

9)Правила навешивания связанной переменной

а)

б)

 

 

34.Пусть P(x), Q(x), R(x,y), S(x,y); P(x),Q(x)- произвольные предикаты, определенные на произвольных предметных областях. Тогда имеют место следующие равносильности:

4)Правило вынесения квантора общности за знак конъюнкции.

а) , здесь С-произвольное высказывание, а в общем случае – любой предикат, в запись которого не входит предметная переменная х.

Док-во: Пусть С=0

Пусть С=1

б)

Док-во: Пусть

5)Правило вынесения квантора общности за знак дизъюнкции

, здесь С-произвольное высказывание, а в общем случае – любой предикат, в запись которого не входит предметная переменная х.

Док-во: Пусть С=0

Пусть С=1

6)Правило вынесения квантора существования за знак дизъюнкции

а) , здесь С-произвольное высказывание, а в общем случае – любой предикат, в запись которого не входит предметная переменная х.

Док-во: Пусть С=0

Пусть С=1

б)

Док-во: Пусть

7)Правило вынесения квантора существования за знак конъюнкции

а) , здесь С-произвольное высказывание, а в общем случае – любой предикат, в запись которого не входит предметная переменная х.

Док-во: Пусть С=0

Пусть С=1

 

 

35.Пусть P(x), Q(x), R(x,y), S(x,y); P(x),Q(x)- произвольные предикаты, определенные на произвольных предметных областях. Тогда имеют место следующие равносильности:

1)Расстановка одноименных кванторов.

Док-во следует из определения кванторных операций.

2)Перестановка разноименных кванторов. Разноименные кванторы не коммутируют.

Док-во:(от противного) Пусть перестановка разноименных кванторов коммутивна. Приведем контрпример. Для док-ва этого св-ва предположим противное, т.е., что перестановка разноименных кванторов коммутивна. Приведем пример, опровергающий наше утверждение: ; верно утв.2)

 

36. Приведенные нормальные формы формул АП.

Говорят, что формула АП имеет приведенную нормальную форму, если в ней не содержатся операции импликация и эквиваленция, а отрицание относится лишь к элементарным формулам.

Под элементарными формулами АП понимаем любое конкретное или переменное высказывание.

Т(о приведенной нормальной форме). Всякая формула АП имеет приведенную нормальную форму. Док-во: представим алгоритм получения приведенной нормальной формы для произвольной формулы АП: 1) избавимся от импликации и эквиваленции (согласно законам логики); 2) используя закон де Моргана добьемся того, чтобы отрицание относилось лишь к элементарным частям формулы. Получили приведенную нормальную форму формулы.

 

37. Предваренная нормальная форма. ПНФ формулы АП называется формула следующего вида: , где N-приведенная нормальная форма формулы, не содержащая кванторов.

Т.Всякую формулу АП можно привести к предваренной нормальной форме.

Док-во: будем считать, что формула АП уже имеет вид приведенной нормальной формы. Докажем теорему ММИ по количеству операций, входящих в запись формулы. Проверим справедливость теоремы в случае, когда количество операций n=0, в этом случае мы имеем дело с элементарной формулой, которая имеет вид ПНФ. Предположим, что теорема справедлива для формул, содержащих не более k операций и докажем, что теорема верна на случай n=k+1. Пусть формулы L₁ и L₂ содержат не более k операций, а значит удовлетворяют условию теоремы. Пусть формула L содержит k+1 операцию, а следовательно, в общем случае L может быть выражена через L₁ одним из следующих способов: , т.к. L₁ имеет вид ПНФ согласно нашему предположению.

2) , но для кванторных операций справедливы законы де Моргана. L₁ имеет ПНФ, значит все кванторы уже вынесены, и вынося из-под знака отрицания не наруш структуру получаемой формулы, следовательно, L имеет ПНФ.

3) , где имеет ПНФ. Согласно правилу 8 переименуем связанные переменные в какой-либо части конъюнкции.

 

 

38.Теоремой называют математическое утверждение (высказывание, предикат) истинность которого устанавливается доказательством.

Чаще всего формируются с помощью связки (если то) т.е. в импликативной форме.

Запишем теорему в общем виде: . (1)

P(x) и Q(x) необязательно одинаковые предикаты, они могут являться как n- местными предикатами так и высказываниями. Если назвать теорему вида (1) прямой, то из нее можно получить следующие виды:

(2) – обратная к (1). Заменим в (1) условие и заключение их отрицанием (3) противоположная (1). Поменяем в (3) условие и заключение местами (4) противоположная к обратной.

Согласно закону контропозиции одновременно истинными или одновременно ложными является следствие пары теорем: (1)-(4), (2)-(3).

Если одновременно истинными являются и прямая и обратная теоремы то их объединяют в одну с помощью слов тогда и только тогда или для того чтобы необходимо и достаточно. Такие теоремы называют критериями или признаками.

Рассмотрим как объединить теоремы (1) и (2) в зависимости их истинности.

1. (1)=1

(2)=1 Для того чтобы Р(х) необ. и дост Q(x)

2. (1)=1

(2)=0 Для того чтобы Р(х) необ но неи дост Q(x)

3. (1)=0

(2)=1 Для того чтобы Р(х) достаточно но необ Q(x)

4. (1)=0

(2)=0 Для того чтобы Р(х) не дост и не неоходимо чтобы Q(x).

Метод доказательства теоремы (1) от противного базируется на законе контропозиции а именно на равносильности теорем (1)-(4) суть метода состоит в том что предположим что заключение теоремы (1) неверно. =1 если в процессе дальнейших рассуждений мы приходим к противоречию с условием теоремы (1) то тем самым показываем, что истинным будет его отрицание =1 а значит =1 а по закону контропозиции верна и (1) теорема.

 

39.Р(х) и Q(x) . Составим их импликацию: =1 и выясним как должны быть связаны их области истинности, для того чтобы их импликация была тождественно истинно формулой на М.

 

 

 

Рассмотрим различные ситуации взаимного расположения областей истинности предикатов:

1. .

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

2. .

.

.

3.

, .

4.

 

 

 

 

 

Т.о. имеет место следующая теорема.

Указанная импликация является тождественно истинной формулой на М когда .

Следствие 1. Импликация обратная данной будет истиной когда .

Следствие 2. Обе импликации тождественно истинные тогда и только тогда когда области истинности предикатов Р(х) и Q(x) совпадают.

Если то говорят что предикат Q(x) является следствием (или следует) из предиката Р(х). Предикат Q(x) в этом случае называют необходимым условием, для предиката Р(х). В свою очередь предикат Р(х) называют достаточным условием для предиката Q(x).

Если же тогда Р(х) является логическим следствием Q(x). Таким образом получаем Q(x) является условием предиката Р(х) если оба предиката определены на одной и той же области . Р(х) логическое следствие Q(x), если определены на одной и той же области и .

 

40.Под рассуждениями понимают такие логические действия с помощью которых из одного или нескольких исходных предложении можно получить новое предложение имеющее новое значение.

Исходные предложения учавствующие в рассуждении называют посылками, а новое предложение полученное в процессе рассуждений называют заключением. Посылками будем обозначать малыми: , а заключения Ф. Рассуждения бывают правильными и неправильными.

Правильное – если из истинных посылок нельзя получить ложное заключение. В противном случае неправильное. – правильное рассуждение (1).

Теорема.(критерий правильности рассуждений). .

пусть рассуждение правильно, следовательно , . =1

чтобы говорить о правельных рассуждениях необходимо учесть, сто все посылки =1

Правила с помощью которых из истинных посылок можно получать истинное заключение, называют правилами вывода и обычно записывают: .

Основные правила вывода:

1. докажем что указанное правило приводит к правильному рассуждению используя критерий =1, P(a)=1, Q(a)=1. , так как =1 и Р(а)=1 следовательно =1 и =1

2. Правило отрицания

3. Правило контропозиции

4. Правило силлогизма

 

41.Под алгоритмом понимается последовательность предписаний (действий) строгое изложение которых ведет к решению поставленной задачи.

Признаки:

1. Завершаемость (результативность)

2. Массовость (решает класс однотипных задач)

3. Дискретность (каждый шаг должен быть выполнен)

4. Определенность, детерминированность

5. Элементарность шагов.

Приведенное понятие алгоритма не является строгим поскольку в нем содержаться фразы, строгое математическое определение которых неизвестно. Указанное понятие алгоритма поэтому называют интуитивным. Интуитивность определения алгоритма достаточно в случае когда мы имеем дело с алгоритмически разрешенной проблемой. Поскольку для доказательства того что проблема является разрешимой достаточно предъявить алгоритм ее решения.

Ситуация меняется в случае когда мы имеем дело с алгоритмически неразрешенными проблемами. Для них нужно доказать не существование алгоритма решения а для доказательства не существования алгоритма необходимо иметь строгое определение этого понятия.

Уточнение понятия алгоритма, по 3 основным направлениям:

1. Связано с формолизацией понятия вычислимая функция и построение класса частично рекурсивных функций.

2. Связанно с машинной математикой, а именно в 1937 Тьюрингом и Постом предложены концепции вычислительной машины.

3. Было связано с понятием алгоритма как процесса переработки слов некотором алфавите, результатом стала теория нормальных алгоритмов предложенных марковым в начале 50-х годов.

Вычислимые функции.

Функция f с натуральными аргументами и значениями называется вычислимой, если существует алгоритм А, её вычисляющий, то есть такой алгоритм А, что

• если f(n) определено для некоторого натурального n, то алгоритм А останавливается на входе n и печатает f(n);

• если f(n) не определено, то алгоритм А не останавливается на входе n.

Несколько замечаний по поводу этого определения:

1. Понятие вычислимости определяется здесь для частичных функций (областью определения которых является некоторое подмножество натурального ряда). Например, нигде не определённая функция вычислима (вкачестве А надо взять программу, которая всегда зацикливается).

2. Можно было бы изменить определение, сказав так:
«если /(гг) не определено, то либо алгоритм А не останавливается, либо останавливается, но ничего не печатает».На самом деле от этого ничего бы не изменилось (вместо того, чтобы останавливаться, ничего не напечатав, алгоритм может зацикливаться).

3. Входами и выходами алгоритмов могут быть не только натуральные числа, но и двоичные строки (слова в алфавите {0,1}), пары натуральных чисел, конечные последовательности слов и вообще любые, как говорят, «конструктивные объекты». Поэтому аналогичным образом можно определить понятие, скажем, вычислимой функции с двумя натуральными аргументами, значениями которой являются рациональные числа.

 

42. Частично числовой функцией от n –переменных ,будем называть n-местную функцию, область определения которой , – облать значения.

n- местной числовой фунцией будем называть функцию n-переменных область , а область значения .

Любой алгоритм можно представить как задачу отыскания значений некоторой частично числовой функцией. Частично числовая функция называется вычислимой если существует алгоритм позволяющий вычислить ее значение на области определения функции и работающий вечно в противном случае.

Построим формальную теория вычислимых функций. Для этого зададим аксиомы или элементарные функции которые вычислимы, а затем приведем правило вывода или правило плучения вычислимых функций из элементарных.

Аксиомы и их простейшие ф-ии:

1. 0(х)=0, (оператор окупирования)

2. Функция следования , .

3. Проектирующая функция .

Основные операторы теории вычислимости.

1. Суперпозиции. , говорят что n – местная функция h получена из указанных функций с помощью оператора суперпозиции если выполнено следущее равенство (1). Если функции и функция g будут вычислимы то и функция h такжк будет вычислима.

Действительно алгоритм ее вычисления на наборе следующий:

1. – вычислимы

2. следовательно h- вычислима.

Ex: выяснить какие функции можно получить из простейших используя оператор суперпозиции.

 

 

 

 

 

 

 

 

 

Любая константа выислима и функция вида х+n вычислима.

 

 

43. Пусть заданы функции n- местные и n+2 местная . Говорят что n+1 местная функция может быть полученна из функции g и h с помощью оператора примитивной рекурсии, если имеют место след:

 

 

(2) – схема примитивно рекурсии

……………………………………………..

 

Если функции g и h вычислимы то f вычислима причем вычисляется значение по схеме (2).

В случае если функция f одноместная то схема примитивной рекурсии выглядит так:

 

 

(3)

………………………

 

 

Ex: Покажем что следующие функции могут быть вычислимы с помощью оператора примитивной рекурсии.

1.

 

 

 

 

 

………………………………………………………………..

 

 

Показали, что является вычислимой, поскольку она получена с помощью оператора примитивной рекурсии из вычислимой функции.

2.

 

 

 

 

 

………………………………………………………………..

 

следовательно получили, так как суммирующая вычислима то и h – вычислима, g(x) –вычислима то и – вычислима.

Ex: Какая из функций может быть получена из g и h с помощью оператора примитивной рекурсии.

1.

 

 

 

 

………………………………………………………………..

 

2.

 

 

 

 

………………………………………………………………..

 

 

44. - оператор наименьшего числа.

Пусть дана функция двух переменных зафиксируем переменную х и выясним при каком наименьшим у данная функция обратима в 0. Очевидно что результат зависит от х . . Поэтому нахождение наименьшего у при приведенных условиях называют действием - оператора по переменной у на функцию .

Покажем на примере что если то и функция - вычислима.

Покажем что с помощью - оператора можно получить: , а именно .

 

 

z=0:

z=1:

z=2:

…………………………

z=5:

 

В результате действий - оператора возможны следующие ситуации:

1. Перебирая все возможные значения переменной у начиная с 0 мы найдем то значение при котором в этом случае говорят, что определена и равна найденному наименьшему у.

2. - оператор не применим к функции это возможно если ни при каком у , либо если в результате перебора значений у получим такое значение при котором f неопределенна.

Если функция может быть получена из простейших с помощью операторов суперпозиции и примитивной рекурсии (применим конечное число раз) то такую функцию будем называть примитивно рекурсивной.

Если функция может быть получена из простейших функций с помощью операторов суперпозиции, примитивной рекурсии и минимизации (применим операторы применены конечное число раз) то такую функцию будем называть частично рекурсивной.

 

45. Машина Тьюринга – абстрактная математическая машина представляющая собой тройку множеств <А, Q, Р> где А- внешний алфавит машины содержащий конечное число символов , Q –множество содержащее конечное число символов – внутренний алфавит машины , Р – программа .

Программа задается в виде системы команд каждая из которых имеет один из следующих видов:

(1), (2), (3). R,L символы сдвига соответственно влево и вправо, которые можно отнести к элементам внутреннего алфавита Q.

Рассмотрим элементы стандартной модели машины Тьюринга считая, что она заданна определенной тройкой A, Q, P.

1. Бесконечная лента- внешняя память машины она разбита на ячейки при этом в каждой ячейке может быть записан один из символов внешнего алфавита А.

2. Через элементы внешнего алфавита кодируется та информация которая подается на ленту, причем во внешнем алфавите имеются случайные символы. К этим символам относится а₀ – пустой символ.

Словом в алфавите А будем называть конечный упорядоченный набор элементов этого алфавита. Алфавит А относится к внешней памяти машины.

3. Внутренняя память машины которая определяется через алфавит Q и символы сдвига.

Алфавит Q описывает внутреннее состояние машины Тьюринга. Среди всех внутренних состояний имеются 2 следующих: стоп состояние и начальное

4. Управляющая головка. С ее помощью происходит процесс преобразования слов записанных на ленте машины Тьюринга. Управляющая головка обозревать в конкретный момент времени только 1 ячейку и менять содержимое ячейки. Кроме того переводить машину в другое внутреннее состояние. Также управляющая головка может двигаться вправо или влево согласно команде машины Тьюринга которая выполняется в данный момент времени. Управляющая головка может достраивать на ленте ячейки в пустом состаянии.

5. Программа состоит из команд вида 1-3 которые означают следующее. Команда вида (1) – если находясь во внутренним состоянии управляющая головка обозревает ячейку ленты в которой записан элемент то машина Тьюринга меняет внутреннее состояние на и заменяет в обозреваемой ячейки на элемент .

Команда (2) - в начале производится действие так же как и в команде (1) после чего управляющая головка сдвигается вправо на 1 ячейку ленты.

Команда (3) – в начале производится команда (1) и (2) …влево на 1 ячейку ленты.

6. Механическое устройство – с помощью которого управляющая головка движется вдоль ленты и преобразовывая содержимое ячеек.

Замечание. Если машина Тьюринга попала в стоп состояние то всякие преобразования слов на ленте прекращаются.

Машинным словом или конфигурацией машины Тьюринга будем называть где D и В слова в алфавите А - внутр. алфавита, - внешнего.

Машинное слово определяет состояние машины в конкретный момент времени.

Работой машины тьюринга называется пошаговый переход от первого машинного слова к другому. Этот переход еще называют тактом работы машины тьюринга. Переход от одного машинного слова к другому переходит согласно программе данной машины тьюринга.

 

46. Третье направление в уточнении понятия алгоритма явилось обобщением понятия ассоциативное исчисление и основывается на процессе переработки слов в некотором алфавите согласно некоторым правилам которые называют подстановками.

Алфавитом - конечное множество символов. Пусть - некоторое множество тогда расширение алфавита . Символом в алфавите - называется конечная упорядоченная последовательность букв из расширения .

Пусть слово и – тогда объединением . Относительно операции объединения слов существует нейтральный элемент – пустое слово так что .

Рассмотрим слово АВС в нем В называется подсловом рассматриваемого слова в качестве правила переработки слов в алгоритмах Маркова рассмотрим понятие подстановки которое обозначается (1) где В и Р некоторое слово а алфавите Х. Запись (1) означает что в слове подслово В должно быть заменено на Р.

Марковские подстановки бывают двух видов:

1. Простые (2)

2. Заключительные (3)

Если на шаге переработки слов, подставим на заключительную подстановку (3) то процесс заканчивается.

Алгоритмом Маркова (нормальным алгоритмом) называют упорядоченную систему марковых подстановок:

 

(4)

…………

 

– cлова в алфавите Х. опишем процесс преобразования слова основанный на (4).

, где В первое слово вхождения в слово М. Пусть дано некоторое слово М (4) применяется следующим образом: вначале ищется первое левое вхождение слова М если таковое имеется то в слово . Если же вхождение в слове М нет то применяем к слову М следующую подстановку из списка если это возможно.

Предположим, что в результате получим слово и к нему слово (4) начиная с первой до тех пор пока не приведем к заключительной подстановке.

В случае попадания на заключительную подстановку процесс преобразования слов завершается и полученное будет являться результатом работы алгоритма маркова.

При использовании (4) возможна ситуация когда ни одна из подстановок (4) не может применена к слову М. В этом случае система не применима а М.

Если процесс преобразования слов согласно (4) никогда не завершается то в этом случае также говорят, что (4) не применима к начальному слову М.

Ex:

1.

 

 

 

 

47.Если функция может быть получена из простейших с помощью операторов суперпозиции и примитивной рекурсии (применим конечное число раз) то такую функцию будем называть примитивно рекурсивной.

Если функция может быть получена из простейших функций с помощью операторов суперпозиции, примитивной рекурсии и минимизации (применим операторы применены конечное число раз) то такую функцию будем называть частично рекурсивной.

Чаще всего в качестве: Х={0,1}. Предположим что в слове начальное слово будет иметь вид . Для n-местной функции: n-местная частично числовая функция называется нормально вычислимой если существует такой алфавит Х и его расширение что всякое начальное слово заключенное с помощью указанных алфавитов будет переработано с помощью алгоритма маркова вида (4) в заключительное слово записанное а алфавите в случае если начальное слово из области определения функции и указанный алгоритм не будет пременим к словам не из области определения указанной функции. Другими словами функция нормально вычислима если существует алгоритм Маркова с помощью которого может быть вычислено значение функции на области ее определения и работающий вечно в противном случае.

Ех:

 

 

 

 

Тезис Черча.

Класс всех частично числовых вычислимых функций совпадает с классом частично рекурсивных функций.

Тезис Тьюринга.

Введено понятие абстрактной математической машины был выдвинут тезис названный его чменим. «Класс частично числовых вычислимых функций совпадает с классом функций выводимых из гипотез».

Теорема Тьюринга.

Функция вычислима по Тьюрингу тогда и только тогда когда она частична рекурсивна.