Form for vedlegg

En formel for førsteordens logikk er i vedleggsform hvis alle dens kvantifiserere ( og ) vises til venstre i den formelen. Det vil si at G er i forhåndsvedlagt form hvis og bare hvis med og en formel uten kvantifiserere. $\ for alle$ $\ eksisterer$ ${\ displaystyle G = Q_ {1} x_ {1} Q_ {2} x_ {2} ... Q_ {n} x_ {n} G ^ {\ prime}}$ ${\ displaystyle Q_ {i} \ i \ {\ forall, \ eksisterer \}}$ $G ^ {{\ prime}}$

Alle førsteordensformler er logisk ekvivalente med en formel i vedleggsform.

Den kompleksiteten av en forhåndsformatert logikk formel måles ved dens første kvantifikator og antallet på en alternerende blokker av universelle eller eksistensielle quantifiers som følger den og går forut formelen uten en kvantifiserings.

Transformasjonsregler

For å sette en logisk formel i vedleggsform, kan vi bruke følgende transformasjonsregler mellom tilsvarende formler: ${\ displaystyle Left \ Rightarrow Right}$

#	Opprinnelig form	Form for vedlegg
1	${\ displaystyle \ lnot \ forall xF}$	${\ displaystyle \ eksisterer x \ lnot F}$
2	${\ displaystyle (\ forall xF) \ land G}$	${\ displaystyle \ forall x (F \ land G)}$
3	${\ displaystyle (\ forall xF) \ lor G}$	${\ displaystyle \ forall x (F \ lor G)}$
4	${\ displaystyle (\ forall xF) \ rightarrow G}$	${\ displaystyle \ eksisterer x (F \ rightarrow G)}$
5	${\ displaystyle G \ land (\ forall xF)}$	${\ displaystyle \ forall x (G \ land F)}$
6	${\ displaystyle G \ lor (\ forall xF)}$	${\ displaystyle \ forall x (G \ lor F)}$
7	${\ displaystyle G \ rightarrow (\ forall xF)}$	${\ displaystyle \ forall x (G \ rightarrow F)}$
8	${\ displaystyle \ lnot \ eksisterer xF}$	${\ displaystyle \ forall x \ lnot F}$
9	${\ displaystyle (\ exist xF) \ land G}$	${\ displaystyle \ eksisterer x (F \ land G)}$
10	${\ displaystyle (\ exist xF) \ l G)$	${\ displaystyle \ eksisterer x (F \ lor G)}$
11	${\ displaystyle (\ exist xF) \ rightarrow G}$	${\ displaystyle \ forall x (F \ rightarrow G)}$
12	${\ displaystyle G \ land (\ existerer xF)}$	${\ displaystyle \ eksisterer x (G \ land F)}$
1. 3	${\ displaystyle G \ lor (\ existerer xF)}$	${\ displaystyle \ eksisterer x (G \ lor F)}$
14	${\ displaystyle G \ rightarrow (\ exist xF)}$	${\ displaystyle \ eksisterer x (G \ rightarrow F)}$

Variabelen x må ikke ha noen fri forekomst i G (se Beregne predikater ). Ellers endre navn på x på forhånd med en ny variabel som ikke vises fritt i formlene F og G.

Merknader

Det er ingen enkle transformasjonsregler for en formel inkludert koblingen, men disse reglene er tilstrekkelige fordi det er et komplett system med kontakter. For å transformere en formel kan vi derfor bruke denne tilnærmingen: ${\ displaystyle \ leftrightarrow}$ ${\ displaystyle \ {\ lnot, \ land, \ lor, \ rightarrow \}}$

Fjern ekvivalenser, og erstatt dem med implikasjoner;
Transportnegasjoner foran atomformler;
Bær kvantifisererne til hodet på formelen, og gi navn om variablene om nødvendig.

Relaterte artikler