Stel dat er een implicatie is van de vorm: (P(p) en P(q)) impliceert P(r) met P(x) = x zit in een bepaalde taal L. In dit voorbeeld hebben we dat p en q strings zijn in een bepaalde taal L en r = pq (de concatenatie). Gevraagd is dus om te bewijzen dat: als p en q in L zitten, dan zit pq in de taal L. Stel dat men dit met inductie wil doen, waarom is het dan voldoende om de inductie alleen over p (of alleen over q) te doen? Ik dacht dat inductie over alle variabelen moest?
Erik Jan
25-11-2021
Dat hangt een beetje van de situatie af, maar beide mogelijkheden zouden zich voor kunnen doen.
Het zou inderdaad zo kunnen zijn dat het volgende bewijsschema werkt:
"Laat $p$ een willekeurige string zijn; we bewijzen met inductie dat voor elke $q$ ook $pq$ in de taal zit."
Maar in sommige ingewikkelder situaties zou het kunnen dat je zowel inductie naar $p$ als naar $q$ moet doen. Dan krijg je dit:
"Neem aan dat voor elke string $s$ korter dan $p$ (of iets dergelijks) geldt dat voor elke $q$ ook $sq$ in de taal zit. We bewijzen nu met inductie dat voor elke $q$ ook $pq$ in de taal zit."
In het eerste geval zal alleen $p$ een rol in het bewijs spelen; in het tweede geval kun je op kortere strings terugvallen.
Het is maar net wat werkt.
Op de vraag "Waarom is het voldoende?" is het antwoord: als het bewijs goed is is het voldoende. Het hoeft niet met inductie naar $p$ maar als inductie naar $p$ handiger is zou ik het wel mooi gebruiken.
kphart
25-11-2021
#92927 - Logica - Student universiteit