1

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?

John Glen
  • 185
  • 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$). – Théophile Sep 20 '20 at 03:55

1 Answers1

0

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\ $.

lonza leggiera
  • 28,646
  • 2
  • 12
  • 33
  • $v'$ is supposed to give the opposite value of $v$. Since $v(\phi)=F$, it should be the case that $v'(\phi)=T$. – John Glen Sep 20 '20 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'\ $. – lonza leggiera Sep 20 '20 at 16:49
  • 1
    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\ $. – lonza leggiera Sep 20 '20 at 16:56
  • That makes sense. Thank you – John Glen Sep 20 '20 at 19:30
  • If the definition of $v'$ takes a propositional variable, how come it is legal to pass a formula into $v'$? – John Glen Sep 21 '20 at 14:52
  • To apply $\ v'\ $ to any formula you just apply it to every propositional variable in the formula and then use the rules \begin{align} T\vee T&=T\vee F= F\vee T=T\wedge T=\neg F\ &=T\ F\vee F&=F\wedge F=F\wedge T=T\wedge F=\neg T\ &=F\ . \end{align} – lonza leggiera Sep 21 '20 at 15:30
  • Just to clarify, in my first comment above I didn't say that $\ v'\ $ can be applied only to propositional variables, merely that it is only on propositional variables where it is defined to have the opposite truth value to $\ v\ $. The truth value it assigns to a formula composed of logical operations applied to one or more propositional variables is defined by the rules given in my immediately preceding comment. – lonza leggiera Sep 21 '20 at 16:33
  • $\phi'$ is made by replacing every propositional variable in $\phi$ with it's negation. Then the truth function $v'(\phi')$ is applied. Does that mean there is a double negation applied to every propositional variable? – John Glen Sep 22 '20 at 02:04
  • I think you have the right idea, although I wouldn't quite express it the way you have, because $\ v'\ $ doesn't actually negate the propositional variables themselves, merely assigns truth values to them which are the negations of the truth value assigned to them by $\ v\ $. – lonza leggiera Sep 22 '20 at 02:46
  • So if $$\phi=f(a_1,a_2,\dots,a_r)\ ,$$ where $\ a_1,a_2,\dots,a_r\ $ are the propositional variables appearing in $\ \phi\ $, then $$v(\phi)=f(v\left(a_1\right), v( a_2),\dots,v(a_r))\ ,\ \phi'=f(\neg a_1,\neg a_2,\dots,\neg a_r)\text{ , and}\ v'\left(\phi'\right)=f\left(\neg v'(a_1),\neg v'(a_2),\dots,\neg v'(a_r)\right)\ . $$ But since $\ v'\ $ assigns to each $\ a_i\ $ the negation of the truth value assigned to it by $\ v\ $, then we have $\ \neg v'(a_i)=v(a_i)\ $ for all $\ i\ $. – lonza leggiera Sep 22 '20 at 02:47