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

1.1k questions

1.3k answers

1.7k comments

556 users

0 votes

I M not able to understand how the propositional logic formula is written. Can you please guide me with an explanation?

Question from 2017, August 29th - 2a

in * TF "Intelligent Systems" by (850 points)

1 Answer

0 votes

The exam question was as follows: 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.

Hint: This means that the formula φ evaluates to true if zero, one, or two of the variables {a,b,c,d} are assigned true. The formula φ evaluates to false if three or four of them are assigned true.

There are four cases where three of the four variables are true, namely:

    {  b,c,d}
    {a,  c,d}
    {a,b,  d}
    {a,b,c  }

and obviously one where all four variables are true. Hence, we have

    ¬φ =
        ¬a ∧  b ∧  c ∧  d ∨
         a ∧ ¬b ∧  c ∧  d ∨
         a ∧  b ∧ ¬c ∧  d ∨
         a ∧  b ∧  c ∧ ¬d ∨
         a ∧  b ∧  c ∧  d

which can be simplified to

    ¬φ =
        ¬a ∧   b ∧   c ∧  d ∨
         a ∧ (¬b ∧   c ∧  d ∨
               b ∧ (¬c ∧  d ∨
                     c ∧ (¬d ∨ d )))

and further to

    ¬φ =
        ¬a ∧   b ∧   c ∧  d ∨
         a ∧ (¬b ∧   c ∧  d ∨
               b ∧ (c ∨ d))

by (170k points) 1 flag
Simplification rule

Related questions

0 votes
1 answer
asked Aug 22, 2020 in * TF "Intelligent Systems" by Khushnood (640 points)
0 votes
1 answer
0 votes
1 answer
Imprint | Privacy Policy
...