Sto studiando per un esame e mi sono imbattuto in due esercizi che non so come risolvere:
1) Considerare formule generate dalla sintassi
F::=⊥|¬F|F∧F|F∨F
Definire per ricorsione strutturale una funzione c(F) che ritorni true sse tutte le negazioni occorrono come sottoformule di almeno una congiunzione.
Esempio:
c(¬(⊥∧⊥)) = false
c(⊥∧(⊥∨¬⊥)) = true
Qui il grande dubbio è: come faccio, dopo aver appurato che c'è una congiunzione, vedere se c'è anche la negazione nelle sue sottoproduzioni immediate?
2) Considerare le liste di numeri naturali definite dalla grammatica
L::= [] | N::L
dove [] rappresenta la lista vuota e N::L la lista con il naturale N in testa e L come coda. Scrivere una funzione f(L) che ordini la lista L usando esclusivamente ricorsione strutturale. Come al solito, è possibile usare funzioni ausiliarie purchè definite anch’esse per ricorsione strutturale.
Come posso scorrere la lista ed ordinarla?
Grazie