I'm having trouble proving this:

Let $\alpha$ be a wff such that the only possible connectives in it are $\lnot, \land, \lor$. Let $\alpha^{\ast}$ be the result of changing every $\land$ in $\alpha$ to $\lor$, every $\lor$ in $\alpha$ to $\land$, and every sentence symbol in $\alpha$ with its negation.

Prove: $\lnot(\alpha^{\ast})\vDash(\lnot\alpha)^{\ast}$ and $(\lnot\alpha)^{\ast}\vDash\lnot(\alpha^{\ast})$

I tried proving this in two way, one is Mathematical Induction on the length of the wff, and the other is with the Induction Principle (as described in Enderton's). In both ways I got stuck in the Step.

This is my attempt with Mathematical Induction:

Let $n$ be the length of $\alpha$. if $n=1$ then $\alpha$ can only be a symbol sentence and: $(\lnot\alpha)^{\ast}\overset{\alpha^{\ast}\;def}{=}(\lnot(\lnot\alpha))=\lnot(\lnot\alpha)=\lnot(\alpha^{\ast})$

Assume that every wff $\delta$ of length $1\leq j<n$ satisfies $\lnot(\delta^{\ast})\vDash(\lnot\delta)^{\ast}$ and $(\lnot\delta)^{\ast}\vDash\lnot(\delta^{\ast})$

Now we show for $n$,

Case 1: There's a wff $\beta$ such that $\alpha=\lnot \beta$ and we get that $\alpha^{\ast}=(\lnot \beta)^{\ast}$. Let $v$ be a truth assignment for the set of all sentence symbols in $\lnot(\alpha^{\ast}),(\lnot\alpha)^{\ast}$. Then:

$\overline{v}(\lnot(\alpha^{\ast}))=\overline{v}(\lnot((\lnot \beta)^{\ast}))=T\; \Leftrightarrow\;\overline{v}((\lnot \beta)^{\ast})=F \; \Leftrightarrow\; \overline{v}((\lnot(\beta^{\ast}))=F \; \Leftrightarrow\; ???? \; \Leftrightarrow\; \overline{v}((\lnot(\lnot \beta))^{\ast})=\overline{v}((\lnot\alpha)^{\ast})=T$

And that is how far i got. I thought maybe I haven't used the assumption the right way, or maybe I haven't assume the right thing.

Also I was trying to prove that $\lnot(\alpha^{\ast})=(\lnot\alpha)^{\ast}$ which I thought might also be true, but had problems there too.

Thanks for any help

  • $\begingroup$ After revising my answer, I do think that my and @Bram28 's approach share the same problem. We try to avoid talking about the symbolic modification of $*$ by restricting ourselves to equivalent formulas, but that doesn't seem to work. Instead, one should be a little more careful and prove the equality of the strings $\neg [\alpha^*]$ and $[\neg \alpha]^*$, where $[ ]$ indicate the order of the operation but do not represent characters in the respective strings. Unfortunately, I don't have the time right now to write this down. $\endgroup$ – Stefan Mesken Dec 24 '16 at 15:25
  • $\begingroup$ Isn't this entire question trivial? By definition of your transform, $(\lnot A)^* = \lnot(A^*)$. The only way to make this more complicated is to condition the definition of ${}^*$ on the inductive definition of replacement, which is probably overkill. $\endgroup$ – DanielV Dec 24 '16 at 15:52
  • $\begingroup$ @Stefan Well then thank you anyway $\endgroup$ – Jon Dec 24 '16 at 16:06

First, point out that for any $\alpha$ and $\beta$:

Lemma 1. $(\alpha \land \beta)^* = \alpha ^* \lor \beta ^*$ , because doing all replacements for $(\alpha \land \beta)$ amounts to replacing the $\land$ with a $\lor$, and otherwise replacing everything in $\alpha$ and $\beta$

Lemma 2. $(\alpha \lor \beta)^* = \alpha ^* \land \beta ^*$ (same idea)

Now use structural induction to show that for any $\alpha$: $\neg (\alpha)^* \Leftrightarrow (\neg \alpha )^*$ (from which it immediately follows that both $\neg (\alpha)^* \vDash (\neg \alpha )^*$ and $(\neg \alpha )^* \vDash \neg (\alpha)^* $

Base: $\alpha = A$ for some atomic statement $A$


$\neg (\alpha)^* \Leftrightarrow \neg (A)^* \Leftrightarrow \neg \neg A \Leftrightarrow (\neg A )^* \Leftrightarrow (\neg \alpha )^*$

Step: (assuming $\neg$, $\land$ and $\lor$ are the only operators ... but the proof can easily be extended to any other operators)

Case 1: $\alpha = \neg \beta$ with inductive hypothesis: $\neg (\beta)^* \Leftrightarrow (\neg \beta )^*$

Then: $\neg (\alpha)^* \Leftrightarrow \neg (\neg \beta)^* \Leftrightarrow $ (Inductive Hypothesis) $\neg \neg (\beta)^* \Leftrightarrow ( \beta )^* \Leftrightarrow \Leftrightarrow ( \neg \neg \beta )^* \Leftrightarrow (\neg \alpha) ^*$

Case 2: $\alpha = \beta \land \gamma $ with inductive hypothesis: $\neg (\beta)^* \Leftrightarrow (\neg \beta )^*$ and $\neg (\gamma)^* \Leftrightarrow (\neg \gamma )^*$

Then: $\neg (\alpha)^* \Leftrightarrow \neg (\beta \land \gamma )^* =$ (Lemma 1) $\neg (\beta^* \lor \gamma^*) \Leftrightarrow$ (DeMorgan) $ \neg \beta^* \land \neg \gamma^* $ (Inductive Hypothesis) $ (\neg \beta)^* \land (\neg \gamma)^* =$ (Lemma 2) $ (\neg \beta \lor \neg \gamma)^* \Leftrightarrow$ (DeMorgan) $(\neg (\beta \land \gamma))^* \Leftrightarrow (\neg \alpha) ^*$

Case 3: $\alpha = \beta \lor \gamma $ ... similar to case 2

  • $\begingroup$ Hey thanks for your answer. In case 1, why is $(\beta)^{\ast}\;\Leftrightarrow (\lnot \lnot \beta)^{\ast}$ ? I mean, shouldn't it be $(\beta)^{\ast}\;\Leftrightarrow \lnot \lnot (\beta)^{\ast}$ ? $\endgroup$ – Jon Dec 24 '16 at 13:40
  • $\begingroup$ @Jon Note that I do use the basic Double Negation equivalence as one of the steps. But I also use $(\beta)^* \Leftrightarrow (\neg \neg \beta)^*$ ... and why should that be so? Well, that's because of how the * is defined: doing all the *-replacements in $\neg \neg \beta$ really amounts to doing all the replacements for $\beta$, sine the two negations are left alone. But of course, once you point that out, you can just as well say: $(\neg \beta)^* \Leftrightarrow \neg (\beta)^*$. So, I had the same thought as Stefan and DanielV: the result to be proven trivially follows from how * is defined! $\endgroup$ – Bram28 Dec 24 '16 at 16:18

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.