close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
Федеральное агентство связи
Сибирский Государственный Университет Телекоммуникаций и Информатики
Межрегиональный центр переподготовки специалистов
Контрольная работа
По дисциплине: Математическая логика и теория алгоритмов
Выполнил: Шарипов В.Б.
Группа:
Вариант: 06
Проверила:
Новосибирск, 2015 г
Задача 1
Проверить выводимость в исчислении высказываний методом Куайна,
методом редукции и методом резолюций.
1) Метод Куайна
а) Пусть A=0
Тогда
0  B   (0 &  B )  1
при любом B.
б) Пусть A=1
Тогда 1 
B=0 1 
B   (1 &  B )
0   (1 & 1) =
B=1 1  1 
1
0 0  0 0 1
 (1 & 0 )  1  1  1  1
- тавтология
- тавтология
Данная формула является тавтологией, следовательно, она выводима в
исчислении высказываний.
2) Метод редукции
A
B  ( A &  B )  A  B  ( A  B )
A
B  1,
A
B
=0 – противоречие.
Формула не может быть ложной ни при какой интерпретации,
следовательно, она выводима.
3) Метод резолюций
Преобразуем во множество предложений отрицание целевой формулы
 ( A  B   ( A &  B ))
 (  (  A  B )   ( A &  B ))
(  A  B )&( A &  B )
Множество предложений:
A  B
, A,
B
Производим резольвирование:
1.
A  B
2. A
3.
B
2
4. B
Правило резолюции из 1 и 2
5. ∅ Правило резолюции из 3 и 4
В результате очередного применения правила резолюции получено
пустое предложение. Это означает, что формула выводима.
3
Задача 2
Пусть Омега - множество людей. На множестве Омега заданы следующие
предикаты:
1.
E(x, y) = И <=> x и y – один и тот же человек;
2.
P(x, y) = И <=> x родитель y;
3.
C(x, y) = И <=> x и y – супруги;
4.
M(x) = И <=> x – мужчина;
5.
W(x) = И <=> x – женщина.
С использованием этих предикатов записать формулы, выражающие
следующие утверждения:
X – деверь
P(y,x)&P(y,z) = y «x» и «z» общий родитель
P(y,x)&P(y,z)&  E(x,z)&M(x)&M(y) – «x» и «y» – братья
P(y,x)&P(y,z)&  E(x,z)&M(x)&M(y)&c(z,a) &W(a) - «x»- деверь «а»
Фраза «X – деверь» зависит только от одной переменной Х, поэтому и формула
также должна иметь только одну свободную переменную Х. А ваша формула
зависит от многих переменных… В формулу необходимо добавить подходящие
кванторы.
4
Задача 3
Привести формулу к предваренной форме.
  (  x  yQ ( x , y ))  (  y  xQ ( x , y )) 
Следующий переход (в середине выражения) неверный. Далее также
переходы неправильные. Указывайте какие равносильности применяются
(  x  yQ ( x , y )  (  y   xQ ( x , y ))
(
 (  y  xQ ( x , y ))  (  y  xQ ( x , y )) 
y  x  Q ( x , y ) )  (  y xQ ( x , y ) )   y  y (  x  Q ( x , y ))  (  xQ ( x , y )) 
 y  x (  Q ( x , y )  Q ( x , y ))
5
Задача 4
Построить машину Тьюринга для перевода из одной конфигурации в
другую. На ленте всех машин Тьюринга записаны лишь нули и единицы,
при этом пустые ячейки содержат нули. ( x , y ,z 1) Проверить работу
машины Тьюринга для конкретных значений x , y , z .
q11x01y01z => q01x+z
q 1 1  1 Rq 1
q 1 0  0 Rq
2
q 2 1  0 Rq
2
q 2 0  0 Rq 3
q 3 1  0 Rq 4
q 3 0  STOP 0
q 4 1  1L q 5
q 4 0  0 Lq 6
q 5 1  1 Rq 7
q 5 0  0 Lq 5
q 6 1  1 Rq 8
q 6 0  0 Lq 6
q 7 1  STOP 1
q 7 0  1R q 9
6
q 8 1  STOP 1
q 8 0  STOP 1
q 9 1  0R q 4
q 9 0  0Rq9
Для x=1, y=2, z=3:
На ленте: 10110111
Проходим через группу единиц x вправо
q 1 1  1 Rq 1
q 1 0  0 Rq
2
Проходим вправо 0, разделяющий группы x и y
q 2 1  0 Rq
2
Проходим вправо через группу единиц y, обнуляем ее
На ленте: 10000111
q 2 0  0 Rq 3
Проходим 0, разделяющий группы x и z
q 3 1  0 Rq 4
Обнуляем первую единицу из z, идем вправо
На ленте: 10000011
q 4 1  1L q 5
Следующая цифра – 1, отступаем влево
q 5 0  0 Lq 5
Проходим через нули влево
q 5 1  1 Rq 7
До x, находим 1, отступаем вправо
q 7 0  1R q 9
На месте 0 после x пишем 1, отступаем вправо
На ленте: 11000011
q 9 0  0Rq9
Через нули вправо
q 9 1  0R q 4
Нашли 1, обнуляем эту единицу, отступаем вправо
На ленте: 11000001
q 4 1  1L q 5
Следующая цифра – 1, отступаем влево
q 5 0  0 Lq 5
Через группу нулей влево до x
q 5 1  1 Rq 7
До x, находим 1 , отступаем вправо
q 7 0  1R q 9
На месте 0 после x записываем единицу
7
На ленте: 11100001
q 9 0  0Rq9
Проходим через нули вправо
q 9 1  0R q 4
Находим 1, обнуляем, отступаем вправо
На ленте: 11100000
q 4 0  0 Lq 6
Следующая цифра – 0, идем влево через нули к x
q 6 1  1 Rq 8
Находим 1, отступаем вправо
Задача 5
Показать примитивную рекурсивность функции f(x,y)
Непонятно, откуда следует примитивная рекурсивность функции…
Напишите пояснения.
1) (x,0) =
1, x  0
 s g ( x)

0, x  0
 0 , y  1, x
2) f(x,y+1) = 
1, y  1  x
= f(x,y)+ s g (|
h(x,y,z)= U 33 ( x , y , z )  s g (|
x  y  1 |)  h ( x , y , f ( x , y ))
x  y  1 |)
8
= h(x,y,f(x,y))
1/--страниц
Пожаловаться на содержимое документа