A method for the automated generation of proof exercises with comparable levels of proving complexity

Dit artikel presenteert een methode voor het automatisch genereren van bewoefsoefeningen met vergelijkbare complexiteit, waarbij de moeilijkheidsgraad wordt bepaald op basis van informele bewijsinspanning die formeel wordt vastgelegd via cut-gebaseerde tableau-bewijzen zonder logische symbolen.

De kern

Stel je voor dat je een leraar wiskunde bent. Je moet elke week nieuwe oefeningen bedenken voor je studenten. Het probleem? Het kost ontzettend veel tijd om die oefeningen zelf te maken, en nog moeilijker is het om te zorgen dat ze allemaal even moeilijk zijn. Als je een oefening te makkelijk maakt, vervelen de studenten zich; is hij te moeilijk, dan raken ze gefrustreerd.

Deze paper beschrijft een slimme manier om een computer te leren om automatisch wiskundepuzzels te maken die precies even moeilijk zijn als een voorbeeld dat jij geeft.

Hier is hoe dat werkt, vertaald naar alledaagse taal:

1. Het probleem: "Moeilijkheid" is lastig te meten

Tot nu toe probeerden computers de moeilijkheidsgraad te meten door te tellen hoeveel symbolen er in een vraag staan (bijvoorbeeld: "Hoeveel keer komt het woord 'en' voor?").

• De analogie: Dit is alsof je de moeilijkheid van een film meet door te tellen hoeveel seconden hij duurt. Een korte film kan een ramp zijn om te begrijpen, en een lange film kan heel simpel zijn. Het aantal symbolen zegt niets over hoe moeilijk het is om de oplossing te vinden.

2. De oplossing: Kijk naar de "bouwtekening" van het antwoord

De auteurs zeggen: "Laten we niet kijken naar de vraag zelf, maar naar de stappen die je nodig hebt om het antwoord te vinden."

Ze gebruiken een methode die lijkt op het oplossen van een logische puzzel met een speciale set regels (zoals een LEGO-instructieboekje).

• De analogie: Stel je voor dat je een huis moet bouwen.
  • Oefening A vereist: "Leg 3 bakstenen, leg 1 dakpan."
  • Oefening B vereist: "Leg 3 bakstenen, leg 1 dakpan."
  • Zelfs als de bakstenen een andere kleur hebben of de dakpan een andere vorm, is de bouwpoging (de moeite die je doet) precies hetzelfde. De computer kijkt dus niet naar de kleur van de bakstenen, maar naar het aantal stappen en de structuur van het bouwproces.

3. Hoe werkt de computer? (De "Magische Regels")

De computer heeft een voorraad met "wiskundige wetten" (bijvoorbeeld uit de verzamelingenleer: "Als iets in een doos zit, zit het ook in een grotere doos").

1. De Input: Jij geeft de computer één voorbeeldvraag en het bewijs (de oplossing).
2. De Analyse: De computer kijkt naar de oplossing en maakt een "bouwtekening" (een boomdiagram) van alle stappen die nodig waren. Hij telt hoe complex die boom is.
3. De Creatie: De computer gaat op zoek naar nieuwe vragen. Hij vervangt de woorden in je voorbeeldvraag door andere woorden, maar alleen als de nieuwe vraag dezelfde "bouwtekening" heeft.
   • Voorbeeld: Als je vraag was "Bewijs dat een appel in een mand zit", kan de computer een nieuwe vraag maken: "Bewijs dat een auto in een garage zit".
   • De computer zorgt ervoor dat de logische stappen om van "appel" naar "mand" te gaan, exact hetzelfde zijn als van "auto" naar "garage".

4. Waarom is dit speciaal?

De meeste AI-tools die vragen maken, gokken op moeilijkheid of gebruiken menselijke beoordelingen (wat vaak onbetrouwbaar is). Deze methode is puur wiskundig en logisch.

• De analogie: Het is alsof je een machine hebt die niet vraagt "Is dit moeilijk?", maar die zegt: "Ik heb net 5 stappen nodig om dit op te lossen. Ik ga nu een nieuwe vraag maken die ook precies 5 stappen nodig heeft, maar dan met andere woorden."

5. Wat levert dit op?

Leraars kunnen nu één goede, moeilijke oefening bedenken. De computer genereert vervolgens tientallen variaties daarvan.

• De leraar krijgt een lijst met vragen die garanderen dat ze even zwaar zijn voor de hersenen van de student.
• Dit maakt het mogelijk om een "adaptieve test" te maken: als een student een vraag goed heeft, krijgt hij de volgende vraag die even moeilijk is, maar net iets anders. Als hij faalt, krijgt hij een vraag met dezelfde structuur maar misschien iets anders geformuleerd, zodat de leraar precies kan zien waar het misgaat.

Samenvatting

Deze paper introduceert een slimme "recept-generator" voor wiskundevragen. In plaats van te raden hoe moeilijk een vraag is, kijkt de computer naar de bouwtekening van de oplossing. Als twee vragen dezelfde bouwtekening hebben, zijn ze even moeilijk. Hierdoor kunnen leraren eindeloos veel oefeningen maken die perfect op elkaar aansluiten qua niveau, zonder urenlang zelf te hoeven rekenen.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "A method for the automated generation of proof exercises with comparable levels of proving complexity" in het Nederlands.

Probleemstelling

Automatische vraaggeneratie (Automatic Question Generation - AQG) kan docenten aanzienlijk tijd besparen bij het ontwerpen van oefeningen. Een groot obstakel voor de integratie van deze automatisering in het onderwijs is echter de beperkte mogelijkheid om de moeilijkheidsgraad van gegenereerde oefeningen nauwkeurig te controleren.
Bestaande AQG-systemen vertrouwen vaak op:

1. Syntactische parameters: Aantal symbolen, diepte van formules of aantal connectieven. Dit is problematisch omdat twee formules met dezelfde syntactische structuur zeer verschillende bewijscomplexiteiten kunnen hebben.
2. Machine Learning-modellen: Deze voorspellen moeilijkheid op basis van menselijke classificaties, wat leidt tot inconsistenties (experts zijn het oneens) en gebrek aan uitlegbaarheid.

Er is een dringende behoefte aan een methode die de moeilijkheidsgraad van wiskundige bewijsoefeningen (specifiek in de eerste-orde logica) bepaalt op basis van de effort die nodig is om ze op te lossen, in plaats van alleen op de oppervlakkige structuur van de vraag.

Methodologie

De auteurs stellen een methode voor die bewijsoefeningen genereert met vergelijkbare niveaus van "bewijscomplexiteit" (proving complexity). De aanpak bestaat uit de volgende kerncomponenten:

1. Theorie-specifieke Tableau-proeven (Cut-based)
In plaats van standaard logische bewijzen te gebruiken, maken de auteurs gebruik van theorie-specifieke tableaux.

• Logische symbolen: De bewijzen bevatten geen logische symbolen (zoals $\land, \lor, \neg, \forall, \exists$) in de knopen. In plaats daarvan worden alleen "theorie-specifieke formules" (atomaire formules) gebruikt.
• Regels: De uitbreidingsregels worden mechanisch geëxtraheerd uit definitional axioma's van een wiskundige theorie (bijv. Zeteltheorie of Getaltheorie).
• Analyticiteit: De regels voldoen aan strikte analytische beperkingen (variabelen en predikaten moeten afnemen in complexiteit of diepte), wat zorgt voor een eindige en beheersbare bewijsruimte.
• Cut-methode: Er wordt een "cut-based" aanpak gebruikt (gebaseerd op de KE-methodologie), waarbij de "cut-formule" een subformule is van een reeds aanwezige formule. Dit zorgt voor een polynomiale simulatie van waarheidstabellen en betere controle over de bewijsuitbreiding dan traditionele Smullyan-style tableaux.

2. Formalisering van Complexiteit
De complexiteit van een oefening wordt niet gemeten aan de hand van de vraagtekst, maar aan de hand van de minimale bewijsstructuur:

• Isomorfisme: Twee oefeningen hebben een vergelijkbare complexiteit als hun minimale bewijzen deductief isomorf zijn. Dit betekent dat de "justification trees" (de boomstructuur die aangeeft welke regels welke stellingen rechtvaardigen) identiek zijn in vorm, zelfs als de specifieke symbolen verschillen.
• Deductieve grootte: De complexiteit wordt gekwantificeerd door het aantal knopen in de justification tree.

3. Het Generatie-algoritme
Het proces verloopt in twee hoofdstappen:

• Stap 1: Zoeken naar minimale bewijzen. Gegeven een invoer-oefening (een verzameling gesigneerde formules), zoekt het systeem naar alle minimale bewijzen (kleinste deductieve grootte) binnen het systeem van theorie-specifieke regels.
• Stap 2: Zoeken naar bewijs-isomorfe sets. Het systeem genereert nieuwe sets van gesigneerde formules die een bewijs hebben dat deductief isomorf is met het minimale bewijs van de invoer-oefening.
  • Dit gebeurt door symbolen (predikaten en functies) in de invoerformules te vervangen door andere symbolen uit dezelfde theorie, maar alleen als deze vervangingen "deductief matchen" met de regels die in het originele bewijs zijn gebruikt.
  • Dit beperkt de zoekruimte aanzienlijk en garandeert dat de gegenereerde oefeningen inderdaad dezelfde bewijsstrategie vereisen.

Belangrijkste Bijdragen

1. Nieuwe definitie van Complexiteit: De paper introduceert een formele, op bewijs gebaseerde definitie van moeilijkheidsgraad die losstaat van menselijke subjectiviteit en syntactische oppervlakken.
2. Mechanische Regel-extractie: Een procedure om uit definitional axioma's een set van lineaire, theorie-specifieke regels te extraheren die vrij zijn van logische symbolen.
3. Concept van Deductief Isomorfisme: Een methode om te bepalen wanneer twee verschillende wiskundige stellingen structureel hetzelfde bewijs vereisen, gebaseerd op de isomorfie van hun justification trees.
4. Implementatie: Een werkend prototype (beschikbaar via GitHub) dat bewijsoefeningen genereert voor de Set-theorie, waarbij de output oefeningen zijn die qua complexiteit gelijkwaardig zijn aan de invoer.

Resultaten

• De methode slaagt erin om sets van bewijsoefeningen te genereren die deductief isomorf zijn met een gegeven voorbeeld.
• Voorbeeld: Als de invoer is "Bewijs dat $x \in y \cap (w \cup z)$ impliceert $x \in (y \cap w) \cup z$", genereert het systeem oefeningen zoals "Bewijs dat $x \in y \setminus (w \triangle z)$ impliceert $x \in (y \setminus w) \cup z$".
• Hoewel de symbolen ($\cap, \cup, \setminus, \triangle$) verschillen, vereisen beide oefeningen exact dezelfde reeks bewijsstappen (dezelfde regels in dezelfde volgorde), wat betekent dat ze voor de student even moeilijk zouden moeten zijn.
• De zoekruimte voor kandidaat-oefeningen wordt drastisch verkleind door alleen symbolen te toestaan die deductief matchen met de regels van het originele bewijs.

Significantie en Toekomstperspectief

• Pedagogische Toepassing: Docenten kunnen nu oefeningen genereren die perfect aansluiten bij het niveau van de studenten, zonder dat ze handmatig complexe bewijzen hoeven te ontwerpen. Dit ondersteunt adaptief leren en gepersonaliseerde assessments.
• Uitlegbaarheid: In tegenstelling tot ML-modellen, biedt deze methode een transparante reden voor de moeilijkheidsgraad: de structuur van het minimale bewijs.
• Beperkingen en Toekomst:
  • De methode werkt momenteel alleen voor oefeningen die kunnen worden vertaald naar een specifieke normaalvorm (STSNF).
  • De auteurs plannen om de restricties op de axioma's te versoepelen en de methode uit te breiden naar meer theorieën.
  • Er is plannen voor empirisch onderzoek om te valideren of studenten inderdaad oefeningen met "deductief isomorfe" bewijzen als even moeilijk ervaren, zelfs als de specifieke regels (bijv. meerpremise regels) variëren.

Kortom, dit paper biedt een robuuste, logisch gefundeerde oplossing voor het probleem van het controleren van de moeilijkheidsgraad in automatisch gegenereerde wiskundige oefeningen, door de focus te verleggen van de vraagtekst naar de onderliggende bewijsstructuur.