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

ПРАВИЛА ВЫПОЛНЕНИЯ И ОФОРМЛЕНИЯ КОНТРОЛЬНОЙ РАБОТЫ

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

1. На титульном листе должны быть ясно написаны фамилия студента, его инициалы, номер варианта, название дисциплины.

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

3. Решения задач необходимо располагать в порядке номеров, указанных в заданиях, сохраняя номера задач. Решение каждой задачи должно быть полным и максимально понятным.

4. Перед решением каждой задачи необходимо выписать полностью ее условие. В том случае, если несколько задач, из которых студент выбирает задачу своего варианта, имеют общую формулировку, следует, при переписывании условия задачи, заменить общие данные конкретными из соответствующего номера.

5. После получения прорецензированной работы, как незачтенной, студент должен исправить все отмеченные рецензентом ошибки и недочеты, выполнить все рекомендации и прислать для повторной проверки в короткий срок.

6. Без выполненной контрольной работы студент к зачету не допускается.

ПРАВИЛА ВЫБОРА ВАРИАНТА

Вариант контрольной работы выбирается в зависимости от последней цифры номера зачетной книжки студента (если последняя цифра 0, вариант 10). Будьте внимательны при выборе варианта. Работа, выполненная не по своему варианту, возвращается без проверки!

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

1. A®B├ (C®A)®(C®B)

2. A®B├ (C&A)®(C&B)

3. A®B├ (CÚA)®(CÚB)

4. AÚ(B&C) ├ (AÚB)&(AÚC)

5. (AÚB)&(AÚC) ├ AÚ(B&C)

6. ├A®B®Ø(A&ØB)

7. ├ØAÚB®(A®B)

8. ├AÚB®(ØA®B)

9. A&(BÚC) ├ (A&B)Ú(A&C)

10. (A&B)Ú(A&C) ├ A& (BÚC)

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

E(x, y) = И Û x и y – один и тот же человек;

P(x, y) = ИÛx родитель y;

C(x, y) = И Ûx и y – супруги;

M(x) = И Ûx – мужчина;

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

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

1. У каждого есть отец и мать.

2. У каждого есть бабушка

3. У каждого есть дедушка

4. X – прабабушка

5. X – прадедушка

6. X – деверь

7. X – шурин

8. X – кузен

9. X – кузина

10. X – золовка

3. Привести формулу к предваренной форме

1. ($x"yA(x,y))&($x"yB(x,y))

2. ($x"yA(x,y))®($x"yB(x,y))

3. ($x"yA(x,y))Ú($x"yB(x,y))

4. ($x"yA(x,y))®("x$yB(x,y))

5. ($x"yQ(x,y))®("y$xQ(x,y))

6. ("x$yQ(x,y))®($y"xQ(x,y))

7. Ø(($xP(x))®("xP(x)))

8. ("x$yQ(x,y))®(($yQ(x,y))ÚR(x,y))

9. "x$yQ(x,y)®(($y"xP(x,y))®Q(x,y))

10. ("xQ(x,y))®(($yQ(x,y))Ú($xR(x,y)))

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

1. q₁ 1^x01^y0Þ q₀ 1^y001^x0

2. q₁ 1^x01^y01^zÞ q₀ 1^z01^y01^x0

3. q11x01y01zÞ	q0 1x, если y>z
   	q0 0, если y£z

4. q11x01y01zÞ	q0 1y, если z>2
   	q0 1x, если z£2

5. q₁ 1^x01^y01^zÞ q₀ 1^x+z01^y

6. q₁ 1^x01^y01^zÞ q₀ 1^x+z

7. q₁ 1^x01^y01^zÞ q₀ 1^z+x

8. q₁ 1^xÞ q₀ 1^x01^x01^x

9. q₁ 1^x01^y01^zÞ q₀ 1^x01^y+201^x+2

10. q₁ 1^x01^yÞ q₀ 1^x+2y