1
$\begingroup$

I need some help to prove that the set $\{\rightarrow, \land \}$ of logical connectives is not a complete set.

can someone help me to understand what should I do?

thanks!

$\endgroup$
4
  • 1
    $\begingroup$ How would you get "not A" with just those two? $\endgroup$
    – almagest
    Apr 6, 2016 at 15:25
  • $\begingroup$ what do you mean in A? $\endgroup$
    – user9
    Apr 6, 2016 at 15:27
  • $\begingroup$ sorry the TeX did not work the way I expected! Edited. $\endgroup$
    – almagest
    Apr 6, 2016 at 15:28
  • $\begingroup$ I think you can not get "not A" but I don't know how to prove it. I saw that it should be wuth induction somehow,,, $\endgroup$
    – user9
    Apr 6, 2016 at 15:34

1 Answer 1

Reset to default
2
$\begingroup$

HINT: Prove by induction on the complexity of all well formed propositional expressions $\phi$ that only contain $\rightarrow, \wedge$ as connective symbols that $\phi^* \equiv \text{true}$, where $\phi^*$ results from $\phi$ by assigning $\text{true}$ to each variable in $\phi$. Since $\neg \text{true} \equiv \text{false}$, this implies that $\{ \rightarrow, \wedge \}$ is not a complete set of logical connectives.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .