Date: February 24, 2026

Topic: 2-Satisfiability

<aside> πŸ“Œ SUMMARY: SAT problems have a CNF where we want to show that the statement holds ($f$ is True) through some combination of its literals For 2-SAT problems in any form, they can be reduced to a CNF containing clauses of exactly 2 literals

</aside>

Recall

Notations for SAT

Notes

SAT: Notation

Satisfiability

Boolean formula

CNF

Clause

$f$ in CNF is $AND$ of $m$ classes


A satisfying formula returns $T$ for some combination of the literals.

$k$-SAT Problem

Input

Output

Example

Properties


All 2-SAT inputs can be reduced (simplified) to clauses with sizes exactly 2.

When encountering single literal clauses (e.g., $a_i$), we can use them to perform simplification by setting $a_i$ to $T$ and then:

Simplifying Input for 2-SAT

Approach

  1. Take a unit clause (e.g, a literal $a_i$)
  2. Satisfy it (set $a_i = T$)
  3. Remove clauses containing $a_i$ and drop $\overline{a_i}$ within clauses
    1. If contain $a_i$, then delete the whole clause as that clause is $T$
    2. If contain $\overline{a_i}$, then just remove the literal $\overline{a_i}$ from the clause; keep the other literal
  4. Let $f’$ be the resulting formula β€” $f$ is satisfiable iff $f’$ is satisfiable

Example

$(x_3 \vee \overline{x_2}) \land (\overline{\red{\cancel{x_1}}}) \land (\blue{\cancel{x_1}} \vee x_4) \land (\overline{x_4} \vee x_2) \land (\overline{x_3} \vee x_4)= (x_3 \vee \overline{x_2}) \land (x_4) \land (x_4 \vee x_2) \land (\overline{x_3} \vee x_4)$


Date: February 24, 2026

Topic: Graphs and SCCs

<aside> πŸ“Œ SUMMARY: Based on a given formula $f$, we can draw a graph of implications showing how the literals are connected to each other. When we set a literal to $T$ in a graph, all subsequent nodes and edges starting from the literal has to be $T$ which may cause contradictions. If for some $i$, $x_i$ and $\overline{x_i}$ are in the same SCC, then $f$ is not satisfiable. β€” need to show this for both directions If for all $i$, $x_i$ and $\overline{x_i}$ are in different SCCs, then $f$ is satisfiable.

</aside>

Recall

For a clause $(\alpha \vee \beta)$, we can get the implication edges

We need at least one literal to be true (cannot have both false)

If $\alpha$ is $F$ (or $\overline{\alpha}$ is $T$), then $\beta$ must be $T$ ****to satisfy the clause.

Notes

Graph of Implications

Example

For this graph, we have no SCCs

For this graph, we have no SCCs

General Clause Relation

| --- | --- | --- |




Date: February 25, 2026

Topic: Algorithm and Proofs