0
$\begingroup$

I just stuck upon a discrete maths-related problem with proving that a set of logical connectives is complete. I already know how to prove that ("basic") sets are full (examples like show that the given set of connectives is complete: $\{\lnot, \Rightarrow\}$), but I got stuck upon the following example...

Three-figure logical connective $W(p,q,r)$ is defined as $W(p,q,r) \equiv (p \lor q) \Rightarrow \lnot r$. Proove that set $\{W\}$ is a complete set of connectives.

What should I do here? I know that a known complete set is $\{\lnot, \land, \lor\}$ and that I should "derive" each one of those connectives with $(p \lor q) \Rightarrow \lnot r$, but how should I even start?

P.S.: I'm sorry if the translation of the assignment isn't 100% accurate, because English is not my first language and this assignment is given in my native language :)

$\endgroup$
1
  • $\begingroup$ $p \lor q \Rightarrow \lnot r$ is equivalent to $(\lnot p \land \lnot q)\lor \lnot r$ $\endgroup$ – user6767509 Aug 24 '19 at 11:04
0
$\begingroup$

Hint: see what happens when you use only one or two distinct arguments. For example, what does $W(p, p, p)$ yield?

$\endgroup$
0
$\begingroup$

W(p,p,p) is equivalent to $p \implies \neg p$
which is equivalent to $\neg p \lor \neg p.$
$ W(p,p,\neg q)$
is equivalent to $p \implies q.$

Exercise. Show {$p \implies \neg q$} is a complete set of connectives.

$\endgroup$

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.