Question

नि 5.4 Compute the Shannon expansion of (p (q -> r)) - ((p q) + (pr)) with respect to each one of its atomic propositions. Why do you know the answer even before you start the computation?

Answer 1

The Shannon expansion of a boolean function F about a variable p is given by

F(p, q, r) = p' * F(0, q, r) + p * F(1, q, r).

For our case F = (p --> (q --> r)) --> ((p --> q) --> (p --> r))

Thus our Shannon expansion about p is

F = p' * [(0 --> (q --> r)) --> ((0 --> q) --> (0 --> r))] + p * [(1 --> (q --> r)) --> ((1 --> q) --> (1 --> r))]

For ease of expression let's compute each summand separately, i.e.

  p' * [(0 --> (q --> r)) --> ((0 --> q) --> (0 --> r))]

= p' * [(1) --> ((1) --> (1))] Since 0 --> x is equivalent to 1

= p' * [(1) --> (1)] Since 1 --> 1 is equivalent to 1

= p' * [1]      Since 1 --> 1 is equivalent to 1

= p' Since 1*x is equivalent to x

Now, let's compute the second term.

  p * [(1 --> (q --> r)) --> ((1 --> q) --> (1 --> r))]

= p * [(q --> r) --> (q --> r)] Since 1 --> x is equivalent to x

= p* [1] Since x --> x is equivalent to 1

= p   Since 1*x is equivalent to x

Thus, F = p' + p = 1.

Similarly, compute the Shannon expansion about variables q and r. You will get F = 1. This is so because F is a tautology.