{"entities":{"Q2366362":{"pageid":2377105,"ns":120,"title":"Item:Q2366362","lastrevid":78751157,"modified":"2026-05-06T12:21:13Z","type":"item","id":"Q2366362","labels":{"en":{"language":"en","value":"Polynomial expansions of Boolean functions with respect to nondegenerate functions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 223734"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366362$11CCDD0A-900F-4BB3-B0E0-D3336D74A39C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2aee0823fc1ef003620c8e17e027762558d1f2e2","datavalue":{"value":{"text":"Polynomial expansions of Boolean functions with respect to nondegenerate functions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2366362$2231CB4C-C1C1-4D53-8875-43FCC9612B3F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5850504bcb52944fa4a73729ae8d923fad3af62b","datavalue":{"value":"0773.06018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366362$6F86BA02-0DB5-4207-8ACC-7314BBFCD462","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"896e95abc4dfdaf8bcab263d8c89bb186779e94b","datavalue":{"value":"10.1007/BF02018736","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366362$BD0E9334-0F1D-4E3B-9FFE-E5B8FBC54F34","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ef3ca3322541db05049091162b21145bd512b130","datavalue":{"value":{"entity-type":"item","numeric-id":251873,"id":"Q251873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366362$834E6F22-8007-4C16-8E2D-3CCCAFAAE072","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be4381b75afe2df0dbe37cd1a66e006418c0c5aa","datavalue":{"value":{"time":"+1993-06-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2366362$39D549F6-37C2-4D88-B74E-5FA487836050","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4356794217e5e676e03c9109214f615b401c58b2","datavalue":{"value":"https://eudml.org/doc/187586","type":"string"},"datatype":"url"},"type":"statement","id":"Q2366362$FDC9A8D4-9789-4188-936A-68C7B164FD8C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0be3c038e8c00c95e1bac30f1b9585ddaac1d350","datavalue":{"value":"The derivative of a Boolean function \\(f(x_ 1,\\dots,x_ n)\\) with respect to variables \\(x_{i_ 1},\\dots,x_{i_ m}\\) \\((m\\leq n)\\) is defined by  \\[ f^{(m)}_{x_{i_ 1}\\cdots x_{i_ m}}(x_ 1,\\dots,x_ n)=\\oplus f(x_ 1,\\dots,\\sigma_{i_ 1},\\dots,\\sigma_{i_ m},\\dots,x_ n), \\]  where the sum on the right hand side is taken over all the binary strings \\((\\sigma_{i_ 1},\\dots,\\sigma_{i_ m})\\). A function \\(g\\) is nondegenerate if \\(f^{(n)}_{x_ 1\\cdots x_ n}(x_ 1,\\dots,x_ n)\\neq 0\\). A Boolean function \\(f(x_ 1,\\dots,x_ n)\\) has a polynomial expansion with respect to function \\(g(x_ 1,\\dots,x_ m,y)\\), \\(m\\leq n\\), if  \\[ f(x_ 1,\\dots,x_ n)=\\oplus g\\bigl(x^{\\tau_ 1}_ 1,\\dots,x^{\\tau_ m}_ m,\\;f^ \\tau(\\sigma_ 1,\\dots,\\sigma_ m,x_{m+1},\\dots,x_ n)\\bigr), \\]  where \\(\\tau=g^{(m)}_{x_ 1\\cdots x_ m}(x_ 1,\\dots,x_ m,1)\\) and the sum is taken over all the binary strings \\((\\sigma_ 1,\\dots,\\sigma_ m)\\), \\((\\tau_ 1,\\dots,\\tau_ m)\\) for which \\(g_ y'(\\sigma^{\\tau_ 1}_ 1,\\dots,\\sigma^{\\tau_ m}_ m,y)=1\\).   It is proved that a function \\(f(x_ 1,\\dots,x_ n)\\) has a polynomial expansion with respect to function \\(g(x_ 1,\\dots,x_ m,y)\\) iff the function \\(g\\) is nondegenerate. A canonical form presentation over the set \\(\\{\\neg,\\land,\\lor,\\to\\}\\) of nondegenerate binary functions follows.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366362$FF47A7C4-C2A2-49DD-98B0-FCDD408CE9D6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"09f3eb9b2932c3fdc120e877804d57f4cb2d94e9","datavalue":{"value":"06E30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366362$AB9EBD7B-D44B-4452-A6D4-D14A994E818A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"674153c9488f8b0f9e97858664bfaf3fbbbac9b1","datavalue":{"value":"03G05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366362$C882ED6A-F9F2-4093-89C6-100B4115BB07","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2f8b8ce761bd1652f383a4db82b6ac60efc33194","datavalue":{"value":"223734","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366362$B089E82C-9130-4B52-BF64-38AA569F7022","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"77a67d3063adaff6308b980f29d6c81435673372","datavalue":{"value":"Boolean expansion","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366362$933BB9F4-19AD-4AA9-B45C-F9B785DB5E47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f5c821f9d02791363226e77baef4eb9bf3b6b41b","datavalue":{"value":"nondegenerate functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366362$4C5C3923-46A5-45C7-9568-D625EAA11E71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"078d3356eff7d5c85080a6208cb433d2b09f6650","datavalue":{"value":"derivative of a Boolean function","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366362$3C28722F-6F62-4F3F-9292-2964042251C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ab3878e608cb00f199f44811faa7a4ec2e47f95e","datavalue":{"value":"polynomial expansion","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366362$F45DCD90-CDD5-41B1-ACF3-3646F27BD432","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8d3582ec6187197901d43d93b8a9fd1bdd2c5a25","datavalue":{"value":{"entity-type":"item","numeric-id":332333,"id":"Q332333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366362$8CF80404-41CA-419E-8581-9FFCE93991AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7db674421ed0db1e1bef5dc27884ca11fa057c40","datavalue":{"value":{"entity-type":"item","numeric-id":832981,"id":"Q832981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366362$713EE86A-0482-41A3-A923-C3FE288B7807","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4e1df29911c330da2d8d89435a35b182dae9e523","datavalue":{"value":{"entity-type":"item","numeric-id":589408,"id":"Q589408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366362$16E6DDF6-B3F1-44AC-8D52-4CA435D118F0","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366362$10A73FDB-6782-47E3-B844-683D2341E7C3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd9b83ece01cc525d214778f22e2c695a59cd967","datavalue":{"value":{"entity-type":"item","numeric-id":1842415,"id":"Q1842415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b76449018dec4443351fce8fe11a051b6dc6432a","datavalue":{"value":{"amount":"+0.96262443","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2366362$BD737259-EC00-4D4A-B25E-B6D8CFD62019","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6baf70d1cbeefe86d60b5dfa2e42e681fb927600","datavalue":{"value":{"entity-type":"item","numeric-id":3351312,"id":"Q3351312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0dc96faeb13ddd7c7d073e766c09a2338dd2bd47","datavalue":{"value":{"amount":"+0.9351789","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2366362$1C0E565F-6CF1-455B-B957-8EA1294E2105","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15f598b44f1dd3521bc742b7f9d6b09c82dabb7f","datavalue":{"value":{"entity-type":"item","numeric-id":5951301,"id":"Q5951301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a1c1c25bff34cff1b6d1462a0ef8a3160e721e1","datavalue":{"value":{"amount":"+0.9334787","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2366362$777526E0-E9C7-42DE-AC39-EDD8B341FEDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c1d8a20fbd1639c9452dec003da234f48b38286","datavalue":{"value":{"entity-type":"item","numeric-id":3727867,"id":"Q3727867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f39f73c3160e161e75100a1275618362e1b4c733","datavalue":{"value":{"amount":"+0.93206435","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2366362$AA656B5C-1891-48B5-BE47-B35363035AB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc06652af0332472454883b6e7495d247577581a","datavalue":{"value":{"entity-type":"item","numeric-id":1326027,"id":"Q1326027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dabac79ac24954239993e6e78af6a3a85e38ef0b","datavalue":{"value":{"amount":"+0.9251521","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2366362$F3C6A9C8-632C-4DAA-BD14-BA61FB59DFF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e23939d994d21ebdacb06ee58572e4752de02be","datavalue":{"value":{"entity-type":"item","numeric-id":4571448,"id":"Q4571448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"deb259ff9979c574d198bc3d9b472e6ea5cdc2b1","datavalue":{"value":{"amount":"+0.9145087","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2366362$3948BD62-405E-461B-9BB5-1AE18F739449","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60b0342b257298c948c73cca86e1b8d6ec6de93a","datavalue":{"value":{"entity-type":"item","numeric-id":4325367,"id":"Q4325367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f099e930179105929a9295ffebb13680dbbae56d","datavalue":{"value":{"amount":"+0.9105174","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2366362$B20C606B-DD1B-4088-A358-877CC8926053","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05a02361d4a75e6d12f4f2c6f296883dab1c5e7f","datavalue":{"value":{"entity-type":"item","numeric-id":677739,"id":"Q677739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0374dba813ce157277f5f0854ea217d3beedf5f","datavalue":{"value":{"amount":"+0.90767395","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2366362$46176B0D-224A-45FB-A4EE-03FDE745FE1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4858b797f73e6deb92ab2fbe30d00284394e78a8","datavalue":{"value":{"entity-type":"item","numeric-id":1346612,"id":"Q1346612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ed6e05112098a7617f90bb3a7793230f02231fb","datavalue":{"value":{"amount":"+0.9073546","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2366362$651CB815-D8C0-4415-AF82-557D29CAA127","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ec397f04e69687559c9458b5d1a75beed6df190","datavalue":{"value":{"entity-type":"item","numeric-id":5435396,"id":"Q5435396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"edf511807b04dc4be8374b7e3e8a056ab2e0f174","datavalue":{"value":{"amount":"+0.9053613","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2366362$4C9F26D8-3913-45D4-A0EF-F59B3AD8D462","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Polynomial expansions of Boolean functions with respect to nondegenerate functions","badges":[]}}}}}