0
$\begingroup$

I've been trying to figure this out for hours now, there doesn't seem to be ample resources online for my skill level to solve such a question:

Show that a set of connectives {∧,¬} is expressively complete, given that {∨,∧,¬} is expressively complete.

I don't have the slightest clue how to solve this or really what it even means in context. I am very new to logic. Concepts I do understand are what the logical operators mean, and how to set up truth tables for sentence letters, and how to use truth trees for sentences.

I don't even know how to show that {∨,∧,¬} is expressively complete, let alone derive {∧,¬} . Any help is appreciated.

$\endgroup$
  • $\begingroup$ The term to search for is "functionally complete" or "functional completeness". That should find you lots of online references (including many MSE questions). $\endgroup$ – Rob Arthan Feb 25 '16 at 20:52
0
$\begingroup$

I presume you are working with propositional logic. You are given that $\{\lor, \land, \neg\}$ is expressively complete. This means that any formula in propositional logic can be rewritten so that it only uses the connectives $\lor$, $\land$, and $\neg$.

Now, to show that $\{\land, \neg\}$ is also expressively complete, all you need to do is show that you can rewrite any formula that uses only $\lor$, $\land$, and $\neg$ so that it only uses $\land$ and $\neg$, or more to the point, you need to show that you can write $\lor$ using $\land$ and $\neg$.

This can of course be done using De Morgan's laws. One of De Morgan's laws says that $$\neg (A \lor B) \equiv \neg B \land \neg A.$$ Now, if we negate both sides of this equivalence, we get $$\neg \neg (A \lor B) \equiv (A \lor B) \equiv \neg (\neg B \land \neg A),$$ which tells you how to write $\lor$ in terms of $\neg$ and $\land$.

$\endgroup$
  • $\begingroup$ So I would do something like: (A∧B) Apply DeMorgan's law: -(A∨B) $\endgroup$ – SeesSound Feb 25 '16 at 14:07
  • $\begingroup$ @SajSeesSound Essentially yes, but you need to write $A \lor B$ with $\land$ and $\neg$, so you use the other De Morgan law. $\endgroup$ – mrp Feb 25 '16 at 14:23
  • $\begingroup$ Okay let me see if I get this. we have established that {∨,∧,¬} (set 1) is expressively complete. We need to show that set 2 {∧,¬} is also expressively complete. Now, set 1 and set 2 have the connectives '¬' and '∧' in common, however set 1 has '∨' but set 2 does not have ∨. We are attempting to 'get rid of' the '∨' in set 1 by converting it in to connectives only present in set 2. By doing this we prove that set two is logically equivalent? $\endgroup$ – SeesSound Feb 25 '16 at 14:58
  • $\begingroup$ @SajSeesSound That's correct. $\endgroup$ – mrp Feb 25 '16 at 15:21
  • $\begingroup$ I am being told that the answer should be (A or B) == -(-A and -B), How do you transform (A or B) in to the latter? DeMorgans law only applies to negations from what I know $\endgroup$ – SeesSound Feb 25 '16 at 16:34
0
$\begingroup$

I'm assuming this is for the propositional language. What it means for a set of connectives to be expsively complete is that these connectives suffice to express any truth function. You don't need to show that $ \{ \lor , \land , \lnot \}$ is expressively complete---you get that for free as the hypothesis, and proceed from there that $\{ \land , \lnot \}$ is expressively complete.

Hint: you can convert any disjunction to a conjunction, so any formula containing a disjunction can be converted to one containing conjunction and negation only, using De Morgan laws.

$\endgroup$
0
$\begingroup$

All you need to do is show that $\lor$ can be expressed in terms of $\land$ and $\neg$. Using De Morgan, that's easy: $$ (p\lor q) \equiv \neg(\neg p \land \neg q). $$

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