Simplification

From Wikipedia, the free encyclopedia

Transformation rules
Propositional calculus
Rules of inference Modus ponens Modus tollens Biconditional introduction Biconditional elimination Conjunction introduction Simplification Disjunction introduction Disjunction elimination Disjunctive syllogism Hypothetical syllogism Constructive dilemma Destructive dilemma Absorption Rules of replacement Associativity Commutativity Distributivity Double negation De Morgan's laws Transposition Material implication Material equivalence Exportation Tautology
Predicate logic
Universal generalization Universal instantiation Existential generalization Existential instantiation
v t e

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

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

↑ Copi and Cohen
↑ Moore and Parker
↑ Hurley

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.