0
$\begingroup$

How would one prove that the golden rule is a tautology without a truth table?

$A\,\land\,B\,\equiv\,A\,\equiv\,B\,\equiv\,B\,\lor\,A $

I've been searching a lot and cannot find a demonstration. I've tried to simplify the formula using another inference rules to reach a true value, without success.

Any help or at least a hint would be very appreciated.

$\endgroup$
  • 4
    $\begingroup$ parentheses, please $\endgroup$ – spaceisdarkgreen Dec 12 '17 at 4:00
  • 1
    $\begingroup$ @rschwieb not sure it's OP's fault.... see pg 7 here: cs.nott.ac.uk/~psarb2/G51MPC/slides/LogicalConnectives.pdf $\endgroup$ – spaceisdarkgreen Dec 12 '17 at 4:03
  • 1
    $\begingroup$ @spaceisdarkgreen yeah... what a ridiculous notation. $\endgroup$ – rschwieb Dec 12 '17 at 4:06
  • 2
    $\begingroup$ Just to help understand why people are clamoring for you to clarify your notation, normally, this form of "chaining" equivalences is meant to be read as shorthand for $$(A \wedge B \equiv A) \wedge (A \equiv B) \wedge (B \equiv B \vee A)$$ which, presumably, isn't anything like what you mean by the formula. $\endgroup$ – Hurkyl Dec 12 '17 at 4:06
  • 3
    $\begingroup$ @spaceisdarkgreen: The $\leftrightarrow$ connective is actually associative and commutative in classical logic, so each of the bracketings should be equally provable, $\endgroup$ – Henning Makholm Dec 12 '17 at 4:25
1
$\begingroup$

$$(A \land B) \equiv A \equiv B \equiv (B \lor A) \Leftrightarrow$$

$$((A \land B \land A) \lor (\neg (A \land B) \land \neg A)) \equiv (((B \land (B \lor A)) \lor (\neg B \land \neg (B \lor A))) \Leftrightarrow $$

$$((A \land B) \lor ((\neg A \lor \neg B) \land \neg A)) \equiv (B \lor (\neg B \land \neg B \land \neg A)) \Leftrightarrow$$

$$((A \land B) \lor \neg A) \equiv (B \lor (\neg B \land \neg A)) \Leftrightarrow $$

$$(B \lor \neg A) \equiv (B \lor \neg A) \Leftrightarrow$$

$$\top$$

I used the following equivalences:

Equivalence

$P \equiv Q \Leftrightarrow (P \land Q) \lor (\neg P \land \neg Q)$

Absorption

$P \land (P \lor Q) \Leftrightarrow P$

$P \lor (P \land Q) \Leftrightarrow P$

Reduction

$P \land (\neg P \lor Q) \Leftrightarrow P \land Q$

$P \lor (\neg P \land Q) \Leftrightarrow P \lor Q$

Biconditional Tautology

$P \equiv P \Leftrightarrow \top$

$\endgroup$
  • $\begingroup$ Thanks man, this is what i was looking for. $\endgroup$ – Mariano Córdoba Dec 12 '17 at 5:57

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.