12 Strukturell induksjon

Question 1

strukturell induksjon

Answer 1

Anta at en mengde er induktivt definert. For å vise at en påstand er sann for alle elementer i denne mengden, er det nok å vise følgende to punkter:

• Basissteget: Påstanden holder for alle elementer i basismengden.
• Induksjonssteget: Hvis mengden er lukket under en operasjon som gjør at x fremkommer fra x1, x2, …, xn, og påstanden holder for alle disse, holder påstanden også for x.

Hvis begge disse punktene holder, kan vi ved strukturell induksjon (eng: structural induction) konkludere med at påstanden er sann for alle elementer i mengden. Vi sier i så fall at vi beviser påstanden ved strukturell induksjon på den induktivt definerte mengden.

Question 2

substitusjon

Answer 2

La P være en utsagnsvariabel og H en utsagnslogisk formel. Vi definerer rekursivt en funksjon som bytter ut alle forekomster av P med H, og vi skriver F[P/H] for resultatet av å erstatte eller substituere alle P-er i F med H:

• F[P/H] = H når F er en utsagnsvariabel og F = P
• F[P/H] = F når F er en utsagnsvariabel og F ≠ P
• (¬F)[P/H] = ¬(F[P/H])
• (F ∘ G)[P/H] = (F[P/H] ∘ G[P/H]) når ∘ ∈ {∧, ∨, →}