# De Morgan's Laws Proof for Logic

Hello I am working on the logic proof for De Morgan's Law. I can only work with a very specific set of axioms, rules, and theorems and I need to prove all four implications. I am very lost on where to even start. The axioms are

1. $$(x \vee x) \to x$$
2. $$x\to (x \vee y)$$
3. $$(x \vee y)\to (y \vee x)$$
4. $$(x \to y) \to [(z \vee x) \to (z \vee y)]$$

The rule of transitivity is applicable. Substitution and Modus ponens is also allowed. The theorems are

1. $$(x \to y) \to [(z\to x)\to (z\to y)]$$
2. $$(\neg x) \vee x$$
3. $$x \vee\neg x$$
4. $$x\to\neg(\neg x)$$
5. $$(\neg(\neg x))\to x$$
6. $$(x\to y)\to((\neg y)\to(\neg x))$$

I am confused on how to even start and help would be much appreciated!

Edit: Also there is no uses of premises. It must be derived from one of the original axioms.

• How is $\land$ defined? Apr 11 at 16:19
• It is defined as (x' or y')'. Apr 11 at 16:22
• Also there is no uses of premises. It must be derived from one of the original axioms. Apr 11 at 16:25
• @waffles Are you sure that $\wedge$ is defined as 'or'? It must be 'and'. Apr 11 at 16:26
• Your def of and gives you one of De Morgan laws using Double Negation: $x \land y \equiv \lnot (\lnot x \lor \lnot y)$ Apr 11 at 16:28

If you define:

$$(x \land y) \leftrightarrow \neg(\neg x \lor \neg y)\tag1$$

Then you can use theorem $$5$$ (double negation) to prove that:

$$\neg(x\lor y)\leftrightarrow(\neg x\land\neg y)\tag2$$

$$\neg(x\land y)\leftrightarrow(\neg x\lor\neg y)\tag3$$

Since, by theorems $$5$$ and $$6$$:

$$(x\leftrightarrow y) \leftrightarrow (\neg x\leftrightarrow\neg y)\tag4$$

Notice how $$(2)$$ is equivalent to:

$$\neg(x\lor y)\leftrightarrow(\neg(\neg x) \lor \neg(\neg y))\tag5$$

By applying definition $$(1)$$.

• This proof does not work because it must be derived from one of the axioms or theorems already proved. I am having trouble starting the actual proof. Apr 11 at 21:55
• @waffles where did I use axioms or theorems not listed? Apr 11 at 21:59
• It must start from one of the original axioms or theorems, it cannot start from the definition. Apr 11 at 22:36
• @waffles that is the definition you provided in the comments. I could remove that from the answer and the proof would be just as good, I decided to write it explicitly for clarity. The proof is fine, it doesn't assume anything you didn't state in the answer or in the comments, although it's not complete, but I believe it is trivial now, with the information given. If it isn't, let me know. Apr 11 at 22:40