Jump to content

Conjunction elimination

From Wikipedia, the free encyclopedia
Conjunction elimination
TypeRule of inference
FieldPropositional calculus
StatementIf the conjunction A and B is true, then A is true, and B is true.
Symbolic statement
  1. P∧Q∴P,P∧Q∴Q
  2. (P∧Q)⊢P,(P∧Q)⊢Q
  3. (P∧Q)→P,(P∧Q)→Q

In propositional logic, conjunction elimination (also called and elimination, ∧ elimination,[1] or simplification)[2][3][4] 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:

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

The rule consists of two separate sub-rules, which can be expressed in formal language as: P∧Q∴P and P∧Q∴Q

The two sub-rules together mean that, whenever an instance of "P∧Q" appears on a line of a proof, either "P" or "Q" can be placed on a subsequent line by itself. The above example in English is an application of the first sub-rule.

Formal notation

[edit]

The conjunction elimination sub-rules may be written in sequent notation:

(P∧Q)⊢P and (P∧Q)⊢Q

where ⊢ is a metalogical symbol meaning that P is a syntactic consequence of P∧Q and Q is also a syntactic consequence of P∧Q in logical system;

and expressed as truth-functional tautologies or theorems of propositional logic:

(P∧Q)→P and (P∧Q)→Q

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

References

[edit]
  1. ↑ David A. Duffy (1991). Principles of Automated Theorem Proving. New York: Wiley. Sect.3.1.2.1, p.46
  2. ↑ Copi and Cohen[citation needed]
  3. ↑ Moore and Parker[citation needed]
  4. ↑ Hurley[citation needed]