Negation normal form (original) (raw)
Eine logische Formel ist in Negationsnormalform (NNF), falls die Negationsoperatoren in ihr nur direkt über atomaren Aussagen vorkommen. Eine Formel in Negationsnormalform kann in die konjunktive (KNF) oder disjunktive Normalform (DNF) gebracht werden, indem man die Distributivgesetze anwendet. Im Allgemeinen gibt es für jede aussagenlogische Formel mehr als eine Negationsnormalform. Das kann man sich veranschaulichen, indem man sich vor Augen führt, dass jede konjunktive und jede disjunktive Normalform zugleich auch eine Negationsnormalform ist.
| Property | Value |
|---|---|
| dbo:abstract | En lògica matemàtica, una fórmula és en forma normal negativa si l'operador negació només està aplicat a variables, i els únics altres operadors booleans permesos són la conjunció i la disjunció . La forma normal negativa no és una forma canònica: per exemple i són equivalents, i totes dues estan en forma normal negativa. En lògica clàssica i el moltes lògiques modals, tota fórmula pot transformar-se en aquesta forma, tot substituint implicacions i equivalències per llurs definicions, usant les Lleis de De Morgan per desplaçar les negacions cap a l'interior de la fórmula, i eliminant dobles negacions. Aquest procés es pot representar mitjançant les següents regles de reescriptura: Una fórmula en forma normal negativa es pot transformar en les formes normal conjuntiva o normal disjuntiva tot aplicant distributivitat. (ca) Eine logische Formel ist in Negationsnormalform (NNF), falls die Negationsoperatoren in ihr nur direkt über atomaren Aussagen vorkommen. Eine Formel in Negationsnormalform kann in die konjunktive (KNF) oder disjunktive Normalform (DNF) gebracht werden, indem man die Distributivgesetze anwendet. Im Allgemeinen gibt es für jede aussagenlogische Formel mehr als eine Negationsnormalform. Das kann man sich veranschaulichen, indem man sich vor Augen führt, dass jede konjunktive und jede disjunktive Normalform zugleich auch eine Negationsnormalform ist. (de) En logique mathématique, une formule est dite être en forme normale négative (abrégé FNN) si l'opérateur de la négation est appliqué uniquement aux variables, et les seuls opérateurs booléens autorisés sont la conjonction et la disjonction . La forme normale négative n'est pas une forme canonique, par exemple, et sont équivalentes, et sont toutes deux en forme normale négative. En logique classique et beaucoup de logiques modales, chaque formule peut être représentée dans cette forme, par le remplacement des implications et des équivalences par leurs définitions, en utilisant les lois de De Morgan, et en éliminant les doubles négations. Ce processus peut être représenté en utilisant les règles de réécriture suivantes (Handbook of Automated Reasoning 1, p. 204.): Une formule en forme normale négative peut être mise sous la forme normale conjonctive ou en forme normale disjonctive en appliquant la distributivité. (fr) En lógica proposicional, una fórmula lógica está en forma normal negativa si, de poseer negaciones, estas únicamente afectan las fórmulas atómicas, y si además los únicos conectivos existentes son {}. En lógica clásica cada fórmula puede ser representada de esta manera reemplazando implicaciones y equivalencias por sus definiciones, utilizando las Leyes de De Morgan para distribuir las negaciones dentro de cada átomo, o bien eliminando las dobles negaciones. Este proceso puede representarse utilizando las siguientes reglas: Una fórmula en forma normal negativa puede ponerse en las formas más fuertes de forma normal conjuntiva o forma normal disyuntiva, aplicando las leyes de distributividad. (es) In mathematical logic, a formula is in negation normal form (NNF) if the negation operator is only applied to variables and the only other allowed Boolean operators are conjunction and disjunction . Negation normal form is not a canonical form: for example, and 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): [In these rules, the symbol indicates logical implication in the formula being rewritten, and is the rewriting operation.] Transformation into negation normal form can increase the size of a formula only linearly: the number of occurrences of atomic formulas remains the same, the total number of occurrences of and is unchanged, and the number of occurrences of may double. A formula in negation normal form can be put into the stronger conjunctive normal form or disjunctive normal form by applying distributivity. Repeated application of distributivity may exponentially increase the size of a formula. In the classical propositional logic, transformation to negation normal form does not impact computational properties: the satisfiability problem continues to be NP-complete, and the validity problem continues to be co-NP-complete. For formulas in CNF, validity problem is solvable in polynomial time, and for formulas in DNF, the satisfiability problem is solvable in polynomial time. (en) Nella logica booleana, una formula è in forma normale negativa (FNN), indicata anche come NNF (acronimo di Negation Normal Form) se l'operatore di negazione è applicato solo agli atomi. Inoltre, gli unici operatori consentiti sono congiunzione e disgiunzione. La forma normale negativa non è una forma canonica: ad esempio, e sono equivalenti, pur essendo entrambe in forma normale negativa. Nella logica classica e in molte logiche modali, ogni formula può essere espressa in questa forma, applicando ad implicazioni ed equivalenze le rispettive definizioni, usando le leggi di De Morgan ed eliminando le negazioni doppie. Questo processo può essere definito tramite le seguenti formule di riscrittura: Nelle formule di cui sopra, il simbolo indica l'implicazione logica nella formula da riscrivere, mentre è l'operatore di riscrittura. Una formula in FNN può essere trasposta nelle forme normali—queste canoniche—congiuntiva o disgiuntiva grazie alla proprietà distributiva degli operatori e . (it) 否定標準形（ひていひょうじゅんけい、英: negation normal form, NNF）とは、否定記号 が原子論理式のみにかかり、他には選言記号 と連言記号 のみが論理記号として用いられる形の論理式を指す。 命題論理もしくは述語論理においては、いかなる論理式も、ド・モルガンの法則を用い否定演算子を内側に押し込む操作を繰り返すことによって、論理的に等価な否定標準形に置き換えることができる。この操作の具体例を次に示す。 連言標準形(conjunctive normal form)と選言標準形(disjunctive normal form)は否定標準形の性質を満たしている。任意の否定標準形の論理式は、論理式の結合法則と分配法則による操作によって、論理的に等価な連言標準形や選言標準形に変形することができる。 (ja) Uma fórmula lógica está na forma normal da negação se a negação ocorre logo após , e {} são os únicos conectivos booleanos permitidos. Na lógica clássica, cada fórmula pode ser convertida para essa forma substituindo implicações e equivalências pelas suas definições, usando as leis de De Morgan para internalizar a negação na fórmula e eliminando duplas negações. Esse processo pode ser representado através das seguintes regras de conversão: Uma fórmula na forma normal da negação pode ser colocada numa forma mais forte, como a forma normal conjuntiva ou a forma normal disjuntiva aplicando as leis da distributividade. (pt) В математичній логіці, формула є запереченням нормальної форми, якщо заперечення утворене оператором , який може бути записаний або сам, або з логічними операторами: кон'юнкції і диз'юнкція . Заперечення нормальної форми не є канонічною формою: наприклад, і є еквівалентними, і обидва знаходяться в запереченні нормальній формі. У класичній логіці і багатьох видах модальної логіки, кожна формула може бути приведена в цю форму, замінивши наслідки і еквівалентності їх визначеннями, використовуючи закони де Моргана, щоб підштовхнути запереченням до середини, і усунення подвійних заперечень. Цей процес можна представити за допомогою наступних правил переписування (Handbook of Automated Reasoning 1, с 204.): Формула заперечення нормальної форми може бути використана в більш сильному КНФ або ДНФ шляхом застосування дистрибутивності. (uk) |
| dbo:wikiPageExternalLink | https://archive.today/20121208184549/http:/www.izyt.com/BooleanLogic/applet.php |
| dbo:wikiPageID | 554622 (xsd:integer) |
| dbo:wikiPageLength | 3715 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1058509801 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Modal_logic dbc:Normal_forms_(logic) dbr:De_Morgan's_laws dbr:Mathematical_logic dbr:Negation dbr:Conjunctive_normal_form dbr:Logical_conjunction dbc:Propositional_calculus dbr:Distributive_property dbr:Handbook_of_Automated_Reasoning dbr:Logical_disjunction dbr:Disjunctive_normal_form dbr:Boolean_algebra dbr:Boolean_satisfiability_problem dbr:Rewrite_rule |
| dbp:wikiPageUsesTemplate | dbt:Smallcaps dbt:Isbn |
| dcterms:subject | dbc:Normal_forms_(logic) dbc:Propositional_calculus |
| rdfs:comment | Eine logische Formel ist in Negationsnormalform (NNF), falls die Negationsoperatoren in ihr nur direkt über atomaren Aussagen vorkommen. Eine Formel in Negationsnormalform kann in die konjunktive (KNF) oder disjunktive Normalform (DNF) gebracht werden, indem man die Distributivgesetze anwendet. Im Allgemeinen gibt es für jede aussagenlogische Formel mehr als eine Negationsnormalform. Das kann man sich veranschaulichen, indem man sich vor Augen führt, dass jede konjunktive und jede disjunktive Normalform zugleich auch eine Negationsnormalform ist. (de) 否定標準形（ひていひょうじゅんけい、英: negation normal form, NNF）とは、否定記号 が原子論理式のみにかかり、他には選言記号 と連言記号 のみが論理記号として用いられる形の論理式を指す。 命題論理もしくは述語論理においては、いかなる論理式も、ド・モルガンの法則を用い否定演算子を内側に押し込む操作を繰り返すことによって、論理的に等価な否定標準形に置き換えることができる。この操作の具体例を次に示す。 連言標準形(conjunctive normal form)と選言標準形(disjunctive normal form)は否定標準形の性質を満たしている。任意の否定標準形の論理式は、論理式の結合法則と分配法則による操作によって、論理的に等価な連言標準形や選言標準形に変形することができる。 (ja) En lògica matemàtica, una fórmula és en forma normal negativa si l'operador negació només està aplicat a variables, i els únics altres operadors booleans permesos són la conjunció i la disjunció . La forma normal negativa no és una forma canònica: per exemple i són equivalents, i totes dues estan en forma normal negativa. Una fórmula en forma normal negativa es pot transformar en les formes normal conjuntiva o normal disjuntiva tot aplicant distributivitat. (ca) En lógica proposicional, una fórmula lógica está en forma normal negativa si, de poseer negaciones, estas únicamente afectan las fórmulas atómicas, y si además los únicos conectivos existentes son {}. En lógica clásica cada fórmula puede ser representada de esta manera reemplazando implicaciones y equivalencias por sus definiciones, utilizando las Leyes de De Morgan para distribuir las negaciones dentro de cada átomo, o bien eliminando las dobles negaciones. Este proceso puede representarse utilizando las siguientes reglas: (es) En logique mathématique, une formule est dite être en forme normale négative (abrégé FNN) si l'opérateur de la négation est appliqué uniquement aux variables, et les seuls opérateurs booléens autorisés sont la conjonction et la disjonction . La forme normale négative n'est pas une forme canonique, par exemple, et sont équivalentes, et sont toutes deux en forme normale négative. Une formule en forme normale négative peut être mise sous la forme normale conjonctive ou en forme normale disjonctive en appliquant la distributivité. (fr) In mathematical logic, a formula is in negation normal form (NNF) if the negation operator is only applied to variables and the only other allowed Boolean operators are conjunction and disjunction . Negation normal form is not a canonical form: for example, and are equivalent, and are both in negation normal form. [In these rules, the symbol indicates logical implication in the formula being rewritten, and is the rewriting operation.] (en) Nella logica booleana, una formula è in forma normale negativa (FNN), indicata anche come NNF (acronimo di Negation Normal Form) se l'operatore di negazione è applicato solo agli atomi. Inoltre, gli unici operatori consentiti sono congiunzione e disgiunzione. La forma normale negativa non è una forma canonica: ad esempio, e sono equivalenti, pur essendo entrambe in forma normale negativa. Nelle formule di cui sopra, il simbolo indica l'implicazione logica nella formula da riscrivere, mentre è l'operatore di riscrittura. (it) Uma fórmula lógica está na forma normal da negação se a negação ocorre logo após , e {} são os únicos conectivos booleanos permitidos. Na lógica clássica, cada fórmula pode ser convertida para essa forma substituindo implicações e equivalências pelas suas definições, usando as leis de De Morgan para internalizar a negação na fórmula e eliminando duplas negações. Esse processo pode ser representado através das seguintes regras de conversão: (pt) В математичній логіці, формула є запереченням нормальної форми, якщо заперечення утворене оператором , який може бути записаний або сам, або з логічними операторами: кон'юнкції і диз'юнкція . Заперечення нормальної форми не є канонічною формою: наприклад, і є еквівалентними, і обидва знаходяться в запереченні нормальній формі. Формула заперечення нормальної форми може бути використана в більш сильному КНФ або ДНФ шляхом застосування дистрибутивності. (uk) |
| rdfs:label | Forma normal negativa (ca) Negationsnormalform (de) Forma normal negativa (es) Forme normale négative (fr) Forma normale negativa (it) 否定標準形 (ja) Negation normal form (en) Forma normal da negação (pt) Заперечення нормальної форми (uk) |
| owl:sameAs | freebase:Negation normal form wikidata:Negation normal form dbpedia-ca:Negation normal form dbpedia-de:Negation normal form dbpedia-es:Negation normal form dbpedia-fr:Negation normal form dbpedia-it:Negation normal form dbpedia-ja:Negation normal form dbpedia-pt:Negation normal form dbpedia-sr:Negation normal form dbpedia-uk:Negation normal form https://global.dbpedia.org/id/cpaS |
| prov:wasDerivedFrom | wikipedia-en:Negation_normal_form?oldid=1058509801&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Negation_normal_form |
| is dbo:wikiPageDisambiguates of | dbr:NNF dbr:Normal_form |
| is dbo:wikiPageRedirects of | dbr:Negational_normal_form |
| is dbo:wikiPageWikiLink of | dbr:Enumeration_algorithm dbr:NNF dbr:Dependence_logic dbr:Algebraic_normal_form dbr:De_Morgan's_laws dbr:Normal_form dbr:Conjunctive_normal_form dbr:Propositional_directed_acyclic_graph dbr:Knowledge_compilation dbr:Binary_decision_diagram dbr:Boolean_function dbr:Method_of_analytic_tableaux dbr:Canonical_form dbr:Outline_of_logic dbr:Negational_normal_form |
| is foaf:primaryTopic of | wikipedia-en:Negation_normal_form |