Семантика на езиците за програмиране 2005/06 - упражнения

Индукция

• обикновена - ако P(0) и $$\forall n$$(P(n) => P(n+1)), то P е вярно за всяко естествено число
• пълна (възвратна) - ако (P(m) за m<n => P(n)), то P е вярно за всяко естествено число
• еквивалентност на пълната и обикновената индукция
• Всяко естествено число > 1 се представя като произведение на прости множители (с пълна индукция)

Фундирани множества

• (Строга) частична наредба: $$x\not< x$$ (антирефлексивност), x<y, y<z => x<z (транзитивност)
• (Строго) частично наредено множество - множество със зададена частична наредба
• линейна наредба - частична наредба, за която всеки два елемента са сравними, т.е. x<y или x=y или y<x (трихотомия)
• минимален елемент - няма по-малък от него
• най-малък елемент - по-малък от всички, различни от него
• всеки най-малък елемент е минимален, но обратното не е вярно
• Z - множество без минимални и най-малки елементи
• {{1},{2},{1,2}} - множество с два минимални елемента и без най-малки елементи
• $$Z \cup \{a\}$$ - множество с точно един минимален елемент, който не е най-малък
• фундирано множество - частично наредено множество, всяко непразно подмножество на което има минимален елемент
• Добре наредено множество - частично наредено множество, всяко непразно подмножество на което има най-малък елемент
• едно множество е добре наредено <=> то е фундирано с линейна наредба
• Структурна индукция - пълна индукция за фундирани множества

Задачи

• стр.9 / зад. 4 - едно множество е фундирано <=> в него не може да се избере безкрайно намаляваща редица
• стр.10 / зад. 8а,д - N, {X|X е крайно множество от естествени числа} - фундирани множества
• стр.10 / зад. 8б,г - Z, {X|X е множество от естествени числа} - не са фундирани множества
• Лексикографска наредба - (x₁,y₁) < (x₂,y₂), ако x₁ < y1 или x₁ = y₁, x₂ < y₂
• стр.11 / зад. 10а - декартово произведение на фундирани множества с лексикографската наредба е фундирано множество
• стр.11 / зад. 10б - безкрайно декартово произведение на фундирано множество със съответната лексикографска наредба не е фундирано множество
• стр. 11 / зад. 11 - Задача за НОД
• стр. 13 / зад. 12 - Задача за функцията 91 на Макарти