# Replace propositional variables in $\phi$ by their negation, flip the truth value of result, and show result has the same truth value as $\phi$.

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?

• 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$). Sep 20, 2020 at 3:55

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\$$.
• $v'$ is supposed to give the opposite value of $v$. Since $v(\phi)=F$, it should be the case that $v'(\phi)=T$. Sep 20, 2020 at 15:59
• 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'\$. Sep 20, 2020 at 16:49
• 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\$. Sep 20, 2020 at 16:56
• If the definition of $v'$ takes a propositional variable, how come it is legal to pass a formula into $v'$? Sep 21, 2020 at 14:52