初等数论/基础逻辑

逻辑(Boolean Logic)遵从以下的推理：

• 一个命题$P$，要不为真，要不为伪
• 命题$P$的否定记做$(\neg P)$
• 假如命题$P\to Q$(读作：“若P则Q”)成立，则$(\neg Q)\to (\neg P)$亦成立
• $P\land Q$意为“$P$成立且$Q$成立”
• $P\lor Q$意为“$P$成立或者$Q$成立”
• $P\equiv Q$意即$P$与$Q$的陈述在逻辑上为等价的
• $\neg (P\land Q)\equiv (\neg P)\lor (\neg Q)$
• $\neg (P\lor Q)\equiv (\neg P)\land (\neg Q)$

真值表

真值表为一种检验命题真伪的方法，为将命词中的所有命题假设为真或伪看它的真伪性，若在所有可能的状况下此命题皆为真则此命题恒真，若在所有可能的状况下此命题皆为伪则此命题恒伪

若两个命题在不同状况下的真伪相同则说这两个命题等价

以下为一些命题的真值表：

$P\land Q$的真值表

真伪	$P$	$Q$	$P\land Q$
第一种状况	T	T	T
第二种状况	T	F	F
第三种状况	F	T	F
第四种状况	F	F	F

$P\lor Q$的真值表

真伪	$P$	$Q$	$P\lor Q$
第一种状况	T	T	T
第二种状况	T	F	T
第三种状况	F	T	T
第四种状况	F	F	F

$((\lnot P)\lor (\lnot Q))\lor (P\lor Q)$的真值表

真伪	$P$	$Q$	$((\lnot P)\lor (\lnot Q))\lor (P\lor Q)$
第一种状况	T	T	T
第二种状况	T	F	T
第三种状况	F	T	T
第四种状况	F	F	T

因此这是个恒为真的命题

$(\lnot P)\lor Q$的真值表

真伪	$P$	$Q$	$(\lnot P)\lor 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

由$(\lnot P)\lor Q$的真值表和$P\to Q$的真值表可知，命题$P\to Q\equiv (\lnot P)\lor Q$