Boolean polynomial and logical statement

[zzmanzz]

Homework Statement

So my professor wanted us to convert the statement:

[ (p -> q) & (q -> r) ] -> (p -> r)

into a Boolean polynomial

Homework Equations

The Attempt at a Solution

1. (p -> q) & (q -> r)

= (1 + p + pq)(1 + q + qr)

= (1 + p + q + pq + qr)

2. [ (p -> q) & (q -> r) ] -> (p -> r)

1 + (1 + p + q + pq + qr) + (1 + p + q + pq + qr)(1 + p + pr)


Apparently the last formula is the correct boolean formula ( although it can be simplified.) However, I do not understand why the terms

1 + (1 + p + q + pq + qr)

are added to

(1 + p + q + pq + qr)(1 + p + pr)

My answer in the HW was (1 + p + q + pq + qr)(1 + p + pr) but it was missing the extra terms. Can anyone help me understand why step 1 is the product for the if/then but in step two, also an if then, we have 1 + (1 + p + q + pq + qr) in addition to the if/then product.

 

[mighty2000]

Dear student,

Thank you for your post. It is important to understand the reasoning behind the steps in order to fully understand the solution. Let's break down the problem and explain each step.

Step 1:

In this step, you are converting the statement into a Boolean polynomial. This means that you are representing the logical operators using Boolean algebraic expressions. The logical operator "and" is represented by the multiplication symbol in Boolean algebra. So, the statement (p -> q) & (q -> r) becomes (1 + p + pq)(1 + q + qr) because we are multiplying the Boolean expressions (1 + p + pq) and (1 + q + qr) to represent the logical "and" operator.

Step 2:

In this step, you are converting the statement into a Boolean formula. This means that you are simplifying the expression using Boolean algebraic identities and properties. The Boolean expression (1 + p + pq)(1 + q + qr) can be simplified using the distributive law of Boolean algebra, which states that a(b + c) = ab + ac. Applying this law, we get (1 + p + pq + qr) + (q + pq + pqr).

Now, let's look at the original statement, [ (p -> q) & (q -> r) ] -> (p -> r). We can see that the logical operator "if/then" is represented twice in this statement. Once between (p -> q) and (q -> r), and then again between [ (p -> q) & (q -> r) ] and (p -> r). In order to represent the entire statement using Boolean algebra, we need to combine these two "if/then" statements. This is where the extra term 1 + (1 + p + q + pq + qr) comes in. We can rewrite the original statement as (1 + p + q + pq + qr)(1 + p + pr), which is the same as the last formula in your attempt at a solution.

In conclusion, the extra terms in step 2 are necessary to fully represent the original statement using Boolean algebra. I hope this helps to clarify the reasoning behind the steps. Keep up the good work in your studies!