Uniwersalne uogólnienie - Universal generalization

W kwantyfikatorów logicznych , uogólnienie (również uniwersalny uogólnieniem lub uniwersalny wprowadzenie , GEN ) jest ważna reguła wnioskowania . Stwierdza, że ​​jeśli zostało wyprowadzone, to można wyprowadzić. ${\ Displaystyle \ vdash \! P (x)}$${\displaystyle \vdash \!\forall x\,p(x)}$

Uogólnienie z hipotezami

Pełna reguła generalizacji dopuszcza hipotezy po lewej stronie kołowrotu , ale z ograniczeniami. Załóżmy, że to zestaw formuł, formuła i została wyprowadzona. Reguła uogólnienia określa, że można je wyprowadzić, jeśli nie jest wymienione w i nie występuje w . ${\ Displaystyle \ Gamma}$${\displaystyle \varphi}$${\ Displaystyle \ Gamma \ vdash \ varphi (y)}$${\ Displaystyle \ Gamma \ vdash \ forall x \ \ varphi (x)}$${\displaystyle y}$${\ Displaystyle \ Gamma}$${\displaystyle x}$${\displaystyle \varphi}$

Ograniczenia te są konieczne dla zachowania zdrowej kondycji. Bez pierwszego ograniczenia można by wywnioskować z hipotezy . Bez drugiego ograniczenia można by dokonać następującego potrącenia: ${\ Displaystyle \ forall xP (x)}$${\ Displaystyle P (y)}$

1. ${\ Displaystyle \ istnieje z \, \ istnieje w \, (z \ nie = w)}$ (Hipoteza)
2. ${\ Displaystyle \ istnieje w \, (y \ nie = w)}$ (Instancja egzystencjalna)
3. ${\ Displaystyle y \ nie = x}$ (Instancja egzystencjalna)
4. ${\displaystyle \forall x\,(x\nie =x)}$ (Wadliwe uniwersalne uogólnienie)

Ma to na celu pokazanie tego, co jest nierozsądną dedukcją. Zauważ, że jest to dopuszczalne, jeśli nie jest wymienione w (drugie ograniczenie nie musi mieć zastosowania, ponieważ struktura semantyczna nie jest zmieniana przez podstawienie jakichkolwiek zmiennych). ${\displaystyle \istnieje z\,\istnieje w\,(z\nie = w)\vdash \forall x\,(x\nie =x)}$${\ Displaystyle \ Gamma \ vdash \ forall y \ \ varphi (y)}$${\displaystyle y}$${\ Displaystyle \ Gamma}$${\ Displaystyle \ varphi (y)}$

Przykład dowodu

Udowodnić: można wyprowadzić z i . ${\displaystyle \forall x\,(P(x)\rightarrow Q(x))\rightarrow (\forall x\,p(x)\rightarrow \forall x\,Q(x))}$${\displaystyle \forall x\,(P(x)\rightarrow Q(x))}$${\displaystyle \forall x\,p(x)}$

Dowód:

Numer	Formuła	Uzasadnienie
1	${\displaystyle \forall x\,(P(x)\rightarrow Q(x))}$	Hipoteza
2	${\displaystyle \forall x\,p(x)}$	Hipoteza
3	${\displaystyle (\forall x\,(P(x)\rightarrow Q(x)))\rightarrow (P(y)\rightarrow Q(y))}$	Uniwersalna instancja
4	${\displaystyle P(y)\rightarrow Q(y)}$	Z (1) i (3) przez Modus ponens
5	${\displaystyle (\forall x\,P(x))\rightarrow P(y)}$	Uniwersalna instancja
6	${\displaystyle P(y)\}$	Od (2) i (5) przez Modus ponens
7	${\displaystyle Q(y)\}$	Od (6) i (4) przez Modus ponens
8	${\displaystyle \forall x\,Q(x)}$	Od (7) przez uogólnienie
9	${\ Displaystyle \ forall x \ (P (x) \ rightarrow Q (x)), \ forall x \ p (x) \ vdash \ forall x \ Q (x)}$	Podsumowanie od (1) do (8)
10	${\displaystyle \forall x\,(p(x)\rightarrow Q(x))\vdash \forall x\,p(x)\rightarrow \forall x\,Q(x)}$	Od (9) przez twierdzenie o dedukcji
11	${\displaystyle \vdash \forall x\,(p(x)\rightarrow Q(x))\rightarrow (\forall x\,p(x)\rightarrow \forall x\,Q(x))}$	Od (10) przez twierdzenie o dedukcji

W tym dowodzie w kroku 8 zastosowano uniwersalną generalizację. Twierdzenie o dedukcji miało zastosowanie w krokach 10 i 11, ponieważ przesuwane formuły nie mają zmiennych swobodnych.

Zobacz też

• Logika pierwszego rzędu
• Pospieszne uogólnienie
• Uniwersalna instancja

Bibliografia