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
- $n$ variables: $x_1, x_2, β¦, x_n$
- $2n$ literals: $x_1, \overline{x_1}, x_2, \overline{x_2},...,x_3, \overline{x_3}$
CNF
Clause
- $OR$ of several literals
- E.g., $(x_3 \lor \overline{x_5} \lor \overline{x_1} \lor x_2)$ β a clause consists of several literals linked by an OR
$f$ in CNF is $AND$ of $m$ classes
- $(x_2) \land (\overline{x_3} \lor x_4) \land (x_3 \lor \overline{x_5} \lor \overline{x_1} \lor x_2) \land (\overline{x_2} \lor \overline{x_1})$
- If we have $x_1=F, x_2=T, x_3 = F$, then the above statement is $T$
A satisfying formula returns $T$ for some combination of the literals.
$k$-SAT Problem
Input
- Formula $f$ in CNF with $n$ variables and $m$ clauses each of size $\leq k$
Output
- Assignment (assign $T$ or $F$ to each variable) satisfying if one exists
- If none exists, then NO
Example
- $f = (\overline{x_1} \vee \overline{x_2} \vee x_3) \land (x_2 \vee x_3) \land (\overline{x_3} \vee \overline{x_1}) \land (\overline{x_3})$ β this is a 3-SAT formula (at most 3 literals in a clause)
- To satisfy the above, we have to use: $x_1 = F, x_2 = T, x_3 = F$
Properties
- SAT is NP-complete
- $k$-SAT is NP-complete for all $k \geq 3$
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:
- Remove clauses containing $a_i$.
- Drop $\overline{a_i}$ within clauses.
Simplifying Input for 2-SAT
- Consider the following $f$ for 2-SAT:
- $f = (x_3 \vee \overline{x_2}) \land (\overline{x_1}) \land (x_1 \vee x_4) \land (\overline{x_4} \vee x_2) \land (\overline{x_3} \vee x_4)$
Approach
- Simplify using unit clauses (clauses with 1 literal)
- Take a unit clause (e.g, a literal $a_i$)
- Satisfy it (set $a_i = T$)
- Remove clauses containing $a_i$ and drop $\overline{a_i}$ within clauses
- If contain $a_i$, then delete the whole clause as that clause is $T$
- If contain $\overline{a_i}$, then just remove the literal $\overline{a_i}$ from the clause; keep the other literal
- Let $fβ$ be the resulting formula β $f$ is satisfiable iff $fβ$ is satisfiable
- Keep repeating until we end up with an empty equation, or all clauses have exactly 2 literals
- Thus; assume input to the problem are all clauses of sizes exactly 2
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)$
- In the above, we took the unit clause $\overline{x_1}$ and satisfied it (set $\overline{x_1}$ to $T$)
- Then, we dropped the negation (i.e., $x_1$) which appeared in other clauses since it will be $F$
- If the clause contains $\overline{x_1}$, that entire clause is now satisfied so we can remove it
- If the clause contains $x_1$, we can drop the literal as it is always $F$
- The resulting $f'$ has to be satisfied as well to prove that $f$ is satisfied
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)
- $\overline{\alpha} \rightarrow \beta$ (if $\overline{\alpha}$ is T then $\beta$ must be T, doesnβt apply for F)
- $\overline{\beta} \rightarrow \alpha$
If $\alpha$ is $F$ (or $\overline{\alpha}$ is $T$), then $\beta$ must be $T$ ****to satisfy the clause.
Notes
Graph of Implications
- For $f$ with all clauses of size 2, we have:
- We create a directed graph where:
Example

For this graph, we have no SCCs
- For the first clause $\overline{x_1} \vee \overline{x_2}$, if we set $x_1 = T$, this implies $x_2 = F$ and vice versa
- Derive all edges from the other clauses to get the complete graph
- Draw the implication edges, where $u \to v$ means if $u$ is true, $v$ must be true
General Clause Relation
- In general for a 2 literal clause $\alpha \vee \beta$, we get the edges β this is only for the $T$ case
| --- | --- | --- |
- For $A \to B$ to be True, this only holds when $A$ is True
- If $A$ is False, this does not imply that $B$ is False
Date: February 25, 2026
Topic: Algorithm and Proofs