Editing First-order logic (section)

===Rules of inference===
{{Further|List of rules of inference}}
A ''[[rule of inference]]'' states that, given a particular formula (or set of formulas) with a certain property as a hypothesis, another specific formula (or set of formulas) can be derived as a conclusion. The rule is sound (or truth-preserving) if it preserves validity in the sense that whenever any interpretation satisfies the hypothesis, that interpretation also satisfies the conclusion.

For example, one common rule of inference is the ''rule of substitution''. If ''t'' is a term and φ is a formula possibly containing the variable ''x'', then φ[''t''/''x''] is the result of replacing all free instances of ''x'' by ''t'' in φ. The substitution rule states that for any φ and any term ''t'', one can conclude φ[''t''/''x''] from φ provided that no free variable of ''t'' becomes bound during the substitution process. (If some free variable of ''t'' becomes bound, then to substitute ''t'' for ''x'' it is first necessary to change the bound variables of φ to differ from the free variables of ''t''.)

To see why the restriction on bound variables is necessary, consider the logically valid formula φ given by <math>\exists x (x = y)</math>, in the signature of (0,1,+,×,=) of arithmetic. If ''t'' is the term "x + 1", the formula φ[''t''/''y''] is <math>\exists x ( x = x+1)</math>, which will be false in many interpretations. The problem is that the free variable ''x'' of ''t'' became bound during the substitution. The intended replacement can be obtained by renaming the bound variable ''x'' of φ to something else, say ''z'', so that the formula after substitution is <math>\exists z ( z = x+1)</math>, which is again logically valid.

The substitution rule demonstrates several common aspects of rules of inference. It is entirely syntactical; one can tell whether it was correctly applied without appeal to any interpretation. It has (syntactically defined) limitations on when it can be applied, which must be respected to preserve the correctness of derivations. Moreover, as is often the case, these limitations are necessary because of interactions between free and bound variables that occur during syntactic manipulations of the formulas involved in the inference rule.