Règles de déduction impliquant un ensemble $\Gamma$des locaux par rapport aux règles de déduction naturelle des manuels élémentaires. En quoi diffèrent-ils exactement?

Dec 01 2020

Dans les manuels élémentaires, les règles de déduction naturelle sont présentées de la manière suivante, par exemple pour $\&$-Introduction

de $\phi$ et $\psi$, déduire $\phi\&\psi$

ou

$(n).....\phi$

$(m)....\psi$

$\therefore$

$(p)....\phi\&\psi$.

Je voudrais savoir dans quelle mesure la manière suivante de déclarer $\&$-Intro diffère de la présentation de manuel "ordinaire" ci-dessus. La façon dont je fais référence est celle que je trouve dans la présentation de Shapiro de la logique classique (https://plato.stanford.edu/entries/logic-classical/#Dedu):

(& I) Si Γ1⊢θ et Γ2⊢ψ, alors Γ1, Γ2⊢ (θ & ψ).

(signifiant: "si $\theta$ est dérivable d'un ensemble de prémisses $\Gamma_1$ anf si $\psi$ est dérivable d'un ensemble de prémisses $\Gamma_2$, puis $(\theta\&\psi)$ est dérivable d'un ensemble de prémisses $\Gamma_1\cup\Gamma_2$. ")

La présentation de Shapiro peut-elle être qualifiée de « déduction naturelle »? Ou plutôt est-ce un cas de « calcul séquentiel» ?

A part: Connaissez-vous un manuel pour débutants sur la logique mathématique qui présente des exemples de dérivations dans le style de Shapiro?

Réponses

1 GrahamKemp Dec 04 2020 at 06:19

La règle du «manuel élémentaire» est la suivante: quand$\phi$ et $\psi$ peut être dérivée, alors nous pouvons en déduire que $\phi\mathop\&\psi$peuvent être dérivées . Il n'est pas précisé que ces dérivations ont lieu dans le même contexte (prémisses et hypothèses). Cette règle d'inférence pourrait être résumée comme$$\dfrac{~\phi\qquad\psi~}{\phi\mathop\&\psi}{\small\&\mathsf I}$$

Les règles de «calcul séquentiel» étendent cela à la liste explicite sous laquelle les éléments de contexte sont dérivés. La même règle ci-dessus peut alors être présentée avec le contexte ($\Gamma$, un ensemble d'énoncés) déclarait explicitement: $$\dfrac{~\Gamma\vdash\phi\qquad\Gamma\vdash\psi~}{\Gamma\vdash\phi\mathop\&\psi}{\small\&\mathsf I}$$

On peut alors étendre la règle pour ainsi dire: quand$\phi$ et $\psi$peut être dérivé dans des contextes$\Gamma_1$ et $\Gamma_2$respectivement, alors nous pouvons déduire que$\phi\&\psi$peut être dérivée dans le contexte uni,$\Gamma_1\cup\Gamma_2$.

$$\dfrac{~\Gamma_1\vdash\phi\qquad\Gamma_2\vdash\psi~}{\Gamma_1\cup\Gamma_2\vdash\phi\mathop\&\psi}{\small\&\mathsf I}$$


En bref: la présentation avancée dit la même chose que la présentation élémentaire, mais avec quelques détails supplémentaires ajoutés.