2026-09-28
first_model.rs
fn satisfied(clauses: &[&[i32]], mask: u32) -> bool {
clauses.iter().all(|clause| {
clause.iter().any(|&lit| {
let value = (mask >> (lit.unsigned_abs() - 1)) & 1 == 1;
value == (lit > 0)
})
})
}
fn main() {
let clauses: [&[i32]; 3] = [&[1, 3], &[2, -1], &[-2, -3]];
let n: u32 = 3;
match (0..1 << n).find(|&m| satisfied(&clauses, m)) {
Some(m) => println!("{m:03b}"),
None => println!("UNSAT"),
}
}
これは何を出力するでしょうか?
Answer
011 です。
clauses は論理式を節の並びで表しています。k は変数 xk、-k はその否定で、節の中のどれか1つが真ならその節は真、すべての節が真なら式全体が真です。ここでの式は (x1 ∨ x3) ∧ (x2 ∨ ¬x1) ∧ (¬x2 ∨ ¬x3) で、xk の値は mask の k - 1 ビット目から読みます。
find は 0 から順に試し、最初に式を満たした m を返します。0 は x1 も x3 も偽なので最初の節で落ち、1(x1 だけ真)は2番目の節で、2(x2 だけ真)はまた最初の節で落ちます。3 は x1 と x2 が真で x3 が偽なので、3つの節がそれぞれ x1、x2、¬x3 で満たされ、ここで探索が終わります。
表示では左右が入れ替わります。{m:03b} は 3 を3桁の2進数 011 にしますが、2進数の表記は最上位ビットを左に書くので、左から x3、x2、x1 の順に並びます。x1 から順に書いた 110 とは逆向きです1。
(mask >> (lit.unsigned_abs() - 1)) & 1 == 1は、Rust では((mask >> …) & 1) == 1と読まれます。Rust の&は==より強く結びつくからで、C では逆に==のほうが先に結びつきます。