論理 Logic
<Propositional Calculus/Propositional Logic>
真か偽(True or False)か、どちらか一方に明確に定まる主張を命題(Proposition)という。
例：
命題: Washington, D.C., is the capital of the U.S.A. …真(True)
命題: 2 + 2 = 3 …偽(False)
What time is it? …真か偽か分からないので命題ではない
命題を英小文字p, q, r, ... (propositional variable/statement variable)などを使って表す。
また、命題の真偽を真理値(Truth value)といい、真の時はT、偽の時はFを使って表す。
例：
p = 犬は動物である…T
q = Tronto is the capital of Canada. …F
<論理式（Compound Propositions）>
いくつかの命題が∧、∨、¬(connective operators)によって結びつけられている命題を論理式(compound propositions)という。
- 論理否定(negation)
命題pについて、命題pの否定を¬pと表す。
p = 犬は動物である …T
¬p = 犬は動物ではない …F
- 連言、論理積(conjunction)
命題p、qについて、p∧qで表される。
It is true when both p and q are true and is false otherwise.
p＝犬は動物である …T、q＝バラは植物である …T
p∧q＝犬は動物であり、バラは植物である …T
r＝犬は動物ではない …F、s＝バラは植物である …T
r∧s＝犬は動物ではなく、バラは植物である …F
t＝犬は動物ではない …F、u＝バラは植物ではない …F
t∧u＝犬は動物でなく、バラは植物でない …F
- 選言、論理和(disjunction)
命題p、qについて、p∨qで表される（inclusive or）。
It is false when both p and q are false and is true otherwise.
p＝Students who have taken calculus…T、q＝Students who have taken CS…T
p∨q＝Students who have taken calculus or CS can take this class…T
対し、exclusive orはp⊕qと表される。
It is true when exactly one of p and q is true and false otherwise.
p＝Students who have taken calculus…T、q＝Students who have taken CS…T
p⊕q＝Students who have taken calculus or CS, but not both, can take this class…F
- 条件命題(conditional statement)
命題p、qに対して「もしpならばqである(If p, then q)」という命題（十分条件）。p→qと表される。
pを条件(hypothesis/premise)、qを結論(conclusion/consequence)という。
It is false when p is true and q is false, and true otherwise.
p＝ You get 100% on the final…F、q＝ You get an A…T
p→q＝ If you get 100% on the final, then you will get and A…T
期末で100点を取れなくても、他の要因でAを取れる可能性がある。
「pはqの必要十分条件である(p if and only if)」という形の命題を重条件文(biconditional statement/bi-implications)といい、p⇔qと表される。
It is true when p and q have the same truth values, and is false otherwise.
p＝ You can take the flight…F、q＝ You buy a ticktet…F
p⇔q＝ You can take the flight if and only if you buy a ticket…T
論理式の優先順位は一に否定、二に∨、∧、最後に→、⇔となる。
<真理表(Truth Table)>
命題の真偽を表に表したものを真理表(truth table)という。
＜逆、裏、対偶＞
命題p→qを基準にして、
q→pを逆(converse)、¬p→¬qを裏(inverse)、¬q→¬pを対偶(contrapositive)という。
例：
The home team wins whenever it is raining.＝If it is raining, then the home team wins.
p＝It is raining、q＝ The home team wins
逆(converse)は、
If the home team wins, then it is raining.
裏(inverse)は、
If it is not raining, then the home team does not win.
対偶(contrapositive)は、
If the home team does not win, then it is not raining.＝ original statement
２つの論理式の真偽が完全に一致する時、同値(equivalent)という。
例：
真理表より、p→qと¬q→¬pは同値である。先の例からも同値であることが分かる。
<恒真命題、矛盾命題>
命題が、それを構成している命題の真偽にかかわらず恒に真である時、恒真命題(tautology)といい、恒に偽である時、矛盾命題(contradiction)という。
恒真命題、矛盾命題のどちらでもない条件命題をcontingencyという。
また、pとqの重条件p⇔qが恒真命題の時、pとqはlogically equivalentといい、p≡qと表される。
例：
p∨¬pはtautology、(p∧q)∧¬pはcontradiction。
<ド・モルガンの法則(De Morgan Laws)>
¬(p∧q) ≡ ¬p∨¬q
¬(p∨q) ≡ ¬p∧¬q
<Logical Equivalences>
- ベキ等律(Idempotent laws)
p∨p ≡ p、p∧p ≡ p
- 交換律(Commutative laws)
p∨q ≡ q∨p、p∧q ≡ q∧p
- 結合律(Associative laws)
(p∨q)∨r ≡ p∨(q∨r)、(p∧q)∧r ≡ p∧(q∧r)
- 分配律(Distributive laws)
p∨(q∧r) ≡ (p∨q)∧(p∨r)、p∧(q∨r) ≡(p∧q)∨(p∧r)
- Absorption laws
p∨(p∧q) ≡ p、p∧(p∨q) ≡ p
論理式がある真理値割り当ての際に真となる時、その論理式は充足可能(satisfiable)といい（恒真命題も充足可能である）、また真理値割り当ての際に恒に偽となる時、その論理式は充足不能(unsatisfiable)という（矛盾命題）。
<コンピュータのお話 Bitについて>
コンピュータはビットを使って情報を表す。
ビットは０か１の値でこれを二進数(binary)と呼ぶ。
ビットは０か１かの二つしかないため、これを使って真理値(True or False)を表すことができる。１をT(Truth)、０をF(False)とする。プログラミングの際、０がFalse valueとなるのはこのためである。
ある変数の値がTrueかFalseかのどちらかである時、その変数をブール変数(Boolean variable)という。よって、ブール変数はビットを使って表すことができる。
ビットの演算は論理式に対応している。
