Sentential logic substitution rule

[ky2345]

Homework Statement

Show that if A is a tautology, then so is *(A). A is a well formed formula, * is a function that replaces all sentence symbols A_1, A_2, etc. with formulas B_1, B_2, etc. , respectively

Homework Equations

* is defined recursively, starting with the fact that if A_n is a sentence symbol, *(A_n)=B_n. If C ad D are a well formed formulas, then *(not C)=not *(C), *(C and D)=*(C) and *(D), and so on with the last 3 binary connectives, or, implies, and iff.

The Attempt at a Solution

I'm trying to use the induction principle. So, if S is the set of all wffs (well formed formulas) with the property that if A is a tautology, *(A) is a tautology, I want to show that S is the set of all wffs. Starting with just a sentence symbol, A, I know that A is never a tautology because there is a truth valuation such that A is false. Thus, the property holds vacuously for the base case. Now, I need to show that the property is closed under all five formula building operations. Assume that B is in S, so that if B s a tautology, *(B) is a tautology. Then, consider (not B). If (not B) is not a tautology, we are finished. But if (not B) is a tautology... this is where I get muddled up. I undertand intuitivley why this is true, because for every truth valuation u there is a truth valuation v such that u(A)=v(*(A)), so if there is a tautology G, every truth valuation gives true as the value of G, and so every corresponding v should give true as the value of *(G). I just don't know how to prove that all the corresponding "v"s consist of all possible truth valuations.

 

[mighty2000]

To prove that *(A) is a tautology if A is a tautology, we can use a proof by contradiction.

Assume that A is a tautology but *(A) is not a tautology. This means that there exists a truth valuation u such that u(*(A)) = False. But since A is a tautology, every truth valuation will give True as the value of A. This means that there exists a truth valuation v such that v(A) = True.

But since * replaces all sentence symbols in A with other formulas, v(*(A)) = v(*(B_1 and B_2 and ... and B_n)), where B_1, B_2, ..., B_n are the formulas that replace the sentence symbols in A. Since v(A) = True, v(B_i) = True for all i, which means that v(*(B_1 and B_2 and ... and B_n)) = True. This contradicts our initial assumption that u(*(A)) = False.

Therefore, our assumption must be false and *(A) must be a tautology if A is a tautology. This proves that the property holds for the base case.

Now, we can use induction to show that the property holds for all wffs. Assume that the property holds for a wff A and consider the formula (not A). By our induction hypothesis, *(A) is a tautology if A is a tautology. This means that there exists a truth valuation v such that v(*(A)) = True. But since *(not A) = not *(A), v(*(not A)) = False, which means that *(not A) is a tautology.

Using similar arguments for the other formula building operations, we can show that the property holds for all wffs. Therefore, if A is a tautology, then *(A) is also a tautology.