Introduction to Boolean Logic

Sample Lesson - Introduction

Lesson 1.05: Logically Equal

The only logical reaction to a tangle of p's and q's. (Source)

Logic may be all yes-or-no questions, but things can get complicated.

Fast.

Before you know it, it's four in the morning and you're lying unconscious under a pile of your own connectives and disjunctions.

But enough about our average Friday night. (Or is it Saturday morning?) If a connective is a connective, you need to be able to tell when you can simplify and when you…can't. Otherwise you could be left with a tangle of conjunctions, disjunctions, and other unmentionables.

We'll never think of p's or q's in the same way again…

Sample Lesson - Reading

Reading 1.1.05: What's Equal is Equal is Equal

Two things are equivalent when they're…the same. Sounds simple enough, but it can get a little complicated. Two statements are logically equivalent when they have the same values for their entire truth table. Hmm. This might need some explanation, and a truth table. Hey, look at that. We had a truth table just lying around.

Take a good look at the table above. The converse and inverse of two propositions are logically equivalent, because they both go T, T, F, T. We could, in fact, replace one of them with the other and no one would be able to tell the difference. It would be the perfect crime—if swapping logically equivalent statements were a crime. It isn't, so we're not sure why we even brought it up.

You know what, let's just move on to something called a tautology. No, it's not the art of reducing slack. A tautology is a statement that's always true, in every way possible. You could say that a tautology is a tautology.

Before the soup incident, we would have said the statement "bacon is good" was a tautology. Here's a better example: bacon is good or not good. In other words, p || !p.

That's always true. No matter what. Makes the entire statement a little redundant, no?

Two propositions are also logically equivalent when the biconditional between them is a tautology (p ↔ q is always true). Going back to the converse and inverse, we see that:

Keep in mind that when both statements match in a biconditional, they're true. That third row down is false in both partial statements, making it true in the biconditional.

The truth values of two propositions being the same is completely equivalent to the biconditional being a tautology. Betcha didn't see that one coming.

The opposite of a tautology is a contradiction, when every value is false. It means we have a combination of statements or ideas that oppose each other.

Now that we know all about logical equivalencies, let's move on to some of the more common equivalent statements. We'll come back to this idea soon, so don't touch that dial.

Some logical equivalencies are fairly common to see, so they've been given fancy names. It can be useful to memorize some of them in computer science; we'll get to the most important ones…also soon. (If you want to read ahead, though, you can check some equivalencies here.)

Sample Lesson - Activity

Activity 1.05b: Some Made Equal

It's easy to get lost in logic. Sometimes you can add thousands of variables to a statement only to find that you needed two to give the same. Exact. Output. This activity's going to give you some practice doing just that: figuring out which statements are logically equivalent and which can be simplified.

Say you have this statement:

!(!(p && (q || p)) || !q) || p

As readable as that logical statement is, the output's going to be functionally the same as p, if you use equivalent statements.

Wait, what?

Check out what the truth table looks like.

We don't know about you, but to us writing p sounds a lot simpler than muddling through that truth table. You're going to do the same logical reasoning for us and determine if two statements

1. are the same.
2. can be simplified.

For example, Shmoop has the statements: (p && q) || p and p && (q || p)

We'll break down what columns we need to construct a truth table for both statements. This means all letters and any simple statements we can break down from the two larger statements. (If you try to skip this step of determining the basic statements, you're opening yourself up to silly mistakes. Don't do that.) We can break down these statements to:

• p
• q
• p && q
• q || p

Then we make our table, which has six columns: the four from above, and the two final statements. To get this table started off right, we put TTFF under p and TFTF under q to cover every possible combination of true and false, then figure out the combinations from those values.

From looking at those last two columns, we can see their truth values matching up at every combination. That means they're equivalent—both to each other and just plain p—so we'll write:

The two statements are equivalent to both each other and p; it'd be simpler just to write them as p.

Now it's your turn to determine whether each pair of statements is equivalent by writing out the truth table in the input field. Then write a sentence telling us whether the two are equivalent or not. Remember, if the statements are equivalent, they'll have identical results in their table columns.

After that, tell us if one or both of the statements could be simplified to a shorter logical statement. A statement's considered simplified if it has fewer

• parentheses.
• relational operators.
• symbols in general.

Sample Lesson - Activity