Няколко често срещани грешки на задачи
Няколко често срещани грешки на задачи в групи 1, 2 и 3.
-- Зад. 1 е елементарна, но не е достатъчно просто да се напише таблица с трите съставни съждения. Трябва да има нещо като "от това, че колона Х е същата като колона У .....". Решенията се пишат в явен вид.
-- На зад 1 няколко души са записали простите съждения като "p: дали уча". Това не е просто съждение, това е въпрос.
-- В зад 2 има няколко души, които са объркали предиката (често наричан P(n)) с аритметичен израз. Предикатът има булева интерпретация, той е T или F. В аритметичен израз ние можем да заместим подизраз с друг аритметичен израз, но не и с предикат. Всички "решения", които ползват заместване на 1.2 + ... + k2k (аритм. израз) с предиката P(k) са фундаментално грешни по тази причина.
-- Задача 3 почти няма верни решения. Прилично д-во по инд-я допуска, че твърдението е вярно за ВСИЧКИ графи с не повече от n върха и разглежда произволен граф с n+1 върха. Ние нямаме индуктивна дефиниция на този клас графи -- може да е очевидна, но трябва да се докаже. Което никой не е направил. При липса на инд. деф, ние не знаем как се правят по-големи графи от по-малки и правилното е, да разгледаме произв. граф с n+1 върха и да изтрием произв. връх v. Тогава очевидно получаваме граф с n върха, в който има такъв маршрут М от инд. предположение. Всички негови върхове имат ребра до/от изтрития връх v (връщаме го обратно, заедно с оригиналните ребра), но никой не е казал, че има ребро от v до началото на М или от края на М до v. Ако има, ясно, но ако няма.. Грешка е да се казва "щом има едно ребро от v до връх x от М и едно от връх y от М до v, директно увеличаваме М, минавайки след x през v и после y", защото от никъде не следва, че x е непоср. преди y в М. За правилно решение, виж примерните решения.
-- В решенията на зад. 4 има няколко, които доказват антисиметричност като опровергават симетричност с контрапример. Не става. Антисим. не е обратното на сим (не са комплементарни).
-- В зад. 6 трябва по някакъв начин да се говори за композиция на функции, ако разсъждаваме на семантично ниво, или за схема от функц. елементи, ако сме на по-ниско ниво. Но, формално, не е решение просто да се каже "ако пуснем единици на входовете, няма как да получим 0". На КОИ входове? Също така, критерият па Пост не е доказван на лекции и който го ползва, трябва и да го докаже.
-- ММ