#noindex
mk page [[satisfaction]]? [[충족,satisfaction]] or [[만족,satisfaction]]? NdEn:satisfaction KmsE:satisfaction Ndict:satisfaction
영단어의 다른 가능한 번역 [[만족가능성,satisfaction]] ... Ggl:"만족가능성 satisfiability"
----
//wpen
[[수리논리,mathematical_logic]]학에서
 formula [[공식,formula]]? 은, 그 [[변수,variable]]들에 어떤(적당한) [[대입,assignment]]을 해서 [[참,true]]이 되면, satisfiable.
 예를 들어
  $x+3=y$ 는 $x=3,y=6$ 을 넣으면 만족하므로 satisfiable.
  $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.


----
관련 [[문제,problem]]:
SAT - [[충족가능성문제,satisfiability_problem,SAT]] w

[[Boolean_satisfiability_problem]] - curr at [[문제,problem?action=highlight&value=Boolean_satisfiability_problem]]

관련 [[정리,theorem]]:
[[쿡_정리,Cook_theorem]] =쿡_정리,Cook_theorem =,Cook_theorem 쿡_정리 Cook_theorem //OR//
[[쿡-레빈_정리,Cook-Levin_theorem]] =쿡-레빈_정리,Cook-Levin_theorem =,Cook-Levin_theorem 쿡-레빈_정리 Cook-Levin_theorem //? PAGENAME TBD.//
{

//tmp from wpko
SAT가 NP-완전임을 증명하는 정리, 모든 NP에 속하는 결정 문제는 다항 시간 내에 SAT로 환산할 수 있다는 정리
///// [[충족가능성문제,satisfiability_problem,SAT]] np-complete

//tmp notes
Cook-Levin 정리에 의하면 3-SAT은 NP-hard,
다른 문제들은 보통 3-SAT에서 환원 가능(reducible)한 것을 보임으로써 증명[* https://www.acmicpc.net/board/view/25634]

//bookmarks
http://www.aistudy.com/pioneer/Cook_Levin.htm (발췌 from 컴퓨터를 만든 15 인의 과학자)

Twins:
[[WpKo:쿡-레빈_정리]] = https://ko.wikipedia.org/wiki/쿡-레빈_정리
[[WpEn:Cook–Levin_theorem]] = https://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem
https://pub.mearie.org/쿡레빈정리
https://proofwiki.org/wiki/Cook-Levin_Theorem
https://everything2.com/title/Cook%2527s+theorem - Cook's theorem

MKL
[[충족가능성문제,satisfiability_problem,SAT]]
[[NP완전성,NP-completeness]]
Stephen_Cook
Leonid_Levin

}

----
Sub
[[Horn-satisfiability]] =,Horn-satisfiability =,Horn-satisfiability . Horn-satisfiability
[[Horn_satisfiability]] =,Horn_satisfiability =,Horn_satisfiability . Horn_satisfiability
{
https://en.wikipedia.org/wiki/Horn-satisfiability

"Horn-satisfiability"
Ggl:"Horn-satisfiability"
}

----
Twin

https://en.wikipedia.org/wiki/Satisfiability