結合法則 - 暇つぶしWikipedia

結合法則

集合の交叉および合併: ( A ∩ B ) ∩ C = A ∩ ( B ∩ C ) = A ∩ B ∩ C ( A ∪ B ) ∪ C = A ∪ ( B ∪ C ) = A ∪ B ∪ C ( ∀ A , B , C ) . {\displaystyle {\begin{array}{l}(A\cap B)\cap C=A\cap (B\cap C)=A\cap B\cap C\\(A\cup B)\cup C=A\cup (B\cup C)=A\cup B\cup C\end{array}}\qquad (\forall A,B,C).}

適当な集合 M に対する M 上の自己写像（写像 M → M）全体の成す集合 S ? MMについて、S 上で定義された合成演算 ? は結合的である: ( f ∘ g ) ∘ h = f ∘ ( g ∘ h ) = f ∘ g ∘ h ( ∀ f , g , h ∈ S ) . {\displaystyle (f\circ g)\circ h=f\circ (g\circ h)=f\circ g\circ h\qquad (\forall f,g,h\in S).}

少し一般に、四つの集合 M, N, P, Q とそれらの間の写像 h: M → N, g: N → P, f: P → Q についてやはり ( f ∘ g ) ∘ h = f ∘ ( g ∘ h ) = f ∘ g ∘ h {\displaystyle (f\circ g)\circ h=f\circ (g\circ h)=f\circ g\circ h} が成り立つ。要するに写像の合成は常に結合的である。

三元集合 {A, B, C} に演算を以下の乗積表に従って定めたものは結合的である（かつ可換でない）:

演繹の推論規則
命題計算

モーダスポネンス
 モーダストレンス
モーダスポネンストレンス（英語版）
連言導入
 簡単化
 選言導入
 選言除去
 選言三段論法
 仮言三段論法
構成的ジレンマ（英語版）
破壊的ジレンマ（英語版）
二条件導入（英語版）
二条件除去（英語版）
述語計算

普遍汎化
 普遍例化
 存在汎化
 存在例化
 カテゴリ:推論規則
.mw-parser-output .hlist ul,.mw-parser-output .hlist ol{padding-left:0}.mw-parser-output .hlist li,.mw-parser-output .hlist dd,.mw-parser-output .hlist dt{margin-right:0;display:inline-block;white-space:nowrap}.mw-parser-output .hlist dt:after,.mw-parser-output .hlist dd:after,.mw-parser-output .hlist li:after{white-space:normal}.mw-parser-output .hlist li:after,.mw-parser-output .hlist dd:after{content:" ・\a0 ";font-weight:bold}.mw-parser-output .hlist dt:after{content:": "}.mw-parser-output .hlist-pipe dd:after,.mw-parser-output .hlist-pipe li:after{content:" |\a0 ";font-weight:normal}.mw-parser-output .hlist-hyphen dd:after,.mw-parser-output .hlist-hyphen li:after{content:" -\a0 ";font-weight:normal}.mw-parser-output .hlist-comma dd:after,.mw-parser-output .hlist-comma li:after{content:"、";font-weight:normal}.mw-parser-output .hlist-slash dd:after,.mw-parser-output .hlist-slash li:after{content:" /\a0 ";font-weight:normal}.mw-parser-output .hlist dd:last-child:after,.mw-parser-output .hlist dt:last-child:after,.mw-parser-output .hlist li:last-child:after{content:none}.mw-parser-output .hlist dd dd:first-child:before,.mw-parser-output .hlist dd dt:first-child:before,.mw-parser-output .hlist dd li:first-child:before,.mw-parser-output .hlist dt dd:first-child:before,.mw-parser-output .hlist dt dt:first-child:before,.mw-parser-output .hlist dt li:first-child:before,.mw-parser-output .hlist li dd:first-child:before,.mw-parser-output .hlist li dt:first-child:before,.mw-parser-output .hlist li li:first-child:before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child:after,.mw-parser-output .hlist dd dt:last-child:after,.mw-parser-output .hlist dd li:last-child:after,.mw-parser-output .hlist dt dd:last-child:after,.mw-parser-output .hlist dt dt:last-child:after,.mw-parser-output .hlist dt li:last-child:after,.mw-parser-output .hlist li dd:last-child:after,.mw-parser-output .hlist li dt:last-child:after,.mw-parser-output .hlist li li:last-child:after{content:")\a0 ";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li:before{content:" "counter(listitem)" ";white-space:nowrap}.mw-parser-output .hlist dd ol>li:first-child:before,.mw-parser-output .hlist dt ol>li:first-child:before,.mw-parser-output .hlist li ol>li:first-child:before{content:" ("counter(listitem)" "}.mw-parser-output .navbar{display:inline;font-size:75%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}.mw-parser-output .infobox .navbar{font-size:88%}.mw-parser-output .navbox .navbar{display:block;font-size:88%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}

表

話

編

歴

 結合規則

標準的な真理函数的命題論理において、結合則 (association [4][5], associativity [6]) は二つの妥当（英語版）な置換規則（英語版）を言う。それは、論理学的証明における論理式に現れる括弧の位置を動かしてもよい規則を述べるもので、論理結合子を用いて書けば

( P ∨ ( Q ∨ R ) ) ⟺ ( ( P ∨ Q ) ∨ R ) {\displaystyle (P\lor (Q\lor R))\iff ((P\lor Q)\lor R)}

( P ∧ ( Q ∧ R ) ) ⟺ ( ( P ∧ Q ) ∧ R ) , {\displaystyle (P\land (Q\land R))\iff ((P\land Q)\land R),}

のふたつである。ただし、" ⟺ {\displaystyle \iff } " はメタ論理（英語版）の記号（英語版）で、「形式的証明において置換してよい」ことを表す。
論理演算の結合性

真理函数的命題論理における真理函数の結合子のいくつかは結合性 (associativity) を持つ。以下の論理同値（英語版）（これらは真理函数的恒真式である）は結合性が特定の結合子の持つ性質であることを示している [7]:
選言の結合性
( ( P ∨ Q ) ∨ R ) ↔ ( P ∨ ( Q ∨ R ) ) {\displaystyle ((P\lor Q)\lor R)\leftrightarrow (P\lor (Q\lor R))} ( P ∨ ( Q ∨ R ) ) ↔ ( ( P ∨ Q ) ∨ R ) {\displaystyle (P\lor (Q\lor R))\leftrightarrow ((P\lor Q)\lor R)}
連言の結合性
( ( P ∧ Q ) ∧ R ) ↔ ( P ∧ ( Q ∧ R ) ) {\displaystyle ((P\land Q)\land R)\leftrightarrow (P\land (Q\land R))} ( P ∧ ( Q ∧ R ) ) ↔ ( ( P ∧ Q ) ∧ R ) {\displaystyle (P\land (Q\land R))\leftrightarrow ((P\land Q)\land R)}
論理同値の結合性

Size:58 KB
出典: フリー百科事典『ウィキペディア（Wikipedia）』
担当:undef