Logical equivalence
Encyclopedia
In logic
Logic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...

, statements p and q are logically equivalent if they have the same logical content.

Syntactically
Syntax (logic)
In logic, syntax is anything having to do with formal languages or formal systems without regard to any interpretation or meaning given to them...

, p and q are equivalent if each can be proved from the other. Semantically, p and q are equivalent if they have the same truth value in every model.

The logical equivalence of p and q is sometimes expressed as , Epq, or .
However, these symbols are also used for material equivalence; the proper interpretation depends on the context. Logical equivalence is different from material equivalence, although the two concepts are closely related.

Example

The following statements are logically equivalent:
  1. If Lisa is in France
    France
    The French Republic , The French Republic , The French Republic , (commonly known as France , is a unitary semi-presidential republic in Western Europe with several overseas territories and islands located on other continents and in the Indian, Pacific, and Atlantic oceans. Metropolitan France...

    , then she is in Europe
    Europe
    Europe is, by convention, one of the world's seven continents. Comprising the westernmost peninsula of Eurasia, Europe is generally 'divided' from Asia to its east by the watershed divides of the Ural and Caucasus Mountains, the Ural River, the Caspian and Black Seas, and the waterways connecting...

    . (In symbols, .)
  2. If Lisa is not in Europe, then she is not in France. (In symbols, .)


Syntactically, (1) and (2) are derivable from each other via the rules of contraposition
Contraposition
In traditional logic, contraposition is a form of immediate inference in which from a given proposition another is inferred having for its subject the contradictory of the original predicate, and in some cases involving a change of quality . For its symbolic expression in modern logic see the rule...

 and double negation
Double negation
In the theory of logic, double negation is expressed by saying that a proposition A is identical to not , or by the formula A = ~~A. Like the Law of Excluded Middle, this principle when extended to an infinite collection of individuals is disallowed by Intuitionistic logic...

. Semantically, (1) and (2) are true in exactly the same models (interpretations, valuations); namely, those in which either Lisa is in France is false or Lisa is in Europe is true.

(Note that in this example classical logic
Classical logic
Classical logic identifies a class of formal logics that have been most intensively studied and most widely used. The class is sometimes called standard logic as well...

 is assumed. Some non-classical logic
Non-classical logic
Non-classical logics is the name given to formal systems which differ in a significant way from standard logical systems such as propositional and predicate logic. There are several ways in which this is done, including by way of extensions, deviations, and variations...

s do not deem (1) and (2) logically equivalent.)

Relation to material equivalence

Logical equivalence is different from material equivalence. The material equivalence of p and q (often written pq) is itself another statement in same object language
Formal system
In formal logic, a formal system consists of a formal language and a set of inference rules, used to derive an expression from one or more other premises that are antecedently supposed or derived . The axioms and rules may be called a deductive apparatus...

 as p and q, which expresses the idea "p if and only if q". In particular, the truth value of pq can change from one model to another.

The claim that two formulas are logically equivalent is a statement in the metalanguage
Metalanguage
Broadly, any metalanguage is language or symbols used when language itself is being discussed or examined. In logic and linguistics, a metalanguage is a language used to make statements about statements in another language...

, expressing a relationship between two statements p and q. The claim that p and q are semantically equivalent does not depend on any particular model; it says that in every possible model, p will have the same truth value as q. The claim that p and q are syntactically equivalent does not depend on models at all; it states that there is a deduction of q from p and a deduction of p from q.

There is a close relationship between material equivalence and logical equivalence. Formulas p and q are syntactically equivalent if and only if pq is a theorem
Theorem
In mathematics, a theorem is a statement that has been proven on the basis of previously established statements, such as other theorems, and previously accepted statements, such as axioms...

, while p and q are semantically equivalent if and only if pq is true in every model (that is, pq is logically valid).

See also

  • Logical biconditional
    Logical biconditional
    In logic and mathematics, the logical biconditional is the logical connective of two statements asserting "p if and only if q", where q is a hypothesis and p is a conclusion...

  • Logical equality
    Logical equality
    Logical equality is a logical operator that corresponds to equality in Boolean algebra and to the logical biconditional in propositional calculus...

  • If and only if
    If and only if
    In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....

  • Equisatisfiability
    Equisatisfiability
    In logic, two formulae are equisatisfiable if the first formula is satisfiable whenever the second is and vice versa; in other words, either both formulae are satisfiable or both are not. Two equisatisfiable formulae may have different models, provided they both have some or both have none...

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK