0
$\begingroup$

When constructing both a DNF and CNF of the below, my solutions look the same. I must be off somewhere.

This is what they look like: $\lnot s ∨ \lnot q ∨ \lnot s$

How would you construct a DNF and CNF of this: $(s → \lnot q) ∨ \lnot s$

$\endgroup$
2
  • $\begingroup$ In both cases I'd simplify to $\neg s\lor\neg q$, but this formula is in both conjunctive and disjunctive normal form. For CNF: It's the conjunction of a single clause, which is the disjunction of two literals. ForDNF: It's the disjunction of two clauses, each of which is the conjunction of a single literal. $\endgroup$
    – Andreas Blass
    Commented Jul 2, 2019 at 17:41
  • $\begingroup$ incredibly helpful, thank you! $\endgroup$
    – logicsnewbie2019
    Commented Jul 2, 2019 at 17:56

2 Answers 2

Reset to default
2
$\begingroup$

Since your formula has no $\land$ at all, it makes no difference whether the place they are absent from is above or below the $\lor$s in the syntax tree.

The formula is indeed in both CNF and DNF, either as one clause with three literals, or as a disjunction of three one-literal clauses.

$\endgroup$
2
$\begingroup$

First, note that the expression $\lnot s \lor \lnot q \lor \lnot s$ can be further simplified to $\lnot s \lor \lnot q$ by the commutativity of $\lor$ operator.

Then, $\lnot s \lor \lnot q$ is both in CNF and DNF form.

  • For CNF form, we can consider $\lnot s \lor \lnot q$ as a clause so the CNF form has $1$ clause.
  • For DNF form, we can consider $\lnot s$ and $\lnot q$ as clauses so the DNF form has $2$ clauses.
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .