# By replacing proposition variables by its negation and flipping the truth values of all prop. variables, show $v(\phi)=v^*(\phi^*)$

This is Exercise 2.28 from Propositional and Predicate Calculus: A Model of Argument by Derek Goldrei:

For a formula built up using the connectives $\neg,\land,\lor$, let $\phi^*$ be constructed by replacing each propositional variable in $\phi$ by its negation.
(a) For any truth assignment $v$, let $v^*$ be the truth assignment that gives each prop. variable the opposite value to that given by $v$, i.e. $$v^*=\begin{cases} T&\ \text{if}\ v(p)=F\\ F&\ \text{if}\ v(p)=T, \end{cases}$$ for all prop. variables $p$. Show that $v(\phi)=v^*(\phi^*)$.
(b) (i) Use the result of part (a) to show that $\phi$ is a tautology iff $\phi^*$ is a tautology.
$\hspace{25mu}$(ii) Is it true that $\phi$ is a contradiction iff $\phi^*$ is a contradiction?

Related: Same question without (b).

I have already done part (a) by strong induction on the length of $\phi$:

For every $n\in\mathbb{N}$, let $P(n)$ be the statement. $P(0)$ is clearly true. Suppose $P(i)$ is true for $0\le i\le k$. Let $\phi$ be a formula of length $k+1$, then $\phi$ is one of the three forms $\neg\theta$, $(\theta\land\psi)$, or $(\theta\lor\psi)$. Suppose $\phi$ is of the form $\neg\theta$. $\theta$ has length $k$ so by $P(k)$, $v(\theta)=v^*(\theta^*)$. Suppose for any truth assignment $v$, $v(\neg\theta)=T$, then $v(\theta)=F=v^*(\theta^*)$. Since $v$ and $v^*$ are truth assignments, $v(\neg\theta)=T=v^*(\neg\theta^*)$ and $P(k+1)$ is true; similarly if $v^*(\neg\theta^*)=T$. The cases for $\phi$ of the remaining two forms are similar. By strong induction, for every $n\in\mathbb{N}$, $P(n)$ is true.

I'm having trouble with part (b). What I've done is:

Suppose $\phi$ is a tautology, then for any truth assignment $v$, $v(\phi)=T$. By (a), $v^*(\phi^*)=T$. Since $v$ is any truth assignment, $v^*$ is also any truth assignment (for any specific $v^*$ we can choose the corresponding $v$), so $\phi^*$ is a tautology. And likewise for (ii).

Alternatively, it seems like if $\phi$ is a tautology, it must be of the form $(\theta\lor\neg\theta)$, so by (a), $v(\theta)=v^*(\theta^*)$, by definition of truth assignment, $v(\neg\theta)=v^*(\neg\theta^*)$, and therefore $v((\theta\lor\neg\theta))=v((\theta^*\lor\neg\theta^*))=v(\phi^*)$. And likewise for $\phi$ contradiction of the form $(\theta\land\neg\theta)$.

I'm not confident either method is correct, what am I missing here?

• The proof of part (a) is OK. Concerning the proof of part (b), see my answer. – Taroccoesbrocco Feb 13 '18 at 13:28

Your proof of property (b) is not correct, even if there are good intuitions. Your claim "$v^*(\phi^*)$ is a tautology" is meaningless because only a formula can be a tautology, a truth value cannot be a tautology. This is not only a formal and pedantic distinction: proving that $\phi$ is a tautology means to prove that $v(\phi) = \top$ for every assignment $v$. Moreover, a priori, it might not be enough to show that $v^*(\phi) = \top$ for every assignment $v$ (actually, it is sufficient, but you have to explain why).

Let us prove that if $\phi$ is a tautology then $\phi^*$ is a tautology: let $\phi$ be a tautology; we have to prove that $v(\phi^*) = \top$ for every assignment $v$.

Let $v$ be an assignment. Since $\phi$ is a tautology, $v^*(\phi) = \top$. By definition of $(\cdot)^*$, $\phi \equiv \phi^{**}$ ($\equiv$ stands for logical equivalence) because $\phi^{**}$ is just obtained from $\phi$ by replacing each propositional variable in $\phi$ by its double negation, and in classical logic $\lnot\lnot p \equiv p$. Therefore, $v^{*}(\phi^{**}) = \top$. According to property (a), $v(\phi^*) = \top$. QED

Let us see also the vice-versa, which can be proved in a similar (even simpler) way.

Let us prove that if $\phi^*$ is a tautology then $\phi$ is a tautology: let $\phi^*$ be a tautology; we have to prove that $v(\phi) = \top$ for every assignment $v$.

Let $v$ be an assignment. Since $\phi^*$ is a tautology, $v^*(\phi^*) = \top$. According to property (a), $v(\phi) = \top$. QED

The proof that $\phi$ is a contradiction iff $\phi^*$ is a contradiction is analogous.

P.S. Your claim "if $\phi$ is a tautology, it must be of the form $(\theta \lor \lnot \theta)$" is false! It is true that if $\phi$ is a tautology then $\phi \equiv (\theta \lor \lnot \theta)$, but the syntactical form of $\phi$ might be completely different. For instance, $p \to (q \to p)$ is a tautology.

• Hi, yes I should have wrote $\phi^*$ is a tautology and not $v^*(\phi^*)$, I have edited that part. For the implication direction, is there any way of showing 'If $\phi$ is a tautology, then $\phi^*$ is a tautology' without $\phi\equiv\phi^*$? – palmpo Feb 13 '18 at 18:45
• Also, in your P.S., my suggestion was only because the formula is built only using $\neg,\land,\lor$. – palmpo Feb 13 '18 at 18:48
• The reason I don't want to use logical equivalence is that this question was one of the final questions right before the section on logical equivalence. Using your idea, how about: 'Since $\phi$ is a tautology, $v^*(\phi)=T$. By (a), $v^*(\phi)=v^{**}(\phi^*)$, but $v^{**}=v$ so we're done.'? – palmpo Feb 13 '18 at 18:52
• @palmpo - Yes, this perfect as well! – Taroccoesbrocco Feb 13 '18 at 23:18
• @palmpo - Concerning the PS, also in the fragment $\lnot, \lor, \land$ or even in the fragment $\lnot, \lor$ you can easily find tautologies different from (but logically equivalent to) $\theta \lor \lnot \theta$: think of $\lnot(p \land \lnot p)$ or $\lnot p \lor (\lnot q \lor p)$. – Taroccoesbrocco Feb 13 '18 at 23:23