- Conjunctions and disjunctions are useful tools for building algorithms.
- They enable you to combine propositions.
- Truth tables are a fast way to find solutions.
- Analogies can help you to remember the results.
Dive into machine learning, and you’ll come across algorithms that include conjunctions and disjunctions. For example, you might come across a set of conjunctive rules in a hypothesis space (the set of all functions a model can return) or create a learning algorithm that builds a conjunction using similar features.
Conjunctions and Disjunctions are one way to combine propositions into more complex ones. Propositions [noterm] are statements that are either true or false. For example, “2 is greater than 3” or “10 + 10 = 21.” Some statements like “He is a great swimmer” or “How are you today” don’t have true or false answers and so aren’t propositions. Once you have a set of propositions, you can combine them in various ways, including:
- Conjunction (and, &, ∧): combine (add) propositions.
- Disjunction (or): choose (select) propositions.
Many outcomes for these two simple statements are possible. You can quickly find solutions using truth tables.
Truth Table for Conjunctions
In order to account all the possible combinations of truth values for two statements p and q, we can create a four-row truth table:
A key fact from the table: a conjunction is true only if all the variables in it are true. If you’re familiar with the simple model theory of eye color (where Brown B is dominant over blue b) [1], one way to make sense of the table results is just to remember a single fact: “False” is dominant over “true”. In order for true to appear, it must be paired (t, t). But if False shows in any position, it dominates truth; It will result in an F even when paired with true (F, t) or (t, F).
What happens when the “Basket” is empty?
In that case, an empty conjunction is always defined as true. [2] The eye color analogy obviously doesn’t work here, but an old saying does work:
One bad apple spoils the bunch.
Imagine you have a basket that you’re going to fill with varieties of good (true) and bad (False) apples. If you have a single false statement, everything in the basket is tainted (i.e. False). But if your basket is empty (a.k.a. the empty truth table), then it hasn’t been filled with apples yet . You have no reason to assume that your basket is going to be filled with good apples. Unless you’re very pessimistic, in which case perhaps data science isn’t the career for you!
Truth Table for Disjunctions
Similarly, a truth table can find solutions for disjunctions. The format is the same but the results are slightly different:
Here’s my analogy for remembering the results here. It’s similar to the “bunch of apples” analogy except here we are given a choice: apple P or apple Q. So, given that basket of apples where some are rotten, which would you choose? Every time, you would choose the good (a.k.a. true) apple. In the last row, you have two bad apples so you have no choice but to pick one of those.
The empty disjunction is defined as false. Back to our basket analogy, the “OR” here is you being forced to choose between good apples OR bad apples that are already in the basket. The basket is empty when everyone has chosen their apples. You’re left with a basket that has, unfortunately, mold in it from those bad apples. So you’re left with bad (False) residue.
How to Use a Truth Table: An Example
Let’s take two statements:
P: There are 99 cents in $1
Q: The dollar ($) is US currency.
We want to know: what is the conjunction of P and Q?
Solution:
Step 1. Construct a truth table. This is an “and” question, so create a conjunction truth table.
Step 2: Determine whether the statements are true or false. For this example, P is False and Q is true.
Step 3: Refer to the line that reflects whether the statements are true or False. The third line (F, t = F) is the correct solution.
References
Table pictures by author.
[1] Eye Color and its Inheritance
[2] Foundations of Machine Learning
Credit: Data Science Central By: Stephanie Glen
