Дисциплина «Математическая логика и теория алгоритмов» (стр. 4 )

Предположим, что I(?xA??xB)=1 на последовательности d. Тогда, в силу определения дизъюнкции, I(?xA)=1 на последовательности d илиI(?xB)=1 на последовательности d. По смыслу квантора всеобщности верно хотя бы одно из следующих утверждений: I(A)=1 на любой последовательности d? или I(B)=1 на любой последовательности d?. В силу определения дизъюнкции, I(A?B)=1 на любой последовательности d? и в первом случае, и во втором случае. Вновь используя определение квантора всеобщности, получим, что ?x(A?B)=1 на последовательности d. Следовательно, в силу определения импликации, I(X)=1 на последовательности d.

Таким образом, для любой интерпретации Iмы получили, что I(X)=1 на любой последовательности d элементов интерпретации I.

Ответ: формула X – логически общезначимая формула.

2) Пусть интерпретацияIесть множество всех действительных чисел, x=x1, примером формулы A возьмем формулу x=5, а примером формулыB – формулу x?5. Тогда формула Y примет следующий вид: ?x(x=5?x?5)?(?xx=5??xx?5).

Вычислим истинностное значение I(Y) формулы Y на любой последовательности d элементов интерпретации I.

(a) I(x=5)=1 на любой последовательности вида d=(5,…).

(b) I(x?5)=1 на любой последовательности d, 1-я компонента которой отлична от 5.

В обоих случаях, в силу определения дизъюнкции, I(x=5?x?5)=1.

По смыслу квантора всеобщности I(?x(x=5?x?5))=1 на любой последовательности.

Из пункта (a) по смыслу квантора всеобщности следует I(?xx=5)=0 на любой последовательности. Из пункта (b) по смыслу квантора всеобщности следует I(?xx?5)=0 на любой последовательности.

В силу определения дизъюнкции, I(?xx=5??xx?5)=0 на любой последовательности. В силу определения импликации, I(Y)=0 на любой последовательности.

Ответ: формула Y не является логически общезначимой формулой.

№8. Пусть L – язык первого порядка со следующими собственными символами: = (бинарный предикатный символ); + (бинарный функциональный символ);? (бинарный функциональный символ); M (бинарный предикатный символ); (константа).

Данное математическое предложение запишите в виде формулы языка L. Истинна ли эта формула в интерпретации N с множеством интерпретации N – множеством натуральных чисел и с естественной интерпретацией собственных символов языка L?

0	Простое число имеет ровно два делителя.
1	Для любых двух чисел x и y найдется такое число d, что для всех чисел z числа x и y делятся на z тогда и только тогда, когда число d делится на z.
2	Если произведение двух чисел делится на простое число p, то хотя бы один из множителей делится на p.
3	Каждое простое число, отличное от 1, имеет простой делитель.
4	Если числа x и y взаимно просты, то существуют такие числа a и b, что ax+by=1.
5	Любые два числа имеют наибольший общий делитель.
6	Для любых двух чисел x и y найдется такое число c, что для всех чисел z числа x и y делят число z тогда и только тогда, когда число c делит число z.
7	Отношение делимости рефлексивно, симметрично и транзитивно.
8	Существуют два простых числа, таких, что одно больше другого на 1.
9	Неверно, что произведение двух чисел делится на z тогда и только тогда, когда хотя бы один из сомножителей делится на z.
10	Любые два числа имеют наименьшее общее кратное.

Решение варианта 0. Целое число p называется простым числом, если оно отлично от 1 и его делителями являются только делители 1 и кратные p. Значит, данное математическое предложение можно записать в виде следующей формулы:

(p?1??z(pMz?(1Mz?zMp)))??x?y((pMx?pMy)?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?Ng(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?Ng(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

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