1. «Совершенные дизъюнктивные нормальные формы (сднф) и совершенные конъюнктивные нормальные формы (скнф) в алгебре высказываний (АВ)»

Истинность формулы логики предикатов в алгебраической системе Написать формулу Ф(х), истинную в алгебраической системе тогда и только тогда, когда х=1; х=2n для некоторого натурального n; х>4; х – нечетное число; х – простое число. Написать формулу Ф(х,y), истинную в алгебраической системе тогда и только тогда, когда ; ; х делит ; ; , где p - простое число. Написать формулу Ф(х,y,z), истинную в алгебраической системе тогда и только тогда, когда x делится на y с остатком 2; x+3y>2z; z – общий делитель y и z; z = НОК (x,y); z = НОД (x,y). Написать формулу Ф(х,y,z), истинную в алгебраической системе тогда и только тогда, когда x=0; x=-1; 2x-3y – четное число; 3z=4x-5y; z-2y делится на 3x. Пусть – булеан множества B, т.е. множество всех подмножеств множества B.Написать формулу Ф(х,y,z), истинную в алгебраической системе тогда и только тогда, когда есть пересечение и ; есть объединение и ; Ø; ; есть дополнение . Пусть – булеан множества B, т.е. множество всех подмножеств множества B.Написать формулу Ф(х,y,z), истинную в алгебраической системе тогда и только тогда, когда ; Ø; есть одноэлементное множество; Написать формулу , такую что Логическое следствие в логике предикатов Пусть – формулы логики предикатов, и . . Доказать следующие соотношения. ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; . Пусть – формулы логики предикатов. Проверить следующие соотношения. ; ; ; ; ; ; ; ; ; ; 3.8. Исчисление предикатов Пусть - формулы исчисления предикатов. Построить вывод формулы исчисления предикатов из данного множества гипотез. ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; 3.9. Пренексная нормальная форма Пусть – атомарные формулы логики предикатов. Привести следующие формулы логики предикатов к пренексной нормальной форме. 3.10. Машины Тьюринга Построить машину Тьюринга , вычисляющую следующую функцию. Примитивно рекурсивные функции Доказать, что следующие функции примитивно рекурсивны. x+1; x+y; |x-y|; max(x,y); min(x,y); – частное от деления x на y (здесь ); rest(x,y) – остаток от деления x на y ( здесь rest(x,0)=x); τ(x) – число делителей числа x, где τ(0)=0; σ(x) – сумма делителей числа x, где σ(0)=0; lh(x) – число простых делителей числа x, где lh(0)=0; π(x) – число простых чисел, не превосходящих x; k(x,y) – наименьшее общее кратное чисе x и y, где k(x,0)=k(0,y)=0; d(x,y) – наибольший общий делитель чисе x и y, где d(0,0)=0. Частично рекурсивные функции Доказать, что следующие функции частично рекурсивны. ; ; СПИСОК ЛИТЕРАТУРЫ Основная литература Ершов Ю.Л., Палютин Е.А. Математическая логика. – М.: Наука, 1987. Судоплатов С.В., Овчинникова Е.В. Математическая логика и теория алгоритмов. – М.: ИНФРА-М; Новосибирск: Изд-во НГТУ, 2004. Новиков П.С. Элементы математической логики. – М.: Наука,1973. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М.: Наука,1981. Степанова А.А. Математическая логика и теория алгоритмов. Учеб.пособие.- Находка: Институт технологии и бизнеса, 2003.-56 с. 4.2. Дополнительная литература Мендельсон Э. Введение в математическую логику. – М.: Наука,1976. Лихтарников Л.М., Сукачева Т.Г. Математическая логика. С.П.:Лань,1998. Черч А. Введение в математическую логику. – М.: Наука. 1960. СОДЕРЖАНИЕ ВВЕДЕНИЕ 3 1.ПРОГРАММА КУРСА 4 2. ТЕОРЕТИЧЕСКИЙ МАТЕРИАЛ 6 2.1. Алгебра высказываний 6 2.2. Исчисление высказываний 12 2.3. Логика предикатов 19 2.4. Исчисление предикатов 26 2.5. Элементы теории алгоритмов 30 3. ЗАДАНИЯ ДЛЯ ДОМАШНИХ И КОНТРОЛЬНЫХ РАБОТ 34 3.1. Совершенные дизъюнктивные нормальные формы, совершенные конъюнктивные нормальные формы 34 3.2. Логическое следствие в алгебре высказываний 34 3.3. Исчисление высказываний 35 3.4. Алгебраические системы 36 3.5. Формулы логики предикатов 37 3.6. Истинность формулы логики предикатов в алгебраической системе 39 3.7. Логическое следствие в логике предикатов 40 3.8. Исчисление предикатов 41 3.9. Пренексная нормальная форма 42 3.10. Машины Тьюринга 43 3.11 Примитивно рекурсивные функции 44 3.12. Частично рекурсивные функции 45 4. СПИСОК ЛИТЕРАТУРЫ 47

Похожие:

	Теория алгоритмов Нормальные алгоритмы Маркова и ассоциативные исчисления в исследованиях по искусственному интеллекту		Программа по формированию навыков безопасного поведения на дорогах... История появления, развития и запись чисел: в Древней Греции, Египте, на Руси; Фигурные числа, совершенные числа, дружественные числа,...
	Ответы на вопросы к экзамену "Физиология высшей нервной деятельности" Высшая нервная деятельность- условно-рефлекторная деятельность ведущих отделов головного мозга (у человека и животных- больших полушарий...		Министерство общего и профессионального образования Ростовской области... «Ребенок, развитие которого осложнено дефектом, не есть менее развитой, чем его нормальные сверстники, но иначе развитой»
	Преступления, совершённые за два с половиной года великой чистки... Общественная атмосфера, которая была порождена попытками обуздать, стереть историческую память народа, ярко передана в поэме А. Твардовского...		2. Нормальные и экстремальные ситуации в жизни человека Соотношение понятий «среда» и «ситуация»; соотношение объективного и субъективного в ситуации. Эмпирические исследования влияний...
	Урок: кейс-метод Практическая часть В россии сейчас 1 млн беспризорных детей. И у многих из них нормальные семьи, мама и папа. В библии можно найти много заповедей о...		Проблемы исполнения обязательств в гражданском праве Охватывают как нормальные отношения между субъектами гражданского права, связанные с производством продукции, реализацией работ,...
	Урок №47. Формы мышления. Алгебра высказываний. Цели урока Правомерно ли считать, что религия, искусство, наука – духовные истоки философии? Обоснуйте свой ответ		Учебно-методическое пособие для самостоятельной работы по дисциплине... Полноценное кормление животных обеспечивает хорошее состояние здоровья, получение высокой продуктивности, нормальные воспроизводительные...
	И. Б. Ничипоров И. А. Бунин. Очерк творчества Художественное наследие... Золотого века до психологической прозы второй половины ХIХ столетия и в то же время аккумулировало новейшие эстетические открытия,...		Программа по формированию навыков безопасного поведения на дорогах... Как построить нормальные отношения с ребенком? Как заставить его слушаться? Можно ли поправить отношения, если они зашли в тупик?...
	Программа по формированию навыков безопасного поведения на дорогах... Как построить нормальные отношения с ребенком? Как заставить его слушаться? Можно ли поправить отношения, если они зашли в тупик?...		Программа по формированию навыков безопасного поведения на дорогах... Как построить нормальные отношения с ребенком? Как заставить его слушаться? Можно ли поправить отношения, если они зашли в тупик?...
	Для того чтобы правильно выполнить задание 2, необходимо усвоить... Видо-временные формы глагола: а) активный залог – формы Indefinite (Present, Past, Future); формы Continuous (Present, Past, Future);...		Программа по формированию навыков безопасного поведения на дорогах... Ага, как же, полюбому есть, только крысит. Мысля! У лоточников зарешать они всегда добавят, пофиг, что хачи, зато выручают по мелочи....