1
$\begingroup$

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?

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

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.

$\endgroup$
  • $\begingroup$ 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^*$? $\endgroup$ – palmpo Feb 13 '18 at 18:45
  • $\begingroup$ Also, in your P.S., my suggestion was only because the formula is built only using $\neg,\land,\lor$. $\endgroup$ – palmpo Feb 13 '18 at 18:48
  • $\begingroup$ 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.'? $\endgroup$ – palmpo Feb 13 '18 at 18:52
  • $\begingroup$ @palmpo - Yes, this perfect as well! $\endgroup$ – Taroccoesbrocco Feb 13 '18 at 23:18
  • $\begingroup$ @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)$. $\endgroup$ – Taroccoesbrocco Feb 13 '18 at 23:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.