Règle structurale

Dans la théorie de preuve de , une règle structurale est une règle d'inférence qui ne se rapporte à aucun logique connectif, mais opère à la place les jugements ou le Sequents directement. L'imitateur structural de règles souvent a prévu les propriétés méta-théorétiques de la logique. Des logiques qui nient un ou plusieurs des règles structurales sont classifiées comme logiques substructurales

Règles structurales générales

affaiblissant , où les hypothèses ou la conclusion d'un Sequent peuvent être prolongées avec les membres supplémentaires. En forme symbolique des règles de affaiblissement peuvent être écrites comme

\ frac {\ gamma \ vdash \ sigma} {\ gamma, A \ vdash \ sigma}

du côté gauche du tourniquet , et, de

\ frac {\ gamma \ vdash \ sigma} {\ gamma \ vdash A \ sigma}

du côté droit.
Contraction , où deux membres d'égale (ou unifiable) du même côté d'un Sequent peuvent être remplacés par un membre simple (ou exemple commun). Symboliquement :

, A, A \ vdash \ sigma} {\ gamma, A \ vdash \ sigma}

et, de

\ frac {\ gamma \ vdash A, d'A \ sigma} {\ gamma \ vdash A \ sigma}

. Également connu comme factorisant dans le théorème automatisé par prouvant des systèmes de using la résolution .
Échange , où deux membres du même côté d'un Sequent peuvent être permutés. Symboliquement :

\ frac {\, de Gamma_1, d'A \, de Gamma_2, de B \ Gamma_3 \ vdash \ sigma} {\, de Gamma_1, de B \, de Gamma_2, d'A \ Gamma_3 \ vdash \ sigma}

\ frac {\ gamma \ vdash \, de Sigma_1, d'A \, de Sigma_2, de B \ Sigma_3} {\ gamma \ vdash \, de Sigma_1, de B \, de Sigma_2, d'A \ Sigma_3}

. (Ceci est également connu comme règle de permutation de .)

Une logique sans l'un des au-dessus des règles structurales interpréterait les côtés d'un sequent comme le pur ordonnance avec l'échange, ils sont les multi-ensembles et avec la contraction et l'échange ils sont les ensembles

Une règle structurale célèbre est connue comme le de a coupé . L'effort considérable est consacré par des théoriciens de preuve en prouvant que les règles de coupe sont superflues dans diverses logiques. Plus avec précision, ce qui est montré est que la coupe est seulement (dans une certaine mesure) un outil pour l'abrégement des preuves, et n'ajoute pas aux théorèmes qui peuvent être prouvés. Le « déplacement » réussi des règles coupées, connu sous le nom de a coupé l'élimination , est directement lié à la philosophie du calcul comme normalisation (voir le calcul du lambda) ; il donne souvent une bonne indication de la complexité du décidant une logique donnée.

Voir également

Logique substructurale
Logique linéaire
Le affinent la logique
Logique stricte
Logique commandée par

Random links: