Logical Equivalence

If any two propositions are joined up by the phrase "if, and only if", the result is a compound proposition called an equivalence. The two propositions connected in this way are referred to as the left and right side of the equivalence. By asserting the equivalence of two propositions, it is intended to exclude the possibility that one is true and the other false; therefore, an equivalence is true if its left and right sides are either both true or both false, and otherwise the equivalence is false.

Formally,

In other words, two propositions are called logically equivalent if, and only if, when same proposition  variables (or sentential variables) are used to represent identical compound propositions, their forms are logically equivalent. 

For instance, the negation of the negation (or double negation) of a proposition is logically equivalent to the proposition.

Since column 1 and column 3 have the same truth values, so proposition p and statement ~(~p) are logically equivalent.

Formally,

Two propositions P(p, q, r, ...) and Q(p, q, r, ...) are said to be logically equivalent, denoted by

P(p, q, r, ...) ≡ Q(p, q, r, ...)

if they have identical truth tables.

De Morgan's Laws of Logic

The negation of an "and" statement is logically equivalent to the "or" statement in which each component is negated. Similarly, the negation of an "or" statement is logically equivalent to the "and" statement in which each component is negated.

As an example, consider the following truth table:

Since column 6 and column 7 have the same truth values, so ~(p ∧ q) and ~p ∨ ~q are logically equivalent.

Symbolically,

~(p ∧ q) ≡  ~p ∨ ~q 

Similarly,

~(p ∨ q) ≡ ~p ∧ ~q

Augustus De Morgan was the first to state the above two logical equivalences in formal mathematical terms and so in his honor they are known as De Morgan's laws of logic.

About the "Definition" in Context of Equivalence

The phrase "if, and only if" is frequently used in laying definitions. This is a way to specify what meaning is to be attached to a "thing" (expression, if we are working in mathematics) which thus far has not occurred, but which may be immediately understandable. What the hell are you saying, you may ask? Let us explain this with the help of examples. Suppose that the symbol ">" (say) belongs to the set of arithmetic symbols we already know all about and our job is to introduce a brand new symbol "≤" in the set of arithmetic symbols as an abbreviation of the expression "is less than or equal to." To do this, it is necessary to explain the meaning of ">" in terms of expressions which are already known to us and whose meanings are crystal clear to us and beyond any shadow of doubt. One good candidate out of many candidate of the set of arithmetic symbols is the symbol ">."

Now we formulate the symbol "≤" in terms of the symbol ">." We say that

x≤y if, and only if, it is false that x > y.

If you look closely, the definition just formulated states the equivalence of the two propositional functions:

x≤y

and 

It is false that x > y

So, in a sense, we are formulating the propositional function x≤y into an equivalent expression which no longer contains the symbol ≤. In other words, we are formulating the propositional function x≤y in terms already clear to us.

The same holds for any proposition derived from the proposition function x≤y by replacing x and y by arbitrary symbols. For example, the proposition

3 + 2 ≤ 5

is equivalent to the proposition

It is false that 3 + 2 > 5.

Our reasoning is that since the proposition "3 + 2 ≤ 5" is a true assertion, so is the proposition "it is false that 3 + 2 > 5."

You can see the beauty of this reasoning by the following. Using above line of arguemnts, we say that the proposition:

4 ≤ 2 + 1

is equivalent to the proposition:

4 > 2 + 1

But in this particular instance, our both assertions are false.

It should not come with surprise that the same applies to more complicated propositions and propositional functions. (Well! in fact, we are repeating ourselves.) For example, 

if x ≤ y and y ≤ z, the x ≤ z

is equivalent to:

if it is false that x > y and if it is false that y > z, then it is false that x > z.

It is important to see the main point of these examples. The punch line of these examples is that we can transform propositions containing the symbol "≤" into the equivalent proposition containing no "≤" symbol. And this is the very fact which plays the basic role in formulating definitions (at least) within the mathematics. 

Logical Equivalence

Given any proposition variables p, q, and r, a tautology t and a contradiction c, the following logical equivalences hold: