I am aware that there are many previously asked questions regarding the proof that the duals of two equivalent compound propositions containing only logical operators ∨, ∧, and ¬ are also equivalent, although I have not yet been content with the solutions I have found.

If possible, I would like someone qualified to see if I am on the right track with my current proof of the above. Please note that I am only at a relatively basic level for proof-writing, although I wish to advance this whenever possible.

Below is a definition of the dual of a compound proposition containing only logical operators ∨, ∧, and ¬, found in Discrete Mathematics and Its Applications, 7th Edition, by Rosen, followed by the relevant theorem and current draft of my proof.

The dual of a compound proposition that contains only the logical operators ∨, ∧, and ¬ is the compound proposition obtained by replacing each ∨ by ∧, each ∧ by ∨, each T by F, and each F by T. The dual of s is denoted by s∗.


The duals of two equivalent compound propositions are also equivalent.

Let $s_0$, $s_n$ be two arbitrary compound propositions containing only logical operators ∨, ∧, or ¬, such that $s_0$ $\equiv$ $s_n$ after transforming $s_0$ with n logical equivalences containing only logical operators ∨, ∧, or ¬.

Let $t_0$, $t_1$, $\ldots$ , tn-1 be an ordered sequence of n transformations using logical equivalences only containing the ∨, ∧, or ¬ operators such that $t_i$($s_i$) = si+1, for 0 $\leq$ i $\leq$ n-1, where $s_i$, si+1 are compound propositions, and let $s_0^*$, $s_1^*$, $\ldots$ , $s_n^*$ be the corresponding duals for $s_0$, $s_1$, $\ldots$ , $s_n$, respectively.

We wish to find an ordered list of m transformations, $t_0^*$, $t_1^*$, $\ldots$ , tm-1$^*$ such that $t_i^*$($s_i^*$) = si+1$^*$,
for 0 $\leq$ i $\leq$ m-1, where $s_i$, si+1 are compound propositions.

Since every logical equivalence for a compound proposition containing only the ∨, ∧, or ¬ operators has a dual equivalent, that is, a complementary logical equivalence for the dual of the compound proposition, we let the logical equivalence transformation $t_i^*$ be the dual equivalent of the transformation $t_i$ when the transformation is performed on a compound proposition, and otherwise the same transformation when performed on an individual element,
for 0 $\leq$ i $\leq$ n-1.

Thus, $t_i^*$($s_i^*$) = si+1$^*$, for 0 $\leq$ i $\leq$ n-1, is a valid ordered sequence of logical equivalence transformations, and $s_0^*$ $\equiv$ $s_n^*$. Since $s_0^*$ and $s_n^*$ were chosen to be arbitrary, true for all such.

End of proof.

I feel that the first statement in last paragraph of my proof is not explicit enough, although I am not currently able to think of what is additionally needed.

Please help if possible. Thank you!

  • $\begingroup$ Yes, this is correct. $\endgroup$ – Berci Dec 26 '18 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.