Read-once function (original) (raw)
In mathematics, a read-once function is a special type of Boolean function that can be described by a Boolean expression in which each variable appears only once. More precisely, the expression is required to use only the operations of logical conjunction, logical disjunction, and negation. By applying De Morgan's laws, such an expression can be transformed into one in which negation is used only on individual variables (still with each variable appearing only once). By replacing each negated variable with a new positive variable representing its negation, such a function can be transformed into an equivalent positive read-once Boolean function, represented by a read-once expression without negations.
| Property | Value |
|---|---|
| dbo:abstract | In mathematics, a read-once function is a special type of Boolean function that can be described by a Boolean expression in which each variable appears only once. More precisely, the expression is required to use only the operations of logical conjunction, logical disjunction, and negation. By applying De Morgan's laws, such an expression can be transformed into one in which negation is used only on individual variables (still with each variable appearing only once). By replacing each negated variable with a new positive variable representing its negation, such a function can be transformed into an equivalent positive read-once Boolean function, represented by a read-once expression without negations. (en) |
| dbo:wikiPageExternalLink | http://www.cs.haifa.ac.il/~golumbic/courses/algorithmic-graph-theory/slides_and_notes_of_lectures/Lecture%207%20-%20Cographs%20and%20their%20Applications/readonce-chapter-final.pdf http://mi.mathnet.ru/eng/umn3055 |
| dbo:wikiPageID | 50568483 (xsd:integer) |
| dbo:wikiPageLength | 7944 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1089153594 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Monotonic_function dbr:De_Morgan's_laws dbr:Negation dbr:Conjunctive_normal_form dbr:Logical_conjunction dbr:Lowest_common_ancestor dbr:Theoretical_Computer_Science_(journal) dbr:Discrete_Applied_Mathematics dbr:Discrete_Mathematics_(journal) dbr:Journal_of_the_ACM dbr:Logical_disjunction dbc:Boolean_algebra dbr:Cograph dbr:Disjunctive_normal_form dbr:Boolean_expression dbr:Boolean_function dbr:Polynomial_time dbr:Median_algebra dbr:Variable_(mathematics) dbr:Russian_Mathematical_Surveys dbr:Maximal_clique dbr:Triangle_graph dbr:Truth_assignment |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Mvar dbt:Refbegin dbt:Refend dbt:Reflist |
| dct:subject | dbc:Boolean_algebra |
| rdfs:comment | In mathematics, a read-once function is a special type of Boolean function that can be described by a Boolean expression in which each variable appears only once. More precisely, the expression is required to use only the operations of logical conjunction, logical disjunction, and negation. By applying De Morgan's laws, such an expression can be transformed into one in which negation is used only on individual variables (still with each variable appearing only once). By replacing each negated variable with a new positive variable representing its negation, such a function can be transformed into an equivalent positive read-once Boolean function, represented by a read-once expression without negations. (en) |
| rdfs:label | Read-once function (en) |
| owl:sameAs | wikidata:Read-once function https://global.dbpedia.org/id/2Nmxm |
| prov:wasDerivedFrom | wikipedia-en:Read-once_function?oldid=1089153594&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Read-once_function |
| is dbo:wikiPageWikiLink of | dbr:List_of_Boolean_algebra_topics dbr:Cograph dbr:Boolean_function |
| is foaf:primaryTopic of | wikipedia-en:Read-once_function |