0
$\begingroup$

Prove that $\phi$ is tautology if only and only when $\overline{\phi}$ is tautology.
Remark
$\phi$ must contain only $\vee$ and $\wedge$. Forbidden are: $\tilde{}, \mathbb{false}, \mathbb{true}$.
$\overline{\phi}$ reverse conjunctions, for example $\overline{p\wedge q\vee r}=p\vee q\wedge r$.

My approach:
Lets use induction by number ($n$) of conjunctions.
(1) Base $n=0$.
It is trivial because $\overline{\phi}=\phi$.
(2) Hypothesis: For each $k\le n$ where $k$ is number of conjunctions in $\phi$ we have $\phi$ is tautology if only and only when $\overline{\phi}$ is tautology.
T (3) Induction step:
Let $\phi$ contain $n+1$ conjcutions. Then, there are two cases:
(1) $\phi = \psi\vee p$.
(2) $\phi = \psi \wedge p$
where $\psi$ has $n$ conjcutions and fulfill induction hypothesis.
Case (1) is fairly easy - Because $\psi$ is always satisfable then $p$ may be arbitrar.
However, I have a problem with case (2).
Can you help me ? Maybe someone propose other solution ?

Edit Seems to me that I managed to prove also (2). We know that $\overline{\phi}=\overline{\psi}\vee p$, where $\overline{\psi}$ is tautology. So the same situation as (1).
Is it ok solution ?

$\endgroup$
  • 1
    $\begingroup$ Maybe you have to specify what is $\overline \phi$... $\endgroup$ – Mauro ALLEGRANZA Oct 7 '16 at 7:58
  • $\begingroup$ Look at my edition please and try to check my soltuion again, please $\endgroup$ – user343207 Oct 7 '16 at 8:00
  • 1
    $\begingroup$ Without $\lnot$ (negation), $\to$, $\bot$ and $\top$ there are no tautologies. $\endgroup$ – Mauro ALLEGRANZA Oct 7 '16 at 8:03
  • $\begingroup$ Why (1) is "fairly easy" ? If $\phi$ is $\psi \lor p$ then $\overline \phi$ is $\overline \psi \land p$. With $p$ evaluated to false, if $\psi$ is taut then $\psi \lor p$ is still true while $\overline \psi \land p$ is false. $\endgroup$ – Mauro ALLEGRANZA Oct 7 '16 at 8:05
  • $\begingroup$ Yes, you are right. So how to correct it ? $\endgroup$ – user343207 Oct 7 '16 at 8:08
0
$\begingroup$

Hint

Consider the case : $\phi$ is tautology (assuming that it makes sense ...) and $\phi$ is $\psi \lor p$.

Thus, $\overline \phi$ is $\overline \psi \land p$.

If $\phi$ is taut, this means that it is true for every truth assignment $v$. We have two cases :

(i) $v(\psi)=$ t : in this case also $v(\overline \psi)=$ t - by induction hypotheses - and thus $v(\overline \phi)=$ t.

(ii) $v(p)=$ t, and thus also $v(\overline \phi)=$ t.


Now for the case : $\phi$ is tautology and $\phi$ is $\psi \land p$.

If $\phi$ is taut, this means that it is true for every truth assignment $v$, and thus : $v(\psi)=v(p)=$ t.

From $v(\psi)=$ t - by induction hypotheses - we have $v(\overline \psi)=$ t.

Thus : $v(\overline \psi)=v(p)=$ t and so : $v(\overline \psi \lor p)=v(\overline \phi)=$ t .

$\endgroup$

Your Answer

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