Equivalence

Equivalence

Within propositional logic, the term equivalence is used in either of the following two ways: (1) as a particular type of propositional statement or (2) as the logical operator used to form an "equivalence" statement. In order to develop a precise definition of equivalence, some background regarding propositional logic is necessary. The Greek philosopher Aristotle (384 b.c.-322 b.c.) provided the first systematized approach to propositional logic. Keep in mind that logic at that time was expressed entirely in ordinary language and not at all symbolically. Nevertheless, "Aristotelian logic" was, and remains, the starting point to formal logic. Within the Aristotelian system the concepts of "proposition" and "truth" are of paramount importance. A proposition (also called a statement) is defined as a linguistic formation used to communicate information that may be labeled as "true" or "false". Moreover, there exist several principles related to propositions: the principle of identity states that every proposition is equal to itself; the principle of the excluded middle means that every proposition is either true or false; and the principle of excluded contradiction states that no proposition is both true and false. An "equivalence statement", then, is simply a type of proposition (as stated at the beginning in definition #1) that may be evaluated as being true or false.

More than 2000 years after Aristotle, linguistic logic gave way to a purely symbolic logic (also called mathematical logic). In this symbolic form of propositional logic, statements are often denoted by capital letters (A, B, C, etc.) and "logical operators" are used to form compound statements. Equivalence (as stated at the beginning in definition #2) is used along with other logical operators, like "" (and), "~" (not), "" (implication), etc. to form new compound statements. Thus, two propositions, say A and B, and the symbol "" are used to form the equivalence statement A B, where denotes "equivalence". The truth or falsity (called the truth-value) of the equivalence statement A B is dependent solely upon the corresponding truth-values of statements A and B. This situation is best illustrated via the use of a truth table, as shown below:

This truth table demonstrates the four possible combinations of truth/falsity for statement A (the first column), statement B (the second column), and the resulting truth-value for the equivalence A B (the third column), where T = true and F = false. As demonstrated by the truth table, A B is true if A and B are both true, or A and B are both false. If A and B have different truth-values (one is true and the other false) then the proposition A B is false.

For a valid (i.e., true) equivalence statement the truth-value of one component statement ensures the same truth-value for the other. (See rows 1 and 4 in the above truth table.) This relationship can be expressed by saying that A is true if and only if B is true, and likewise A is false if and only if B is false. The phrase "if and only if" can be replaced by the statement "A is a necessary and sufficient condition for B", which means that for a valid equivalence statement the truth of statement A is a "necessary and sufficient condition" for the truth of statement B (likewise, the falsity of A is a "necessary and sufficient condition" for the falsity of B). The condition of "if and only if" does not hold between the statements A and B in the case of invalid (i.e., false) equivalence statements.

An interesting and important theorem within propositional logic is the tautology ((A B) (B A)) (A B). A tautology is a statement that is true for every possible truth-value of its component statements. The truth table below demonstrates that the statement in column (g) is true for every possible truth-value of the component statements A and B, and therefore the statement ((A B) (B A)) (A B) is indeed a tautology.

The four possible truth-values of statement A and statement B appear in columns (a) and (b) of the above truth table. The propositions A B and B A within columns (c) and (d), respectively, are called implications, or conditionals. An implication, in general, can be read as "If A, then B" or as "A implies B". The implication A B is false only for A = true and B = false, as shown in cell (2c). It is true for all other truth-value combinations of A and B, as shown within the table. The same conditions apply to the implication B A (i.e., false only for B = true and A = false).

The statement in column (e), which is the conjunction of two implications, is called a biconditional, or double implication. The fundamental purpose of the preceding truth table is to demonstrate that, given statements A and B, the double implication of statements A and B (i.e., (A B) (B A)) is true if and only if the equivalence A B is true. This relationship between the double implication of two statements and their corresponding equivalence can often be of use in mathematical proofs. Specifically, one can demonstrate rigorously that "A B" is true using the following procedure: one proves that the implication A B is true, and further that the implication B A is true, then one can say that both A B and B A are true statements, or symbolically (A B) (B A) is true. This last statement is the double implication for statements A and B; then according to the preceding truth table the truth of the equivalence A B has been proven.

This is the complete article, containing 926 words (approx. 3 pages at 300 words per page).