User:Phantomsq/命題邏輯

基本術語

• 陳述
• 命題
• 原子命題（簡單命題）
• 命題公式
• 命題常元
• 命題變元

命題連接詞

意義	符號	其他符號	說明
否定	$\lnot P$	~	非P
合取	$P\land Q$	‧	P且Q
析取	$P\lor Q$		P或Q
蘊涵	$P\to Q$	⊃	若P則Q，P為Q的充分條件，Q為P的必要條件
等值	$P\leftrightarrow Q$	≣	P若且唯若Q，P為Q的充要條件

二元連接詞

主条目：逻辑运算符

P	Q	$\bot$	$\land$														$\top$
0	0	0	0	0	0	1	0	0	0	1	1	1	0	1	1	1	1
0	1	0	0	0	1	0	0	1	1	0	0	1	1	0	1	1	1
1	0	0	0	1	0	0	1	0	1	0	1	0	1	1	0	1	1
1	1	0	1	0	0	0	1	1	0	1	0	0	1	1	1	0	1
		f0	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12	f13	f14	f15

推理規則

基本及衍生的推理形式：

名稱	推理式	說明
排中律 (Law of excluded middle)	$\vdash (p\lor \neg p)$	$p$ or not $p$ is true
無矛盾律 (Law of non-contradiction)	$\vdash \neg (p\land \neg p)$	$p$ and not $p$ is false, is a true statement
雙否定律 (Double Negation, DN)	$\neg \neg p\vdash p$	$p$ is equivalent to the negation of not $p$
合取律 (Conjunction, conj)	$p,q\vdash (p\land q)$	$p$ and $q$ are true separately; therefore they are true conjointly
簡化律 (Simplification, simp)	$(p\land q)\vdash p$	$p$ and $q$ are true; therefore $p$ is true
添加律 (Addition, add)	$p\vdash (p\lor q)$	$p$ is true; therefore the disjunction ($p$ or $q$) is true
重言式1 (Tautology)	$p\vdash (p\lor p)$	$p$ is true is equiv. to $p$ is true or $p$ is true
重言式2 (Tautology)	$p\vdash (p\land p)$	$p$ is true is equiv. to $p$ is true and $p$ is true
實質蘊涵 (Material Implication)	$(p\to q)\vdash (\neg p\lor q)$	If $p$ then $q$ is equiv. to not $p$ or $q$
換質換位律 (Transposition, trans)	$(p\to q)\vdash (\neg q\to \neg p)$	If $p$ then $q$ is equiv. to if not $q$ then not $p$
實質等值1 (Material Equivalence)	$(p\leftrightarrow q)\vdash ((p\to q)\land (q\to p))$	($p$ iff $q$) is equiv. to (if $p$ is true then $q$ is true) and (if $q$ is true then $p$ is true)
實質等值2 (Material Equivalence)	$(p\leftrightarrow q)\vdash ((p\land q)\lor (\neg p\land \neg q))$	($p$ iff $q$) is equiv. to either ($p$ and $q$ are true) or (both $p$ and $q$ are false)
實質等值3 (Material Equivalence)	$(p\leftrightarrow q)\vdash ((p\lor \neg q)\land (\neg p\lor q))$	($p$ iff $q$) is equiv to., both ($p$ or not $q$ is true) and (not $p$ or $q$ is true)
交換律1 (Commutation, comm)	$(p\lor q)\vdash (q\lor p)$	($p$ or $q$) is equiv. to ($q$ or $p$)
交換律2 (Commutation, comm)	$(p\land q)\vdash (q\land p)$	($p$ and $q$) is equiv. to ($q$ and $p$)
交換律3 (Commutation, comm)	$(p\leftrightarrow q)\vdash (q\leftrightarrow p)$	($p$ is equiv. to $q$) is equiv. to ($q$ is equiv. to $p$)
結合律1 (Association, asso)	$(p\lor (q\lor r))\vdash ((p\lor q)\lor r)$	$p$ or ($q$ or $r$) is equiv. to ($p$ or $q$) or $r$
結合律2 (Association, asso)	$(p\land (q\land r))\vdash ((p\land q)\land r)$	$p$ and ($q$ and $r$) is equiv. to ($p$ and $q$) and $r$
分配律1 (Distribution, dist)	$(p\land (q\lor r))\vdash ((p\land q)\lor (p\land r))$	$p$ and ($q$ or $r$) is equiv. to ($p$ and $q$) or ($p$ and $r$)
分配律2 (Distribution, dist)	$(p\lor (q\land r))\vdash ((p\lor q)\land (p\lor r))$	$p$ or ($q$ and $r$) is equiv. to ($p$ or $q$) and ($p$ or $r$)
狄摩根定理1 (De Morgan's Theorem, DeM)	$\neg (p\land q)\vdash (\neg p\lor \neg q)$	The negation of ($p$ and $q$) is equiv. to (not $p$ or not $q$)
狄摩根定理2 (De Morgan's Theorem, DeM)	$\neg (p\lor q)\vdash (\neg p\land \neg q)$	The negation of ($p$ or $q$) is equiv. to (not $p$ and not $q$)
正前律 (Modus Ponens, MP)	$((p\to q)\land p)\vdash q$	If $p$ then $q$; $p$; therefore $q$
負後律 (Modus Tollens, MT)	$((p\to q)\land \neg q)\vdash \neg p$	If $p$ then $q$; not $q$; therefore not $p$
選言三段論 (Disjunctive Syllogism, DS)	$((p\lor q)\land \neg p)\vdash q$	Either $p$ or $q$, or both; not $p$; therefore, $q$
假言三段論 (Hypothetical Syllogism, HS)	$((p\to q)\land (q\to r))\vdash (p\to r)$	If $p$ then $q$; if $q$ then $r$; therefore, if $p$ then $r$
移出律 (Exportation)	$((p\land q)\to r)\vdash (p\to (q\to r))$	from (if $p$ and $q$ are true then $r$ is true) we can prove (if $q$ is true then $r$ is true, if $p$ is true)
移入律 (Importation)	$(p\to (q\to r))\vdash ((p\land q)\to r)$	If $p$ then (if $q$ then $r$) is equivalent to if $p$ and $q$ then $r$
組合律 (Composition, comp)	$((p\to q)\land (p\to r))\vdash (p\to (q\land r))$	If $p$ then $q$; and if $p$ then $r$; therefore if $p$ is true then $q$ and $r$ are true
建設性兩難 (Constructive Dilemma, CD)	$((p\to q)\land (r\to s)\land (p\lor r))\vdash (q\lor s)$	If $p$ then $q$; and if $r$ then $s$; but $p$ or $r$; therefore $q$ or $s$
破壞性兩難 (Destructive Dilemma, DD)	$((p\to q)\land (r\to s)\land (\neg q\lor \neg s))\vdash (\neg p\lor \neg r)$	If $p$ then $q$; and if $r$ then $s$; but not $q$ or not $s$; therefore not $p$ or not $r$
雙向兩難 (Bidirectional Dilemma, BD)	$((p\to q)\land (r\to s)\land (p\lor \neg s))\vdash (q\lor \neg r)$	If $p$ then $q$; and if $r$ then $s$; but $p$ or not $s$; therefore $q$ or not $r$
歸繆法 (Reductio ad absurdum)	$((\lnot p\to q)\land (\lnot p\to \lnot q))\vdash p$
枚舉法 (Proof by cases)	$((p\lor q)\land (p\to q)\land (p\to r))\vdash r$
爆炸原理 (Principle of explosion)	$(p\land \lnot p)\vdash q$