Przykładowe zadania

Egzamin będzie składał się z 10 dość krótkich zadań (poniżej jest ich nieco więcej). Na każde będzie trzeba odpowiedzieć na kartce z pytaniami - zwykle w kilku linijkach.

Każde zadanie będzie punktowane jednakowo oceną od 2 do 5. Punkty odpowiadają ocenie za każde zadanie. Końcowy wynik będzie odpowiadał średniej, choć przewidujemy lekkie obniżenie progów w dół (zadań będzie dużo, a czasu mało, stąd niezbędna korekta).

Oceniane będzie przede wszystkim zrozumienie, nie zaś pamięciowe opanowanie materiału. W szczególności pytania nie będą polegały na wypisaniu definicji. W związku z tym będzie wolno mieć jedną kartkę ze ściągą (format A5, tj. kartka zeszytowa) Drobne pomyłki rachunkowe będą traktowane wyrozumiale.

• Zdefiniować za pomocą definicji indukcyjnej wyrażenia arytmetyczne, gdzie operatory +, *, itp. są zastąpione przez funkcje SUMA, ILOCZYN, itp. (tj. tak jak w arkuszu kalkulacyjnym Excell).
• Przetłumaczyć na odwrotną notację polską wyrażenie arytmetyczne (x+y)*((2)+((a*b)+3))
• Pokazać, że jeśli formuła zawiera jedynie operatory alterantywy i koniunkcji i nie zawiera stałych logicznych (0,1) to jej wartość logiczna po podstawieniu 0 pod zmienne wynosi 0.
• Znaleźć formułe logiczną taką, że F(x,y,z) zachodzi wtedy i tylko wtedy, gdy x+y+z jest liczbą parzystą.
• Znaleźć błąd w następującym dowodzie w systemie hilbertowskim:
  ... i tu podany byłby dowód oraz przypomnienie aksjomatów i reguł dowodzenia.
• Czy jeśli D jest różne od D' to na pewno istnieje A takie, że
  • z D daje się udowodnić A,
  • formuła A nie daje się udowodnić z D'.
• Zapisać formułą I rzędu zdanie: jeśli funkcja nie jest różnowartościowa to jest funkcją stałą (abstrahujemy od sensowności takiego stwierdzenia).
• Zapisać rozwiązanie poprzedniego zadania w takiej formie, by wszystkie kwantyfikatory występowały w bloku na początku formuły.
• Co oznacza formuła: FORALL y EXISTS x ((FORALL x NOT(y = x+1)) => x+y=x) (FORALL oznacza kwantyfikator "dla każdego", EXISTS kwantyfikator "istnieje")
  Czy jest ona spełniona w zbiorze liczb naturalnych?
• Znaleźć model, w którym spełnione byłoby zdanie: FORALL x FORALL y FORALL z ( NOT(z=x) => ( NOT(y=z) => z=0))
• Czy rozstrzygalny jest problem: program P zatrzymuje się dla dokładnie jednej wartości danych wejściowych x ?
• Zdefiniować przy pomocy programu logicznego pojęcie SIOSTRA-CIOTECZNA, o ile zdefiniowane są pojęcia RODZIC, KOBIETA