Propositional equivalences are used extensively in the construction of mathematical arguments. By using these equivalences, we can substitute propositions with other propositions with the same truth value. This proves to be very useful in different types of situations.
Two compound propositions p and q are logically equivalent if p ↔ q is a tautology. The symbol we use to show that there is a logical equivalence is ‘≡’. As an example, p ≡ q means that p is logically equivalent to q.
Let’s define some terms that will help you understand better the previous definition and see some examples.
Table of Contents
- Definitions
- Example 1: Shows the following by using a a truth table
- Logical equivalences that you can use
- Example 2. Shows that the following compound proposition is a tautology by using a series of propositional equivalences
- Example 3: Show that ¬(p ∨ (¬p ∧ q)) is logically equivalent to ¬p ∧ q
- Key points to remember related to propositional equivalences
Definitions
Def. A compound proposition is an expression created using propositional variables and logical operators. Examples, p v q, p ^ q v r.
Def. A tautology is a compound proposition that is always true, with disregard of the truth values of the propositional variables in the compound proposition.
Def. A contradiction is a compound proposition that is always false, with disregard of the truth values of the propositional variables in the compound proposition.
Def. A contingency is a compound proposition that is not a tautology, nor a contradiction.
Def. Two compound propositions p and q are logically equivalent if p ↔ q is a tautology.
We start with definitions because in mathematics you can’t do anything without using definitions.
So, it is very important that you understand the definitions so you can use them to create arguments and proofs.
Example 1: Shows the following by using a a truth table
If we follow the definition above that tells us if two compound propositions are logically equivalent, we can see that by creating a truth table we can answer whether the two compound propositions are logically equivalent or not.
I wrote another post for you in case you still don’t know how to create a truth table.
See below the table.
As you can see, the compound proposition in the last column is a tautology because it is always true. Then, by the definition of logical equivalence, we can state that:
Notice that is not enough to just create the truth table. You always must state the conclusion and why that is your conclusion. Notice that the way we justify the conclusion, in this case, is by using definitions. That’s why you must start by learning the definitions.
What will happen if you have to prove that two compound propositions that involve 3 propositional variables are logically equivalent?
You can create the truth table as in the previous example, but this time you will have 8 rows because you have to use all possible combinations of truth values for each propositional variable.
If the compound propositions have 4 propositional variables, then you will have to use 16 rows.
As you can see, the growth in rows is exponential. So, this method is not scalable for a bigger number of propositional variables.
Let’s see a better way of doing this in an example.
Logical equivalences that you can use
As stated at the beginning of this post, we use logical equivalences to substitute a compound proposition with another one while we are creating a mathematical argument.
Once you prove two compound propositions are logically equivalent, you can substitute one with the other one in any place.
There are some important logical equivalences that you can use. They are already proved and therefore are accepted in any mathematical argument.
Every time you use one of these logical equivalences, you have to justify it just by mentioning the name. In the last two cases, you justify by saying “by conditional logical equivalence”.
Let’s see an example of how to use them.
Example 2. Shows that the following compound proposition is a tautology by using a series of propositional equivalences
Solution:
As you can see from the example above, you can use more than one law or propositional equivalence in one step. Just don’t forget to mention why you are taking each step.
Example 3: Show that ¬(p ∨ (¬p ∧ q)) is logically equivalent to ¬p ∧ q
Key points to remember related to propositional equivalences
- Always learn the definitions first, so you can use them later.
- Remember each of the logical equivalences from the section “Logical equivalences that you can use” above. You can just use all of them without proving them. They were proved long ago and are common knowledge.
- Every time you substitute a compound proposition with a logically equivalent one, make sure you justify why the two are equivalent.
Related topics:
- Use truth tables to verify these equivalences( Ex.1 pp 34 from the textbook)
- Show that ¬(¬p) and p are logically equivalent (Ex. 2 pp 34 from the textbook)
- Use truth tables to verify the associative laws (Ex. 4 pp. 34 from the textbook)
- Use a truth table to verify the first De Morgan law (Ex. 6 pp. 34 from the textbook)
- Show that p → q and ¬q → ¬p are logically equivalent (Ex. 18 pp 35 from the textbook)
- How to create the truth table for a compound proposition
- Negating propositions
- Show that p↔ q and (p∧q)∨(¬p∧¬q) are logically equivalent
