Difference between r1.7 and the current
@@ -1,5 +1,6 @@
#noindex
mk page [[satisfaction]]? [[충족,satisfaction]] or [[만족,satisfaction]]? NdEn:satisfaction KmsE:satisfaction Ndict:satisfaction
----
//wpen
mk page [[satisfaction]]? [[충족,satisfaction]] or [[만족,satisfaction]]? NdEn:satisfaction KmsE:satisfaction Ndict:satisfaction
----
영단어의 다른 가능한 번역 [[만족가능성,satisfaction]] ... Ggl:"만족가능성 satisfiability"----
//wpen
@@ -18,6 +19,15 @@
wff의 집합 Σ의 모든 유한부분집합이 satisfiable하면, Σ는 finitely satisfiable.
/// from https://chocobear.tistory.com/160?category=851370 의 정의 1., 2.
----
관련 [[문제,problem]]:
/// from https://chocobear.tistory.com/160?category=851370 의 정의 1., 2.
----
// from [[WpKo:모형_이론#1차_논리]]
"[[자유변수,free_variable]]가 없는 [[논리식,logical_formula]]을 [문장,sentence]]이라 하고, 그것들의 어떠한 집합을 [[이론,theory]]이라 정의할 때,
어떠한 이론 내의 모든 문장을 만족시키는 논리적 [[구조,structure]]를 이론의 [[모형,model]]이라 한다.
곧 어떠한 이론 T는 모형 M을 가진다면 만족가능하다(satisfiable) // '''충족가능성,satisfiability'''
고 표현하고 기호로는
𝑀⊨𝑇
$\displaystyle M\models T$
와 같이 쓴다. 이렇게 [[모형이론,model_theory]]은 1차 논리([[일차논리,first-order_logic]] [[VG:일차논리,first-order_logic]])의 [[의미론,semantics]]을 이룬다."
----
관련 [[문제,problem]]:
@@ -66,3 +76,9 @@
"Horn-satisfiability"
Ggl:"Horn-satisfiability"
}
Ggl:"Horn-satisfiability"
}
----
Twin
https://en.wikipedia.org/wiki/Satisfiability
//wpen
수리논리,mathematical_logic학에서
(명제논리,propositional_logic에서 ?)
wff의 집합 Σ의 모든 원소를 만족하는 Boolean_interpretation 이 존재하면 Σ는 satisfiable.
wff의 집합 Σ의 모든 유한부분집합이 satisfiable하면, Σ는 finitely satisfiable.
/// from https://chocobear.tistory.com/160?category=851370 의 정의 1., 2.
수리논리,mathematical_logic학에서
formula 공식,formula? 은, 그 변수,variable들에 어떤(적당한) 대입,assignment을 해서 참,true이 되면, satisfiable.
예를 들어
충족가능성,satisfiability의 부정,negation은 unsatisfiability,
타당성,validity의 부정은 invalidity.
2022-08-09예를 들어
$\displaystyle x+3=y$ 는 $\displaystyle x=3,y=6$ 을 넣으면 만족하므로 satisfiable.
$\displaystyle x+1=x$ 는 정수에 대해 not satisfiable.
충족가능성,satisfiability의 쌍대,dual 개념은 타당성,validity.$\displaystyle x+1=x$ 는 정수에 대해 not satisfiable.
충족가능성,satisfiability의 부정,negation은 unsatisfiability,
타당성,validity의 부정은 invalidity.
(명제논리,propositional_logic에서 ?)
wff의 집합 Σ의 모든 원소를 만족하는 Boolean_interpretation 이 존재하면 Σ는 satisfiable.
wff의 집합 Σ의 모든 유한부분집합이 satisfiable하면, Σ는 finitely satisfiable.
/// from https://chocobear.tistory.com/160?category=851370 의 정의 1., 2.
// from 모형_이론#1차_논리
"자유변수,free_variable가 없는 논리식,logical_formula을 문장,sentence이라 하고, 그것들의 어떠한 집합을 이론,theory이라 정의할 때,
어떠한 이론 내의 모든 문장을 만족시키는 논리적 구조,structure를 이론의 모형,model이라 한다.
곧 어떠한 이론 T는 모형 M을 가진다면 만족가능하다(satisfiable) // 충족가능성,satisfiability
고 표현하고 기호로는
"자유변수,free_variable가 없는 논리식,logical_formula을 문장,sentence이라 하고, 그것들의 어떠한 집합을 이론,theory이라 정의할 때,
어떠한 이론 내의 모든 문장을 만족시키는 논리적 구조,structure를 이론의 모형,model이라 한다.
곧 어떠한 이론 T는 모형 M을 가진다면 만족가능하다(satisfiable) // 충족가능성,satisfiability
고 표현하고 기호로는
𝑀⊨𝑇
$\displaystyle \displaystyle M\models T$
와 같이 쓴다. 이렇게 모형이론,model_theory은 1차 논리(일차논리,first-order_logic 일차논리,first-order_logic)의 의미론,semantics을 이룬다."$\displaystyle \displaystyle M\models T$
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.//
{
쿡_정리,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
SAT가 NP-완전임을 증명하는 정리, 모든 NP에 속하는 결정 문제는 다항 시간 내에 SAT로 환산할 수 있다는 정리
///// 충족가능성문제,satisfiability_problem,SAT np-complete
Twins:
쿡-레빈_정리 = https://ko.wikipedia.org/wiki/쿡-레빈_정리
Cook–Levin_theorem = https://en.wikipedia.org/wiki/Cook–Levin_theorem
https://pub.mearie.org/쿡레빈정리
https://proofwiki.org/wiki/Cook-Levin_Theorem
https://everything2.com/title/Cook%27s theorem - Cook's theorem
쿡-레빈_정리 = https://ko.wikipedia.org/wiki/쿡-레빈_정리
Cook–Levin_theorem = https://en.wikipedia.org/wiki/Cook–Levin_theorem
https://pub.mearie.org/쿡레빈정리
https://proofwiki.org/wiki/Cook-Levin_Theorem
https://everything2.com/title/Cook%27s theorem - Cook's theorem
}
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 =,Horn-satisfiability =,Horn-satisfiability . Horn-satisfiability
Horn_satisfiability =,Horn_satisfiability =,Horn_satisfiability . Horn_satisfiability
{
https://en.wikipedia.org/wiki/Horn-satisfiability
Twin