Substitution instance of a well-formed formula ( if two variables are replaced)

893 Views Asked by At

According to my Discrete Mathematics books:

A statement formula p is called a Substitution instance of another statement formula q, if p can be generated from q by substituting formulas for some variables of q. Here, the condition required is that the same formula is substituted for the same variable each time it occurs.

As it says that substituting formulas for some variables of q

so I was thinking that If I substitute two different statement formulas for two different variables of q to get p then will p still be called as the Substitution instance of q?

For example, let's say ((p.q)+r) is a WFF so if I replace q with (q+p) and r with (q+r) to get (p.(q+p))+(q+r), then will the latter be a Substitution Instance of the initial one?

1

There are 1 best solutions below

0
On BEST ANSWER

No. The idea lies in that a substitution instance has the same truth value as the original formula if the original formula is a tautology. That substitution preserves the truth of the original formula, or at least does not lead from a true formula to a false one. If you allow for the same variable to get substituted with two different formulas, then as William Eliot suggest, a substitution instance of a tautology will no longer be true for all valuations of it's variables as a tautology is.

For instance, consider the tautology (in Polish notation) Cpp. If we substitute the first p with 'Cpp' and the second with 'NCpp', then we obtain CCppNCpp. But, Cpp is always true, and NCpp is always false. Thus, we would have a substitution instance of a tautology which would always be false, when all substitution instances of a tautology come as intended to hold true.

Thus, we have the uniformity requirement for substitution instances of formulas.

"For example, let's say (p.q+r) is a WFF so if I replace q with (q+p) and r with (q+r) to get (p.(q+p))+(q+r), then will the latter be a Substitution Instance of the initial one?"

This example satisfies the condition: "... the same formula is substituted for the same variable each time it occurs."