21.
Contradiction -- from MathWorld
- Weisstein, Eric W.
A sentence is called a contradiction if its truth table contains only 'F.' See also: Consistency Strength, Contingency, Tautology, Truth Table
22.
Contradiction Law -- from MathWorld
- Weisstein, Eric W.
No A is not-A. See also: NOT
23.
Critical Pair -- from MathWorld
- Weisstein, Eric W.
Let x\to y and u\to v be two rules of a term rewriting system, and suppose these rules have no variables in common. If they do, rename the variables. If x_1 is a subterm of x (or the term x itself) such that it is not a variable, and the pair (x_1, u) is unifiable with the most general unifier \theta, then y\theta and the result of replacing x_1\theta in x\theta by v\theta are called a critical pair. The fact that all critical pairs of a term rewriting system are joinable, i.e., can be reduced to...
24.
Crocodile's Dilemma -- from MathWorld
- Weisstein, Eric W.
An unsolvable problem in logic dating back to the ancient Greeks and quoted, for example, by German philosopher Carl von Prantl (1855). The dilemma consists of a crocodile capturing a child and promising his father that he will release it provided that the man can tell in advance what the crocodile is going to do. The father says that the crocodile will not give the child back. What should the crocodile do?
25.
Cut Elimination Theorem -- from MathWorld
- Weisstein, Eric W.
The cut elimination theorem, also called the" Hauptsatz" (Gentzen 1969), states that every sequent calculus derivation can be transformed into another derivation with the same endsequent (bottom sequent) and in which the cut rule does not occur. All derivations without cuts posses the sub-formula property that all formulas occurring in a derivation are sub-formulas of the formulas from the endsequent. A sharpened form of theorem applies to the classical variant of sequent calculus. ...
26.
Deducible -- from MathWorld
- Weisstein, Eric W.
If q is logically deducible from p, this is written p\vdash q. See also: Deduction, Deduction Theorem
27.
Deduction -- from MathWorld
- Weisstein, Eric W.
Deduction is the process of drawing conclusions from premises and syllogisms. See also: Conclusion, Deducible, Deduction Theorem, Premise, Syllogism
28.
Deduction Theorem -- from MathWorld
- Weisstein, Eric W.
A metatheorem in mathematical logic also known under the name "conditional proof." It states that if the sentential formula B can be derived from the set of sentential formulas A_1,\dots, A_n, then the sentential formula A_n\Longrightarrow B can be derived from A_1,\dots,A_{n-1}. In a less formal setting, this means that if a thesis S can be proven under the hypotheses U, V, then one can prove that V implies T under hypothesis U. See also: Deducible, Deduction, Sentential Formula
29.
Definite Clause -- from MathWorld
- Weisstein, Eric W.
See also: Clause
30.
Disjunctive Normal Form -- from MathWorld
- Weisstein, Eric W.
A statement is in disjunctive normal form if it is a disjunction (sequence of ORs) consisting of one or more disjuncts, each of which is a conjunction (AND) of one or more literals (i.e., statement letters and negations of statement letters; Mendelson 1997, p. 30). The Mathematica command LogicalExpand[expr] gives disjunctive normal form (with some contractions, i.e., LogicalExpand attempts to shorten output with heuristic simplification). Examples of disjunctive normal forms include A (1) ...
31.
Disjunctive Syllogism -- from MathWorld
- Weisstein, Eric W.
...under construction...
32.
Equational Logic -- from MathWorld
- Weisstein, Eric W.
The terms of equational logic are built up from variables and constants using function symbols (or operations). Identities (equalities) of the form s = t, where s and t are terms, constitute the formal language of equational logic. The syllogisms of equational logic are summarized below. 1. Reflexivity: \overline{s=s}. 2. Symmetry: {s=t\over t=s}. 3. Transitivity: {s=t, t=v\over s=v}. 4. For f a function symbol and n\geq 0, {s_1 = t_1, \dots , s_n = t_n\over f(s_1,\dots,s_n) =...
33.
Equipollent -- from MathWorld
- Weisstein, Eric W.
Two statements in logic are said to be equipollent if they are deducible from each other. Two sets A and B are said to be equipollent iff there is a one-to-one function (i.e., a bijection) from A onto B (Moore 1982, p. 10; Rubin 1967, p. 67; Suppes 1972, p. 91). The term equipotent is sometimes used instead of equipollent. See also: Bijective
34.
Existential Closure -- from MathWorld
- Weisstein, Eric W.
A class of processes which attempt to round off a domain and simplify its theory by adjoining elements. See also: Model Completion
35.
Existential Quantifier -- from MathWorld
- Weisstein, Eric W.
The exists quantifier \exists. See also: Exists, For All, Quantifier, Universal Quantifier
36.
Existential Sentence -- from MathWorld
- Weisstein, Eric W.
A statement claiming the existence of an object with given properties. In the language of set theory it can be formulated as follows, \exists x\in U\hbox{ such that }x\in A, where U is the universal set and A is a given set contained in it. In other words, it states that set A is nonempty. See also: Existential Quantifier, For Some, Sentence, Sufficiently Large, Universal Sentence
37.
False -- from MathWorld
- Weisstein, Eric W.
A statement which is rigorously not true. Regular two-valued logic allows statements to be only true or false, but fuzzy logic treats "truth" as a continuum which can have a value between 0 and 1. The symbol \curlywedge is sometimes used to denote "false," although "F" is more commonly used in truth tables. See also: Alethic, Booleans, Fuzzy Logic, Logic, True, Truth Table, Undecidable
38.
Finitely Terminating -- from MathWorld
- Weisstein, Eric W.
A reduction system is called finitely terminating (or Noetherian) if there are no infinite rewriting sequences. This property guarantees that any rewriting algorithm will terminate on any input. Ordering expressions may help to find out that a reduction system is finitely terminating. Orders used for this purpose are based on some measure of expression complexity. Existence of a reduction order compliant with rules of a term rewriting system guarantees that the system is finitely terminating. The...
39.
First-Order Logic -- from MathWorld
- Weisstein, Eric W.
The set of terms of first-order logic (also known as first-order predicate calculus) is defined by the following rules: 1. A variable is a term. 2. If f is an n-place function symbol (with n\geq 0) and t_1, ..., t_n are terms, then f(t_1,\dots,t_n) is a term. If P is an n-place predicate symbol (again with n\geq 0) and t_1, ..., t_n are terms, then P(t_1,\dots,t_n) is an atomic statement. Consider the sentential formulas \forall x B and \exists x B, where B is a sentential formula, \forall is...
40.
First-Order Predicate Calculus -- from MathWorld
- Weisstein, Eric W.
See: First-Order Logic
