Благодарю за контрольную по логике)
Информация о работе
Подробнее о работе
Логика
- 9 страниц
- 2014 год
- 367 просмотров
- 0 покупок
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
Контрольная работа по «Математической логике и теории алгоритмов»
527 mod 15 = 2+1 = 3 вариант
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.
Нормальная схема подстановок:
Министерство образования Российской Федерации
Пермский государственный технический университет
Кафедра автоматизированных систем управления
КОНТРОЛЬНАЯ РАБОТА
по «Математической логике и теории алгоритмов»
Вариант № 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.
Нормальная схема подстановок:
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
