Вход

Логика

Рекомендуемая категория для самостоятельной подготовки:
Контрольная работа*
Код 294269
Дата создания 20 мая 2014
Страниц 9
Покупка готовых работ временно недоступна.
910руб.

Описание

Министерство образования Российской Федерации
Пермский государственный технический университет
Кафедра автоматизированных систем управления












КОНТРОЛЬНАЯ РАБОТА
по «Математической логике и теории алгоритмов»

Вариант № 3













Выполнил:
Рахимзянов В.Р.
Группа: АСУ-13бзу
Проверила:
Викентьева О.Л.







Пермь 2014
...

Содержание

I. Логика и исчисление высказываний
1. Записать высказывания в виде формул логики высказываний.
Если х=5 и у=3, то х>y.
Решение:
1.3

2. Построить таблицы истинности для формул
2.1.

2.2




3. Доказать, что формулы являются тавтологиями
3.3.
Решение:
A B C





4. Доказать полноту (неполноту) систем булевых функций
Класс функций F называется полным, если его замыкание совпадает с Pn:
.
Другими словами, множество функций F образует полную систему, если любая функция реализуема в виде формулы над F.

Воспользуемся критерием Поста. Проверим каждую из этих функций на принадлежность к замкнутым классам P0, P1, L, S, M.

5. Получить СДНФ для формул, а затем перейти к СКНФ:
5.3

6. Получить СКНФ, а затем перейти к СДНФ
6.3

7. Получить МДНФ для формул
7.3


2.Получить множество дизъюнктов.
2.3 x,y,z (P(x)  Q(x,y) →R(z)  M(y))
Формула, в которой из логических символов встречаются только ⌐, &, , причем отрицание должно стоять перед символами предикатов, называется приведенной формой.
Приведенная форма называется нормальной (ПНФ), если она не содержит символов кванторов или все символы кванторов стоят в начале формулы за скобками (кванторная приставка).

3.3 Преобразовать теоремы в вопросы и получить ответы с помощью метода резолюции.
А1: Кто ходит в гости по утрам, тот поступает мудро.
А2: Если у кого угодно есть воздушный шарик, тот поступает мудро.
А3: У Пяточка есть воздушный шарик.
Вопрос: Кто поступает мудро?

Решение:

4.3 Для заданной системы аксиом доказать теорему.
А1:
T:
Решение.

III Теория алгоритмов
1. Построить машину Тьюринга (результат представить в форме таблицы):
В последовательности, состоящей из 0 и 1 сдвинуть слово, состоящее из 1 влево.

Решение. Дан входной алфавит A = {0, 1, l}.
2.1 Доказать, что функции примитивно-рекурсивны:
f(x)=x+n;
Доказательство:

3.3 Построить нормальный алгоритм Маркова, который:
Преобразует любое слово в алфавите {x,y,z} в слово zzx.
Нормальная схема подстановок:

Введение

Контрольная работа по «Математической логике и теории алгоритмов»

527 mod 15 = 2+1 = 3 вариант

Фрагмент работы для ознакомления

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Формулы являются тавтологиями, так все значения – истина.
4. Доказать полноту (неполноту) систем булевых функций
Класс функций F называется полным, если его замыкание совпадает с Pn:
.
Другими словами, множество функций F образует полную систему, если любая функция реализуема в виде формулы над F.
Воспользуемся критерием Поста. Проверим каждую из этих функций на принадлежность к замкнутым классам P0, P1, L, S, M.
1) P0 - класс функий, сохраняющих нуль (т.е если f(0,0,...,0)=0, то f принадлежит этому классу). Проверяем
F(0,0)=0↓0=1 – не принадлежит классу P0
2) P1 - класс функций, сохраняющих единицу (т.е если f(1,1,...,1)=1, то f принадлежит этому классу).
F(1,1)=1↓1=0 – не принадлежит P1
3)L-класс функций, представимы линейным многочленом Жегалкина.
F(x,y)=x↓y=¬xÙ¬y=(x⊕1)Ù(y⊕1)= xy⊕x⊕y⊕1
Получился нелинейный многочлен, значит, функция не принадлежит классу L.
4) S - класс самодвойственных функций. То есть функций, для которых выполняется:
f(x1,x2,...,xn)=¬f(¬x1,¬x2,...,¬xn)
Самодвойственность проще всего определять по таблице значений функции. 
x
y
F
1
1
1
1
1
Таблица самодвойственной функции интересна тем, что столбец ее значений переходит сам в себя при инвертировании. То есть, например, первое значение функции должно равняться отрицанию последнего, второе - отрицании предпоследнего, и так далее. 
В нашем случае функция F является несамодвойственной функцией.
5) M -класс монотонных функций. 
Функция f называется монотонной, если для любых наборов значений переменных(α1,α2,...,αn) и (β1,β2,...,βn), таких что (α1,α2,...,αn)≤(β1,β2,...,βn), выполняется f(α1,α2,...,αn)≤f(β1,β2,...,βn).
Бинарное отношение ≤ понимается так: (α1,α2,...,αn)≤(β1,β2,...,βn) ⇔ ∀i (αi≤βi).
Тогда функция F не монотонна.
Теперь, когда мы проверили все функции на принадлежность к этим пяти классам, можно построить таблицу Поста.
P0
P1
L
S
M
F
-
-
-
-
-
Согласно критерию Поста, чтобы система функций была полна, необходимо и достаточно, чтобы в каждом столбце таблицы Поста был хотя бы один минус.
Значит, наша система функций полна.
5. Получить СДНФ для формул, а затем перейти к СКНФ:
5.3
x
y
z
1
2
3
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
СДНФ:
Переход к СКНФ:
6. Получить СКНФ, а затем перейти к СДНФ
6.3
x
y
z
1
2
3
4
5
6
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
СКНФ:
Переход к СДНФ:
7. Получить МДНФ для формул
7.3
x
y

Список литературы

I. Логика и исчисление высказываний
1. Записать высказывания в виде формул логики высказываний.
Если х=5 и у=3, то х>y.
Решение:
1.3

2. Построить таблицы истинности для формул
2.1.

2.2




3. Доказать, что формулы являются тавтологиями
3.3.
Решение:
A B C





4. Доказать полноту (неполноту) систем булевых функций
Класс функций F называется полным, если его замыкание совпадает с Pn:
.
Другими словами, множество функций F образует полную систему, если любая функция реализуема в виде формулы над F.

Воспользуемся критерием Поста. Проверим каждую из этих функций на принадлежность к замкнутым классам P0, P1, L, S, M.

5. Получить СДНФ для формул, а затем перейти к СКНФ:
5.3

6. Получить СКНФ, а затем перейти к СДНФ
6.3

7. Получить МДНФ для формул
7.3


2.Получить множество дизъюнктов.
2.3 x,y,z (P(x)  Q(x,y) →R(z)  M(y))
Формула, в которой из логических символов встречаются только ⌐, &, , причем отрицание должно стоять перед символами предикатов, называется приведенной формой.
Приведенная форма называется нормальной (ПНФ), если она не содержит символов кванторов или все символы кванторов стоят в начале формулы за скобками (кванторная приставка).

3.3 Преобразовать теоремы в вопросы и получить ответы с помощью метода резолюции.
А1: Кто ходит в гости по утрам, тот поступает мудро.
А2: Если у кого угодно есть воздушный шарик, тот поступает мудро.
А3: У Пяточка есть воздушный шарик.
Вопрос: Кто поступает мудро?

Решение:

4.3 Для заданной системы аксиом доказать теорему.
А1:
T:
Решение.

III Теория алгоритмов
1. Построить машину Тьюринга (результат представить в форме таблицы):
В последовательности, состоящей из 0 и 1 сдвинуть слово, состоящее из 1 влево.

Решение. Дан входной алфавит A = {0, 1, l}.
2.1 Доказать, что функции примитивно-рекурсивны:
f(x)=x+n;
Доказательство:

3.3 Построить нормальный алгоритм Маркова, который:
Преобразует любое слово в алфавите {x,y,z} в слово zzx.
Нормальная схема подстановок:
Пожалуйста, внимательно изучайте содержание и фрагменты работы. Деньги за приобретённые готовые работы по причине несоответствия данной работы вашим требованиям или её уникальности не возвращаются.
* Категория работы носит оценочный характер в соответствии с качественными и количественными параметрами предоставляемого материала. Данный материал ни целиком, ни любая из его частей не является готовым научным трудом, выпускной квалификационной работой, научным докладом или иной работой, предусмотренной государственной системой научной аттестации или необходимой для прохождения промежуточной или итоговой аттестации. Данный материал представляет собой субъективный результат обработки, структурирования и форматирования собранной его автором информации и предназначен, прежде всего, для использования в качестве источника для самостоятельной подготовки работы указанной тематики.
© Рефератбанк, 2002 - 2022