From Wikipedia, the free encyclopedia
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
Inference rule that may be applied to only a particular segment of an expression
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 .
Common rules of replacement include de Morgan's laws , commutation , association , distribution , double negation ,[ a] transposition , material implication , logical equivalence , exportation , and tautology .
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
(
p
∨
q
)
∨
r
∴
p
∨
(
q
∨
r
)
¯
{\displaystyle {\begin{aligned}(p\vee q)\vee r\\\therefore {\overline {p\vee (q\vee r)}}\\\end{aligned}}}
(
(
p
∨
q
)
∨
r
)
→
(
p
∨
(
q
∨
r
)
)
{\displaystyle ((p\vee q)\vee r)\rightarrow (p\vee (q\vee r))}
Associative
p
∧
q
∴
q
∧
p
¯
{\displaystyle {\begin{aligned}p\wedge q\\\therefore {\overline {q\wedge p}}\\\end{aligned}}}
(
p
∧
q
)
→
(
q
∧
p
)
{\displaystyle (p\wedge q)\rightarrow (q\wedge p)}
Commutative
(
p
∧
q
)
→
r
∴
p
→
(
q
→
r
)
¯
{\displaystyle {\begin{aligned}(p\wedge q)\rightarrow r\\\therefore {\overline {p\rightarrow (q\rightarrow r)}}\\\end{aligned}}}
(
(
p
∧
q
)
→
r
)
→
(
p
→
(
q
→
r
)
)
{\displaystyle ((p\wedge q)\rightarrow r)\rightarrow (p\rightarrow (q\rightarrow r))}
Exportation
p
→
q
∴
¬
q
→
¬
p
¯
{\displaystyle {\begin{aligned}p\rightarrow q\\\therefore {\overline {\neg q\rightarrow \neg p}}\\\end{aligned}}}
(
p
→
q
)
→
(
¬
q
→
¬
p
)
{\displaystyle (p\rightarrow q)\rightarrow (\neg q\rightarrow \neg p)}
Transposition or contraposition law
p
→
q
∴
¬
p
∨
q
¯
{\displaystyle {\begin{aligned}p\rightarrow q\\\therefore {\overline {\neg p\vee q}}\\\end{aligned}}}
(
p
→
q
)
→
(
¬
p
∨
q
)
{\displaystyle (p\rightarrow q)\rightarrow (\neg p\vee q)}
Material implication
(
p
∨
q
)
∧
r
∴
(
p
∧
r
)
∨
(
q
∧
r
)
¯
{\displaystyle {\begin{aligned}(p\vee q)\wedge r\\\therefore {\overline {(p\wedge r)\vee (q\wedge r)}}\\\end{aligned}}}
(
(
p
∨
q
)
∧
r
)
→
(
(
p
∧
r
)
∨
(
q
∧
r
)
)
{\displaystyle ((p\vee q)\wedge r)\rightarrow ((p\wedge r)\vee (q\wedge r))}
Distributive
p
q
∴
p
∧
q
¯
{\displaystyle {\begin{aligned}p\\q\\\therefore {\overline {p\wedge q}}\\\end{aligned}}}
(
(
p
)
∧
(
q
)
)
→
(
p
∧
q
)
{\displaystyle ((p)\wedge (q))\rightarrow (p\wedge q)}
Conjunction
p
∴
¬
¬
p
¯
{\displaystyle {\begin{aligned}p\\\therefore {\overline {\neg \neg p}}\\\end{aligned}}}
p
→
(
¬
¬
p
)
{\displaystyle p\rightarrow (\neg \neg p)}
Double negation introduction
¬
¬
p
∴
p
¯
{\displaystyle {\begin{aligned}{\neg \neg p}\\\therefore {\overline {p}}\\\end{aligned}}}
(
¬
¬
p
)
→
p
{\displaystyle (\neg \neg p)\rightarrow p}
Double negation elimination
See also
Notes
References