命題

真か偽かが定まる文。

• 「2 は素数である」… 真の命題
• 「$x>3$」… 命題ではない（$x$ が決まらないと真偽が定まらない）。述語

複合命題#

論理演算で組み合わせる。

$$P\wedge Q,P\vee Q,\neg P,P\to Q$$

含意が分かりにくい#

$P\to Q$ は $P$ が偽のとき必ず真。

$P$	$Q$	$P\to Q$
T	T	T
T	F	F
F	T	T
F	F	T

「偽から何でも導ける」（vacuous truth）。 $P\to Q$ が偽になるのは「$P$ が真なのに $Q$ が偽」の 1 通りだけ、 と覚えると迷わない。

逆・裏・対偶#

	式	$P\to Q$ との関係
逆	$Q\to P$	同値でない
裏	$\neg P\to \neg Q$	同値でない
対偶	$\neg Q\to \neg P$	同値

対偶が同値であることが証明で使われる。 直接示しにくい主張を、対偶なら示せることがある。

参考文献#

• Kenneth H. Rosen. Discrete Mathematics and Its Applications, 8th ed. McGraw-Hill, 2019. https://www.mheducation.com/highered/product/discrete-mathematics-applications-rosen/M9781259676512.html
• MIT OCW 6.042J Mathematics for Computer Science https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-fall-2010/