Discrete: Applications of Propositional Logic, Part 2

We are re-visiting Applications of Propositional Logic today for Part 2, which includes Boolean searches and logic circuits. Make sure you have already read through Part 1, as information there will come in handy for this section.

Problem 3 is about Boolean searches on the internet. When searching on the internet (on Yahoo! or Bing, for example), you can use Boolean search terms to narrow your sea of results. The connectives used are AND, OR, and NOT. If you wanted to search for information about universities in Mexico, you could type “university AND Mexico,” but this would return results for universities in New Mexico also (because “Mexico” is in the name). To further narrow your search, you could instead search for “(university AND Mexico) NOT New,” which would exclude results that contain the word “new.”

Note that Google, the word “NOT” is not used. Instead, a minus sign (“-“) is placed before an excluded term.

To include a search term, use the conjunction AND; to exclude, use NOT. To include either of two search terms, use the connective OR.

Lastly, we will look at logic circuits, which are sometimes used in the design of computer hardware. Instead of words, we use symbols to create logic circuits. The symbol set consists of gates: the “inverter” (NOT gate), the OR gate, and the AND gate. Notice the difference in the shape of the AND and OR gates (shown below).

Here is problem 4.

Begin by reading the statement from left to right. Here, we first need p and r to go through NOT gates, then through an OR gate (green). Beginning at the top left, we construct the two NOT gates that then feed into a single OR gate (green). Next, we need a q that feeds first through a NOT gate, then into an AND gate (red) along with the result of the previous OR gate.

Below that q, we need another p that again feeds through a NOT gate. Then we need another q and r, that go to an OR gate (blue). The product of this OR gate (blue) joins up with the p that has gone through the NOT gate and together, they go through an AND gate (purple). The products of the two AND gates (red and purple) come together and go through an OR gate (orange).

You can check the work by following through the circuit and writing out the products. You should end up with the same statement as given in the problem.

I hope this series has helped you learn more about propositional logic and has allowed you to practice what you have already learned by applying your knowledge to various types of problems. The best way to improve your skills with this topic is to practice (as with any math, right?).

Don’t forget to leave comments about what you are working on, what you would like me to cover in the future, or how you are doing in your studies! I love to read them, and will try to respond to each of you. I am always excited to receive topic suggestions. Thanks for reading!