|
Normal Form (other)
{{dab ...
Normal form may refer to: * Normal form (databases) * Normal form (game theory) *Canonical form * Normal form (dynamical systems) *Hesse normal form * Normal form in music *Jordan normal form in formal language theory: *Chomsky normal form *Greibach normal form *Kuroda normal form *Normal form (abstract rewriting), an element of a rewrite system which cannot be further rewritten in logic: * Normal form (natural deduction) * Algebraic normal form *Canonical normal form * Clausal normal form *Conjunctive normal form *Disjunctive normal form *Negation normal form *Prenex normal form *Skolem normal form in lambda calculus: * Beta normal form See also * Normalization (other) *Normalization property In abstract rewriting, an object is in normal form if it cannot be rewritten any further, i.e. it is irreducible. Depending on the rewriting system, an object may rewrite to several normal forms or none at all. Many properties of rewriting systems ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Database Normalization
Database normalization or database normalisation (see spelling differences) is the process of structuring a relational database in accordance with a series of so-called normal forms in order to reduce data redundancy and improve data integrity. It was first proposed by British computer scientist Edgar F. Codd as part of his relational model. Normalization entails organizing the columns (attributes) and tables (relations) of a database to ensure that their dependencies are properly enforced by database integrity constraints. It is accomplished by applying some formal rules either by a process of ''synthesis'' (creating a new database design) or ''decomposition'' (improving an existing database design). Objectives A basic objective of the first normal form defined by Codd in 1970 was to permit data to be queried and manipulated using a "universal data sub-language" grounded in first-order logic. An example of such a language is SQL, though it is one that Codd regarded as ser ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Algebraic Normal Form
In Boolean algebra, the algebraic normal form (ANF), ring sum normal form (RSNF or RNF), '' Zhegalkin normal form'', or '' Reed–Muller expansion'' is a way of writing logical formulas in one of three subforms: * The entire formula is purely true or false: *: 1 *: 0 * One or more variables are combined into a term by AND (\and), then one or more terms are combined by XOR (\oplus) together into ANF. Negations are not permitted: : a \oplus b \oplus \left(a \and b\right) \oplus \left(a \and b \and c\right) * The previous subform with a purely true term: : 1 \oplus a \oplus b \oplus \left(a \and b\right) \oplus \left(a \and b \and c\right) Formulas written in ANF are also known as Zhegalkin polynomials and Positive Polarity (or Parity) Reed–Muller expressions (PPRM). Common uses ANF is a normal form, which means that two equivalent formulas will convert to the same ANF, easily showing whether two formulas are equivalent for automated theorem proving. Unlike other normal ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Beta Normal Form
In the lambda calculus, a term is in beta normal form if no ''beta reduction'' is possible. A term is in beta-eta normal form if neither a beta reduction nor an ''eta reduction'' is possible. A term is in head normal form if there is no ''beta-redex in head position''. Beta reduction In the lambda calculus, a beta redex is a term of the form: : (\mathbf x . A) M. A redex r is in head position in a term t, if t has the following shape (note that application has higher priority than abstraction, and that the formula below is meant to be a lambda-abstraction, not an application): : \lambda x_1 \ldots \lambda x_n . \underbrace_ M_2 \ldots M_m , where n \geq 0 and m \geq 1. A beta reduction is an application of the following rewrite rule to a beta redex contained in a term: : (\mathbf x . A) M \longrightarrow A := M where A := M/math> is the result of substituting the term M for the variable x in the term A. A ''head'' beta reduction is a beta reduction applied in head position ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Skolem Normal Form
In mathematical logic, a formula of first-order logic is in Skolem normal form if it is in prenex normal form with only universal first-order quantifiers. Every first-order formula may be converted into Skolem normal form while not changing its satisfiability via a process called Skolemization (sometimes spelled Skolemnization). The resulting formula is not necessarily equivalent to the original one, but is equisatisfiable with it: it is satisfiable if and only if the original one is satisfiable. Reduction to Skolem normal form is a method for removing existential quantifiers from formal logic statements, often performed as the first step in an automated theorem prover. Examples The simplest form of Skolemization is for existentially quantified variables that are not inside the scope of a universal quantifier. These may be replaced simply by creating new constants. For example, \exists x P(x) may be changed to P(c), where c is a new constant (does not occur anywhere e ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Prenex Normal Form
A formula of the predicate calculus is in prenex normal form (PNF) if it is written as a string of quantifiers and bound variables, called the prefix, followed by a quantifier-free part, called the matrix. Together with the normal forms in propositional logic (e.g. disjunctive normal form or conjunctive normal form), it provides a canonical normal form useful in automated theorem proving. Every formula in classical logic is equivalent to a formula in prenex normal form. For example, if \phi(y), \psi(z), and \rho(x) are quantifier-free formulas with the free variables shown then :\forall x \exists y \forall z (\phi(y) \lor (\psi(z) \rightarrow \rho(x))) is in prenex normal form with matrix \phi(y) \lor (\psi(z) \rightarrow \rho(x)), while :\forall x ((\exists y \phi(y)) \lor ((\exists z \psi(z) ) \rightarrow \rho(x))) is logically equivalent but not in prenex normal form. Conversion to prenex form Every first-order formula is logically equivalent (in classical logic) to so ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Negation Normal Form
In mathematical logic, a formula is in negation normal form (NNF) if the negation operator (\lnot, ) is only applied to variables and the only other allowed Boolean operators are conjunction (\land, ) and disjunction (\lor, ). Negation normal form is not a canonical form: for example, a \land (b\lor \lnot c) and (a \land b) \lor (a \land \lnot c) are equivalent, and are both in negation normal form. In classical logic and many modal logics, every formula can be brought into this form by replacing implications and equivalences by their definitions, using De Morgan's laws to push negation inwards, and eliminating double negations. This process can be represented using the following rewrite rules (Handbook of Automated Reasoning 1, p. 204): :\begin A \Rightarrow B &~\to~ \lnot A \lor B \\ \lnot (A \lor B) &~\to~ \lnot A \land \lnot B \\ \lnot (A \land B) &~\to~ \lnot A \lor \lnot B \\ \lnot \lnot A &~\to~ A \\ \lnot \exists x A &~\to~ \forall x \lnot A \\ \lnot \ ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Disjunctive Normal Form
In boolean logic, a disjunctive normal form (DNF) is a canonical normal form of a logical formula consisting of a disjunction of conjunctions; it can also be described as an OR of ANDs, a sum of products, or (in philosophical logic) a ''cluster concept''. As a normal form, it is useful in automated theorem proving. Definition A logical formula is considered to be in DNF if it is a disjunction of one or more conjunctions of one or more literals. A DNF formula is in full disjunctive normal form if each of its variables appears exactly once in every conjunction. As in conjunctive normal form (CNF), the only propositional operators in DNF are and (\wedge), or (\vee), and not (\neg). The ''not'' operator can only be used as part of a literal, which means that it can only precede a propositional variable. The following is a context-free grammar for DNF: # ''DNF'' → (''Conjunction'') \vee ''DNF'' # ''DNF'' → (''Conjunction'') # ''Conjunction'' → ''Literal'' \wedge ''Conju ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Conjunctive Normal Form
In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs. As a canonical normal form, it is useful in automated theorem proving and circuit theory. All conjunctions of literals and all disjunctions of literals are in CNF, as they can be seen as conjunctions of one-literal clauses and conjunctions of a single clause, respectively. As in the disjunctive normal form (DNF), the only propositional connectives a formula in CNF can contain are and, or, and not. The not operator can only be used as part of a literal, which means that it can only precede a propositional variable or a predicate symbol. In automated theorem proving, the notion "''clausal normal form''" is often used in a narrower sense, meaning a particular representation of a CNF formula as a set of sets of literals. Examples and non-exampl ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Clausal Normal Form
In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs. As a canonical normal form, it is useful in automated theorem proving and circuit theory. All conjunctions of literals and all disjunctions of literals are in CNF, as they can be seen as conjunctions of one-literal clauses and conjunctions of a single clause, respectively. As in the disjunctive normal form (DNF), the only propositional connectives a formula in CNF can contain are and, or, and not. The not operator can only be used as part of a literal, which means that it can only precede a propositional variable or a predicate symbol. In automated theorem proving, the notion "''clausal normal form''" is often used in a narrower sense, meaning a particular representation of a CNF formula as a set of sets of literals. Examples and non-examples ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Canonical Normal Form
In Boolean algebra, any Boolean function can be expressed in the canonical disjunctive normal form ( CDNF) or minterm canonical form and its dual canonical conjunctive normal form ( CCNF) or maxterm canonical form. Other canonical forms include the complete sum of prime implicants or Blake canonical form (and its dual), and the algebraic normal form (also called Zhegalkin or Reed–Muller). ''Minterms'' are called products because they are the logical AND of a set of variables, and ''maxterms'' are called sums because they are the logical OR of a set of variables. These concepts are dual because of their complementary-symmetry relationship as expressed by De Morgan's laws. Two dual canonical forms of ''any'' Boolean function are a "sum of minterms" and a "product of maxterms." The term "Sum of Products" (SoP or SOP) is widely used for the canonical form that is a disjunction (OR) of minterms. Its De Morgan dual is a "Product of Sums" (PoS or POS) for the canonical form that ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Normal Form (natural Deduction)
An inference of natural deduction is a normal form, according to Dag Prawitz Dag Prawitz (born 1936, Stockholm) is a Swedish philosopher and logician. He is best known for his work on proof theory and the foundations of natural deduction. Prawitz is a member of the Norwegian Academy of Science and Letters, of the Roya ..., if no formula occurrence is both the principal premise of an elimination rule and the conclusion of an introduction rule. References Logic {{Logic-stub ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Normal-form Game
In game theory, normal form is a description of a ''game''. Unlike extensive form, normal-form representations are not graphical ''per se'', but rather represent the game by way of a matrix. While this approach can be of greater use in identifying strictly dominated strategies and Nash equilibria, some information is lost as compared to extensive-form representations. The normal-form representation of a game includes all perceptible and conceivable strategies, and their corresponding payoffs, for each player. In static games of complete, perfect information, a normal-form representation of a game is a specification of players' strategy spaces and payoff functions. A strategy space for a player is the set of all strategies available to that player, whereas a strategy is a complete plan of action for every stage of the game, regardless of whether that stage actually arises in play. A payoff function for a player is a mapping from the cross-product of players' strategy spaces to ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
