## 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

Here are some example open sentences:

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)`.

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.

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.
Given propositions `P` and `Q`:

### Logic

The study of propositions and deductive reasoning.#### Sibling topics:

#### Contents:

- De Morgan's Law
- Definition of counterexample
- Definition of existential quantifier
- Definition of implication
- Definition of open sentence
- Definition of truth set
- Definition of universal quantifier
- Definition of vacuously true

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:

- `S sube ZZ` (`S` is unbound)
- `y^2-5y+6=0` (`y` is unbound)

Definition of 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

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

- `not (P ^^ Q) = not P vv not Q`, and
- `not (P vv Q) = not P ^^ not Q`, and
- `not (P => Q) = P ^^ not Q`, and
- `not (AA x)(P(x)) = (EE x)(not P(x))`, and
- `not (EE x)(P(x)) = (AA x)(not P(x))`