Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

870 questions

988 answers

1.4k comments

439 users

0 votes
Hello,

Wich possible ways are there to determine a DNF?
The only way I know is about a truth table, but is there a faster or even easier way?
in # Mandatory Modules Bachelor by (230 points)

1 Answer

+1 vote
There are many ways: Truth tables are certainly one, but that one is always an exponential-size effort. Another approach is to compute a ROBDD, and then to enumerate the paths from the root node to the 1-leaf; each path is a conjunction of possibly negated variables and denotes a variable assignment. Using a disjunction of the paths gives you another DNF.  And there is also the way to use Boolean algebra to rewrite a given formula to DNF which is also sometimes a fast solution. Yet another way is to compute the CNF of the negation, and to negate that again to make it a DNF.

In general, there is no best way, it always depends on the given formulas.
by (139k points)

Related questions

0 votes
1 answer
asked Aug 23, 2020 in # Mandatory Modules Bachelor by VF (120 points)
0 votes
1 answer
asked Aug 23, 2020 in # Mandatory Modules Bachelor by kremenadla (380 points)
+1 vote
1 answer
+1 vote
1 answer
asked Aug 23, 2020 in # Mandatory Modules Bachelor by least (260 points)
0 votes
1 answer
Imprint | Privacy Policy
...