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$
  • $\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 Jul 2 '19 at 17:41
  • $\begingroup$ incredibly helpful, thank you! $\endgroup$ – logicsnewbie2019 Jul 2 '19 at 17:56
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.