Functional completeness (original) (raw)
Con base di connettivi s'intende un sottoinsieme di connettivi logici coi quali è possibile dare la definizione logica di tutti gli altri connettivi. Questa proprietà viene chiamata anche completezza funzionale. Formano una base di connettivi, ad esempio, negazione, congiunzione e disgiunzione, oppure negazione e condizionale materiale. Quest'ultima base di connettivi è pertanto utilizzata per il sistema ipotetico-deduttivo dato dagli assiomi di Hilbert. Tra le basi di connettivi più potenti (in quanto contengono un solo connettivo) vi sono i funtori di Sheffer.
| Property | Value |
|---|---|
| dbo:abstract | En lógica, un conjunto funcionalmente completo de conectivas lógicas u operadores booleanos es aquel que puede ser usado para expresar todas las tablas de verdad posibles combinando sus elementos en expresiones booleanas. Un conjunto bastante conocido de conectivas es { AND, NOT }, que consisten en la conjunción y la negación lógica. También existen conjuntos funcionalmente completos formados por un único operador booleano, como puede ser el caso de { NAND } y { NOR }. En el contexto de la lógica proposicional, los conjuntos de conectivas funcionalmente completos también son llamados suficientes. (es) In logic, a functionally complete set of logical connectives or Boolean operators is one which can be used to express all possible truth tables by combining members of the set into a Boolean expression. A well-known complete set of connectives is { AND, NOT }. Each of the singleton sets { NAND } and { NOR } is functionally complete. A gate or set of gates which is functionally complete can also be called a universal gate / gates. A functionally complete set of gates may utilise or generate 'garbage bits' as part of its computation which are either not part of the input or not part of the output to the system. In a context of propositional logic, functionally complete sets of connectives are also called (expressively) adequate. From the point of view of digital electronics, functional completeness means that every possible logic gate can be realized as a network of gates of the types prescribed by the set. In particular, all logic gates can be assembled from either only binary NAND gates, or only binary NOR gates. (en) Con base di connettivi s'intende un sottoinsieme di connettivi logici coi quali è possibile dare la definizione logica di tutti gli altri connettivi. Questa proprietà viene chiamata anche completezza funzionale. Formano una base di connettivi, ad esempio, negazione, congiunzione e disgiunzione, oppure negazione e condizionale materiale. Quest'ultima base di connettivi è pertanto utilizzata per il sistema ipotetico-deduttivo dato dagli assiomi di Hilbert. Tra le basi di connettivi più potenti (in quanto contengono un solo connettivo) vi sono i funtori di Sheffer. (it) System funkcjonalnie pełny – taki zbiór funkcji boolowskich, dla którego dowolna funkcja boolowska może być przedstawiona za pomocą funkcji należących do tego zbioru i argumentów funkcji. Funkcje sumy, iloczynu i negacji tworzą tzw. podstawowy system funkcjonalnie pełny. Nie jest to jednak system minimalny. Systemy funkcjonalnie pełne tworzą również: * iloczyn i negacja (suma może zostać wyeliminowana dzięki prawu De Morgana) * suma i negacja (analogicznie jak wyżej) * funkcja Sheffera (NAND) (jak wyżej oraz ponieważ ) * funkcja Peirce'a (NOR). (pl) Em lógica, um grupo de conectivos ou operadores Booleanos tem a propriedade da completude funcional se todos outros conectivos possíveis podem ser definidos em função dele. Do ponto de vista da eletrônica digital, completude funcional significa que cada porta lógica possível pode ser tratada como uma rede de portas dos tipos prescritos pelo conjunto. Em particular, todas as portas lógicas podem ser montadas a partir de apenas NANDs e NOR. (pt) Функциональная полнота множества логических операций или булевых функций — это возможность выразить все возможные значения таблиц истинности с помощью формул из элементов этого множества. Математическая логика обычно использует такой набор операций: конъюнкция, дизъюнкция, отрицание, импликация и эквиваленция. Это множество операций является функционально полным. Но оно не является минимальной функционально полной системой, поскольку: Таким образом также является функционально полной системой. Но также может быть выражено (в соответствии с законом де Моргана) как: также может быть определена через подобным образом. Также может быть выражена через следующим образом: Итак и одна из является минимальной функционально полной системой. (ru) 自足算子或自足连结词是在一特定类的算子中只靠自身就能生成所有这些算子的算子。在逻辑中，它是足够生成所有布尔值函数的一个逻辑算子，，这里的 是一个任意集合而 是一个通用的 2-元素集合，典型为 ，特别是生成所有的有限布尔函数，。 (zh) Функціональна повнота множини логічних операцій чи булевих функцій — це можливість подати всі можливі значення таблиць істинності за допомогою формул із елементів цієї множини. У логіці зазвичай застосовують такий набір операцій: кон'юнкція, диз'юнкція, заперечення, імплікація та еквівалентність. Ця множина операцій є функціонально повною. Але вона не є мінімальною функціонально повною системою, оскільки: Отже також є функціонально повною системою. Але також може бути виражене (за законом де Моргана) як: також може бути визначено через подібним чином. Також може бути виражена через таким чином: Отже та одна з є мінімальною функціонально повною системою. У контексті логіки висловлювань, функціонально повний набір зв'язків також називається (неформально) адекватним[джерело?]. (uk) |
| dbo:wikiPageID | 5279259 (xsd:integer) |
| dbo:wikiPageLength | 14905 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1106460263 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Quantum_logic_gate dbr:Sheffer_stroke dbr:Algebra_of_sets dbr:Unary_operation dbr:Quantum_computing dbr:Post's_lattice dbr:Material_conditional dbr:Mathematical_logic dbr:Russell's_Paradox dbr:NAND_gate dbr:NOR_gate dbr:Negation dbr:Emil_Leon_Post dbr:Monotonic dbr:Arity dbr:Logical_NAND dbr:Logical_NOR dbr:Logical_conjunction dbc:Propositional_calculus dbr:Clone_(algebra) dbr:Propositional_logic dbr:Majority_function dbr:Truth_table dbr:Truth_value dbr:Lattice_(order) dbr:Logical_biconditional dbr:Affine_transformation dbr:Digital_electronics dbr:Isomorphism dbr:Logical_connective dbr:Logical_disjunction dbr:Logic_gate dbc:Boolean_algebra dbr:Hadamard_gate dbc:Logic_in_computer_science dbr:Charles_Sanders_Peirce dbr:Henry_M._Sheffer dbr:Toffoli_gate dbr:Boolean_algebra dbr:Boolean_algebra_(structure) dbr:Boolean_domain dbr:Boolean_expression dbr:Boolean_function dbr:Fredkin_gate dbr:Set_(mathematics) dbr:Singleton_(mathematics) dbr:Universal_set dbr:Subset dbr:Universal_logic_gate dbr:Reversible_computation dbr:De_Morgan_dual |
| dbp:wikiPageUsesTemplate | dbt:Annotated_link dbt:Further dbt:Reflist dbt:Mathematical_logic |
| dct:subject | dbc:Propositional_calculus dbc:Boolean_algebra dbc:Logic_in_computer_science |
| rdfs:comment | Con base di connettivi s'intende un sottoinsieme di connettivi logici coi quali è possibile dare la definizione logica di tutti gli altri connettivi. Questa proprietà viene chiamata anche completezza funzionale. Formano una base di connettivi, ad esempio, negazione, congiunzione e disgiunzione, oppure negazione e condizionale materiale. Quest'ultima base di connettivi è pertanto utilizzata per il sistema ipotetico-deduttivo dato dagli assiomi di Hilbert. Tra le basi di connettivi più potenti (in quanto contengono un solo connettivo) vi sono i funtori di Sheffer. (it) System funkcjonalnie pełny – taki zbiór funkcji boolowskich, dla którego dowolna funkcja boolowska może być przedstawiona za pomocą funkcji należących do tego zbioru i argumentów funkcji. Funkcje sumy, iloczynu i negacji tworzą tzw. podstawowy system funkcjonalnie pełny. Nie jest to jednak system minimalny. Systemy funkcjonalnie pełne tworzą również: * iloczyn i negacja (suma może zostać wyeliminowana dzięki prawu De Morgana) * suma i negacja (analogicznie jak wyżej) * funkcja Sheffera (NAND) (jak wyżej oraz ponieważ ) * funkcja Peirce'a (NOR). (pl) Em lógica, um grupo de conectivos ou operadores Booleanos tem a propriedade da completude funcional se todos outros conectivos possíveis podem ser definidos em função dele. Do ponto de vista da eletrônica digital, completude funcional significa que cada porta lógica possível pode ser tratada como uma rede de portas dos tipos prescritos pelo conjunto. Em particular, todas as portas lógicas podem ser montadas a partir de apenas NANDs e NOR. (pt) 自足算子或自足连结词是在一特定类的算子中只靠自身就能生成所有这些算子的算子。在逻辑中，它是足够生成所有布尔值函数的一个逻辑算子，，这里的 是一个任意集合而 是一个通用的 2-元素集合，典型为 ，特别是生成所有的有限布尔函数，。 (zh) In logic, a functionally complete set of logical connectives or Boolean operators is one which can be used to express all possible truth tables by combining members of the set into a Boolean expression. A well-known complete set of connectives is { AND, NOT }. Each of the singleton sets { NAND } and { NOR } is functionally complete. A gate or set of gates which is functionally complete can also be called a universal gate / gates. In a context of propositional logic, functionally complete sets of connectives are also called (expressively) adequate. (en) En lógica, un conjunto funcionalmente completo de conectivas lógicas u operadores booleanos es aquel que puede ser usado para expresar todas las tablas de verdad posibles combinando sus elementos en expresiones booleanas. Un conjunto bastante conocido de conectivas es { AND, NOT }, que consisten en la conjunción y la negación lógica. También existen conjuntos funcionalmente completos formados por un único operador booleano, como puede ser el caso de { NAND } y { NOR }. (es) Функціональна повнота множини логічних операцій чи булевих функцій — це можливість подати всі можливі значення таблиць істинності за допомогою формул із елементів цієї множини. У логіці зазвичай застосовують такий набір операцій: кон'юнкція, диз'юнкція, заперечення, імплікація та еквівалентність. Ця множина операцій є функціонально повною. Але вона не є мінімальною функціонально повною системою, оскільки: Отже також є функціонально повною системою. Але також може бути виражене (за законом де Моргана) як: також може бути визначено через подібним чином. (uk) Функциональная полнота множества логических операций или булевых функций — это возможность выразить все возможные значения таблиц истинности с помощью формул из элементов этого множества. Математическая логика обычно использует такой набор операций: конъюнкция, дизъюнкция, отрицание, импликация и эквиваленция. Это множество операций является функционально полным. Но оно не является минимальной функционально полной системой, поскольку: Таким образом также является функционально полной системой. Но также может быть выражено (в соответствии с законом де Моргана) как: (ru) |
| rdfs:label | Completitud funcional (es) Functional completeness (en) Base di connettivi (it) System funkcjonalnie pełny (pl) Completude funcional (pt) Функциональная полнота (ru) Функціональна повнота (uk) 自足算子 (zh) |
| owl:sameAs | freebase:Functional completeness wikidata:Functional completeness dbpedia-da:Functional completeness dbpedia-es:Functional completeness dbpedia-fa:Functional completeness http://hy.dbpedia.org/resource/Ամբողջ_ֆունկցիա dbpedia-it:Functional completeness dbpedia-pl:Functional completeness dbpedia-pt:Functional completeness dbpedia-ru:Functional completeness dbpedia-uk:Functional completeness dbpedia-zh:Functional completeness https://global.dbpedia.org/id/2DJwt |
| prov:wasDerivedFrom | wikipedia-en:Functional_completeness?oldid=1106460263&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Functional_completeness |
| is dbo:wikiPageRedirects of | dbr:Functionally_complete dbr:Expressive_adequacy dbr:Sole_sufficient_operator dbr:Complete_set_of_Boolean_operators dbr:Adequacy_(logic) dbr:Post's_functional_completeness_theorem dbr:Sufficiently_connected |
| is dbo:wikiPageWikiLink of | dbr:Quantum_logic_gate dbr:Sheffer_stroke dbr:List_of_pioneers_in_computer_science dbr:Domino_computer dbr:Index_of_philosophy_articles_(D–H) dbr:List_of_quantum_logic_gates dbr:Post's_lattice dbr:Timeline_of_quantum_computing_and_communication dbr:General-purpose_computing_on_graphics_processing_units dbr:NAND_gate dbr:NAND_logic dbr:NOR_gate dbr:NOR_logic dbr:Quantum_Computing:_A_Gentle_Introduction dbr:Emil_Leon_Post dbr:Functionally_complete dbr:Logical_NOR dbr:Completeness_(logic) dbr:Many-valued_logic dbr:Adder_(electronics) dbr:Truth_function dbr:Truth_table dbr:Laws_of_Form dbr:List_of_Boolean_algebra_topics dbr:Logic_alphabet dbr:DE-9IM dbr:Expressive_adequacy dbr:Knowledge_representation_and_reasoning dbr:Logical_connective dbr:Logic_gate dbr:Predicate_functor_logic dbr:Hans_Kamp dbr:Charles_Sanders_Peirce dbr:Toffoli_gate dbr:Automata_theory dbr:Boolean_algebra dbr:Boolean_algebras_canonically_defined dbr:Boolean_circuit dbr:Boolean_function dbr:Sole_sufficient_operator dbr:Circuit_satisfiability_problem dbr:Frege_system dbr:Implicational_propositional_calculus dbr:Complete_set_of_Boolean_operators dbr:Little_Computer_3 dbr:Reversible_computing dbr:Outline_of_logic dbr:Adequacy_(logic) dbr:Post's_functional_completeness_theorem dbr:Sufficiently_connected |
| is rdfs:seeAlso of | dbr:Truth_function |
| is foaf:primaryTopic of | wikipedia-en:Functional_completeness |