命題論理(Propositional Logic) 述語論理(Predicate Logic) 論理式 命題変数


基本命題(命題変数)

真または偽のいずれかとなる文を命題(statement)という.
これ以上分解できない命題を基本命題という.
真・偽は0・1やT・Fで記述することもある. 

例 
4+2=4  (偽)
2+2=4  (真)   
今日のカレーはおいしいですか?  (真偽がアイマイなので命題であるかどうか微妙.)

いくつかの基本命題を組みあわせた命題を, 合成命題(compound statement)という.
(すなわち、簡単な命題を組みあわせて、いくらでも複雑な命題を作ることができる.)
基本命題や合成命題が真であるか偽であるかを, その命題の真理値という.

例
バラは赤いし, すみれは紫だ. 
赤井くんは賢いが, 青山くんは丈夫だ.
赤井くんが桐生に住んでいれば, 赤井くんは群馬県民だ.
緑川くんが足利に住んでいれば, 緑川くんは群馬県民でない.
(a < b)もしくは(c < b)

命題の記号化

基本命題に記号をわりあてる. (例 p, qなど.) これらを論理変数という.  
AND, OR, NOT, → を, 命題結合子という.
(p AND q), (p OR q), (NOT p), (p → q)を, それぞれ 
p かつ q, p または q, p でない, p ならば q と定義する.
これらを使って合成命題を記述する.

例  
p=1月12日は寒い, q=1月12日は雨がふっている
(p AND q) = 1月12日は寒いし, 雨がふっている.
(p OR q)  = 1月12日は寒い, もしくは, 雨がふっている.
(NOT p)   = 1月12日は寒くない.
(p → q)  = 1月12日が寒いならば, 1月12日は雨がふっている. 

(NOT (NOT p)) = 1月12日は寒くない ことはない.
(NOT p) AND (NOT q) = 1月12日は寒くない かつ 雨はふっていない

合成命題の真理値表

合成命題に含まれるすべての基本命題の真偽が与えられれば,
合成命題の真偽は定まる.
基本命題の真偽のすべての可能性に対し、合成命題の真偽を
表にしたものを真理値表という.
(合成命題は, 基本命題の真偽のすべての可能性, から, {真, 偽}への関数である.)


 p 
 q 
 p AND q
T
T
T
T
F
F
F
T
F
F
F
F



 p 
 q 
 p OR q
T
T
T
T
F
T
F
T
T
F
F
F



 p 
 NOT p
T
F
F
T



 p 
 q 
 p → q
T
T
T
T
F
F
F
T
T
F
F
T

pはqの原因を表しているのでは"ない"ことに注意!

例
4+2=6 AND 3+3=10  は真かな偽かな? 
4+2=6 OR 3+3=10  は真かな偽かな? 
4+2=6 → 3+3=10  は真かな偽かな? 
3+3=10 → 4+2=6  は真かな偽かな? 
NOT 3+3=10       は真かな偽かな? 



合成命題の真理値表の作りかた

まず, 合成命題中に含まれる基本命題の個数を数える. n個とする.
基本命題それぞれが真・偽である場合があるから全部で 2n 個の場合がある.
これらを表の各段に記入する.
合成命題の計算の順にしたがって, 各途中の段階の合成命題の真理値を求める.
全体の合成命題の真理値を求める.

例
(NOT (p AND ( NOT q)))


 p 
 q 
 NOT q 
p AND ( NOT q) 
 NOT ( p AND (NOT q))
 T 
 T 
 F 
 F 
 T
 T 
 F 
 T 
 T 
 F
 F 
 T 
 F 
 F 
 T
 F 
 F 
 T 
 F 
 T


例
(p AND (q or r)) 

恒真(tautology) と 充足可能 と 
 
矛盾(contradiction)(充足不可能)  

常に真となる合成命題を恒真という.
常に偽となる合成命題を矛盾という.

恒真の例
p OR (NOT p)
p → p
(p OR((NOT p) AND q)) = (p OR q)

矛盾の例
p AND (NOT p)

真理値表をかいて確かめよう.
命題1 = 命題2 が恒真のとき, これは, 常に命題1 を 命題2に書き変えても
よいことを意味する.

等価な命題

ふたつの命題が, 同じ基本命題のみを含み, 
これら基本命題のどのような真・偽のわりあてに対しても,
ふたつの命題の真理値が同じとき, これらふたつの命題は等価であるという.
(すなわち、同じことを、複雑にも、簡単にも、様々に表現できる.)
(これを利用して表現を簡単にできるかも.
      if文の条件を簡単な表現に置きかえる, とか,
      証明すべき命題を簡単な表現のものに置きかえる, 
      論理回路を簡単なものに置きかえる, 
などが可能となる.)

例 (( p AND q ) AND r ) と ( p AND ( q AND r) ) とは等価かな？ (結合則)
   p OR ( q AND r) と (p OR q) AND (p OR r) は等価かな? (分配則)
   NOT (p AND q) と (NOT p) OR (NOT q)  は等価かな? (ド モルガンの法則)
    NOT (p OR q) と (NOT p) AND (NOT q)  は等価かな? (ド モルガンの法則)
   p → q と (NOT q)→(NOT p) は等価かな? (対偶)

--------------------
問題
p → q と (NOT p) OR q は等価かな?  ("ならば→"の削除)

問題
下記から"ならば→"を削除して等価な命題を作れ.

寒いならば, 彼はぼうしをかぶる.
生産性があがれば, 給料があがる.


Predicate Logic(述語論理)  
(論理関数からなる論理である。引数の値によって、関数は真にも偽にもなります。
 真のことも偽のこともあります。SQL等の基礎でもある。)
(これに対して、命題論理は、変数の論理です。)

r    : 雨がふる
u(X) : Xさんは傘を持つ
w(X) : Xさんはぬれる

r → u(X):  もし雨がふれば、(Xさんがどんな人でも)Xさんは傘を持つ
u(X) → NOT w(X) : もしXさんが傘を持っていれば、Xさんはぬれない

score(C,S,G) 科目Cで, 学生Sは, 成績G であった。 

for all       = 任意のxxxは yyy である
there exists  = yyyなる xxxが存在する
(それぞれの否定は？)



今回のオススメ本

Title:  Foundations of Computer Science C Edition
        (第12章 Propositional Logic)
Author: A.V. Aho, J.D. Ullman
Hardcover, 786 pages, ISBN: 1-7167-8284-7, Published 1995, Price $68.95

Title:  2000 Solved Problems in Discrete Mathematics (第12章 Propositional Calculus)
Author: Seymour Lipschutz, Marc Lipson
Paperback, 404 pages, ISBN 0-07-038031-7, Published 1992, Price $19.95

Title:  情報系の数学入門 (第3章 論理)
Author: 林 晋,  他
Paperback, 143 pages, ISBN: 4-274-12948-9, Published 1993, Price 2300円

(クイズ) 真理値表を書け
(a)   p or (q or r)
(b)   (p or q) and ( p or r)
(c)   not (p and q)
(d)   (not p) or ( not q)