12 Strukturell induksjon

Question 1

12.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:

• Påstanden holder for alle elementer i basismengden. Dette steget kalles basissteget.
• Hvis mengden er lukket under en operasjon som gjør at x fremkommer fra x₁, x₂, …, x_n, og påstanden holder for alle disse, holder påstanden også for x. Dette steget kalles for induksjonssteget. Antakelsen om at påstanden holder for x₁, x₂, …, x_n kalles induksjonshypotesen.

Hvis begge disse punktene holder, kan vi ved strukturell induksjon 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

12.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 ○ ∈ {∧, ∨, →}