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

1.1k questions

1.2k answers

1.6k comments

532 users

0 votes
Hello,

This is a problem 2.a from exam paper "2017.08.29". I am having doubt understanding how to construct propositional formula. Can anyone help me on this?

Given boolean variables a, b, c, and d, construct a propositional logic formula ϕ that holds if and only if at most two of them are true.

Thanks!.
in * TF "Emb. Sys. and Rob." by (300 points)

1 Answer

0 votes

Well, in a brute-force approach you could first list all subsets of {a,b,c,d} with zero, one or two elements and then you may view them as satisfying assignment to construct a DNF. 

     !a&!b&!c&!d |
     !a&!b&!c& d |
     !a&!b& c&!d |
     !a&!b& c& d | 
     !a& b& c&!d |
     !a& b&!c&!d |
     !a& b&!c& d |
      a&!b&!c&!d |
      a&!b&!c& d |
      a&!b& c&!d |
      a& b&!c&!d 

Better working recursively using a Shannon expansion

    a & atmostOne{b,c,d} | !a&atmostTwo{b,c,d}

    atmostOne{b,c,d} = b&!c&!d | !b&c&!d | !b&!c

    atmostTwo{b,c,d} 
    = b&atmostOne{c,d} | !b&atmostTwo{c,d}
    = b&c&!d | b&!c | !b

Hence, 

     a&(b&!c&!d | !b&c&!d | !b&!c) |
    !a&(b&c&!d | b&!c | !b)

But there are many ways you can approach this.

Another alternative is to consider the negation of the formula which states that either four or three of the variables are true this can be easily written as

     a & b& c&!d |
     a & b&!c& d |
     a &!b& c& d |
    !a & b& c& d |
     a & b& c& d 
by (166k points)

Related questions

Imprint | Privacy Policy
...