Математическая логика и теория алгоритмов (стр. 5 )

(p?1??z(pMz?(1Mz?zMp)))??x?y((pMx?pM y)?x?y).

Эта формула истинна в интерпретации N, так как натуральное простое число p имеет ровно два натуральных делителя 1 и p.

№9. Пусть L – язык первого порядка с одним бинарным предикатным символом < и с множеством констант {?5, ?4,?3, ?2, ?1, 0, 1, 2, 3, 4, 5}, J – интерпретация с множеством интерпретации D?R и с интерпретацией символа < как обычного отношения порядка на множестве действительных чисел. Укажите наибольшее множество интерпретации D, при котором формула A(x) истинна в интерпретации J?

0	A(x)=(x<?4?3<x)?(?5<x?x<4)
1	A(x)=(?3<x?4<x)?(x<?5?x<2)
2	A(x)=(?2<x?3<x)?(0<x?4<x)
3	A(x)=(x<?3?5<x)?(?1<x?x<3)
4	A(x)=(?1<x?x<1)?(x<?5?3<x)
5	A(x)=(?3<x?2<x)?(x<2?x<3)
6	A(x)=(?4<x?x<3)?(x<?2?5<x)
7	A(x)=(x<?3?x<2)?(x<?4?x<1)
8	A(x)=(x<?2?x<4)?(?4<x?3<x)
9	A(x)=(x<?1?2<x)?(?5<x?x<4)
10	A(x)=(x<?1?x<3)?(x<3?x<5)

Решение варианта 0. Множество D по условию является множеством всех тех значений, для которых свойство A(x) истинно: D={x?R|(x<?4?3<x)?(?5<x?x<3)}.

D=[(??;?4)?(3;?)]?(?5;4)=(?5;?4)?(3;4).

№10. Построить предваренную нормальную форму следующей формулы:

0	?xA(x, y)??yB(x, y)
1	?xA(x, y)?(?yB(x, y)??yC(x, y))
2	(?xA(x, y)??yB(x, y))??yC(x, y)
3	?xA(x, y)?(?yB(x, y)??yC(x, y))
4	(?xA(x, y)??yB(x, y))??yC(x, y)
5	?xA(x, y)?(?yB(x, y)??yC(x, y))
6	(?xA(x, y)??yB(x, y))??yC(x, y)
7	?xA(x, y)?(?xB(x, y)??yC(x, y))
8	(?xA(x, y)??xB(x, y))??yC(x, y)
9	?xA(x, y)?(?xB(x, y)??yC(x, y))
10	(?xA(x, y)??xB(x, y))??yC(x, y)

Решение варианта 0. Пусть z – переменная, не содержащаяся в формулах C(x) и D(x), Qx – квантор всеобщности или существования, а Q?x – квантор, противоположный к квантору Qx. Тогда QxC(x)?D(x)?Q?z(C(z)?D(x)) и C(x)?QxD(x)?Qz(C(z)?D(x)). Применяя эти равносильности, приведем нашу формулу к предваренной нормальной форме:

?xA(x, y)??yB(x, y)??z(A(z, y)??yB(x, y)??z?u(A(z, y)?B(x, u)).

Контрольные и самостоятельные работы по теории алгоритмов

Контрольная работа №1

по теме «Примитивно рекурсивные функции, отношения и предикаты»

ВАРИАНТ 1

Пусть f – примитивно рекурсивная n-местная функция, а n-местная функция g, такая, что ?x1, x2, x3, x4,…, xn?N g(x1, x2, x3, x4,…, xn)=f(x3, x1, x2, x4,…, xn). Докажите, что функция g примитивно рекурсивная. Функция y=f(x) определена «с перебором случаев»:

Докажите, что функция y=f(x) примитивно рекурсивная.

Предикаты P(x) и Q(x) примитивно рекурсивны. Определим: (P?Q)(x)?P(x)?Q(x) для всех x?N, где логическая связка ? задана следующей таблицей истинности:

P	Q	P?Q
И	И	И
И	Л	Л
Л	И	Л
Л	Л	И

Докажите, что предикат (P?Q)(x) тоже примитивно рекурсивный.

4.        Определите последовательности, заданные по схеме рекурсии

a)                        b)

ВАРИАНТ 2

Пусть f – примитивно рекурсивная 4-местная функция, а 7-местная функция g, такая, что ?x1, x2, x3, x4, x5, x6, x7?N g(x1, x2, x3, x4, x5, x6, x7)=f(x2, x4, x4, x2). Докажите, что функция g примитивно рекурсивная. Функция y=f(x) определена «с перебором случаев»:

Докажите, что функция y=f(x) примитивно рекурсивная.

3.        Предикаты P(x) и Q(x) примитивно рекурсивны. Определим: (P?Q)(x)?P(x)?Q(x) для всех x?N, где логическая связка ? задана следующей таблицей истинности:

P	Q	P?Q
И	И	И
И	Л	Л
Л	И	И
Л	Л	И

Докажите, что предикат (P?Q)(x) тоже примитивно рекурсивный.

Определите последовательности, заданные по схеме рекурсии

a)                        b)

Контрольная работа №2

по теме «Машина Тьюринга. Нормальный алгоритм Маркова»

ВАРИАНТ 1

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

2.        Построить в алфавите машину Тьюринга, переводящую конфигурацию К1 в конфигурацию К0.

       1) ;        2) .

3.        Сконструируйте нормальные алгоритмы, вычисляющие функции:

       1) ;                         2) .

ВАРИАНТ 2

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

2.        Построить в алфавите машину Тьюринга, переводящую конфигурацию К1 в конфигурацию К0.

       1) ;        2) .

3.        Сконструируйте нормальные алгоритмы, вычисляющие функции:

       1) ;                         2) .

Задачи для проверки остаточных знаний

Примитивно рекурсивные функции, отношения и предикаты

Докажите, что следующие функции примитивно рекурсивны:

1) ;        2) ;                3) ;                

4)        5) ;                        6) .

Докажите, что следующие функции примитивно рекурсивны:

1) ;                2) ;                3) .

Докажите, что следующие функции примитивно рекурсивны:

1)   – остаток от деления на ();