Алгоритмическая модель «Машина Тьюринга»

Оглавление

ИДПО. Задание на КР по Матлогике. 1

Исчисление высказываний. 1

Логика предикатов. 2

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

Подстановки. 5

Унификация. Метод резолюции. 7

Алгоритмическая модель «Машина Тьюринга». 8

Задачи для контрольной работы по Матлогике

Исчисление высказываний

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

1.1.

1.2.

1.3.

1.4.

1.5.

1.6.

1.7.

1.8.

1.9.

1.10.

1.11.

1.12.

1.13.

1.14.

2. Используя метод резолюций, доказать следования:

2.1. ⊢(cÚd);

2.2. ⊢

2.3. ⊢

2.4. ⊢(p®r);

2.5. ⊢d.

3. Исчисление секвенций

3.1. Доказать, что следующие правила являются допустимыми (Правило называется допустимым в ИС, если из выводимости секвенций следует выводимость секвенции ):

3.1.1. (Сечение): ;

(Объединение посылок):

3.1.2. (Расщепление посылок): ;

3.1.3. (Разбор случаев): ;

3.1.4. (Контрапозиция):

3.1.5. (Доказательство от противного):

3.2. Вывести следующие секвенции:

3.2.1.

3.2.2. ;

3.2.3.

3.2.4.

3.2.5.

3.2.6.

3.2.7.

3.2.8. ;

3.2.9. ;

;

Логика предикатов

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

Пусть f¹, g², h³ Î F. Являются ли термами следующие слова:

a. f¹(g²(v₀, v₁));

b. g²(f¹(v₂), h³(v₀, v1, v₂));

c. f¹(g²(v₀), h³(v₀, v₁, v₂))?

2. Пусть , , – одноместный, двуместный и трехместный функциональные символы соответственно. , ÎR – одноместный и трехместный предикатные символы соответственно. Являются ли формулами следующие слова:

a. Q(v₀, f(v₁), h(v₁, v₂, v₂));

b. P(v₀)®"v₁(Q (v₀, v₁, v₂) & P (g(v₀, v₁)));

c. Q (P(v₀), f(v₁), f(v₂));

d. f (h(v₀, v₁, v₁))?

3. Доказать, что слово $v₀"v₁ … "v₀ (P(v₁) & … &P(v₀)), где PÎR, не является формулой.

4. Выписать все подформулы формул:

a. Q(f(v₀), g(v₀, v₁));

5. Описать множество термов от одной переменной v₀ и

a. Функционального символа f¹;

b. Функционального символа g².

6. Какие вхождения переменных являются свободными, а какие связанными в следующих формулах:

a. "xP(x,y)®"yQ(y);

b. "xP(x,y)®"yR(x,y);

7. Является ли терм t свободным для переменной v в формуле U?

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

a. t=f(x,z), v=y, U="x P(x,y);

b. t=f(y,z), v=y, U=((P(y,z) ® $z q(z)).

c. T=y²-y; U=$y (v+y<0), если предметной областью является множество действительных чисел?

8. Доказать, что

a. постоянный терм свободен для любой переменной в любой формуле;

b. переменная x свободна для x в любой формуле;

c. если формула U не содержит свободных вхождений переменной x, то любой терм свободен для x в этой формуле.

9. Используя предикат <, записать следующие утверждения в системе (N; <, =, +, -):

a. Существует число х, меньшее 5 и большее, чем 7;

b. Для любого числа х существует у, меньшее х;

c. Для любого числа х существует число у, большее, чем х;

d. Для любых чисел х и у существует такое число у, что для любого z, если разность z-5<y, то разность x-7<3.

10. Пусть математическая модель сигнатуры имеет вид M=(N; S³, P³), где S(x,y,z) истинна тогда и только тогда, когда x+y=z, и P(x,y,z) истинна тогда и только тогда, когда x*y=z. Записать формулу с одной свободной переменной х, истинную в М тогда и только тогда, когда

a. x=0;

b. x=1;

c. x=2;

d. x – четно;

e. x – нечетно;

f. x – простое число.

11. Рассмотрим модели с одним двуместным предикатом R(x,y), определенным в задаче 10. Записать, что данный предикат

a. Рефлексивен;

b. Симметричен;

c. Транзитивен;

d. Иррефлексивен;

e. Асимметричен;

f. Антисимметричен;

g. R(x,y) – эквивалентность.

12. Определить, выполнимы ли следующие формулы, с помощью семантических таблиц Бета:

a. $xP(x);

b. "xP(x);

c. $x"y(Q(x,x)&ØQ(x,y);

d. $x$y(P(x)&ØP(y);

e. $x"y(Q(x,y)®"zR(x,y,z));

f. (P(x)®"yP(y).

13. Являются ли тождественно истинными следующие формулы с помощью семантических таблиц Бета:

a. ($xP(x)®"xP(x));

b. Ø($xP(x)®"xP(x);

c. ($x"yQ(x,y)®"y$xQ(x,y));

d. ("x$yQ(x,y)®$y"xQ(x,y))?

14. Привести к пренексной нормальной форме, считая U и B бескванторными формулами:

a. Ø$x"y$z"uU;

b. ($x"yU(x,y)&$x"yB(x,y));

c. ($x"yU(x,y)®$x"yB(x,y));

d. ($x"yU(x,y)®$x"yB(x,y)).

15. Для формулы "x$z"y$u ((y>z ® y>x) & (u<z) & Ø(u<x)) построить сколемовскую формулу. Для системы (N,<) найти требуемое обогащение.

16. Для формулы "x"y$z$t (P(x,t) & ØP(y,z)) построить сколемовскую формулу. Для любой системы ((М, P), где М={0,1}, найти подходящее обогащение.

17. Для формулы "x"y$z$v"t (ØS(x,y,y) ® (S(a,v,x) & P(v,t,t))) и системы (N, S³, P³) построить сколемовские функции, если S(x,y,z)=t Û x+y=z; P(x,y,z)=t Û x*y=z.

18. Привести к СНФ:

a. ($x"yQ(x,y) ®"x$yQ(x,y));

b. $x"y$z"v R(x,y,z,v);

c. "x$y"v$z R(x,y,z,v).

Подстановки

1. Определить, какие из следующих пар формул являются вариантами:

a. P(f(x,y), g(z), a) и P(f(y,x), g(u), a);

b. P(x,x) и P(x,y).

2. Докажите, что

a. Если free (x,t,A), то ├ (A{x/t} ® $x A(x));

b. Если free (x,t,A), то ├ ("x A(x) ® A{x/t});

c. ├ (A(x) ® $xA(x));

d. ├ ("x A(x) ® $x A(x));

e. ├ "x$y (x=y);

f. ├ "x$y (x=y);

g. ├ "x"y (x=y ® y=x);

h. ├ "x"y"z [x=y & y=z) ® x=z].

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

3. Сформулируйте следующие высказывания естественного языка, в виде хорновских дизъюнктов (секвенций любого вида):

a. х – мать у, если х – женщина и родитель у.

b. х – отец у, если х – мужчина и родитель у;

c. х – человек, если его родитель человек;

d. х – человек, если родитель х – человек;

e. никто не родитель самому себе.

Сформулируйте задачу и разрешенные действия с помощью хорновских дизъюнктов.

6. Пусть ({a,b}, P²) – модель сигнатуры языка логики предикатов и задана функция интерпретации I такая, что (a,a), (b,b) Î I(P), а (a,b), (b,a) ÏI(P). Определить, являются ли следующие формулы истинными в данной интерпретации:

a. "x$yP(x,y);

b. Ex"yP(x,y);

c. "x$y(P(x,y) ® P(Y,x);

d. "x"yP(x,y);

e. $y

f. "xP(x,x).

8. Пусть дано предложение U: $xP(x)®"xP(x).

a. Докажите, что предложение U всегда истинное в интерпретации, область которой состоит из одного элемента.

b. Найдите интерпретацию с предметной областью, состоящей из двух элементов, в которой предложение U ложно.

9. Найдите интерпретацию с D={a,b}, в которой предложение $x$yP(x,y) было бы истинным, а предложение "x$yP(x,y) – ложным.

11. Приведите к предваренной нормальной форме следующие предложения:

12. Определить теоретико-множественную форму следующих предложений:

a. A1:

b. A2:

c. A3:

13. Пусть S1 и S2 – два множества дизъюнктов:

S1={{P(a)}, {P(x), P(f(x))}};

S2={{P(x), Q(x)}, {R(z)}, {T(y), ØW(y)}}.

Определите эрбрановские множества H3 для S1 и H1, …, H10 для S2.

14. Определите эрбрановские множества H0 и H1 для множества дизъюнктов

S={{P(f(x), a, g(f(x), b))}}. Определите все основные примеры для S на множествах H0 и H1.

15. Докажите с помощью замкнутых семантических таблиц общезначимость следующих предложений:

17. Докажите средствами замкнутых семантических таблиц, что следующие предложения недоказуемы по Бету:

a. A1:

b. A2:

Найдите две интерпретации этих формул, в которых А1 и А2 соответственно ложны.

18. Найдите опровержения приведенных ниже множеств методом семантических деревьев:

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

a. :

b. j:

c. t:

20. Определите, является ли предложение s: логически истинным или нет. Постройте соответствующее доказательство или контр пример.

21. Найдите невыполнимые основные примеры для следующих множеств дизъюнктов:

Унификация. Метод резолюции.

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

S={{P(f(a),g(x)}, {P(y,y)}};
S={{P(a, x, h (g(z)))}, {P(z, h(y), h(y))}};
S={{Q(f(w), a, z)}, {Q(w,b,f(z))}};
S={{любит (w, f(y))}, {любит (Джордж, футбол)}};
S={{R(w,y), Q(w, f(z), z),ØR(w,w)}, {R(w,z), ØQ(f(w),w,z)}};
S={{P(f(x),a)}, {P(y,f(w))}};
S={{P(f(x),z)}, {P(y,a)}}.

2. Определите, какие из следующих предложений унифицируемы, найдите НОУ:

S={{Q(x)}, {Q(b)}};
S={{Q(a,x)}, {Q(a,a)}};
S={{Q(a,x,f(x))}, {Q(a,y,y)}};
S={{Q(x,y,z)}, {Q(u,h(v,v)u)}};
S={{P(x,g(x),y,h(x,y),z,f(x,y,z))}, {P(u,v,e(v),w,k(v,w),s)}}.

Полагаем, что a,b – константы, f,g,h,e,kÎF.

3. Определите невыполнимый основной пример для следующего множества дизъюнктов:

S={{P(x,a,g(x,b))}, {ØP(f(y),z,g(f(a),b)}}.

4. Известны истинные утверждения: «Воробей имеет крылья», «Воробей несет яйца» и «Если животное имеет крылья и несет яйца, то это птица». Требуется доказать утверждение «Воробей является птицей». Для этого выполните следующее;

a) переведите эти утверждения на язык логики предикатов первого порядка, выделив все необходимые группы формул, включая целевую;

b) сделайте опровержение целевой формулы;

c) переведите все формулы в клаузальную форму;

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

5. Предположим, что верны утверждения, представленные ниже:

a. Существует хотя бы один дракон.

b. Дракон либо спит в своей пещере, либо охотится в лесу.

c. Если дракон голоден, он не может спать.

d. Если дракон устал, он не может охотиться.

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

Что делает дракон, когда он голоден?
Что делает дракон, когда он устал?
Что делает дракон, когда он голоден и устал?

6. Пусть следующие предикаты интерпретируются так:

T(x,y,u,v) – “x,y,u,v – это трапеция»;

P(x,y,u,v) – «отрезки xy и vu – параллельны»;

E(x,y,z,u,v,w) – ”угол (xyz) равен углу (uvw)”.

И пусть даны предложения:

A1: "x"y"u"v[T(x,y,u,v)®P(x,y,v,u)] – определение трапеции;

A2: "x"y"u"v [P(x,y,u,v)®E(x,y,v,u,v,y)] – если xy параллельно vu, то угол (xyv) равен углу (uvy);

A3: T(a,b,c,d) (abcd – трапеция).

Алгоритмическая модель «Машина Тьюринга»

1. Выяснить, применима ли машина Тьюринга Т, задаваемая программой П, к слову Р. Если применима, то найти результат применения машины Т к слову Р. Предполагается, что q₁ * начальное состояние, q₀* заключительное состояние и в начальный момент головка машины обозревает самую левую единицу на ленте.

1.1. a) Р=10[01]²1. b) P = 1³0²1², c) P = 1³01^3.

1.2.

a) P=1³01², b) P = 1⁶, c) P= 1⁴01.

2. По заданной машине Тьюринга Т и начальной конфигурации К₁ найти заключительную конфигурацию (q₀ * заключительное состояние).

2.1.

q₁

q₂

q₀1S

q₁0R

q₂0R

q₂1L

а) К₁ = 1²q₁1³01, b)K₁ = 1q₁1⁴.

2.2.

a) K₁= 1q₁1⁵, b) K₁ = q₁1³01, c) K₁= 10q₁1⁴.

a. Построить композицию Т₁Т₂ машин Тьюринга Т1 и Т2 (по паре состояний (q₁₀, q₂₁)) и найти результат применения композиции T₁T₂ к слову P (q₂₀ - заключительное состояние машины Т₂), если

3.1. программы машин Т₁ и Т₂ заданы таблицами:

T₁:

q₁₁

q₁₂

q₁₃

T₂:

q₂₁

q₂₂

q₁₀0L

q₁₃0R

q₁₁0R

q₂₂1Ll

q₂₀0R

q₁₂1R

q₁₃1R

q₁₁0R

q₂₂1L

q₂₁0L

a)P = 1⁴0²1³01², b) P = 1²0101³.

3.2.

a) P = 1²01³01², b) P = 1²01²0²1².

4. Построить машину Тьюринга, складывающую натуральные числа, записанные в унарной системе счисления, т.е. машину Т, удовлетворяющую условию: Т((m)_унарн.+(n)_унарн.) = (m+n)_унарн. Привести пример сложения.

5. Построить машину Тьюринга, удваивающую числа, записанные в унарной системе счисления.

Дата добавления: 2020-11-29; просмотров: 251; Мы поможем в написании вашей работы!

Поделиться с друзьями:

Мы поможем в написании ваших работ!