0
$\begingroup$

I have the following logic question about duality:(Introduction to mathmatical Logic by elliot mendelson , exercise $1.30$)

If $\mathscr B$ is a statement form involving only $\lnot$ , $\land$, and $\lor$, and $\mathscr B'$ results from $\mathscr B$ by replacing each $\land$ by $\lor$ and each $\lor$ by $\land$ , show that $\mathscr B$ is a tautology if and only if $\lnot \mathscr B'$ is a tautology.

Now , at first , I had some confusion about the question itself which I resolved with another post of mine. After that , While trying to prove it , I got stuck for a while until I found another post which has the same question If $\phi$ is a tautology then dual $\phi$ is a contradiction.

There , They defined a couple of things:

$1$.In general, for any two-place logical operator $\times$, the dual expression of $\phi \times \psi$ is $\phi^d \times^d \psi^d$, where $\times^d$ is the dual operator of $\times$, which you can find by: $\phi \times^d \psi \Leftrightarrow \neg (\neg \phi \times \neg \psi)$.

$2$.Define the complement statement $\phi'$ of a statement $\phi$ to be that statement that puts a negation in front of every atomic statement in $\phi$. Recursively:

$A' = \neg A$ for any atomic $A$

$(\neg \phi)' = \neg (\phi)'$

$(\phi \times \psi)' = \phi' \times \psi'$

Also the answer states:"you should be able to prove (by induction of course) that $\phi^d\Leftrightarrow \neg \phi'$. And from that, the desired result follows fairly quickly."

I was able to prove that $\phi^d\Leftrightarrow \neg \phi'$ .But I stuck on figuring out how i will use this corollary to prove that " $\phi$ is a tautology iff $\phi^d$ is a contradiction" .Is it something really trivial I am missing out?

Edit: Here is the question again from mendelsons book but I rewrote some symbols in the context of the symbols used in this post so that it is easier to understand,

If $\phi$ is a statement form involving only $\lnot$ , $\land$, and $\lor$, and $\phi^d$ results from $\phi$ by replacing each $\land$ by $\lor$ and each $\lor$ by $\land$ , show that $\phi$ is a tautology if and only if $\lnot \phi^d$ is a tautology.

$\endgroup$
1
  • $\begingroup$ @MauroALLEGRANZA Why did you delete your answer? I am confused. $\endgroup$ – Prithu biswas Dec 31 '20 at 13:23
1
$\begingroup$

As per the post that you have linked, the Duality Theorem for boolean algebra is different:

Let $A'$ be the result of interchanging ∨ and ∧ in $A$, and replacing $P$ by $¬P$ for each atom $P$. Then $A' \Leftrightarrow ¬A$.

The proof is by structural induction.

The above proof does not apply sic et simpliciter to Mendelson's transformation.

We have to note that $P' = P$, for every atom $P$, and neither $P$ nor $P'$ are tautologies. Thus, the result holds trivially.

The same for a formula with a number of nagation whatever, but without occurrences of $\lor$ and $\land$.

Thus, the formula $A$ must contain at least one occurrence of a binary connective and one of negation.

A very simple example (maybe the simplest) of Mendelson's transformation is with formula $A = P \lor \lnot P$.

We have that $\lnot A' = \lnot (P \lor \lnot P)' = \lnot (P' \land \lnot P')=\lnot P \lor P$.

So, in the "basic case" the property holds.

If instead we consider a formula $B=P \land \lnot Q$, which is not a tautology, we have that $\lnot B'=\lnot (P \land \lnot Q)'= \lnot(P' \lor \lnot Q')=\lnot P \land Q$, and neither it is a tautology.


IMO, the result holds considering that for $A$ whatever, we may rewrite it equivalently in CNF, i.e. as a finite conjunction $C_1 \land \ldots \land C_n$ of formulas that are in turn disjunctions: $C_i= D_{i1} \lor \ldots \lor D_{im}$ of atoms or negated atoms.

We have that the CNF is a tautology iff every $C_i$ contains an atom and it negation, i.e. a "basic disjunction" $P \lor \lnot P$.

Consider now $A$ in CNF; what happens with Mendelson's transform? That $A'$ will be in DNF: a disjunction of conjuncts.

What happens when we prefix $\lnot$ to $A'$? That the and's and or's will be exchanged again when we move inside the negation sign and the new formula will be again in CNF.

What happened to the "basic disjunctions"? The first step changes $P \lor \lnot P$ into $P \land \lnot P$, while the second step changes it into $\lnot P \lor \lnot \lnot P$.

Thus, if every disjunct $D_i$ of the CNF corresponding to $A$ contains a "basic disjunction", this will be so also for the corresponding $D'_i$.

$\endgroup$
3
  • $\begingroup$ You said "Assuming that the property holds for $A$ " , meaning that "$A$ is a tautology iff $\lnot A'$ is a tautology".After that "If $B=¬A$ is a tautology, then $A$ is a contradiction. By induction hypotheses, $¬A′$ is a contradiction".But , "$A$ is a contradiction" just means that "$A$ is not a tautology" . By induction hypothesis , "$\lnot A'$ is not a tautology" . But , "$\lnot A'$" is not a tautology" doesn't necessarily imply that "$\lnot A'$" is a contradiction". I am kinda confused about this. $\endgroup$ – Prithu biswas Dec 31 '20 at 9:24
  • $\begingroup$ You said "If $B=¬A$ is a tautology, then $A$ is a contradiction . By induction hypotheses, $¬A′$ is a contradiction" . Shouldn't it be ""If $B=¬A$ is a tautology, then $A$ is a contradiction . By induction hypotheses, $¬A′$ is not a tautology" .Isn't that How IFF based induction hypothesis works? $\endgroup$ – Prithu biswas Dec 31 '20 at 13:05
  • $\begingroup$ And I think all "Contradictions" are "not tautology" . But not all "not tautology" are "Contradiction". $\endgroup$ – Prithu biswas Dec 31 '20 at 13:08

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.