//wpen
수리논리,mathematical_logic학에서
formula
공식,formula? 은, 그
변수,variable들에 어떤(적당한)
대입,assignment을 해서
참,true이 되면, satisfiable.
예를 들어
$\displaystyle x+3=y$ 는 $\displaystyle x=3,y=6$ 을 넣으면 만족하므로 satisfiable.
$\displaystyle x+1=x$ 는 정수에 대해 not satisfiable.
충족가능성,satisfiability의
쌍대,dual 개념은
타당성,validity.
충족가능성,satisfiability의
부정,negation은 unsatisfiability,
타당성,validity의 부정은 invalidity.
2022-08-09
(
명제논리,propositional_logic에서 ?)
wff의 집합 Σ의 모든 원소를 만족하는 Boolean_interpretation 이 존재하면 Σ는 satisfiable.
wff의 집합 Σ의 모든 유한부분집합이 satisfiable하면, Σ는 finitely satisfiable.
/// from
https://chocobear.tistory.com/160?category=851370 의 정의 1., 2.
//tmp notes
Cook-Levin 정리에 의하면 3-SAT은 NP-hard,
다른 문제들은 보통 3-SAT에서 환원 가능(reducible)한 것을 보임으로써 증명
}
Twin