Minimal axioms for Boolean algebra (original) (raw)

In mathematical logic, minimal axioms for Boolean algebra are assumptions which are equivalent to the axioms of Boolean algebra (or propositional calculus), chosen to be as short as possible. For example, if one chooses to take commutativity for granted, an axiom with six NAND operations and three variables is equivalent to Boolean algebra : where the vertical bar represents the NAND logical operation (also known as the Sheffer stroke). In 1933, Edward Vermilye Huntington identified the axiom The following year, Meredith found a 2-basis in terms of the Sheffer stroke:

Property	Value
dbo:abstract	In mathematical logic, minimal axioms for Boolean algebra are assumptions which are equivalent to the axioms of Boolean algebra (or propositional calculus), chosen to be as short as possible. For example, if one chooses to take commutativity for granted, an axiom with six NAND operations and three variables is equivalent to Boolean algebra : where the vertical bar represents the NAND logical operation (also known as the Sheffer stroke). It is one of 25 candidate axioms for this property identified by Stephen Wolfram, by enumerating the Sheffer identities of length less or equal to 15 elements (excluding mirror images) that have no noncommutative models with four or fewer variables, and was first proven equivalent by William McCune, Branden Fitelson, and Larry Wos. MathWorld, a site associated with Wolfram, has named the axiom the "Wolfram axiom". McCune et al. also found a longer single axiom for Boolean algebra based on disjunction and negation. In 1933, Edward Vermilye Huntington identified the axiom as being equivalent to Boolean algebra, when combined with the commutativity of the OR operation, , and the assumption of associativity, . Herbert Robbins conjectured that Huntington's axiom could be replaced by which requires one fewer use of the logical negation operator . Neither Robbins nor Huntington could prove this conjecture; nor could Alfred Tarski, who took considerable interest in it later. The conjecture was eventually proved in 1996 with the aid of theorem-proving software. This proof established that the Robbins axiom, together with associativity and commutativity, form a 3-basis for Boolean algebra. The existence of a 2-basis was established in 1967 by Carew Arthur Meredith: The following year, Meredith found a 2-basis in terms of the Sheffer stroke: In 1973, Padmanabhan and Quackenbush demonstrated a method that, in principle, would yield a 1-basis for Boolean algebra. Applying this method in a straightforward manner yielded "axioms of enormous length", thereby prompting the question of how shorter axioms might be found. This search yielded the 1-basis in terms of the Sheffer stroke given above, as well as the 1-basis which is written in terms of OR and NOT. (en) Аксиома Вольфрама является результатом исследований, осуществлённых Стивеном Вольфрамом при поиске кратчайшей аксиомы из одного уравнения, эквивалентной аксиомам булевой алгебры (или логике высказываний). Результатом его поиска стала аксиома с шестью логическими операциями «НЕ-И» (так же известными как штрих Шеффера) и тремя переменными, которая эквивалентна булевой алгебре: ((a \| b)	c)	(a	((a	c)	a)) = c Знаком	обозначена логическая операция «НЕ-И» (штрих Шеффера), а высказывание X	Y означает, что X и Y несовместны, т. е. не являются истинными одновременно. Эта булева функция названа в честь Генри Шеффера, который доказал, что логику остальных операций булевой алгебры («НЕ», «И», «ИЛИ» и пр.) можно выразить с использованием только операции «НЕ-И» (штрих Шеффера), которая образует базис для пространства булевых функций от двух переменных. Вольфрам отобрал 25 тождеств Шеффера, состоящих не более чем из 15 элементов (без учёта зеркальных изображений), которые не имеют некоммутативных моделей размером, меньшим или равным 4 переменных. Исследователи знали о существовании аксиомы из одного уравнения, эквивалентной булевой алгебре, которую можно выразить в терминах дизъюнкции, отрицания и штриха Шеффера. Вольфрам доказал, что не существует более короткой записи такой аксиомы, чем найденная им. Доказательство приведено в его книге «A New Kind of Science» и занимает две страницы. Таким образом, аксиома Вольфрама является простейшей (по количеству операций и переменных) аксиомой с одним уравнением, необходимой для воспроизведения булевой алгебры. Тождества Шеффера были независимо получены различными способами и опубликованы в техническом меморандуме в июне 2000 года, подтверждая соответствие с результатом Вольфрама, который нашёл аксиому в 1999 году при подготовке своей книги. В техническом отчёте также приведена кратчайшая аксиома из пары уравнений, которая эквивалента булевой алгебре. (ru)
dbo:wikiPageID	30159410 (xsd:integer)
dbo:wikiPageLength	6640 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID	1114033543 (xsd:integer)
dbo:wikiPageWikiLink	dbr:Carew_Arthur_Meredith dbr:Propositional_calculus dbr:Sheffer_stroke dbr:Branden_Fitelson dbr:MathWorld dbr:Mathematical_logic dbr:Edward_Vermilye_Huntington dbr:Logical_NAND dbr:Stephen_Wolfram dbc:Propositional_calculus dbr:Automated_theorem_proving dbc:History_of_logic dbr:William_McCune dbr:Alfred_Tarski dbc:Boolean_algebra dbr:Herbert_Robbins dbc:Logic_gates dbr:Larry_Wos dbr:Boolean_algebra dbr:Logical_OR
dbp:wikiPageUsesTemplate	dbt:Reflist dbt:Logical_connectives
dcterms:subject	dbc:Propositional_calculus dbc:History_of_logic dbc:Boolean_algebra dbc:Logic_gates
rdfs:comment	In mathematical logic, minimal axioms for Boolean algebra are assumptions which are equivalent to the axioms of Boolean algebra (or propositional calculus), chosen to be as short as possible. For example, if one chooses to take commutativity for granted, an axiom with six NAND operations and three variables is equivalent to Boolean algebra : where the vertical bar represents the NAND logical operation (also known as the Sheffer stroke). In 1933, Edward Vermilye Huntington identified the axiom The following year, Meredith found a 2-basis in terms of the Sheffer stroke: (en) Аксиома Вольфрама является результатом исследований, осуществлённых Стивеном Вольфрамом при поиске кратчайшей аксиомы из одного уравнения, эквивалентной аксиомам булевой алгебры (или логике высказываний). Результатом его поиска стала аксиома с шестью логическими операциями «НЕ-И» (так же известными как штрих Шеффера) и тремя переменными, которая эквивалентна булевой алгебре: ((a \| b)	c)	(a	((a	c)	a)) = c (ru)
rdfs:label	Minimal axioms for Boolean algebra (en) Аксиома Вольфрама (ru)
owl:sameAs	wikidata:Minimal axioms for Boolean algebra http://hy.dbpedia.org/resource/Վոլֆրամի_աքսիոմ dbpedia-ru:Minimal axioms for Boolean algebra https://global.dbpedia.org/id/3kxBr
prov:wasDerivedFrom	wikipedia-en:Minimal_axioms_for_Boolean_algebra?oldid=1114033543&ns=0
foaf:isPrimaryTopicOf	wikipedia-en:Minimal_axioms_for_Boolean_algebra
is dbo:wikiPageRedirects of	dbr:Wolfram_axiom
is dbo:wikiPageWikiLink of	dbr:Carew_Arthur_Meredith dbr:Sheffer_stroke dbr:Branden_Fitelson dbr:Index_of_logic_articles dbr:One-instruction_set_computer dbr:Robbins_algebra dbr:Edward_Vermilye_Huntington dbr:List_of_Boolean_algebra_topics dbr:Boolean_algebra dbr:Boolean_algebra_(structure) dbr:Wolfram_axiom
is foaf:primaryTopic of	wikipedia-en:Minimal_axioms_for_Boolean_algebra