Definició inductiva
En lògica matemàtica i computació, una definició recursiva (o definició inductiva) s'usa per definir un objecte en termes de si mateix (Aczel 1978:740ff).
Una definició recursiva d'una funció defineix els valors de la funció per algunes entrades en termes de valors de la mateixa funció donades diferents entrades. Per exemple, la funció factorial n! es defineix per les regles:
- 0! = 1.
- (n+1)! = (n+1)·n!.
Aquesta definició és vàlida perquè per tot n, la recursió sempre arriba al cas base 0. Per tant, la definició està ben fundamentada. La definició pot donar-se també com un conjunt de regles que descriuen com construir la funció n!, començant per n = 0 i avançat amb n = 1, n = 2, n = 3, etc.
Una definició inductiva d'un conjunt descriu els elements d'un conjunt en termes d'altres elements del conjunt. Per exemple, una definició del conjunt N dels nombres naturals és:
- 0 és a N.
- Si un element n és en N llavors n+1 és en N.
- N és el conjunt més petit que satisfà (1) i (2).
Hi ha molts conjunts que satisfan (1) i (2); la clàusula (3) fa la definició precisa triant el conjunt més petit que esdevé N.
Les propietats de les funcions i conjunts definides recursivament sovint poden ser provades mitjançant una inducció que segueixi la definició recursiva. Per exemple, la definició dels nombres naturals presentada abans directament implica el principi de la inducció matemàtica pels nombres naturals: si el nombre 0 té si una propietat donada, i si la mateixa propietat la té també un nombre n+1 sempre que també la tingui el nombre n, llavors la propietat donada la tenen tots els nombres naturals (Aczel 1978:742).
Formes de definicions recursives
[modifica]La majoria de definicions recursives tenen tres fonaments: un cas base, una clàusula inductiva, i una clàusula extrema.
Les diferències entre una definició circular i una definició recursiva és que la definició recursiva ha de tenir sempre casos base, casos que satisfan la definició sense ser definits en termes de la mateixa definició. En canvi, en una definició circular, pot ser que no hi hagi cas base, i es defineix el valor de la funció en termes del valor mateix, en lloc de en termes d'altres valors de la funció. Aquesta situació porta a regressions infinites.
Exemples de definicions recursives
[modifica]Nombres primers
[modifica]Els nombres primers es poden definir com:
- 2, és el nombre primer més petit;
- tot nombre sencer positiu que no és divisible per cap dels nombres primers més petit que ell.
Nombres parells no negatius
[modifica]Els nombres parells es poden definir com:
- 0 pertany al conjunt N de nombres parells no negatius (clàusula base)
- Per cada element x del conjunt N, x+2 també pertany a N (clàusula inductiva)
- Res pertany a N llevat que s'obtingui de la clàusula base o inductiva (clàusula extrema)
Fórmules ben formades
[modifica]Les definicions recursives es troben normalment en computació o en lògica. Per exemple, una fórmula ben formada (fbf) es pot definir com:
- un símbol que significa una proposició – com ara p significa "Joan és advocat."
- El símbol negació, seguit per una fbf – com ara Np significa "No és veritat que Joan és advocat."
- Qualsevol de les quatre connectives lògiques (∨, ∧, →, or ↔) relacionant dues fbf – com ara ∧ significa "les dues són veritat", per tant p∧q pot voler dir "Joan és advocat i la Maria és metgessa."