Задание состоит в следующем - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Спасская Елена Александровна Задание на самостоятельную письменную... 1 201.63kb.
Вариант №1 Задание № (Тема: Понятие) Задача №1 1 33.23kb.
6 класс 2 тур Рекомендуемые ответы Задание (15 баллов) 1 36.67kb.
Физические основы электроники контрольное задание 1 264.08kb.
Цор как средство формирования развивающей парадигмы 1 64.43kb.
Потребитель Паразит 1 59.63kb.
Урок №39 Урок №40 Доп задачи Задание 6 Задание 5 Задание 2 Задание... 1 34.45kb.
Инструкция по выполнению работы Для выполнения экзаменационной работы... 1 186.35kb.
Задание Памятник «Тысячелетие России» состоит из 3-х ярусов. 1 139.34kb.
Центр ирландской культуры «Изумрудный остров» Универсальная школа... 1 21.07kb.
Правила вида спорта «спортивный бридж» 20 1081.23kb.
Олимпиада по литературе 7 класс I. Знание текстов художественных... 1 50.9kb.
Направления изучения представлений о справедливости 1 202.17kb.

Задание состоит в следующем - страница №1/1

ЗАДАНИЕ СОСТОИТ В СЛЕДУЮЩЕМ:



  1. Выполнить первую задачу

  2. Исправить вторую и третью в соответствии с замечаниями (выделены красным)

ВАРИАНТ 6

Задание 1 (выполнить)

Проверить выводимость в исчислении высказываний методом Куайна, методом редукции и методом резолюций:



Решение:



Задание 2 (исправить формулу)

Пусть  - множество людей. На множестве  заданы следующие предикаты:

Е(х,у)=И х и у – один и тот же человек;

Р(х,у)=И х родитель у;

С(х,у)=И х и у – супруги;

М(х)=И х – мужчина;

W(х)=И х – женщина.

С использованием этих предикатов записать формулу, выражающую утверждение: Х – деверь.

Решение:

Деверь – брат мужа. Таким образом, деверем является каждый мужчина, родитель которого является также родителем другого мужчины, который, в свою очередь, женат на женщине, то есть деверь



  1. каждый человек, являющийся мужчиной;

  2. при этом существует человек, являющийся его родителем;

  3. при этом человек из п.2 является родителем другого мужчины;

  4. при этом мужчина из п. 3 женат на женщине:

Поскольку фраза «х – деверь» зависит от переменной х, то и формула также должна зависеть от этой переменной. Исправьте.


Задание 3 (исправить в соответствии с замечанием)

Построить машину Тьюринга для перевода из одной конфигурации в другую. На ленте всех машин Тьюринга записаны лишь нули и единицы, при этом пустые ячейки содержат нули. Проверить работу машины Тьюринга для конкретных значений x, y, z.



Решение:



По условию задачи нужно построить машину Тьюринга, которая последовательность нулей и единиц вида преобразует в последовательность вида . Составим программу машины Тьюринга и оформим ее в виде таблицы, обозначая символом пустые ячейки, соответствующие нулям: Не совсем понятно. Символ записывается в пустые ячейки? А 0 в какие ячейки записывается? или достаточно одного пустого символа?




q1

q2

q3

q4

q5

q6

q7

q8

1

1Пq2

1Пq2

Пq3

Пq5

1Лq7

Сq0

Пq8

1Сq4



-

Пq3

Пq4

-

Лq6

Лq6

Лq7

Пq8




  • состояние q1 является начальным состоянием;

  • машина находится в состоянии q2 до тех пор, пока происходит движение вправо вдоль последовательности , при этом единицы в ячейках остаются без изменений. Как только появляется пустая ячейка, соответствующая нулю, машина переходит в состояние q3;

  • в состоянии q3 машина осуществляет движение вправо вдоль последовательности до тех пор, пока не встретится пустая ячейка, при этом стирает в ячейках единицы. Как только появляется пустая ячейка, машина переходит в состояние q4;

  • в следующей после нуля ячейке должна содержаться единица (первая единица последовательности ), в состоянии q4 машина ее стирает, смещается вправо на одну ячейку и переходит в состояние q5;

  • в состоянии q5 машина происходит проверка, была ли единица в предыдущей ячейке последней в последовательности , то есть если текущая ячейка оказалось пустой, то машина смещается влево и переходит в состояние q6, иначе – в состояние q7;

  • в состоянии q6 машина движется влево, пока не встретит последнюю справа единицу последовательности , тогда она ее стирает и работа машины заканчивается;

  • в состоянии q7 машина также движется влево, пока не встретит последнюю справа единицу последовательности , и также стирает ее, а после этого возвращается вправо до тех пор, пока не встретит следующую единицу последовательности . После этого она переходит в состояние q4, чтобы опять проверить, последняя ли эта единица последовательности или нет, и т.д.

Проверим работу машины на последовательности 11101011:

Значение ячейки

Новое значение ячейки

Действие

Новое состояние

1

1

вправо

q2

1

1

вправо

q2

1

1

вправо

q2

0

0

вправо

q3

1

0

вправо

q3

0

0

вправо

q4

1

0

вправо

q5

1

1

влево

q7

0

0

влево

q7

0

0

влево

q7

0

0

влево

q7

0

0

влево

q7

1

0

вправо

q8

0

0

вправо

q8

0

0

вправо

q8

0

0

вправо

q8

0

0

вправо

q8

1

1

стоять

q4

1

0

вправо

q5

0

0

влево

q6

0

0

влево

q6

0

0

влево

q6

0

0

влево

q6

0

0

влево

q6

0

0

влево

q6

1

0

стоять

q0

Таким образом, произошло преобразование:

1110101111000000




Большинство складывается случайно, меньшинство — сознательно. Стефан Киселевский
ещё >>