Logic

This fortune soaks up 47 times its own weight in excess memory.

Math

Note: If you cannot view some of the math on this page, you may need to add MathML support to your browser. If you have Mozilla/Firefox, go here and install the fonts. If you have Internet Explorer, go here and install the MathPlayer plugin.

Math > Logic

Logic

The study of propositions and deductive reasoning.

Sibling topics:

Contents:

Definition of open sentence
An open sentence is a boolean expression that contains unbound variables. The truth of an open sentence cannot be evaluated until specific values are substituted for the unbound variables. If a set of values makes an open sentence true when substituted for the unbound variables, the values are said to satisfy the sentence. Typically, a universe of discourse is defined, from which the values can be chosen.

Here are some example open sentences:
  1. `S sube ZZ` (`S` is unbound)
  2. `y^2-5y+6=0` (`y` is unbound)
Definition of implication [tags: implication]
A logical implication is a statement that relates two propositions. If `P` and `Q` and `P` implies `Q`, then `P` is called the hypothesis (or antecedant) and `Q` is called the conclusion (or consequent). The implication can be written as `P => Q`, `P |== Q`, or `P :. Q` (in decreasing order of popularity), all of which can be read "`P` implies `Q`" or "`P` entails `Q`". A logical implication is false only if the hypothesis is true but the conclusion is false.

When the sentence "if A, then B" is encountered, where `A` or `B` is an open sentence, it is generally interpreted as a universally quantified implication: `(AA x in UU)(A => B)`.
Definition of universal quantifier
The symbol `AA` (read "for all" or "for every") is called the universal quantifier. It is generally followed by a variable name, a set or expression restricting that variable, and open sentence about that variable. This forms a new sentence which asserts that all possible substitutions for the variable satisfy the open sentence. If the set is omitted, it is assumed to be `UU`.

For instance, the sentence `A sube B` can be defined using the universal quantifier: `(AA x in A)(x in B)`. This says that every element in `A` exists in `B`, which is exactly what `A sube B` means. The parentheses in the sentence are not strictly required. `AA x in A (x in B)` means the same thing, as does `AA x in A` `x in B`. Note that the sentence containing the universal quantifier may be false. For example: `(AA n in NN)(n < 0)`. This asserts that all natural numbers are negative, but the assertion is false.
Definition of existential quantifier
The symbol `EE` (read "there exists") is called the existential quantifier. It is generally followed by a variable name, a set or expression restricting that variable, and open sentence about that variable. This forms a new sentence which asserts that there exists at least one substition for the variable that satisfies the open sentence. If the set is omitted, it is assumed to be `UU`.

For instance, the sentence `a div b` can be defined using the existential quantifier: `(EE t in ZZ)(at=b)`. This says that there exists an integer `t` such that `at=b`. The parentheses in the sentence are not strictly required. `EE t in ZZ (at=b)` means the same thing, as does `EE t in ZZ` `at=b`. Note that the sentence containing the existential quantifier may be false. For example: `(EE n in NN)(n < 0)`. This asserts that there exists at least one natural number that is negative, but the assertion is false.
Definition of truth set
A truth set of an open sentence is the complete set of values that, when substituted for the open variables in the sentence, make it true. For example, the truth set of `x^2-4x-5=0` (`UU=RR`) is {-1,5}.
Definition of counterexample [tags: counterexample]
A counterexample is a set of values that, when substituted into a logical implication, makes the hypothesis of the implication true and the conclusion false.
Definition of vacuously true
A vacuously true statement is a logical implication that is true, but the truth set of its hypothesis is the empty set. An example of a vacuously true statement is: "If `x` is a real number with `x^2<0`, then `x=17`." The statement is true because there does not exist a counterexample, but it's rather useless because there is no situation to which this statement can be applied.
Hypothesis: De Morgan's Law
Given propositions `P` and `Q`:
  1. `not (P ^^ Q) = not P vv not Q`, and
  2. `not (P vv Q) = not P ^^ not Q`, and
  3. `not (P => Q) = P ^^ not Q`, and
  4. `not (AA x)(P(x)) = (EE x)(not P(x))`, and
  5. `not (EE x)(P(x)) = (AA x)(not P(x))`