Blogs, Mathematical Reasoning, MR Study Help

Truth Tables

Yes, it is that time of the semester when all of my classes are having exams.  It seemed that the last posts going over the practice exam problems for Calculus were helpful, so I will continue to make such posts around exam time.  For this series of posts, I will be working through the practice exam for the exam my introduction to proofs class will take later this week.

In this post, we will be constructing truth tables for different logical statements.  We will then compare the truth values to determine if one implies the other, or if they are equivalent.

You can also view the video solution to this problem on YouTube.

Definitions

When working with logical statements, we will be using the connectives and, or, not and if then.  We will therefore need to define each of these.  When defining them, we can try to refer to the usual definitions; however, in order to avoid confusion we define these exactly using truth tables.

Therefore, let \(p\) be a statement.  When defining the truth table, if we look at the \(p\) column, then the entry in that column will show what the truth value of \(p\) is.  The corresponding row will then give the truth value of statement listed at the top of the column.  In this way, we define not \(p\), \(\sim p\), as the opposite truth value of \(p\). That is,

\(p\) \(\sim p\)
T F
F T

 

If we have statements \(p\) and \(q\), we define \(p\) and \(q\), \(p \wedge q\), as being true precisely when both \(p\) and \(q\) are true. We have this in the following table.

\(p\) \(q\) \(p \wedge q\)
T T T
T F F
F T F
F F F

With statements \(p\) and \(q\), we define \(p\) or \(q\), \(p \vee q\), as true if at least one of \(p\) and \(q\) are true. That is

\(p\) \(q\) \(p \vee q\)
T T T
T F T
F T T
F F F

Furthermore, we define the conditional statement, if \(p\) then \(q), \(p \rightarrow q\) as true if \(p\) is false, or \(q\) is true. That is,

\(p\) \(q\) \(p \rightarrow q\)
T T T
T F F
F T T
F F T

There are other logical connectives that may be used, such as the bi-conditional if and only if; however, these are the are the ones we will need in the following.  Furthermore, we say that the statement \(p\) implies \(q\) if \(q\) is true whenever \(p\) is true.  Two statements are equivalent if they have the same truth table.

Find the truth table for \(p \vee (q \rightarrow r)\) and \((p \vee q) \wedge r\).  Determine if either implies the other or if there is equivalence.

In order to construct our truth tables, we will complete one step at a time.  Therefore, we start off with finding all simple statements provided in the example.  In both cases, there is a \(p\), \(q\) and \(r\).  Therefore, we have to make a table that provides all possibilities for combinations of true and false for these statement.  In doing so, we get the following table.

\(p\) \(q\) \(r\)
T T T
T T F
T F T
T F F
F T T
F T F
F F T
F F F

We will continue to fill in the table working our way from smallest statement to largest. After the \(p\), \(q\) and \(r\), the next smallest statement is \(q \rightarrow r\) and \(p \vee q\). When filling in \(q \rightarrow r\) we look at the \(q\) column, then the \(r\) column. When doing so, if we read \(T\) followed by \(F\) we will get a false statement, otherwise it will be true. When writing the column for \(p \vee q\), we look at the columns labeled \(p\) and \(q\). If at least one of these is true, we have true in the new column. Otherwise we have a false in the column. The corresponding table will be

\(p\) \(q\) \(r\) \(q \rightarrow r\) \(p \vee q\)
T T T T T
T T F F T
T F T T T
T F F T T
F T T T T
F T F F T
F F T T F
F F F T F

Next, we will construct the truth table for \(p \vee (q \rightarrow r)\) by looking at the columns for \(p\) and \(q \rightarrow r\) that we’ve now made. If at least one of these is true, the result will be true. Otherwise we will have a false. Then, when making the truth table for \((p \vee q) \cap r\) we will look at the columns for \(p \vee q\) and \(r\). We then need both to be true in order for the results to be true. We arrive at the following table.

\(p\) \(q\) \(r\) \(q \rightarrow r\) \(p \vee q\) \(p \vee (q \rightarrow r)\) \((p \vee q) \wedge r\)
T T T T T T T
T T F F T T F
T F T T T T T
T F F T T T F
F T T T T T T
F T F F T F F
F F T T F T F
F F F T F T F

Now that we’ve constructed the truth table for each of the statements, we can now compare them to determine any implications. If we start with the column for \(p \vee (q \rightarrow r)\), we look at any row that has a \(T\) in it. We then look at any row with a \(T\) in it and compare to the column for \((p\vee q) \cap r\). If this column is all \(T\) for each of these rows then, the first implies the second. However, we see that \(p \vee (q \rightarrow r)\) is true when \(p\) and \(q\) are true and \(r\) is false. In this case, we also have \((p \vee q) \cap r\) is false. Therefore the first does not imply the second. If we go through the same process looking at \((p \vee q) \cap r\) followed by \(p \vee (q \rightarrow r)\) we note that whenever the first is true, the second is also true. Therefore \((p \vee q) \cap r \Rightarrow p \vee (q \rightarrow r)\), but \(p \vee (q \rightarrow r) \not\Rightarrow (p \vee q) \cap r\). They are also, therefore, not equal.

Conclusion

We have looked at different statement and found the truth values for any possible combination of truth values for statements contained within them.  From this, we were able to see that our second statement implied our first.  However, the first did not imply the second.  If we use continue in the following step by step process, we should be able to make truth tables for a large number of statements.

If you found the post helpful or entertaining, please like it below and share it with anyone else that may be looking at set theory or logic.  You can also find the rest of the solutions to this practice exam here.

We'd love to hear your thoughts!

This site uses Akismet to reduce spam. Learn how your comment data is processed.