離散数学　命題

今回は、命題についてまとめました。

用語について

命題

正しいか正しくない（真か偽か）を判断できる文や式を命題といいます。命題を表す記号（命題変数）として、p,q,rなどがよく用いられます。

真理値

命題が真であるか、偽であるかという情報を、命題の真理値（論理値）といいます。真、偽をそれぞれT(True)、F(False)で表します。

論理演算子

論理積

命題p, qに対して、pかつqも成り立つという文を作ると、これも命題になります。このことをpとqの論理積、連言といい、

$$p\land q$$

で表します。p, qの真理値がわかっているとき、\(p\land q\)の真理値は以下のような表（真理値表という）にまとめることができます。

$$p$$	$$q$$	$$p\land q$$
F	F	F
F	T	F
T	F	F
T	T	T

論理和

命題p, qに対して、pまたはqも成り立つという文を作ると、これも命題になります。このことをpとqの論理和、選言といい、

$$p \lor q$$

で表します。論理和の真理値表は以下になります。

$$p$$	$$q$$	$$p\land q$$
F	F	F
F	T	T
T	F	T
T	T	T

否定

命題pに対して、pではないという文を作ると、これも命題になります。この命題をpの否定といい、

$$\lnot p$$

で表します。否定の真理値表は以下になります。

$$p$$	$$\lnot p$$
F	T
T	F

論理演算

論理演算は上記の真理値表に対応させて、機械的に計算することができます。実際の文や式を解釈することなく、pかつqなどの真偽を判断することができます。

恒真命題

いかなる解釈でも真となるとなる命題を恒真命題といいます。恒真命題の例を示します。

$$p$$	$$\lnot p$$	$$p \lor \lnot p$$
F	T	T
T	F	T

真理値表を見ると、命題pの真理値が真偽どちらでも、\(p \lor \lnot p\)の真理値はTとなることがわかります。

矛盾命題

いかなる解釈でも偽となる命題を矛盾命題といいます。矛盾命題の例を示します。

$$p$$	$$\lnot p$$	$$p \land \lnot p$$
F	T	F
T	F	F

真理値表を見ると、命題pの真理値が真偽どちらでも、\(p \land \lnot p\)の真理値はFとなることがわかります。

論理同値

2つの命題p, qがあって、真理値表が一致する場合、論理同値といいます。命題が論理同値であるとは、同じ内容を主張していることを意味しているので、命題pをq（あるいはqをpで）置き換えてもよいことになります。これによって、様々な式の変形ができるようになります。

命題代数

含意

pならばqであるという形の文を一般に条件文と言います。条件文「pならばqである」について、命題pをその条件文の仮定、命題qをその条件文の結論と言います。

この条件文の形の命題を表すために、論理演算子→を導入します。pならばqを

$$p\rightarrow q$$

と表します。論理演算子→は含意と呼ばれます。p→qの真理値表は下記で定義されます。

$$p$$	$$q$$	$$p\rightarrow q$$
F	F	T
F	T	F
T	F	F
T	T	T

同値

pとqは同値であるという形の命題を表すための演算子\(\leftrightarrow\)を導入します。pとqが同値であるということは、pが真のとき、qも真であり、pが偽のとき、qも偽であることを表します。pとqが同値であることを

$$p\leftrightarrow q$$

で表します。\(p \leftrightarrow q\)の真理値表は以下のように定義されます。

$$p$$	$$q$$	$$p \leftrightarrow q$$
T	T	T
T	F	F
F	T	T
F	F	T

逆

条件文「pならばq」に対して、仮定pと結論qを入れ替えて得られる条件文「qならばp」を「pならばq」の逆といいます。

裏

条件文「pならばq」に対して、仮定pと結論qの両方を否定して得られる条件文「pでないならばqではない」を「pならばq」の裏といいます。

対偶

条件文「pならばq」に対して、裏をとり、かつ逆をとると「qでないならばpではない」という条件文が得られます。このことを「pならばq」の対偶といいます。

述語

変数を含み、その変数の値が決まれば真偽の判断が可能な文や式を述語といいます。