TAPL: Explication et exemple (s) pour satisfaire

Question

Cette question découle de ma lecture de "Types et langages de programmation" ( WorldCat ) par Benjamin C. Pierce.

A la page 36 est la définition pour satisfait

Une règle est satisfait par une relation si, pour chaque instance de la règle, soit la conclusion est dans la relation ou l'un des lieux est pas.

A la page 36 est la définition de par exemple

An instance d'une règle d'inférence est obtenue en remplaçant systématiquement chaque metavariable par le même terme dans la conclusion de la règle et toute sa locaux (le cas échéant).

Par exemple

if true then true else (if false then false else false) -> true

est une instance de E-ifTrue , où les deux occurrences de t_2 $ $ ont été remplacé par true et T_3 $ $ a été remplacé par if false then false else false.

A la page 15 est la définition pour relataion

Un n-lieu relation sur une collection de jeux S_1 $, S_2, ..., S_n $ est R $ set \ subseteq S_1 \ times \; s_2 \; \ times \; ... \; \ times \; S_n $ de tuples des éléments de $ S_1 $ à $ S_n $. Nous disons que les éléments $ s_1 \ en > S_1 $ répercutant $ s_n \ dans S_n $ sont liés par $ R $ si $ (s_1, ..., s_n) $ est un élément ou $ R $.

A la page 36 est la définition pour une étape par rapport d'évaluation ($ \ rightarrow $)

une étape par rapport d'évaluation $ \ rightarrow $ est la plus petite relation binaire des conditions satisfaisant les trois règles de la figure 3-1. Lorsque la paire $ (t, t ') $ est dans la relation d'évaluation, nous disons que « le déclaration d'évaluation (ou jugement) $ t \ rightarrow t '$ est dérivable. "

A la page 34 sont les trois règles de la figure 3-1

E-ifTrue

\ begin {equation} if \; true \, puis \; t_2 \; else \; T_3 \; \ rightarrow \; t_2 \ end {equation}

E-ifFalse

\ begin {equation} si \; false \, puis \; t_2 \; else \; T_3 \; \ rightarrow \; t_2 \ end {equation}

E-IF

\ begin {equation} \ frac {t_1 \ rightarrow \; t_1 '} {if \; t_1 \, puis \; t_2 \; else \; T_3 \; \ rightarrow \, si \; t_1 \, puis \; t_2 \; else \; T_3} \ end {equation}

Quelqu'un peut-il expliquer cette définition et de donner un exemple pour certaines parties du défintion.
1. La conclusion est dans la relation.
2. L'un des locaux n'est pas.

Note: Je suis conscient qu'il ya un forum dédié aux questions pour le livre .

Remarque:. Vous pouvez utiliser Google Scholar pour voir plus de détails à cette question dans le contexte

EDIT

Pour connecter quelques-uns des points sur mon commentaire concernant l'unification et de réécriture.

Quand j'ai vu

$$ (A \ rightarrow B) \ equiv (\ neg A \ vee B) $$

il m'a rappelé claues Corne Prolog , qui, avec l'exemple alors connecté à ma compréhension de la réécriture . Avoir le livre " Réécriture et All That " (< a href = "http://www.worldcat.org/title/term-rewriting-and-all-that/oclc/37315354&referer=brief_results" rel = "nofollow"> WorldCat ) par Franz Baader et Tobias Nipkow , je me suis vite regardé satisfiability et trouvé satisfiable à la page 58. Ceci est en fait le début du chapitre sur équationnel problèmes; mais il a également des couvertures unification À ce moment-là, je compris que la définition avait affaire à satisfiabilité et de là est était un sujet que je connaissais déjà. ce qui m'a jeté était le chemin Benjamin a défini. il a utilisé un droit de définition très précise à l'avant d'une manière que je ne l'ai pas associé à ma connaissance.

Si vous travaillez dans le code comme je suis et je comprends la programmation logique, la définition prend tout son sens.

Answer 1

Une façon de lire la définition de satisfait qui pourrait aider est de changer

Une règle est satisfaite par une relation si, pour chaque instance de la règle, que ce soit la conclusion est dans la relation ou l'un des locaux n'est pas.

à la déclaration logiquement équivalent

Une règle est satisfaite par une relation si, pour chaque instance de la règle, si tous les locaux sont dans la relation, la conclusion est dans la relation.

Ainsi, si la règle dit, par exemple,

$$ \ Dfrac {A \ B de B quad \ à C} {A \ à C} $$

Ensuite relation binaire $ R satisfait $ cette règle chaque fois pour chaque instance de la règle, comme

$$ \ Dfrac {a \ b à \ quad b \ à c} {A \ à c} $$

if $ (a, b) \ dans R $ et $ (b, c) \ dans R $, alors $ (a, c) \ dans R $.

Une autre façon de dire est que $ R $ est fermée par la règle (bien que cela ne probablement pas plus clair).

Maintenant, nous allons revenir à la déclaration originale. Qu'est-ce que

Une règle est satisfaite par une relation si, pour chaque instance de la règle, que ce soit la conclusion est dans la relation ou l'un des locaux n'est pas.

est de dire est qu'il est normal d'avoir $ (a, c) $ dans la relation sans les locaux, mais si tous les locaux sont dans la relation, puis $ (a, c) $ doit être. Autrement dit, il est normal de ne pas avoir tous les locaux dans la relation, sans imposer aucune contrainte supplémentaire.

Personnellement, je pense que la réflexion sur cette définition en termes d'implication est plus simple, donc j'aide cette explication aide.

Answer 2

Comme Dave Clarke a souligné la définition de satisfait est en fait une implication, rappelez-vous dans la logique propositionnelle: $$ (A \ rightarrow B) \ equiv (\ neg A \ vee B) $$

est pas un hasard, les règles d'inférence sont également utilisées pour définir prouvable dans la logique formelle.

---

Exemple de E-ifTrue :

prémisse (s):

• Il n'y a pas prémisse, cette règle est un axiome (ou plutôt un ensemble d'axiomes pour tous les termes $ t_2 $, $ T_3 $).

conclusion:

• la paire $ ($ if true then true else (if false then false else false) $, $ true $) $

La règle E-ifTrue n'a pas de locaux, tous des locaux sont tout rapport tous par exemple. Ainsi, une relation $ R $ satisfaire cette règle doit contenir les conclusions de toutes les instances, à savoir toutes les paires de termes $ (t, t ') $ tel que $ t' peut être dérivé $ de $ t $ en utilisant E-ifTrue . Donc,

$ \ {($ if true then true else false $, $ true $), ($ if true then false else false $, $ false $), ($ if true then false else true $, $ false $), \ points \} \ Subseteq R $.

---

Exemple pour une instance E-IF :

prémisse (s):

• la paire $ ($ if true then false else true $, $ false $) $

conclusion:

• la paire $ ($ if (if true then false else true) then true else false $, $ if true then true else false $) $

Ici, nous avons deux choix pour satisfaire une règle $ R $: Soit nous laissons $ ($ if true then false else true $, $ false $) $ ou nous avons aussi inclure $ ($ if (if true then false else true) then true else false $, $ if true then true else false $) $. Mais en fait, laissant la prémisse est pas une option, puisque la relation d'évaluation doit satisfaire E-ifTrue trop et cette règle exige l'inclusion de $ ($ if true then false else true $, $ false $) $.

---

Comme Dave Clarke a souligné qu'il peut contenir d'autres paires non requis par l'une des règles. Cela doit être autorisé pour chaque règle unique parce que nous voulons une relation d'évaluation de la satisfaire plusieurs règles. En choisissant la relation minimale, nous veillons à ce que ce n'est pas possible de termes Derive pas capturés par aucune règle.