1 真偽割当の基本概念
真偽割当とは、論理式を構成する命題変数や原子命題に対して、真または偽を対応させる規則である。これにより、複合した論理式全体の値が順次定まる。形式論理では、式の意味を与える基礎的な仕組みとして扱われる。
1.1 命題に対する真偽の定義
命題とは、真偽のいずれかに定まる文や表現を指す。真偽割当は、この命題に対してどちらの値を与えるかを明示する。論理学では、文の内容そのものではなく、与えられた値に基づく評価が重要になる。
1.2 原子命題・変数への割当
原子命題や命題変数は、より複雑な式の最小単位である。真偽割当は、まずこれらの基本要素に値を与えることで成立する。そこから論理結合子の規則に従って、全体の真偽が決まる。
1.2.1 変数の値の与え方
命題変数には、真か偽のどちらかを選んで割り当てる。複数の変数がある場合、それぞれに独立に値を指定するのが一般的である。こうした指定の組合せが、式の評価に用いられる割当となる。
1.2.2 原子命題の評価手順
原子命題は、解釈や前提条件に応じて真偽が定まる。命題論理では、しばしば変数そのものを評価対象とみなす。評価手順は単純だが、複合式の基礎を支える重要な段階である。
1.3 論理結合子による真偽の決まり方
論理結合子は、複数の命題を結び付けて新しい式を作る記号である。真偽割当は、各結合子に対する真理値規則を通じて、合成式の値を決める。これにより、局所的な値から全体の意味が導かれる。
1.3.1 否定・連言・選言
否定は、与えられた値を反転させる。連言は両方が真のときにのみ真となり、選言は少なくとも一方が真なら真になる。これらは命題論理で最も基本的な評価規則として用いられる。
1.3.2 ならば・同値の評価
含意は、前件が真で後件が偽の場合のみ偽となる。その他の組合せでは真として扱われる。同値は、両辺の値が一致するときに真となり、不一致のときに偽となる。
2 真偽割当と論理式の意味
真偽割当は、式がどの条件で成立するかを明らかにする。単なる値の付与ではなく、式の意味内容を形式化する役割を持つ。充足可能性や帰結関係は、この考え方を通じて理解される。
2.1 充足性との関係
充足性とは、ある割当の下で論理式が真になる性質をいう。真偽割当は、式が成立する具体的な場合を示すため、充足可能性の議論と密接に結びつく。どの変数にどの値を与えるかが、結果を左右する。
2.1.1 充足可能性の判定
式が少なくとも一つの割当で真になるなら、充足可能であるという。判定では、可能な割当を調べ、真となる組合せの有無を確認する。命題論理では、この問題が重要な判定課題として扱われる。
2.1.2 充足割当の探索観点
充足割当を探すとは、式を真にする値の配置を見つけることである。探索は体系的に行われることもあれば、制約を用いて候補を絞ることもある。実用上は、無駄な組合せを減らす工夫が重視される。
2.2 論理的帰結との関係
論理的帰結は、前提が真なら結論も真になるという関係である。真偽割当を用いると、すべての割当でこの条件が保たれるかを調べられる。したがって、帰結は割当全体に対する性質として定式化される。
2.2.1 すべての割当での成り立ち
ある式がすべての割当に対して真であるなら、その式は論理的に強い性質を持つ。これは、特定の値に依存しない普遍的な成立を意味する。帰結の確認では、この広い範囲での検査が必要になる。
2.2.2反例割当の考え方
反例割当とは、式や推論が成り立たないことを示す値の組である。ひとつでも反例が見つかれば、普遍的成立は否定される。論理の検証では、反例の発見が有効な証明手段になる。
2.3 妥当性・充足不能との関係
妥当性は、すべての割当で真になる性質を表す。これに対し、充足不能は、どの割当でも真にならない場合をいう。真偽割当は、この両極の性質を判別する基盤となる。
2.3.1 常に真となる割当
常に真となるのは、特定の値の選び方ではなく、どの割当でも真が保たれる式である。こうした式は妥当式と呼ばれる。意味論的には、例外のない成立を示す点に特徴がある。
2.3.2 常に偽となる割当
どの割当を選んでも真にならない式は、充足不能である。これは、真にする値の組合せが存在しないことを意味する。論理式の分類では、妥当性と対になる重要な概念である。
3 計算論理における真偽割当
計算論理では、真偽割当は式の評価を機械的に行うための対象となる。与えられた式に対し、割当を探索して真偽を判定する方法が研究される。ここでは、効率化や計算量の問題も重要になる。
3.1 割当探索アルゴリズムの概観
割当探索アルゴリズムは、候補となる値の組を順に調べる手続きである。単純な方法から、制約を利用して探索空間を縮小する方法まで幅広い。目的は、真となる割当の有無や反例の発見である。
3.1.1 全探索とその限界
全探索は、考えられるすべての割当を列挙して調べる方法である。理屈としては確実だが、変数が増えると候補数が急速に膨らむ。したがって、大規模な式にはそのまま適用しにくい。
3.1.2 制約を用いた枝刈りの考え方
枝刈りは、途中で矛盾が明らかになった候補を早めに打ち切る技法である。制約を利用すると、真になりえない分岐を除外できる。これにより、探索の負荷を下げることができる。
3.2 SAT問題との対応
SAT問題は、与えられた論理式を真にする割当が存在するかを問う問題である。真偽割当は、この問題の中心的な概念として機能する。命題論理の充足可能性を形式的に扱う代表例といえる。
3.2.1 偽割当・真割当の意味づけ
SATでは、真割当の存在が解の存在を意味し、偽の組合せは不成立を示す。ここでの「偽割当」は、式を偽にする評価として理解される場合がある。文脈に応じて、何を解とみなすかを区別する必要がある。
3.2.2 節形式との関係
節形式は、論理式を節の連言として表す標準的な記法である。SATソルバーは、この表現を利用して割当の検査を効率化する。節ごとの充足条件が明確になるため、探索との相性がよい。
3.3 評価手続きと計算量
評価手続きとは、与えられた割当に対して論理式の真偽を決める処理である。構文木をたどるように計算できるが、式の大きさに応じて処理量が変わる。計算量の見積もりは実装上も理論上も重要である。
3.3.1 論理式評価の基本手順
基本手順では、まず原子命題の値を参照し、次に結合子の規則を順に適用する。式を下位から評価していけば、全体の値が一意に定まる。これは再帰的な計算として表現されることが多い。
3.3.2 評価コストの見積もり
評価コストは、式の長さや構造に依存する。単純な逐次評価では、各記号を一度ずつ処理する程度で済むことが多い。一方、探索問題として扱うと、割当数の増大により負担が急激に増す。
4 形式体系と拡張
真偽割当の考え方は、命題論理にとどまらず、より広い形式体系にも及ぶ。述語論理では解釈や個体領域を伴い、評価の構造が複雑になる。表現形式の違いも、割当の扱いに影響を与える。
4.1 述語論理での割当（解釈）の位置づけ
述語論理では、単なる真偽の付与だけでなく、個体や関係の意味づけが必要になる。真偽割当に相当する役割は、解釈全体の中に組み込まれる。これにより、式の成立条件がより精密に記述される。
4.1.1 個体割当と述語の解釈
個体割当は、変数がどの対象を指すかを定める。述語の解釈は、それらの対象に対して述語が成り立つかを決める。両者が組み合わさって、述語論理式の真偽が評価される。
4.1.2 量化の扱い
全称量化子と存在量化子は、個体領域全体に関する評価を要求する。前者はすべての対象で成立するかを調べ、後者は少なくとも一つの対象を見つける。量化の導入により、割当は局所的な値付けだけでは済まなくなる。
4.2 表現形式の違いによる影響
論理式は、同じ意味を保ちながらさまざまな形に変換できる。表現形式が変わると、評価の見通しや探索のしやすさが変化する。真偽割当の性質自体は保たれることが多いが、扱い方には差が出る。
4.2.1 正規形化との関係
正規形化は、式を一定の標準的な形に整える操作である。これにより、割当との対応が明確になり、機械的処理が行いやすくなる。SATや証明手続きでは、前処理として用いられることがある。
4.2.2 同値な変換と割当の保存
同値な変換は、意味を変えずに式の形だけを変える操作である。適切な変換であれば、真偽割当による成立条件は保たれる。したがって、式を簡単な形に直しても、本質的な評価結果は失われない。
4.3 関連概念：モデル・解釈・評価
真偽割当は、モデルや解釈と密接に関係する。評価は、与えられた構造の下で式の真偽を求める行為である。これらの概念を区別すると、論理意味論の見通しがよくなる。
4.3.1 モデルとしての真偽割当
モデルとは、ある理論や式群を真にする構造をいう。命題論理では、真偽割当そのものが簡単なモデルとして働くことがある。式を成立させる割当は、その意味で解の役割を担う。
4.3.2 解釈と評価の区別
解釈は、記号に意味を与える枠組みであり、評価はその枠組みの下で式の真偽を決める過程である。両者は近いが同一ではない。解釈が先にあり、その上で評価が行われると考えると整理しやすい。