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$

注釋