1
$\begingroup$

I need to say whether the system of logical laws made of:

  • Double negation
  • Commutative
  • Associative
  • Distributive
  • Idempotent
  • Implication
  • Contradiction
  • de Morgans
  • Absorption
  • Equivalence

is sound and whether it is adequate if we remove de Morgan's laws from it, for my mathematical logic paper. I believe I have a derivation showing that $¬(A ∧ B) ⇔ (¬A ∨ ¬B)$ and $¬(A V B) ⇔ (¬A ∧ ¬B)$, without using the law itself, but I need help saying whether this 'system' is sound and adequate.

$\endgroup$
  • 1
    $\begingroup$ Hint: have you tried proving de Morgan's laws from the other axioms? $\endgroup$ – ShyPerson Aug 5 '15 at 22:51
  • 1
    $\begingroup$ It sounds like, given the derivations you mention, you just need to note some general property of formal systems like the one you're considering. But to spell out those properties, it'd help to clarify the system a bit. Is $\Leftrightarrow$ an expression of the object-language? So, the laws you've listed are all axioms of the system? In that case, what are the rules of inference (whereby you move from step to step in derivations)? E.g., something like from "$A\Leftrightarrow B$" and $C$, infer the result of substituting $A$ for $B$ in $C$? $\endgroup$ – mmw Aug 6 '15 at 3:42
  • $\begingroup$ This is rather unclear. It would come as clearer if the logical laws got expressed in symbolic form. From what you've said, the commutative property of logical equivalence and the associative property of logical equivalence, could come as axioms. I have a feeling though that you meant the comutative property of logical disjunction, and the commutative property of logical conjunction. You might also want to state how "sound" and "adequate" get defined also. $\endgroup$ – Doug Spoonwood Aug 6 '15 at 15:39
0
$\begingroup$

You just need the usual properties of the connectives and double negation elimination.

I suggest you to try a proof of it to make clear the chain of reasoning you need.

Using the natural deduction method:

1) $\neg(A \wedge B)$, Premise

$\quad$ 2) $\neg(\neg A \lor \neg B)$, Assumption

$\quad \quad$ 3) $\neg A $, Assumption

$\quad \quad$ 4) $\neg A \lor \neg B$, 3, $\lor I$

$\quad \quad$ 5) $\bot$, 4,2, $\land I$

$\quad$ 6) $\neg\neg A $, 3-5, $\neg I$

$\quad$ 7) $ A $, 3-5, $DNE$

$\quad$ ...

$\quad$ 12) $ B $ (similar reasoning)

$\quad$ 13) $ A \wedge B $, 7,12, $\land I$

$\quad$ 14) $ \bot$, 1,13, $\land I$

15) $\neg\neg(\neg A \lor \neg B)$, 2-14, $\neg I$

16) $\neg A \lor \neg B$, 15, DNE

Can you complete the proof and prove the $\Leftarrow$ side as well?

$\endgroup$
  • $\begingroup$ The laws referred to the author might come as equational and there might not exist any natural deduction rules of inference than can get used. $\endgroup$ – Doug Spoonwood Aug 6 '15 at 15:40

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.