初等數論/基礎邏輯

邏輯(Boolean Logic)遵從以下的推理：

• 一個命題$P$，要不為真，要不為偽
• 命題$P$的否定記做$(\mathrm{\neg }P)$
• 假如命題$P\to Q$(讀作：「若P則Q」)成立，則$(\mathrm{\neg }Q)\to (\mathrm{\neg }P)$亦成立
• $P\wedge Q$意為「$P$成立且$Q$成立」
• $P\vee Q$意為「$P$成立或者$Q$成立」
• $P\equiv Q$意即$P$與$Q$的陳述在邏輯上為等價的
• $\mathrm{\neg }(P\wedge Q)\equiv (\mathrm{\neg }P)\vee (\mathrm{\neg }Q)$
• $\mathrm{\neg }(P\vee Q)\equiv (\mathrm{\neg }P)\wedge (\mathrm{\neg }Q)$

真值表

真值表為一種檢驗命題真偽的方法，為將命詞中的所有命題假設為真或偽看它的真偽性，若在所有可能的狀況下此命題皆為真則此命題恆真，若在所有可能的狀況下此命題皆為偽則此命題恆偽

若兩個命題在不同狀況下的真偽相同則說這兩個命題等價

以下為一些命題的真值表：

$P\wedge Q$的真值表

真偽	$P$	$Q$	$P\wedge Q$
第一種狀況	T	T	T
第二種狀況	T	F	F
第三種狀況	F	T	F
第四種狀況	F	F	F

$P\vee Q$的真值表

真偽	$P$	$Q$	$P\vee Q$
第一種狀況	T	T	T
第二種狀況	T	F	T
第三種狀況	F	T	T
第四種狀況	F	F	F

$((\mathrm{\neg }P)\vee (\mathrm{\neg }Q))\vee (P\vee Q)$的真值表

真偽	$P$	$Q$	$((\mathrm{\neg }P)\vee (\mathrm{\neg }Q))\vee (P\vee Q)$
第一種狀況	T	T	T
第二種狀況	T	F	T
第三種狀況	F	T	T
第四種狀況	F	F	T

因此這是個恆為真的命題

$(\mathrm{\neg }P)\vee Q$的真值表

真偽	$P$	$Q$	$(\mathrm{\neg }P)\vee Q$
第一種狀況	T	T	T
第二種狀況	T	F	F
第三種狀況	F	T	T
第四種狀況	F	F	T

$P\to Q$的真值表

真偽	$P$	$Q$	$P\to Q$
第一種狀況	T	T	T
第二種狀況	T	F	F
第三種狀況	F	T	T
第四種狀況	F	F	T

由$(\mathrm{\neg }P)\vee Q$的真值表和$P\to Q$的真值表可知，命題$P\to Q\equiv (\mathrm{\neg }P)\vee Q$