Rule of replacement

Transformation rules
Propositional calculus
Rules of inference
Implication introduction / elimination (modus ponens) Biconditional introduction / elimination Conjunction introduction / elimination Disjunction introduction / elimination Disjunctive / hypothetical syllogism Constructive / destructive dilemma Absorption / modus tollens / modus ponendo tollens Negation introduction
Rules of replacement
Associativity Commutativity Distributivity Double negation De Morgan's laws Transposition Material implication Exportation Tautology
Predicate logic
Rules of inference
Universal generalization / instantiation Existential generalization / instantiation

In logic, a rule of replacement^[1]^[2]^[3] is a transformation rule that may be applied to only a particular segment of an expression. A logical system may be constructed so that it uses either axioms, rules of inference, or both as transformation rules for logical expressions in the system. Whereas a rule of inference is always applied to a whole logical expression, a rule of replacement may be applied to only a particular segment. Within the context of a logical proof, logically equivalent expressions may replace each other. Rules of replacement are used in propositional logic to manipulate propositions.

Table: Rules of Replacement

The rules above can be summed up in the following table.^[4] The "Tautology" column shows how to interpret the notation of a given rule.

Rules of inference	Tautology	Name
${\begin{aligned}(p\vee q)\vee r\\\therefore {\overline {p\vee (q\vee r)}}\\\end{aligned}}$	$((p\vee q)\vee r)\rightarrow (p\vee (q\vee r))$	Associative
${\begin{aligned}p\wedge q\\\therefore {\overline {q\wedge p}}\\\end{aligned}}$	$(p\wedge q)\rightarrow (q\wedge p)$	Commutative
${\begin{aligned}(p\wedge q)\rightarrow r\\\therefore {\overline {p\rightarrow (q\rightarrow r)}}\\\end{aligned}}$	$((p\wedge q)\rightarrow r)\rightarrow (p\rightarrow (q\rightarrow r))$	Exportation
${\begin{aligned}p\rightarrow q\\\therefore {\overline {\neg q\rightarrow \neg p}}\\\end{aligned}}$	$(p\rightarrow q)\rightarrow (\neg q\rightarrow \neg p)$	Transposition or contraposition law
${\begin{aligned}p\rightarrow q\\\therefore {\overline {\neg p\vee q}}\\\end{aligned}}$	$(p\rightarrow q)\rightarrow (\neg p\vee q)$	Material implication
${\begin{aligned}(p\vee q)\wedge r\\\therefore {\overline {(p\wedge r)\vee (q\wedge r)}}\\\end{aligned}}$	$((p\vee q)\wedge r)\rightarrow ((p\wedge r)\vee (q\wedge r))$	Distributive
${\begin{aligned}p\\q\\\therefore {\overline {p\wedge q}}\\\end{aligned}}$	$((p)\wedge (q))\rightarrow (p\wedge q)$	Conjunction
${\begin{aligned}p\\\therefore {\overline {\neg \neg p}}\\\end{aligned}}$	$p\rightarrow (\neg \neg p)$	Double negation introduction
${\begin{aligned}{\neg \neg p}\\\therefore {\overline {p}}\\\end{aligned}}$	$(\neg \neg p)\rightarrow p$	Double negation elimination

^ Copi, Irving M.; Cohen, Carl (2005). Introduction to Logic. Prentice Hall.
^ Hurley, Patrick (1991). A Concise Introduction to Logic 4th edition. Wadsworth Publishing. ISBN 9780534145156.
^ Moore and Parker^{[full citation needed]}
^ Kenneth H. Rosen: Discrete Mathematics and its Applications, Fifth Edition, p. 58.

This logic-related article is a stub. You can help Wikipedia by expanding it.

This page was last edited on 10 August 2023, at 02:19