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$
1
  • $\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, 2016 at 20:52

3 Answers 3

Reset to default
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$
6
  • $\begingroup$ So I would do something like: (A∧B) Apply DeMorgan's law: -(A∨B) $\endgroup$
    – SeesSound
    Feb 25, 2016 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, 2016 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, 2016 at 14:58
  • $\begingroup$ @SajSeesSound That's correct. $\endgroup$
    – mrp
    Feb 25, 2016 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, 2016 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$

You must log in to answer this question.

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