Univerzální generalizace - Universal generalization

v predikátová logika, zobecnění (taky univerzální generalizace nebo univerzální úvod,^[1][2][3] GEN) je platný pravidlo odvození. Uvádí se v něm, že pokud ${ displaystyle vdash ! P (x)}$ byl tedy odvozen ${ displaystyle vdash ! forall x , P (x)}$ lze odvodit.

Zobecnění s hypotézami

Pravidlo úplného zobecnění umožňuje hypotézy nalevo od turniket, ale s omezeními. Převzít ${ displaystyle Gamma}$ je sada vzorců, ${ displaystyle varphi}$ vzorec a ${ displaystyle Gamma vdash varphi (y)}$ bylo odvozeno. Zobecňovací pravidlo to říká ${ Displaystyle Gamma vdash pro všechny x , varphi (x)}$ lze odvodit, pokud ${ displaystyle y}$ není zmíněn v ${ displaystyle Gamma}$ a ${ displaystyle x}$ nevyskytuje se v ${ displaystyle varphi}$.

Tato omezení jsou nezbytná pro spolehlivost. Bez prvního omezení by se dalo usoudit ${ displaystyle pro všechny xP (x)}$ z hypotézy ${ displaystyle P (y)}$. Bez druhého omezení by bylo možné provést následující odpočet:

1. ${ displaystyle existuje z , existuje w , (z not = w)}$ (Hypotéza)
2. ${ displaystyle existuje w , (y ne = w)}$ (Existenční instance)
3. ${ displaystyle y not = x}$ (Existenční instance)
4. ${ displaystyle forall x , (x not = x)}$ (Chybné univerzální zobecnění)

Toto to má ukázat ${ Displaystyle existuje z , existuje w , (z not = w) vdash forall x , (x not = x),}$ což je nezdravý odpočet. Všimněte si, že ${ Displaystyle Gamma vdash pro všechny y , varphi (y)}$je přípustné, pokud ${ displaystyle y}$ není zmíněn v ${ displaystyle Gamma}$ (druhé omezení nemusí platit, protože sémantická struktura ${ displaystyle varphi (y)}$se nemění nahrazením žádných proměnných).

Příklad dokladu

Dokázat: ${ displaystyle forall x , (P (x) rightarrow Q (x)) rightarrow ( forall x , P (x) rightarrow forall x , Q (x))}$ lze odvodit z ${ displaystyle forall x , (P (x) rightarrow Q (x))}$ a ${ displaystyle forall x , P (x)}$.

Důkaz:

Číslo	Vzorec	Odůvodnění
1	${ displaystyle forall x , (P (x) rightarrow Q (x))}$	Hypotéza
2	${ displaystyle forall x , P (x)}$	Hypotéza
3	${ displaystyle ( forall x , (P (x) rightarrow Q (x))) rightarrow (P (y) rightarrow Q (y)))}$	Univerzální instance
4	${ displaystyle P (y) pravá šipka Q (y)}$	Od (1) a (3) o Modus ponens
5	${ displaystyle ( forall x , P (x)) rightarrow P (y)}$	Univerzální instance
6	${ displaystyle P (y) }$	Z (2) a (5) o Modus ponens
7	${ displaystyle Q (y) }$	Z (6) a (4) o Modus ponens
8	${ displaystyle forall x , Q (x)}$	Od (7) zobecněním
9	${ displaystyle forall x , (P (x) rightarrow Q (x)), forall x , P (x) vdash forall x , Q (x)}$	Souhrn (1) až (8)
10	${ displaystyle forall x , (P (x) rightarrow Q (x)) vdash forall x , P (x) rightarrow forall x , Q (x)}$	Od (9) od Věta o dedukci
11	${ Displaystyle vdash forall x , (P (x) rightarrow Q (x)) rightarrow ( forall x , P (x) rightarrow forall x , Q (x))}$	Od (10) od Věta o dedukci

V tomto důkazu byla v kroku 8 použita univerzální generalizace teorém o dedukci bylo použitelné v krocích 10 a 11, protože přesouvané vzorce nemají žádné volné proměnné.

Viz také

• Logika prvního řádu
• Unáhlené zobecnění
• Univerzální instance

Reference