Let $\phi$ be a formula built with $\lnot,\ \land,$ and $\lor$.

Let $\phi'$ be constructed by replacing each propositional variable from $\phi$ with its negation.

For any truth assignment $v$, let $v'$ be the truth assignment that gives each propositional variable the opposite value of $v$.

Prove $v(\phi)=v'(\phi')$

I am having stuck on the 2nd step of the induction proof when trying to prove the above with $\land$.

Here is the part of my proof where I got stuck and think I am doing something wrong:

For $\phi$ as $(\theta\land\psi)$:

If $v(\theta\land\psi)=F$, one of the assignment values for $\theta$ and $\psi$ is $v(\theta)=T$ and $v(\psi)=F$.

$\phi'$ is then $(\lnot\theta\land\lnot\psi)$. $v(\lnot\theta)=F$ and $v(\lnot\psi)=T\ \therefore\ v(\lnot\theta\land\lnot\psi)=F$ and $v'(\lnot\theta\land\lnot\psi)=T$

This contradicts what I am trying to prove. Did I make a mistake?

  • $\begingroup$ Typesetting hint: dollar signs are for mathematical expressions, so something like $for$ ($for$) is not a word but actually the product of the variables $f,o,r$. If you want italics, use asterisks. Thus: *Let $\phi$ be a formula* gives Let $\phi$ be a formula. This will look better (and is a lot easier to type!) than $Let\ \phi\ be\ a\ formula\$ ($Let\ \phi\ be\ a\ formula$). $\endgroup$
    – Théophile
    Sep 20, 2020 at 3:55

1 Answer 1


You have made a mistake in calculating $\ v'(\neg\theta\wedge\neg\psi)\ $. While it is true that $\ v(\neg\theta\wedge\neg\psi)=F\ $, this has no relevance for the calculation of $\ v'(\neg\theta\wedge\neg\psi)\ $. You have defined the assignment $\ v\ $ by: $$ v(\theta)=T,\ v(\psi)=F\ . $$ Therefore, by definition, the assignment $\ v'\ $ is given by $$ v'(\theta)=F,\ v'(\psi)=T\ . $$ Therefore $\ v'(\neg\theta)=T\ $, $\ v'(\neg\psi)=F\ $ and $\ v'(\neg\theta\wedge\neg\psi)= F\ $.

  • $\begingroup$ $v'$ is supposed to give the opposite value of $v$. Since $v(\phi)=F$, it should be the case that $v'(\phi)=T$. $\endgroup$
    – John Glen
    Sep 20, 2020 at 15:59
  • $\begingroup$ You appear to be confusing symbols for formulas with symbols for propositional variables. The assignment $\ v'\ $, by definition, assigns the the opposite value to $\ v\ $ to propositional variables only. It can't possibly do so to all formulas. If $\ \xi\ $ is tautology (such as $\ \psi\vee\neg\psi\ $), for instance, then $\ w(\xi)=T\ $ for all truth assignments, including both $\ v\ $ and $\ v'\ $. $\endgroup$ Sep 20, 2020 at 16:49
  • 1
    $\begingroup$ In the case of your formula, $\ \phi=\theta\wedge\psi\ $, where $\ \theta\ $ and $\ \psi\ $ are (presumably) propositional variables, you will have $\ w(\phi)=w'(\phi)=F\ $ for both of the truth assignments for which exactly one of $\ w(\theta)\ $ and $\ w(\psi)\ $ are $\ T\ $ and the other $\ F\ $. The truth value of $\ \phi\ $ under $\ w'\ $ will only be opposite to its truth value under $\ w\ $ when $\ w\ $ assigns the same truth value to both $\ \theta\ $ and $\ \psi\ $. $\endgroup$ Sep 20, 2020 at 16:56
  • $\begingroup$ That makes sense. Thank you $\endgroup$
    – John Glen
    Sep 20, 2020 at 19:30
  • $\begingroup$ If the definition of $v'$ takes a propositional variable, how come it is legal to pass a formula into $v'$? $\endgroup$
    – John Glen
    Sep 21, 2020 at 14:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .