1
$\begingroup$

$\phi$ is a well formed formula.

f($\phi$) is given by replacing ∧ with ∨ (and vice versa) and 1 with 0 (and vice versa) in $\phi$.

g(f($\phi$)) is given by replacing all literals in f($\phi$) (obtained above) with their negations.

For all $\phi$, prove that g(f(¬ $\phi$)) is logically equivalent to $\phi$.

From what I know, there are two ways to prove this - using truth tables, or by proving that $\phi$ ↔ g(f(¬ $\phi$)). But I find the question too vague/abstract, and I am unable to solve it using either method.

Please help.

$\endgroup$
7
  • $\begingroup$ Have you tried induction on the structure of $\phi$? Take a look at this question: math.stackexchange.com/questions/2586642/… $\endgroup$
    – Daniel Mroz
    Commented Nov 19, 2020 at 10:47
  • $\begingroup$ No I haven't, I didn't know I could use induction to prove logical equivalence. Can you help me out by stating the base case for induction? $\endgroup$
    – weak_at_math
    Commented Nov 19, 2020 at 10:49
  • $\begingroup$ What is your definition of a well-formed formula? I presume it says something like "$0$ and $1$ are wff, and so is a literal $A$. If $\phi_1,\phi_2$ are wff, so are $\neg\phi_1$, and $\phi_1\wedge\phi_2$, and ...". Then the base cases would be when $\phi = 0,1,$ or a literal $A$. Can you see how to proceed from here? $\endgroup$
    – Daniel Mroz
    Commented Nov 19, 2020 at 10:55
  • 1
    $\begingroup$ Careful! You must distinguish between syntactic equality ($=$), and logical equivalence ($\equiv$). If $\phi = 0$, then $\neg \phi$ is certainly equivalent to $1$, but it is not equal to $1$---they are not the same formula, and $f$ and $g$ are functions on formulae. Your mistake is that you substitute $1$ for $\neg 0$ when evaluating $f(\neg 0)$. In fact, $f(\neg 0)$ = $\neg 1$. $\endgroup$
    – Daniel Mroz
    Commented Nov 19, 2020 at 11:07
  • 1
    $\begingroup$ So we get that $gf(\neg 0) = g(\neg 1) = \neg 1 \equiv 0$. $\endgroup$
    – Daniel Mroz
    Commented Nov 19, 2020 at 11:12

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .