سوال ۹۲ کنکور ارشد علوم کامپیوتر ۱۴۰۳

A propositional formula is in disjunctive normal form (DNF) when it is a disjunction of conjunctions of literals: $\bigvee_{i}\Big(\bigwedge_{j}\ell_{ij}\Big),$ where each $\ell_{ij}$ is a literal (an atom $p$ or its negation $\neg p$). The degenerate cases count too: a single literal is a (one-literal) conjunction, and a single conjunctive clause is a (one-clause) disjunction.

Formula $\alpha = p_1 \wedge \neg p_2$. This is one conjunction of the two literals $p_1$ and $\neg p_2$. A lone conjunctive clause is a disjunction with a single disjunct, so $\alpha$ matches the DNF shape. ✓

Formula $\beta = p_1 \vee (\neg p_2 \vee \neg p_3)$. Since $\vee$ is associative, $\beta$ is just $\beta = p_1 \vee \neg p_2 \vee \neg p_3,$ a disjunction of the three literals $p_1,\ \neg p_2,\ \neg p_3$. Each literal is a (one-literal) conjunction, so this is a disjunction of conjunctions of literals — exactly DNF. ✓

Both $\alpha$ and $\beta$ are in DNF, so the answer is both (option 3).

Pitfall: Don't disqualify $\alpha$ for lacking a top-level $\vee$, or $\beta$ for lacking any $\wedge$. DNF allows degenerate clauses: a single literal, a single conjunction, or a pure disjunction of literals all qualify. Negations must sit directly on atoms (they do here), and no $\wedge$ may appear over a $\vee$ — neither formula violates that.