[Math] Show that a set of logical connectives is expresively complete

logicpropositional-calculus

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.

Best Answer

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