(* =========================================================================================== *)
(* Übung 1, Aufgabe 2:                                                                         *)
(*                                                                                             *)
(* Zur Erinnerung: Eine Menge A heißt entscheidbar, wenn ihre charakteristische Funktion c_A   *)
(* berechenbar ist. Also lassen sich genau die entscheidbaren Mengen durch "Ausprogrammieren"  *)
(* ihrer charakteristischen Funktionen implementieren. Die Implementierung einer Mengenopera-  *)
(* tion (Teilaufgaben b, c und d) zeigt dann, dass die Klasse der entscheidbaren Mengen unter  *)
(* dieser Operation abgeschlossen ist. Also kann die Funktion image in Teilaufgabe f nicht im- *)
(* plementierbar sein, weil das Bild einer entscheidbaren Menge unter einer totalen berechen-  *)
(* baren Funktion im allgemeinen NICHT entscheidbar ist.                                       *)
(*                                                                                             *)
(* Die Funktion is_empty in Teilaufgabe d ist wohl auch nicht implementierbar, denn man müsste *)
(* ja alle Elemente durchprobieren, um mit Sicherheit behaupten zu können, dass die Menge leer *)
(* ist. Eine saubere Begründung im Sinne der Berechenbarkeitstheorie fehlt mir aber noch.      *)
(* =========================================================================================== *)

(* ------------------------------------------------------------------------------------------- *)
(* Übung 1, Aufgabe 2 a:                                                                       *)
(* a liegt in A <=> c_A (a) = 1                                                                *)
(* ------------------------------------------------------------------------------------------- *)

let member a c_A = c_A a = 1;;

(* ------------------------------------------------------------------------------------------- *)
(* Übung 1, Aufgabe 2 b:                                                                       *)
(* a liegt im Komplement von A <=> c_A (a) = 0 <=> 1 - c_A (a) = 1                             *)
(* ------------------------------------------------------------------------------------------- *)

let complement c_A = fun a -> if c_A a = 0 then 1 else 0;;

(* ------------------------------------------------------------------------------------------- *)
(* Übung 1, Aufgabe 2 c:                                                                       *)
(* a liegt in der Vereinigung von A und B <=> c_A (a) = 1 oder c_B (a) = 1                     *)
(* a liegt im Durchschnitt von A und B <=> c_A (a) = 1 und c_B (a) = 1                         *)
(* a liegt in der Differenz von A und B <=> c_A (a) = 1 und c_B (a) = 0                        *)
(*                                                                                             *)
(* Im folgenden werden die Schreibweisen || und && benutzt, die sich wie folgt als syntakti-   *)
(* scher Zucker auffassen lassen:                                                              *)
(*  e_1 || e_2   steht für   if e_1 then true else e_2                                         *)
(*  e_1 && e_2   steht für   if e_1 then e_2 else false                                        *)
(* Natürlich kann man stattdessen auch mit geschachtelten bedingten Ausdrücken arbeiten.       *)
(* ------------------------------------------------------------------------------------------- *)

let union c_A c_B = 
  fun a -> if c_A a = 1 || c_B a = 1 then 1 else 0;;

let intersection c_A c_B = 
  fun a -> if c_A a = 1 && c_B a = 1 then 1 else 0;;

let difference c_A c_B = 
  fun a -> if c_A a = 1 && c_B a = 0 then 1 else 0;;

(* ------------------------------------------------------------------------------------------- *)
(* Übung 1, Aufgabe 2 e:                                                                       *)
(* a liegt in f^-1 (A) <=> f(a) liegt in A <=> c_A (f (a)) = 1                                 *)
(* ------------------------------------------------------------------------------------------- *)

let preimage f c_A = 
  fun a -> c_A (f a);;

(* ------------------------------------------------------------------------------------------- *)
(* PS: Manche Teilaufgaben lassen sich natürlich trickreicher (aber nicht unbedingt verständ-  *)
(* licher) lösen, indem man geschickt mit den Zahlen 0 und 1 rechnet, etwa:                    *)
(* ------------------------------------------------------------------------------------------- *)

let complement c_A = fun a -> 1 - c_A a;;

let intersection c_A c_B = fun a -> c_A a * c_B a;;