第11章 命題計算 駆け足で読む『離散数学〜コンピュータサイエンスの基礎数学』

本駆け足シリーズの全体の目次はこちら

• 第９章にて形式言語を扱った。文 statement は文字を連ねて書かれる。
• 文には基本的性質である真か偽か true or false があり、これを真理値 truth value という。
• 文は、真偽値を持つ副文 substatements を、結合子と呼ばれる規則で、複数合わせたものとなっている。このような文を複合文 compound statement という。このような文を複合的 composite という。
• 連言 conjunction
  
  • は、副文p q とからなり、pとqの両方が真のときに真であり、それ以外の場合には、偽であるような文である。
• 選言 disjunction
  
  • は、副文p q とからなり、pとqの両方が偽のときに偽であり、それ以外の場合には、真であるような文である。
  • 排他的選言 exclusive disjunction
    
    • pとqのどちらか片方が真のときには真となり、それ以外のときには偽であるような文である。
• 否定 negation
  
  • は、pが真のときに偽、偽のときに真であるような文である。
• 命題
  
  • 真偽値のある副文を結合子で結ぶ。副文を変数とすると、その真偽のパターンが、副文の数nについて、通りある。そのそれぞれについて、その文の真偽値は真か偽をとる。命題とは、このように、副文の真偽パターンに応じて定まる真偽値パターンを持つ文を命題という。
• 恒真命題 tautology と矛盾命題 contradiction
  
  • 命題の真偽値が変数の値によらず必ず真のとき、その命題を恒真命題という。
  • 逆に、変数の値によらず、真偽値が偽になる命題を矛盾命題という。
• 論理同値
  
  • 命題２つあって、その構成変数が同一で、結合の仕方が異なるとする。この２つの命題の真偽値が、構成変数の真偽パターンのすべてについて一致するとき、この２命題は論理同値であるという。
• 命題代数
  
  • 命題には次の規則が成り立つ(ただし、双対(とを交換した命題)を省略)
    
    • べき等律 Idempotent law
    • 結合律 Associative law
    • 交換律 Commutative law
    • 分配律 Distibutive law
    • 同一率 Identity law
    • 補元律 Complement law
    • 対合律 Involution law
    • ド・モルガンの法則 DeMorgan's law
• 条件文 conditional statement と重条件文 biconditional statement
  
  • pならばq。pはqの十分条件である。。これを条件文という。
    
    • pが真、qが偽のときに偽、それ以外は真となる。
    • とと論理同値である。
  • pはqの必要十分条件である。。これを重条件文という。
    
    • pとqが真のとき、pとqが偽のときに真、それ以外が偽となる。
• 論法 argument
  
  • 論法は、(複数の)命題が与えられているときに、別の命題を生む、という主張である。与えられる命題を前提 premises と言い、生み出される命題を結論 conclusion といい、と書く。
  • 論法は真偽値を持つ。論法が真であるのは、前提命題のすべてが真のときに結論が真となるときで、そうならないときにその論法は偽である。
  • 真である論法は妥当 valid といわれ、偽である論法は誤り allacy といわれる。
• プログラミング問題なし