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$ Aug 24, 2019 at 11:04

2 Answers 2

1
$\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$
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$

You must log in to answer this question.

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