¬(p1 ∧ p2 ∧ ··· ∧ p n) ⇔ ¬p 1 ∨ ¬p 2 ∨ ··· ∨ ¬p ¬(p1 ∨ p2

情報ネットワーク学基礎１講義ノート（4 月 23 日）
氏名：
ド・モルガンの法則，分配法則の一般化について
[9]
ド・モルガンの法則と分配法則については以下のより一般の形が成り立ち，よく使用される．
p1 , p2 , . . . pn , q （ただし n は自然数）を論理式とするとき，
¬(p1 ∧ p2 ∧ · · · ∧ pn ) ⇔ ¬p1 ∨ ¬p2 ∨ · · · ∨ ¬pn
¬(p1 ∨ p2 ∨ · · · ∨ pn ) ⇔ ¬p1 ∧ ¬p2 ∧ · · · ∧ ¬pn
がド・モルガンの法則として成立．また，
q ∨ (p1 ∧ p2 ∧ · · · ∧ pn ) ⇔ (q ∨ p1 ) ∧ (q ∨ p2 ) ∧ . . . (q ∨ pn )
q ∧ (p1 ∨ p2 ∨ · · · ∨ pn ) ⇔ (q ∧ p1 ) ∨ (q ∧ p2 ) ∨ . . . (q ∧ pn )
も成立する．証明はド・モルガンの法則と分配法則（n = 2 の場合）を繰り返し用いて示せる．
（Cf. 帰納法）
[10]
命題論理を用いた推論（inference）
命題 A1 , A2 , . . . , An が前提として仮定されているとき，
A1 ∧ A2 ∧ · · · ∧ An =⇒ B
(1)
がトートロジーなら，A1 , A2 , . . . , An から B を結論して良い1 ．式 (1) がトートロジーのとき
「推論 A1 , A2 , · · · , An −→ B は正しい」
と書きあらわす. このとき
「前提 (premise)A1 , A2 , · · · , An から命題 B が結論 (conclusion) として導かれた」
と解釈できる.
［例題］以下の推論 (a)∼(c) は正しいか．もし誤っているなら反論せよ（間違っている理由を具体的に指摘
せよ）．
(1) コーヒーを飲むと，目が覚める．従って，
(a) 目が覚めるので，コーヒーを飲む．
(b) 目が覚めないので，コーヒーを飲まない．
(c) コーヒーを飲まないので，目が覚めない．
(2) 学校に行けば，友達に会える．友達に会えるなら，研究がはかどる．従って，学校に行けば研究がはか
どる．
1
前提が偽なら，式 (1) は真だが，推論としては考える意味がない．
1
[11]
条件法「p ⇒ q 」について（逆は真ならず，対偶もまた真なり．
）
p は q の，q は p のという．
• q ⇒ p は p ⇒ q の（Converse）という．
• ¬p ⇒ ¬q は p ⇒ q の（Inverse）という．
• ¬q ⇒ ¬p は p ⇒ q の（Contraposition）という．
p⇒q
#
$
¬p ⇒ ¬q
[12]
"
!
&
&
%
%
%
&
%
&
& %%
&
%
% &&
%
&
%
&
%
&
%
&
"
!
q⇒p
#
$
¬q ⇒ ¬p
トートロジーの判定法
以下のような方法が良く用いられる：
(1) 真理値表
(a) 真面目に全て書く
(b) 真理値表の重要なところだけをチェックする




 A がトートロジー

(2) 同値変形：
なら B もトートロジー．
かつ

 A ⇒ B がトートロジー 

(3) トートロジー A に現れる命題変数に任意の論理式を代入してもトートロジー
! トートロジーの定義から明らか
[13]
推論式を解析するための注意点
命題論理に関する推論は原理的には必ず解析できる. しかし, 一般に真理値表をすべて書き出すのは非常に
大変である. 例えば,
• ２個の単純命題からなる場合の真理値表は通り，真理関数は通り.
• ３個の単純命題からなる場合の真理値表は通り，真理関数は通り.
• （一般に）n 個の単純命題からなる場合の真理値表は通り，真理関数は通り.
2
そこで，通常はトートロジーを証明する際に用いたテクニックやいろいろな定理を使って議論をする. 特に，
A ⇒ B は A が偽ならば B は常に真であることを考慮すると，A が真のときに B が真であることを示せば良
いことが分かる．つまり，
「推論 A1 , A2 , · · · , An → B が正しい」
とは
「全ての前提 A1 , A2 , · · · , An が真であるときに結論 B が真となる」
ことである．
(1) 真理値表の必要なところのみを調べる.
［例題］以下の推論は正しいか，正しくないか．正しくない場合には，反証を与え，論破せよ．
前提「私が犯人ならば私にはアリバイがない. 」かつ
「私は犯人ではない.」
結論「ゆえに私にはアリバイがある.」
［例題］以下の推論は正しくない．反証を与え，論破せよ．
前提「恐竜の祖先は，鳥類か爬虫類のいづれかだ．
」かつ
「恐竜の祖先が鳥類で，かつ鳥類の祖先が爬虫類ならば，恐竜の祖先は爬虫類である．
」
結論「恐竜の祖先は爬虫類である．
」
(2) 証明したトートロジーをつかう．
［例題］p ⇒ q, p ∨ r −→ q ∨ r が正しい事を証明せよ．
3
述語論理
§2
[1]
述語論理が必要なわけ
［例］「犯人でなければアリバイがある」
(
p：犯人である
として，上の論理式を書き，その対偶を書け．
q：アリバイがある
何かおかしなことはないか？それはなぜか？
変数 x 容疑者のうち誰かとし，p(x) ⇔「x は犯人である」とする．このとき x が与えられると，
（例えば
p(x = A さん) のように）p(x) の真偽が決定される．逆に言うと変数を含んだ式 p(x) の真偽は一般には定まら
ない．
[2]
述語 (predicate) とは
• 変数を含んだ命題．
注意 1
• 変数には自由変数と束縛変数の二つがある．
• 変数は 2 個以上あってもよい．
• 複数の述語を ¬, ∨, ∧, ⇐, ⇔ などで結合しても述語．
• 変数 x の定義されている範囲を変域という．
• 変数 x, y に対してそれらの変域が同じならば，p(x) も p(y) も同じものである.
［例］
(1) 1 変数述語，p(x), q(x), A(x), . . . などと書く．
［例］ P (x) ⇔ x2 ≥ 3
［例題］x ∈ R に対して2 ，述語 P (x) が真になる x，偽になる x を一つずつ例示せよ．
(2) 2 変数述語，p(x, y), q(x, y), A(x, y), . . . などと書く．
［例］ Q(x, y) ⇔ x2 − y 2 = 4
［例題］x ∈ N, y ∈ R に対して3 ，述語 Q(x, y) が真になる (x, y)，偽になる (x, y) を一つずつ例示せよ．
2
3
R：実数 (real number) の集合．x ∈ X は x が集合 X の要素であることを表す．
「集合と写像」の時に扱う．
N：自然数 (natural number) の集合．
4
[3]
限定作用素 (quantifier)
記号
名称（日本語）
∃
∀
名称（英語）
読み（日本語）
Existential quantifier
Universal quantifier
注意 2 今後この講義では x の変域 X は
X = {a1 , a2 , . . . , an }
のような有限集合4 を中心に扱う．証明も有限集合の場合のみを扱うことにする．
x の変域を X とすると，
)
1 if
(1) ∀x P (x) =
0 if
(2) ∃x P (x) =
)
1 if
0 if
x の変域を有限集合 {a1 , a2 , . . . , an } とすると，
• ∀x P (x) ⇐⇒
• ∃x P (x) ⇐⇒
［ド・モルガンの法則］
(1) ¬(∀x P (x)) ⇐⇒
(2) ¬(∃x P (x)) ⇐⇒
4
1, 2, 3, . . . のように数えることができ、かつ要素数が有限．詳しくは集合と写像で扱う．
5
読み（英語）
[4]
演習問題
問題 3
以下の推論について正しいか間違っているかを考察せよ．間違っている場合は反証を与え，論破せよ．
問 3-1 前提「研究がおもしろいならば，論文が書ける．
」かつ
「研究がおもしろい，または先生が素晴らしい．
」
結論「先生が素晴らしいならば，論文が書ける．
」
問 3-2 前提「晴れているならば，富士山が見えるかスカイツリーが見える」かつ
「富士山が見えるならば，スカイツリーが見える．
」かつ
「雲がかかっているならば，スカイツリーが見えない．
」
結論「晴れているならば，雲がかかっていない．
」
問 3-3 (p ∨ q) ⇒ r, s ⇒ ¬q, t ⇒ ¬q, s ∧ ¬t −→ r
問 3-4 p ⇒ (r ⇒ ¬q), ¬s ∨ p, q −→ s ⇒ ¬r
問題 4
問 4-1 次の日本語を二変数述語を用いて書き表せ．ただし，L(x, y) ⇐⇒「x は y を訪れた．
」とし，x の変域は
人全体，y の変域は国全体とする．
(1) x は，すべての国を訪れた．
(2) どの人も y を訪れた．
(3) y を訪れた人がいる．
(4) x は，訪れたことがある国がある．
問 4-2 P (x) の変数 x の変域を X100 = {a1 , a2 , . . . , a100 } としたとき，
(a) ¬ (P (a1 ) ∧ P (a2 ) ∧ · · · ∧ P (ak )) ⇔ ¬P (a1 ) ∨ ¬P (a2 ) ∨ · · · ∨ ¬P (ak )
(b) ¬ (P (a1 ) ∨ P (a2 ) ∨ · · · ∨ P (ak )) ⇔ ¬P (a1 ) ∧ ¬P (a2 ) ∧ · · · ∧ ¬P (ak )
がすべての k = 2, 3, . . . , 100 において成立することを示せ（注意：k の最大値を 100 としているが，そこ
は気にせず帰納法を用いてよい）．
これが証明できると，X100 = {a1 , a2 , . . . , a100 } に対し述語論理のド・モルガン
¬(∀x P (x)) ⇐⇒ ∃x ¬P (x)
¬(∃x P (x)) ⇐⇒ ∀x ¬P (x)
が示されたことになる．
今回は，x の変域を X100 = {a1 , a2 , . . . , a100 } としたが，変域を X = {a1 , a2 , . . . , an } としても同様の議
論ができる．
6

Download Report