I have the following truth table:
p q r Output
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 0
I am taught that one way to come up with the boolean expression for that truth table is the look at the rows that has Output equal to 1 (so in this case it is row 1, 2, 3, 6) and then use the Sum of Produce to form the expression:
First solution: So in this case, it will be (~p ^ ~q ^ ~ r) v (~p ^ ~q ^ r) v (~p ^ q ^ ~ r) v (p ^ ~q ^ r), then I can try to simplify this further.
Second solution: But TA also said we can look at row 1 and row 3 to come up with this: (~p ^ ~ r) and then row 2 and row 6 to come up with this: (~q ^ r) and then join these two as: (~p ^ ~ r) v (~q ^ r)
So I have two questions, for the first solution above (which is a brute force way of doing it) and also the second solution , my question is how do I know that expression holds for every single row in the truth table (I know it must holds for the selected row, for example the first solution expression holds for row 1, 2, 3, 6 because that is how the expression comes from by looking at those 4 rows). But how about the other rows that have 0 as an Output. How do I know my expression that I comes up with just by looking at those rows that have Output of 1 will also holds for ALL other rows?
Similarly for solution 2, how do I know it will holds for every single row (rows with output 1 or output 0)?
Could someone explains? And also in general how do we come up with a boolean expression WITHOUT using Brute Foece? (i.e. not using the first way)
1. How do I know that expression holds for every single row in the truth table?
Sum of Products form is used when you are creating a Disjunctive Normal Form. Each row represents a minterm or a product of literals and the expression is the sum of products (ie. minterms). The sum or disjunction is a logical-OR. So, we don't care about the rows where it is 0 (or X = DONT CARE). The reason is 0 OR x = x.
So, if you consider the disjunction (sum) of minterms that evaluate to 1 in the Truth Table, it is the complete Boolean Expression. You can consider the minterms that evaluate to 0 also, but it doesn't impact the result of the expression because the partial evaluation of that minterm will be 0. Remember 0 OR x is x.
Also all the minterms (i.e, all rows) in the Truth Table in totality represent the exhaustive set of possibilities. They are all mutually exclusive. So, if you consider the True rows, that is sufficient.
2. Combining rows
You combine two minterms that mismatch on one literal. For eg. a.b.c.d + a.b.c.d' You can then apply the distributive law and say this is same as a.b.c.(d + d'). d + d' equals TRUE always and hence can be removed to leave a.b.c
You can repeat this for each pair of minterms and get a simpler expression than the minterms that you started with. You can finally create a disjunction of the simplified terms (and apply this recursively until you cannot simplify anymore).
For smaller truth tables, you can use Karnaugh Maps to simplify.
You have to look at all minterms or all maxterms (if you are using Conjunctive Normal Form). There is no other way.