# Decision tree

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

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 (166k points) 1 flag
Simplification rule