-1
$\begingroup$

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.

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

1 Answer 1

1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – waffles
    Apr 11 at 21:55
  • $\begingroup$ @waffles where did I use axioms or theorems not listed? $\endgroup$
    – NtLake
    Apr 11 at 21:59
  • $\begingroup$ It must start from one of the original axioms or theorems, it cannot start from the definition. $\endgroup$
    – waffles
    Apr 11 at 22:36
  • $\begingroup$ @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. $\endgroup$
    – NtLake
    Apr 11 at 22:40

You must log in to answer this question.

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