CWKSC's blog | 博客 (已棄用)

命題邏輯 Logical Equivalences 邏輯等價, Rules of Inference 推理規則

Featured image

命題邏輯的 Logical Equivalences 邏輯等價, Rules of Inference 推理規則

Logical Equivalences

\[\displaylines{ \begin{array}{|c|c|c|} \hline \text{Equivalence} & \text{Name} \\ \hline \mathbb{\displaylines{p \wedge \top \equiv p \\ p\vee \bot \equiv p}} & \text{Identity laws}\\ \hline \mathbb{\displaylines{p\vee \top \equiv \top \\\ p\wedge \bot \equiv \bot}} & \text{Domination laws}\\ \hline \mathbb{\displaylines{p \vee p \equiv p\\\ p \wedge p \equiv p}} & \text{Idempotent or tautology laws}\\ \hline \mathbb{\displaylines{\lnot (\lnot p) \equiv p}} & \text{Double negation law}\\ \hline \mathbb{\displaylines{p \vee q \equiv q \vee p \\\ p \wedge q \equiv q \wedge p}} & \text{Commutative laws} \\ \hline \mathbb{\displaylines{(p\vee q)\vee r\equiv p\vee (q\vee r)\\\ (p\wedge q)\wedge r\equiv p\wedge (q\wedge r)}} & \text{Associative laws}\\ \hline \mathbb{\displaylines{p\vee (q\wedge r)\equiv (p\vee q)\wedge (p\vee r) \\\ p\wedge (q\vee r)\equiv (p\wedge q)\vee (p\wedge r)}} & \text{Distributive laws} \\ \hline \mathbb{\displaylines{\neg (p\wedge q)\equiv \neg p\vee \neg q \\\ \neg (p\vee q)\equiv \neg p\wedge \neg q}} & \text{De Morgan's laws} \\ \hline \mathbb{\displaylines{p\vee (p\wedge q)\equiv p\\\ p\wedge (p\vee q)\equiv p}} & \text{Absorption laws}\\ \hline \mathbb{\displaylines{p\vee \neg p\equiv \top\\\ p\wedge \neg p\equiv \bot}} & \text{Negation laws}\\ \hline \end{array} }\]

Logical Equivalences Involving Conditional Statements

\[\displaylines{ \begin{aligned} p\rightarrow q &\equiv \neg p\vee q\\\ p\rightarrow q &\equiv \neg q\rightarrow \neg p\\\ p\vee q&\equiv \neg p\rightarrow q\\\ p\wedge q&\equiv \neg (p\rightarrow \neg q)\\\ \neg (p\rightarrow q)&\equiv p\wedge \neg q\\\ (p\rightarrow q)\wedge (p\rightarrow r)&\equiv p\rightarrow (q\wedge r)\\\ (p\rightarrow q)\vee (p\rightarrow r)&\equiv p\rightarrow (q\vee r)\\\ (p\rightarrow r)\wedge (q\rightarrow r)&\equiv (p\vee q)\rightarrow r\\\ (p\rightarrow r)\vee (q\rightarrow r)&\equiv (p\wedge q)\rightarrow r \end{aligned} }\]

Logical Equivalences Involving Biconditional Statements

\[\displaylines{ \begin{aligned} p\leftrightarrow q&\equiv (p\rightarrow q)\wedge (q\rightarrow p)\\\ p\leftrightarrow q&\equiv \neg p\leftrightarrow \neg q\\\ p\leftrightarrow q&\equiv (p\wedge q)\vee (\neg p\wedge \neg q)\\\ \neg (p\leftrightarrow q)&\equiv p\leftrightarrow \neg q \end{aligned}}\]

Rules of Inference

\[\displaylines{ \begin{array} {|c|c|}\hline Rule \space of\space Inference & Name \\ \hline \displaylines{p \\ \underline{p \rightarrow q} \\ \therefore q} & \text{Modus ponens} \\ \hline \displaylines{\lnot q \\ \underline{p \rightarrow q} \\ \therefore \lnot p}& \text{Modus tollens} \\ \hline \displaylines{p \rightarrow q \\ \underline{q \rightarrow r} \\ \therefore p \rightarrow r }& \text{Hypothetical syllogism} \\ \hline \displaylines{p \vee q\\ \lnot p \\ \overline{\therefore q}} & \text{Disjunctive syllogism} \\ \hline \displaylines{p \\ \overline{\therefore p \vee q}} & \text{Addition} \\ \hline \displaylines{\underline{p \wedge q}\\ \therefore p }& \text{Simplification} \\ \hline \displaylines{p\\ q\\ \overline{\therefore p \wedge q} }& \text{Conjunction} \\ \hline \displaylines{p \vee q\\ \lnot p \vee r\\ \overline{\therefore q \vee r}} & \text{Resolution} \\ \hline \end{array} }\]

Rules of Inference for Quantified Statements

\[\displaylines{ \begin{array} {|c|c|} \hline Rule \space of \space Inference & Name \\ \hline \displaylines{\forall x P(x) \\ \therefore P(c)}& \text{Universal instantiation} \\ \hline \displaylines{P (c) \space for \space an \space arbitrary\space c \\ \therefore \forall x P(x)} & \text{Universal generalization} \\ \hline \displaylines{\exists x P(x) \\\ \therefore P(x) \space for \space some \space element \space c }& \text{Existential instantiation} \\ \hline \displaylines{P(x) \space for \space some \space element \space c\\\ \therefore \exists x P(x)} & \text{Existential generalization}\\ \hline \end{array} }\]

Reference

Logical equivalence - Wikipedia

Rule of inference - Wikipedia

CWKSC

Author 作者

CWKSC

喜歡編程,會一點點鋼琴,會一點點畫畫,喜歡使用顏文字 About me 關於我

For any comments or discussions on my blog post, you can open an issue here

對於我博客文章的任何評論或討論,可以在這裏開一個 issue

Feel free to give your comments. OW<