Simplification

From Wikipedia, the free encyclopedia
  (Redirected from Conjunction elimination)
Jump to: navigation, search
For other uses, see Simplification (disambiguation).

In propositional logic, simplification[1][2][3] (equivalent to conjunction elimination) is a valid immediate inference, argument form and rule of inference which makes the inference that, if the conjunction A and B is true, then A is true, and B is true. The rule makes it possible to shorten longer proofs by deriving one of the conjuncts of a conjunction on a line by itself.

An example in English:

It's raining and it's pouring.
Therefore it's raining.

The rule can be expressed in formal language as:

\frac{P \land Q}{\therefore P}

or as

\frac{P \land Q}{\therefore Q}

where the rule is that whenever instances of "P \land Q" appear on lines of a proof, either "P" or "Q" can be placed on a subsequent line by itself.

Formal notation[edit]

The simplification rule may be written in sequent notation:

(P \land Q) \vdash P

or as

(P \land Q) \vdash Q

where \vdash is a metalogical symbol meaning that P is a syntactic consequence of P \land Q and Q is also a syntactic consequence of P \land Q in logical system;

and expressed as a truth-functional tautology or theorem of propositional logic:

(P \land Q) \to P

and

(P \land Q) \to Q

where P and Q are propositions expressed in some logical system.

References[edit]

  1. ^ Copi and Cohen[citation needed]
  2. ^ Moore and Parker[citation needed]
  3. ^ Hurley[citation needed]