Propositional equivalences

A proposition is a statement that has a defined truth value, either true or false. Propositional equivalence is a concept where two propositions are considered logically equivalent. These propositions are different syntactically but have the same truth values. For example, $\sim(m → n)$ and $m ∧\sim n$ are logically equivalent propositions with truth values {F, T, F, F}.

Representation

To represent that two propositions are logically equivalents, we use "$⇔$" or "$≡$" between them. Let's suppose we have two propositions: $m$ and $n$. To represent that these propositions are logically equivalent, we write:

Ways of proving propositions are logically equivalent

There are three ways to prove two propositions are logically equivalent.

• Using biconditional

• Using truth values

• Using laws of logical equivalences

Let's discuss each one in detail now.

Using biconditional

We can prove that two propositions are logically equivalent by taking biconditionalIt returns true if the input truth values are same else returns false. between them. If the result is a tautologyThe output truth values for a proposition is all true. we say that the propositions are logically equivalent.

Suppose we have two compound propositionsA proposition that consists of multiple propositions combined with connectives like AND, OR and XOR.: $\sim(m → n)$ and $m ∧\sim n$. We follow the following steps to prove these propositions are equivalent using bi-conditional.

1. To find truth values for the first proposition, we take the implicationIt results in false when first truth value is true and the second is false else it returns true for all cases. between $m$ and $n$ represented by $m → n$. Then, we take the negationIt returns truth value opposite to our input truth value, of it to get our desired proposition represented by$\sim(m → n)$.

2. To find truth values for the second proposition, we take the negation of n represented by $\sim n$. Then, we take the ANDIt results in true only if all input truth values are true else false for all cases. between $m$ and negation of $n$ to get our desired proposition represented by $m ∧\sim n$.

3. Lastly, to prove that the two propositions are logically equivalent, we take bi-conditional between them represented as $\sim(m → n) ⇔ (m ∧\sim n)$.

We conclude that the two propositions are logically equivalent as their bi-conditional is a tautology.

Using truth values

We can prove that two propositions are logically equivalent if we find their truth values and match if they are equal. Suppose we have to compound propositions: $m → n$ and $\sim m ∨ n$. We use the following steps to prove these propositions are equal.

1. To find truth values for the first proposition, we take the implication between$m$ and $n$ represented by $m → n$.

2. To find truth values for the second proposition, we take the negation of m represented by $\sim m$. Then, we take the ORIt returns true if one of the input truth values is true. between negation $m$ and of $n$ to get our desired proposition represented as$\sim m ∨ n$.

3. Lastly, we compare the output truth values of both propositions.

We conclude that the two propositions are logically equivalent as their output truth values are the same.

Using laws of logical equivalences

Let's discuss some laws that are made based on propositional equivalences first. These laws have already been proven and are a base for determining logical equivalence between any two propositions. Let's suppose we have three propositions: $m$, $n$ and $p$.

We can use the laws above to prove our propositions are logically equivalent. For example, suppose we have two compound propositions: $\sim(m → n)$ and $m ∧ \sim n$.

$\sim (m → n) ⇔ \sim(\sim m ∨ n)$ Implication Law

$⇔ \sim \sim m ∧ \sim n$ De Morgan’s Law

$⇔ m ∧ \sim n$ Double Negation Law

We conclude that the two propositions are logically equivalent.

Conclusion

Propositional equivalence helps us determine if two propositions are logically equivalent. Moreover, it is useful in determining relationships between propositions, simplifying complex propositions, and identifying propositions with a similar behavior.