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

928 questions

1k answers

1.4k comments

441 users

0 votes

Above is given formula for constraint algorithm in exercise sheet 3 and variable ordering is a<b<c<d, I have found my formula Shannon normal form are different with given red highlighted and when compute them by "Teaching Tools" the green highlighted also there are as same as my result, please could someone clarify why the provided result in exercise sheet are different and why?

Thanks in advance!

in # Study-Organisation (Master) by (770 points)

1 Answer

+1 vote

Well, you must have made some mistakes when computing the normal form since it is incorrect. Here is how the computation is done for the first formula by a step-by-step Shannon decomposition on the variables d,c,b,a:

    a&!b&!c&!d | c&!a&!d | d&!a
    = (d ? !a
         : a&!b&!c | c&!a )
    = (d ? !a
         : (c ? !a 
              : a&!b ))
    = (d ? !a
         : (c ? !a 
              : a&!b ))
    = (d ? !a
         : (c ? !a 
              : (b ? false 
                   : a )))
    = (d ? (a ? false
              : true)
         : (c ? (a ? false
                   : true)
              : (b ? false
                   : (a ? true
                        : false))))

This is what the tool computed, and it can also be read from the corresponding BDD using the same variable ordering:

The same way, you can compute the SNF for the other formula. 

by (143k points)

Related questions

0 votes
1 answer
0 votes
1 answer
asked May 13, 2020 in * TF "Emb. Sys. and Rob." by EngiMary (1.7k points)
0 votes
1 answer
asked May 8, 2020 in * TF "Emb. Sys. and Rob." by sschwarz (1.7k points)
+1 vote
1 answer
asked May 6, 2020 in * TF "Emb. Sys. and Rob." by EngiMary (1.7k points)
0 votes
1 answer
asked May 16, 2022 in * TF "Emb. Sys. and Rob." by zain (220 points)
Imprint | Privacy Policy
...