Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Топ:
Основы обеспечения единства измерений: Обеспечение единства измерений - деятельность метрологических служб, направленная на достижение...
Особенности труда и отдыха в условиях низких температур: К работам при низких температурах на открытом воздухе и в не отапливаемых помещениях допускаются лица не моложе 18 лет, прошедшие...
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Интересное:
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Дисциплины:
2018-01-29 | 265 |
5.00
из
|
Заказать работу |
|
|
Базисными функциями называются следующие функции: – нулевая функция; – функция следования; – функция выбора.
Оператор суперпозиции (подстановки) ставит в соответствие –местной операции и – местным операциям –местную операцию , удовлетворяющую тождеству:
Оператор примитивной рекурсии ставит в соответствие – местной операции и – местной операции – местную операцию , удовлетворяющую схеме примитивной рекурсии:
Функция называется примитивно рекурсивной (ПРФ), если существует последовательность функций , в которой и всякая является либо базисной функцией, либо получается из предыдущих функций с помощью оператора суперпозиции или примитивной рекурсии .
Пример 1. Функция сложения является ПРФ:
Пример 2. Функция умножения является ПРФ:
Частично рекурсивные функции
Оператор минимизации ставит в соответствие – местной операции –местную операцию так, что
В этом случае введем обозначение:
Функция называется частично рекурсивной (ЧРФ), если существует последовательность функций , в которой и всякая является либо базисной функцией, либо получается из предыдущих функций с помощью оператора суперпозиции , примитивной рекурсии или минимизации .
Пример 1. Нигде не определенная функция является ЧРФ:
.
Пример 2. Функция
является ЧРФ:
ЗАДАНИЯ ДЛЯ домашних И КОНТРОЛЬНЫХ РАБОТ
Совершенные дизъюнктивные нормальные формы, совершенные конъюнктивные нормальные формы
Построить таблицы истинности для следующих формул алгебры высказываний и привести эти формулы к СДНФи СКНФ.
1. (x∧y)→(y∧z); |
2. (x→y)→(y∧z); |
3. ((x∧y)→x)→z; |
4. (x∧(y→z)→x∨(y∧z); |
5. z→(x∧y)∨(y∧z); |
6. ((x∨z)∧y)→(y→z); |
7. (x∧(z→y)→y)∨z); |
8. ((x∧y)→z∨(y∧z); |
9. (((x→y)→z)∨y)∧z; |
10) x∧(z→y)→z∨y; 11) ((x∨z)∧y)→(y→z); |
12) (x→y)→z∨(y∧z); |
13) x→(y→z)∧(z∨x); |
14) ((x∧z)→y)∨z; |
15) ((x→y)∧z→z)∨y; |
16) x∨(z→y)→(y∧z); |
17) ((x∧z→y)→z)∨z; |
18) (x∧z →y)→z∨y; |
19) (x→y∧z)∨y→z; |
20) x→(y→z)∨(y∧z); |
21) ((x∨y)→z)→(y∧z); |
22) (x→y)→(z∨y)∧z; |
23) ((x→y)∧z)∨y)→z; |
24) (z→y)→x∧(z∨y)∧z; |
25) ((x∧z)∨y)→z∧(x→y). |
|
Логическое следствие в алгебре высказываний
Проверить истинность соотношений тремя способами(используя определение логического следствия и пп. 3,4 теоремы 2.
1. ;
2. ;
3. ;
4. ;
5. ;
6. ;
7. ;
8. ;
9. ;
10. ;
11. ;
12. ;
13. ;
14. ;
15. ;
16. ;
17. ;
18. ;
19. ;
20. ;
21.
22.
23. ;
24. ;
25.
Исчисление высказываний
Пусть - формулы исчисления высказываний. Построить вывод формулы исчисления высказываний из данного множества гипотез.
1. ;
2. ;
3. ;
4. ;
5. ;
6. ;
7.
8.
9. ;
10. ;
11. ;
12. ;
13. ;
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
Логика предикатов. Алгебраические системы.
Построить подсистемуалгебраической системы , порожденную множеством (через обозначен булеан множества B, т.е. множество всех подмножеств множества B):
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24. Ø,
25.
26. Ø,
27.
28.
29. Ø,
Формулы ЛП
Выписать все подформулы данной формулы сигнатуры иопределить свободные и связанные переменные формулы:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
Пусть - атомарные формулы логики предикатов.Выписать все подформулы данной формулы и определить свободные и связанные переменные формулы:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15. ,
16.
17.
18.
19.
20.
Истинность формулыЛП
|
В алгебраической системе
Написать формулу Ф(х), истинную в алгебраической системе тогда и только тогда, когда
1. х=1;
2. х=2n для некоторого натурального n;
3. х>4;
4. х – нечетное число;
5. х – простое число.
Написать формулу Ф(х,y), истинную в алгебраической системе тогда и только тогда, когда
1. ;
2. ;
3. х делит ;
4. ;
5. , где p - простое число.
Написать формулу Ф(х,y,z), истинную в алгебраической системе тогда и только тогда, когда
1. x делится на yс остатком 2;
2. x+3y>2z;
3. z – общий делитель y и z;
4. z = НОК (x, y);
5. z = НОД (x, y).
Написать формулу Ф(х,y,z), истинную в алгебраической системе тогда и только тогда, когда
1. x=0;
2. x=-1;
3. 2x-3y – четное число;
4. 3z=4x-5y;
5. z-2y делится на 3x.
Пусть – булеан множества B, т.е. множество всех подмножеств множества B. Написать формулу Ф(х,y,z), истинную в алгебраической системе тогда и только тогда, когда
1. есть пересечение и ;
2. есть объединение и ;
3. Ø;
4. ;
5. есть дополнение .
Пусть – булеан множества B, т.е. множество всех подмножеств множества B. Написать формулу Ф(х,y,z), истинную в алгебраической системе тогда и только тогда, когда
1. ;
2. Ø;
3. есть одноэлементное множество;
4.
5.
Написать формулу , такую что
Логическое следствие в ЛП
Пусть – формулы логики предикатов, и. .Доказать следующие соотношения.
1. ;
2. ;
3. ;
4. ;
5. ;
6. ;
7. ;
8. ;
9. ;
10. ;
11. ;
12. ;
13. ;
14. ;
15. ;
16. ;
17. .
Пусть – формулы логики предикатов.Проверить следующие соотношения.
1. ;
2. ;
3.
4.
5.
6.
7.
8.
9.
10.
Исчисление предикатов
Пусть - формулы исчисления предикатов. Построить вывод формулы исчисления предикатов из данного множества гипотез.
Пренексная нормальная форма
Пусть –атомарные формулы логики предикатов.Привести следующие формулы логики предикатов к пренексной нормальной форме.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15. ,
16.
17.
18.
19.
20.
Машины Тьюринга
Построить машину Тьюринга , вычисляющую следующую функцию.
1. x+1;
2. x+y;
3.
4.
5.
6.
7.
8.
|
|
История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!