# 「OI」2-SAT

$\texttt{SAT}$ 是适定性（Satisfiability）问题的简称。一般形式为 $\texttt{k}$ – 适定性问题，简称 $\texttt{k-SAT}$。而当 $\texttt{k}>2$ 时该问题为 NP 完全的。所以我们只研究 $\texttt{k}=2$ 的情况。

# $\texttt{2-SAT}$

## 定义

$\texttt{2-SAT}$，简单的说就是给出 $n$ 个集合，每个集合有两个元素 $a,b$，已知若干个 $<a,b>$，表示 $a$ 与 $b$ 矛盾（其中 $a$ 与 $b$ 属于不同的集合）。然后从每个集合选择一个元素，判断能否一共选 $n$ 个两两不矛盾的元素。显然可能有多种选择方案，一般题中只需要求出一种即可。 ## 简单技巧

$$a\to b\Leftrightarrow \begin{cases} a&\to b\\ \lnot b&\to \lnot a \end{cases}$$

$$a\lor b\Leftrightarrow \begin{cases} \lnot a\to b\\ \lnot b\to a \end{cases}$$

$$a\oplus b\Leftrightarrow \begin{cases} a\to\lnot b\\ b\to\lnot a\\ \lnot a\to b\\ \lnot b\to a \end{cases}$$
{"ft_lang_label":"__label__zh","ft_lang_prob":0.8045897,"math_prob":0.9999422,"size":805,"snap":"2021-31-2021-39","text_gpt3_token_len":554,"char_repetition_ratio":0.1710362,"word_repetition_ratio":0.09876543,"special_character_ratio":0.33291924,"punctuation_ratio":0.014084507,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9998023,"pos_list":[0,1,2],"im_url_duplicate_count":[null,2,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-07-28T13:49:32Z\",\"WARC-Record-ID\":\"<urn:uuid:c9ad322d-1978-4542-835f-6876051f16d4>\",\"Content-Length\":\"40583\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:21a7a43a-d6d2-4b07-9f3d-8ae998f74721>\",\"WARC-Concurrent-To\":\"<urn:uuid:8712cb01-3697-4aaf-8d3e-8f67183c9203>\",\"WARC-IP-Address\":\"47.240.44.176\",\"WARC-Target-URI\":\"https://www.lu-anlai.com/oi/knowledge/2-sat/\",\"WARC-Payload-Digest\":\"sha1:QLPZFIAV6WY5QXHF3X6ZBJKCAW74XYYA\",\"WARC-Block-Digest\":\"sha1:UTER6KT4RF47DJHSGYELUWXKWUZXEKGX\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-31/CC-MAIN-2021-31_segments_1627046153729.44_warc_CC-MAIN-20210728123318-20210728153318-00136.warc.gz\"}"}