Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции по математической логике - файл Матлог_лекции.doc


Лекции по математической логике
скачать (152.7 kb.)

Доступные файлы (1):

Матлог_лекции.doc714kb.19.01.2006 20:31скачать

содержание

Матлог_лекции.doc

  1   2   3   4
Самарский Государственный
Аэрокосмический Университет


Лекции по математической логике





Лектор: Тишин В. В.

Напечатал: Студент СГАУ 6 факультета, гр № 622

Соловьёв Илья


Самара 2006

Теория множеств 3

Основные понятия 3

Способы задания множеств 3

Декартово произведение и векторы 4

Соответствия 5

Отношения 8

Разбиения 9

Факторизация отображения 9

Отношения порядка 9

Теория алгоритмов. 11

Понятие алгоритма. 11

Машина Тьюринга. 11

Числовая функция 12

Кодировка машин Тьюринга. 12

Алгоритмически неразрешимые проблемы. 12

Проблема применимости. 13

Нормальные алгоритмы Маркова 13

Рекурсивные функции. 14

Операция минимизации. 15

Предикаты 16

Основные понятия 16

Операции над предикатами 16

Предикатные формулы. 18

К – значные логики 19

Основные понятия 19

Функции k-значной логики. 19

Законы Моргана: 20

Формальные теории 22

Основные понятия 22

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

Классическое исчисление высказываний 22
^

Теория множеств

Основные понятия


Запись означает, что элемент a принадлежит множеству А. Запись означает, что b не является элементом множества А.

Если множество не содержит элементов, то оно называется пустым и обозначается символом Ø.

Примеры множеств:

N = {1, 2, 3…} – множество натуральных чисел;

N0 = {0, 1, 2, 3…} – множество натуральных чисел и ноль;

Z = {-2, -1, 0, 1, 2…} - множество целых чисел;

Q = { - несократимая дробь, где } – множество рациональных чисел;

R – множество действительных чисел (кроме числа 0,999…, запись которого запрещена);

I – множество иррациональных чисел;

C – множество комплексных чисел;

Множество конечно, если существует такое , которое равно количеству элементов множества. Число элементов множества - мощность множества, обозначается |A|=k.

Если для любого можно найти k различных элементов из множества В, то В – бесконечное множество:

Запись означает: множество А включено во множество В, т.е. каждый элемент множества А является элементом множества В (обратное неверно). Таким образом, если . В этом случае А – подмножество, В - надмножество.

Для любого множества А выполняется: .

Теорема (о транзитивности включений):

то .

Док-во:

Для любого x, , если , то . А т.к. , то . Значит, по определению включения . ч.т.д.

Если , то - множество А строго включено во множество В. Если и , то А – собственное подмножество В.

Если и .

Пример: Пусть А={1}; B={{1},2}; C={{{1},2},3}. Тогда запись , неверна, т.е. принадлежность не обладает свойством транзитивности.
^

Способы задания множеств


  1. Перечисление: A={a,b,c}; B={1,2,3,...,100} (повтора элементов быть не должно)

  2. Порождающая процедура – алгоритм получения элементов множества из элементов другого (заранее известного) или получение элементов множества из элементов этого же множества, полученных ранее: .

  3. ^ Распознающая процедура – алгоритм который для любого элемента а определяет принадлежность его множеству А: Ае={271, 828,182,845,…} – знаки числа e.




  1. АВ = {х | хÎA или хÎВ} – объединение:



  1. А∩В ={х | xÎA и хÎВ} – пересечение:




  1. А\В ={x | xÎA и xÏB} – разность:



    1. А Δ В=(A\B)È(B\A) – симметрическая разность:



  1. Ā = {x | xU\A } – дополнение, где U – универсальное множество:



Второе определение разности: А Δ В=(AÈB) \ (A  B).

Докажем равенство: (A\B)È(B\A)=(AÈB) \ (A B).

Док-во: Пусть А={1, 2}; B={2, 3}. Тогда (AÈB)\(AB) ={1, 2, 3}\{2}={1, 3}, а (A\B)È(B\A)={1}È{3}={1, 3}. ч.т.д.

Опр: Множества А и В находятся в общем положении, если:

  1. существует такое а, что аÎА, но а ÏВ;

  2. существует такое b, что bÎB, но b ÏA;

  3. существует такое c, что c ÎА и c ÎВ.

Теорема (о четырех возможных): для любых множеств А и В справедливо хотя бы одно из четырех возможных утверждений:

1.AÍB;

2.BÍA;

3.AB=Æ;

4.A∞B.

Док-во: Допустим, что есть пара множеств, для которых ни одно из вышеперечисленных утверждений не выполняется:

  1. AB => существует такое a, что aÎA и aÏB;

  2. BA => существует такое b, что bÎB и bÏA;

  3. AB≠Æ => существует такое с, что сÎA и cÎB;

  4. .

Т.о. получаем противоречие, т.к. из 1,2,3 следует, что A∞B. ч.т.д.

    1. класс множеств (класс А): А={X | XÎX};

    2. класс множеств (класс B): B={X | XÏX}.

В результате получаем парадокс:

B Î (I) => BÎB => BÏB;

B Î (II) => BÎB => BÏB.

^

Декартово произведение и векторы


Вектор (кортеж) – упорядоченный набор элементов.

Пусть вектор α=(a1, a2,... an). аi – координаты (компоненты) вектора; n – размерность вектора

Пусть вектор =(b1,b2,.., bn). Тогда α=, если .

^ Опр: АВ={(a,b) | aÎAn, bÎBn } – декартово произведение множеств.

Пример1: А={a}; B={1, 2}; AB{(a,1),(a,2)}; BA={(1,a),(2,a)} => ABBA.

Пример2: А={a,b}; AA={(a,a),(a,b),(b,a),(b,b)}

Пример3: Доказать: А (ВС)=(АВ) С.

Док-во: Пусть A=B=C, тогда А(АА)=(АА)А. Пусть (АА)=D. Тогда АD=DА - противоречие. Следовательно А(ВС)(АВ)С.

Декартово произведение: AB={(x,y)| xA и yB}

A1A2 A3…An={(a1,a2…an)| "i aiAi}

Теорема (о мощности декартова произведения конечных множеств): мощность декартова произведения множеств равна произведению мощностей этих множеств.

Пусть |A1|= m1, |A2|= m2,...|An|=mn, тогда | A1 A2... An |= m1*...*mn (1);

Док-во:

  1. Проверка при n=1: |A1| = m1 верно;

  2. Допустим | A1...Ak|= m1* m2*...* mk;

  3. Докажем для n=k+1: |A1A2...Ak+1|= m1*m2*...*mk+1; (x1,..., xk, ak+1) Для каждой фиксированной координаты ak+1 количество различных векторов такого вида равно (по допущению) m1*...*mk. Но фиксированная координата ak+1 может принимать mk+1 значений. На основе метода мат. индукции утверждаем, что теорема справедлива для любого n.



Проекция вектора на ось. Проекция множества на ось

Проекция вектора α=(a1, a2,... an) на ось i прiа=аi.

Проекция множества на А={ α | α=(a1, a2,... an)} прiA={прiа=α}.

Пара – вектор, размерности 2. Графиком назовем множество, элементом которого являются пары.


Действия над графиками

  1. Инверсия графика Р: P-1 ={(y,x)| (x,y)ÎP};

  2. Композиция (суперпозиция) графика: PºQ={(x,y) | $a : (x,a)ÎP и (a,y)ÎQ }

Пример:

Пусть Р={(a,1),(b,2)}; Q={(1,α),(3,β)}.

Тогда Q-1={( α ,1),(β,3)}; PºQ={a, α }: (a,1) Î P, (1, β) Î Q.

Но QºP=Ø. Таким образом, композиция не подчиняется коммутативному закону.

^ Свойства операций над графиками:

  • Двойная инверсия: (P-1)-1=P.

Док-во: (x,y)Î(P-1)-1  (y,x)ÎP-1  (x,y)ÎP

  • Связь композиции и инверсии: (PºQ)-1=Q-1 º P-1.

Док-во: (x,y)Î(PºQ)-1  (y,x)ÎPºQ  a : (y, a)ÎP и (a, x)ÎQ  a : (x, a)ÎQ-1 и (a, y)ÎP-1  (x,y)ÎQ-1 º P-1.

  • Ассоциативность композиции (PºQ) ºT=Pº(Q ºT).

Док-во: (x,y)ÎPº(QºT)  a : (x,a)ÎP и (a,y)ÎQºT  a : b : (x,a)ÎP и (a,b)ÎQ и (b,y)ÎT  b: (x,b)ÎPºQ и (b,y)ÎT  (x,y)Î(PºQ) ºT.

Соответствия


Соответствием Г назовем тройку множеств X,Y,G, где Х – область отправления соответствия, У – область прибытия соответствия, G – график некоторого подмножества декартова произведения XY (график соответствия).

Г=(X,У,G), где GÍ(XY)

Область определения G – пр1G. Область значений G – пр2G. Если (x,y) ÎG, то y – образ элемента x, а x – прообраз элемента y при данном соответствии G.

Если АÍX => Г(А) = {y | (x,y)ÎG, xÎA};

Если BÍY => Г-1(B) = {x | (x,y)ÎG, yÎB}.

Пример: Г=({1,2,3},{a,b,c,d},{(1,a), (1,b), (2,c)}). Пусть А={1} => Г(А)={a,b}. B={a,b,c,d} =>

=> Г-1(B) = {1,2}. Пр1G={1,2}; пр2G={a,b,c}.

Основные свойства соответствия:

  1. Соответствие всюду определено, если его область определения совпадает с областью прибытия.

  2. Соответствие сюръективно, если пр2G=У.

  3. Соответствие функционально, если каждый элемент из X имеет не более одного образа: если(x,y1) ÎG и (x,y2) ÎG, то y1=y2.

  4. Инъективность: если график соответствия не содержит пар с различными первыми и одинаковыми вторыми координатами: если (x1,y) ÎG и (x2,y) ÎG, то x1=x2.

  • Соотв. называется отображением X в У , если соотв. обладает свойствами 1,3.

  • Соотв. называется отображением X на Y (свойства 1,2,3)

  • Соотв. называется взаимнооднозначным, если оно обладает свойствами 3,4.

  • Соотв. называется биекцией, если оно обладает свойствами 1-4.

Пример:

Пусть Х – все жители земли. У – все женщины. Определим соответствие: y мать х. Это соответствие обладает свойствами: .

Если между множествами А и В можно установить биекцию, то пишут А~В. Для бесконечных множеств: |А|=|В|  А~В.

Теорема (о равномощных конечных множествах): конечные множества равномощны тогда и только тогда, когда между ними можно установить биекцию: A~B  |A|=|B|.

Док–во:

  1. Необходимость.

Пусть |A|=|B|. Докажем, что A~B.

A={a1,a2,…,an}

↕ ↕ ↕

B={b1,b2,…,bn}

Таким образом, для всех i, каждому ai ставится в соответствие bi. Очевидно, что все 4 свойства выполняются, то есть это – биекция.

  1. Достаточность.

Пусть A~B. Докажем, что |A|=|B|; Допустим A~B, но |A||B|, тогда A={a1,a2,…,an}, B={b1,b2,…,bk}. При k<n нарушается либо всюду определённость, либо инъективность, при k>n нарушается либо сюръективность, либо функциональность, это значит, что если A~B, то |A|=|B|. ч.т.д.

Опр: Если дано множество А, то через Р(А) обозначается множество всех его подмножеств.

Теорема (о количестве различных подмножеств конечного множества):

Если |A|=n  |P(A)| = 2n.

Док–во: Пусть A={a1,a2,…,an} и пусть A*A поставим в соответствие еA*=(e1,e2,..en), где . Очевидно, что таким образом задается множество всех подмножеств и множество всех двоичных наборов размерности n. Но количество всех двоичных наборов размерности n равно 2n. Следовательно |P(A)|=2n (по теореме о равномощных конечных множествах). ч.т.д.

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

^ Опр: Множество называется счётным, если оно равномощно множеству натуральных чисел: множество А счетно, если A~N.

Теорема (о счётном подмножестве бесконечного множества): любое бесконечное множество содержит счетное подмножество (Если множество А – бесконечно, то существует такое А*, что А*А, и А*~N).

Докво:

a1A;

a2А\{a1};

a3А\{a1, a2};



anА\{a1, a2,…, an–1}.

Если этот процесс прервётся, то множество А – конечно => противоречие. Т.о. А*={a1, a2,…, an,…}, где каждый элемент получит свой номер  A*A, A*~N. ч.т.д.

Теорема (критерий бесконечности множества): множество А бесконечно тогда и только тогда, когда оно равномощно некоторому своему подмножеству, т.е А – бесконечно  А*: А*А и А*~A.

Док-во:

  1. Достаточность.

Пусть множество А–конечно, |A|=n, A*A. Если A*A, то |A*|<n – противоречие.

  1. Необходимость.

Пусть А – бесконечно. Тогда существует такое M, что MA и M~N.

M={a1, a2,…, an,…}=>A=(A\M)M (1);

M*={a2, a4,…, a2n,…}=>A*=(A\M)M* (2); A*A, т.к. a2n+1А*.

А~А*, потому что между одинаковыми частями (A\M) биекцию задаёт тождественное равенство, а М~М* в силу их счетности. ч.т.д.

Теорема (о счётности множества рациональных чисел): множество рациональных чисел счетно: Q~N, где Q={p/q | pZ, qN; p/q – несократимая дробь}.




Док-во:


Зададим маршрут обхода, двигаясь по которому, будем присваивать номера всем дробям. Очевидно, что каждое число встретится в этой таблице и получит свой порядковый номер, т.о. данная конструкция установила биекцию Q~N. ч.т.д.

Теорема Кантора: множество действительных чисел интервала (0,1) несчётно.

Док–во: Пусть это множество счётно.

Число α:

α1=0, a11 a12 a13 …a1n

α2=0, a21 a22 a23 …a2n



αn=0, an1 an2 an3 …ann…, где aij–цифры от 0 до 9. Значит, мы пронумеровали все числа.

Возьмем число β:

b1a11, b19; b2a22, b29,…,bnann, bn9 =>

β=0, b1 b2 … bn … – действительное число, но оно не было подсчитано нами в 1-м случае. Следовательно множество действительных чисел интервала (0,1) несчётно. ч.т.д.

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

^ Пример: Пусть В, С – бесконечные множества. Тогда если |B|>|C| то между В и С нельзя установить биекцию. То есть, если В*В, то В~C.

Опр. |A|>|B|  A не~ B и A*A : A*~B

Теорема (о мощности множества всех подмножеств бесконечного множества): мощность множества всех подмножеств бесконечного множества строго больше мощности самого множества: |P(А)|>|А|.

Док–во:

А*={{a}|aА} – подмножество одноэлементных множеств; очевидно, что А*P(А)



A = { a |aA}, следовательно A*~A;

Допустим, что A~P(A) => b↔B, c↔C;

Возможно, некоторые элементы попали в соответствующие им подмножества, а некоторые нет.

Y={x | xX, x↔X}, YP(A), т.к. составлен из элементов множества P(A);

Y↔y

Допустим, что yY и y↔Y  yY

Допустим, что yY и y↔Y  yY. Противоречие. Ч.т.д.

Для любого множества можно построить более мощное множество всех его подмножеств.

Отношения


Пусть дано множество А. Если вектор (a1, a2,... an) Î G, то говорят, что элементы, составляющие его, вступают в n – местно отношение Ф. Ф=(А,G), причем GÍАn.

  1. Если n=1, то отношение называется свойством.

  2. Если n=2, то отношение называется бинарным.

Диагональю множества A2 называется график A={(x,x)|xA}.

Операции :

Пусть даны Ф=(А,G) и Ψ=(А,F) =>

если (x,y) G  xφy;

ФÈΨ=(A,GÈF);

не Ф=(A,A2\G);

Ф-1=(A,G-1);

ФΨ=(A,GF);

Ф\Ψ=(A,G\F);

ФΨ=(A,GF).

Свойства отношений:

  1. Рефлексивность. xÎА (xφx) или A2G – все точки диагонали включены в график ;

  2. Антирефлексивность xÎА не (xφx) или AG= -диагональ не принадлежит графику ;

  3. Симметричность xÎА"yА(xφyyφx) или G=G-1 – симметрично относительно диагонали ;

  4. Антисимметричность. xÎА"yА (xφy и yφxx=y) или xÎА"yА (xφy и xy  не(yx)) или GG-1 DA – нет точек, симметричных относительно главной диагонали:

;

  1. Транзитивность xÎА"yАzА(xφy и yφz xφz) или GGG

;

  1. Связность "xÎА"yÎА(x≠y => xφy или yφx) или A2\DAGG-1:



    • Отношение называется частичного порядка, если выполняются свойства 1,4,5;

    • Отношение называется строгого порядка, если выполняются свойства 2,4,5;

    • Отношение называется строго линейного порядка, если выполняются 2,4,5,6;

    • Отношение называется отношение эквивалентности, если выполняются 1,3,5.

Пример:

Пусть дано отношение xφy ↔ x тёща y:


Доказать: утверждение «если выполняются свойства 3, 5, то выполняется 1» - ложно.

Док-во:

Пример, когда отношение на множестве А={a,b,c} обладает свойствами :


Разбиения


Пусть дано множество А. Разбиением этого множества называется система непустых попарно непересекающихся множеств m={{Ai}| Ai0, ik→AiAk=, Ai=A}, в объединении дающих множество А. Отношение называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Теорема (о разбиении отношения эквивалентности): Каждое разбиение множества порождает на нем отношение эквивалентности.

Док–во:

Пусть имеется множество А и m. Введём отношение Фm=xφmy  найдётся k : xAk и yAk. Тогда это отношение является отношением эквивалентности.

  1. Рефлексивно: x mx – очевидно, т.к. при разбиении x попал в один класс сам с собой;

  1. Симметрично: x,ymy→yφmx ;

  1. Транзитивно: xyzmy и yφmz→xφmz – так как множества Ai и Ak не пересекаются.

ч.т.д.

Фm - отношение, порождённое разбиением m; оно является отношением эквивалентности.

Фактор-множество – множество классов эквивалентности.

Теорема (о порождении отношением эквивалентности разбиения множества): Каждое отношение эквивалентности, заданное на множестве A, порождает разбиение этого множества.

Пусть имеется множество А и отношение эквивалентности Ф, заданное на этом множестве.

Док-во: Пусть [a]=a/φ={x | xφa}, [b]=… Продолжаем, пока один эл­емент не попадёт в один и тот же класс. m={[a]|aA} – фактор – множество

    1. a[a]  [a]0;

    2. [a][b]. Пусть [a][b]0, тогда с[a] и c[b] → cφa и cφb (из симметричности cφaaφc) → aφc и сφb (из транзитивности получаем ab) → b[a] противоречие, разные классы не имеют общих элемен­тов. ч.т.д.

Индекс разбиения – мощность фактор-множества.
^

Факторизация отображения


Пусть f – отображение X в Y, если х1φх2  f(х1)=f(х2); Это отношение эквивалентности, которое порождает разбиение множества X:

  1. из рефлексивности: "x1 х1φх1 f(х1)= f(х1);

  2. из симметричности: "x1x2 f(х1)=f(х2)  f(х2)=f(х1);

  3. из транзитивности "x1x2x3 f(х1)=f(х2) и f(х2)=f(х3)  f(х1)=f(х3); x/φ – факториальное множество.

g является отображением x на x/; g – соответствие, ставящее в соответствие каждому х в соответствие класс. Соответствие h: x/f(x) обладает свойствами 1,2,3,4, т.о. h – биекция. Обозначим e(y)=y – вложение, где e является отображением f(x) на Y. Взаимнооднозначное отображение f=ghe.

Пример:

Пусть X={a,b,c}; Y={1,2,3,4}; f(a)=f(c)=1; f(b)=3. X/={{a,c},{b}}.

g(a)=g(c)={a,c}; g(b)={b};

h({a,c})=1;

h({b})=3;

f(x)={1,3};

e(1)=1; e(3)=3.
^

Отношения порядка


Отношение порядка – это отношение, обладающие свойствами антисимметричности и транзитивности.

Отношение частичного порядка – это отношение, обладающие свойствами рефлексивности, антисимметричности и транзитивности; обозначается символом “”. Выражение ab обозначает, что a предшествует b или a минорирует b. ABAB

1. A: AA;

4. "AB: если AB и BA, то A=B;

5. "A B C: если AB и BC, то AC.

Пример:

Пусть xy  х делится на у, причем х, уN. Тогда:

  1. х: хх;

  1. х,у: ху, ух =>x=y;

  2. х,у,z: ху, уz =>xz.

Множество с введённым на нем отношением частичного порядка называется частично упорядоченным множеством (ЧУМ). Элемент О называется наименьшим элементом ЧУМ если ОА,xA Ox, т.е. он предшествует всем остальным элементам. Наибольший элемент ЧУМ – I – если IА,xA xI.


Теорема (о единственности наибольшего (наименьшего) элемента ЧУМа): если наибольший (наименьший) элемент существует, то он единственный.

Док-во:

    1. Пусть I и I*– два различных наибольших элемент в ЧУМе.

Т.к. I – наибольший, то I*I. Но I* тоже наибольший, а значит II*. Тогда по свойству антисимметричности I=I*. Следовательно, мы пришли к противоречию.

    1. Пусть О и О*– два различных наибольших элемент в ЧУМе.

Т.к. О – наименьший, то ОО*. Но О* тоже наименьший, а значит О*О. Тогда по свойству антисимметричности О=О*. Следовательно, мы пришли к противоречию.

ч.т.д.

Пусть m и M – минимальный и максимальный элементы ЧУМа А. Тогда

xA: хm → x=m;

xA: Mx → x=M.

Пример:

m{1,4} – стрелки только выходят;

M{2,3} – стрелки только входят.


Опр: Отношение линейного порядка обладает свойствами 1, 4, 5, 6.

Пример: зададим отношение на множестве R: xyxy. Тогда:

  1. х: хх;

  1. х,y: хy, yx => x=y;

  2. х,y,z: хy, yz => xz;

  3. х,y: х≠y => yx или xy.

Опр: Отношение строгого порядка обладает свойствами 2, 4, 5.

Опр: Отношение строгого линейного порядка обладает свойствами 2, 4, 5, 6.

^

Теория алгоритмов.

Понятие алгоритма.


  1. алгоритм имеет дело с данными; данные приведены к единому виду;

  2. существует элементарный шаг;

  3. детерминированность алгоритма (на каждом шаге мы знаем, что делать дальше);

  4. массовость (должен решать класс задач);

  5. результативность (существует условие окончания работы);

  6. алгоритм обладает памятью.
^

Машина Тьюринга.


Машиной Тьюринга называется пятерка объектов: T=(A,S,,μ,), где А={a1, a2,..., an}- алфавит; λ – символ пустой ячейки. S={ s0, s1,..., sm} – множество внутренних состояний, причем s0 – заключительное, а s1 – начальное состояния. Если при работе происходит переход в состояние s0, то машина прекращает свою работу и говорят, что она применима для данного слова, т.е. зациклена.

ν: AS S – функция перехода;

μ: AS  A – функция выхода;

: AS  { Н,Л,П } – функция управления (на месте, лево, право).

Пример:




s1

s2

λ

1, П, s2

1, Н, s0

1

1, П, s1

λ, П, s1

Считаем, что машина Т, при работе со словом, начинает работу из состояния s1, а считывающее устройство зависает над первым слева непустым символом слова.


1 1 λ 1,

1 1 λ 1,

1 1 λ 1,

1 1 1 1,

1 1 1 λ λ,

1 1 1 λ 1

s1

s1

s2

s2

s2

s0

Таким образом Т(12λ1)=13λ1.


Конфигурацией машины Тьюринга в данный момент времени называется запись вида α1, ai, α2, где α1 – начало слова, ai – символ в данный момент времени, α2 – конец (хвост) слова.

Пример: Написать машину Тьюринга применимую к словам вида x1, x2,..., xn (n≥2), где xi{a,b}, и переводящую их в слово α=




1

2

3

4

5

λ







λ Н 0

b П 5

b Н 0

a

a П 2

λ П 3

λ П 3

a П 4




b

b П 2

b П 4

λ П 3

b П 4




Проверим для слова abba:

a b b a

a b b a

a b b a

a b b a

a b b a λ

a b b a b λ

a b b a b b

1

2

4

4

4

5

0

Проверим для слова bab:

b a b

b a b

b λ b

b λ λ λ

b λ λ λ

1

2

3

3

0
^

Числовая функция


Числовая функция f(x1, x2,..., xn) называется вычислимой по Тьюрингу, если существует машина Тьюринга, применимая к любому слову вида 1x1+11x2+1…1xn+1, переводящая его в слово 1y+1, где y= f(x1, x2,..., xn).

Пример: доказать, что функция f(x,y)=x+y вычислима по Тьюрингу (т.е. 1x+11y+1  1x+y+1).




1

2

3

4

λ

1 П 2

λ Л 3







1

1 П 1

1 П 2

λ Л 4

λ Н 0

Пусть x1=1, x2=2. Покажем, что f(1,2)=3:

1 1λ111

1 1 λ111

11 λ 111

111 1 11

1111 1 1

11111 1 λ

111111 λ

11111 1 λ

1

1

1

2

2

2

2

3

1111 1 λλ

1111 λ λλ.



















4

0


















  1   2   3   4



Скачать файл (152.7 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации