{"entities":{"Q2277437":{"pageid":2288180,"ns":120,"title":"Item:Q2277437","lastrevid":43807527,"modified":"2025-11-14T16:12:47Z","type":"item","id":"Q2277437","labels":{"en":{"language":"en","value":"Expressive completeness and decidability"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4197946"}},"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":"Q2277437$71CCE223-F069-4950-BC43-018FC5C41321","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"92a03344efe5389ce9eb24539f243776339566e2","datavalue":{"value":{"text":"Expressive completeness and decidability","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2277437$69E5FB91-1C46-4CA3-A058-DB60894472E4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4944b7142ec7b0ecf15168eaa22048e520a2552f","datavalue":{"value":"0726.03002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277437$C9F9ACB2-431B-453A-A691-0E8C44F4BED9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1c9b0ee9a7c9f7f78c90198c3367b9811fdcdd7f","datavalue":{"value":{"entity-type":"item","numeric-id":758988,"id":"Q758988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277437$596C8874-8C08-447B-A650-E8D4DC51D529","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a9d4209135bf481b154ab5d0a5e11f6fc027d3b4","datavalue":{"value":{"entity-type":"item","numeric-id":218490,"id":"Q218490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277437$1029660D-79B2-4503-81F3-BEE9F62DDFC0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6325d9f59cde8ebbdb24a9f950cab3fcef3decf6","datavalue":{"value":{"entity-type":"item","numeric-id":190248,"id":"Q190248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2277437$3E72997A-7656-421B-BE8C-78BAD218590A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2277437$F4373496-F493-475B-8CB9-1B452EF8312B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5dfb426f37fd852f6df3195c1836ba253f3a0a68","datavalue":{"value":"This short paper first addresses the question of under what conditions of a finite set of (2-valued) truth functional connectives, it is decidable whether that set is expressively complete. The authors first prove a theorem, due to Post, setting truth-table conditions on connectives in the set. They also prove a theorem on the degree of formulae generated by these connectives. Finally, after a short discussion on the Turing representation of truth-functional connectives, they show that ``there is no effective procedure that, given a recursive specification of a finite set of connectives, decides whether the set is expressivley complete''.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277437$B7D77450-AA1B-459A-9CD8-B99F69162BF0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"407654cf92f0702e03297e7fe541e25fa3f13c2d","datavalue":{"value":"03B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277437$1D771B44-D8FF-47A6-81B0-DBB73FBA2DC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"419d6f2b09c39920e34f63114ff159a2f0a01812","datavalue":{"value":"03B05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277437$64B6FE1E-2FFE-4379-8AC8-612D5810EF08","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3163b757069bd66e0889562f1fb4b086e4c6b47d","datavalue":{"value":"4197946","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277437$E0C218ED-3F1A-49CA-90C7-5D03C18F4981","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a89e42f8ccb5393b60889241f4c3f97f36a701b","datavalue":{"value":"expressive completeness of sets of two-valued truth functional connections","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277437$7955F113-4465-43CC-94A4-A2B6CEB16949","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4bf5fa9c8e7864518a235e5de9f8363428c7872","datavalue":{"value":"truth-table conditions","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277437$79D23AB1-45CC-4E14-8E98-43B303E45F44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ddadba17697f4d2f0bb3b4125203c2cced7df709","datavalue":{"value":"Turing representation of truth- functional connectives","type":"string"},"datatype":"string"},"type":"statement","id":"Q2277437$4966F921-C453-43A5-839C-7ADCA3B63CE2","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":"Q2277437$7A1206D9-2F87-40F6-A796-6911C032C41E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d2136a6b8b1682159d6f0f07e8658e3c03ba7fc5","datavalue":{"value":"https://doi.org/10.1305/ndjfl/1093635592","type":"string"},"datatype":"url"},"type":"statement","id":"Q2277437$5172AF0E-519D-40E9-99BB-238B1EF72455","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"80f52d285197d887ad2703008579c62de09896ef","datavalue":{"value":"W2080002446","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277437$5CF0DCA0-38FD-46B4-96A0-53D8DD98CFD4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"29bd1be529295f8bbaccb2a586721d794547b916","datavalue":{"value":"10.1305/NDJFL/1093635592","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2277437$00FBDAD4-53C4-478A-8804-2C38C08E967C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"062ce89ec1163db1ba1c778f8e56fc268e119410","datavalue":{"value":{"entity-type":"item","numeric-id":490672,"id":"Q490672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f6d9990f0e16d16cf5adc1008af3980d5f63628","datavalue":{"value":{"amount":"+0.91773254","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2277437$009A6BF4-4F8C-4BF8-B05F-3F41F141E752","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aadc0bb2cb439a769b92bed21fdb682403da5b43","datavalue":{"value":{"entity-type":"item","numeric-id":5480615,"id":"Q5480615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5a36d29e16adbe5c5f18a415c5b9fd73fb64911","datavalue":{"value":{"amount":"+0.91680443","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2277437$33813484-159C-4DBD-8C4B-C71DC689359D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f92aba65c4784b6aabf699bb3317b7439b59d2bb","datavalue":{"value":{"entity-type":"item","numeric-id":3498460,"id":"Q3498460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af73685367d07360b3b826e34149e15c580bce85","datavalue":{"value":{"amount":"+0.9104542","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2277437$A71AE4F8-87D7-4444-A061-8D85C4F72AE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3da6778f0e2be7ef4cce15a8de2f73d0b2989082","datavalue":{"value":{"entity-type":"item","numeric-id":3794168,"id":"Q3794168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5af5c52a00e95efd1bfecc2dfee9f60e19e6b02d","datavalue":{"value":{"amount":"+0.9080509","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2277437$A0EBA8D6-37E4-4020-AA1B-23563C914C2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e24124c6549167154d9b05d6b50277121676fd4e","datavalue":{"value":{"entity-type":"item","numeric-id":4499219,"id":"Q4499219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72dec509e4e79569093574b63e6b3caf186739ac","datavalue":{"value":{"amount":"+0.90182585","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2277437$B1BBABA2-D882-459F-A381-8F1F3C47ADCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6be2716a73939a8ef5f5bd209f6b1fa11bcbaa2","datavalue":{"value":{"entity-type":"item","numeric-id":800082,"id":"Q800082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce1be1fe5898df041a06cf3dfa50bedf92372695","datavalue":{"value":{"amount":"+0.8994545","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2277437$37688991-D90D-4E55-A6AF-06013729516F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f42d6f9aa9aa6da50464fe3f2e4d856cfebbb6f0","datavalue":{"value":{"entity-type":"item","numeric-id":2042736,"id":"Q2042736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"769b0f893106eab7d8b365e11fbf78f43da32629","datavalue":{"value":{"amount":"+0.8968312","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2277437$CCE5E730-1ECF-493D-B1F1-94D21DDDF32E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"30ebb6b573aa0b610753c12bd1fa15c44d50f035","datavalue":{"value":{"entity-type":"item","numeric-id":5864208,"id":"Q5864208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ae495d4f2fb56f151512ec3655581cfae50ad65","datavalue":{"value":{"amount":"+0.89496386","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2277437$9B8720F6-6087-4C5F-84F6-CA04825F678C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be5be94989e95a5b692ec27555420d25bc46d4ca","datavalue":{"value":{"entity-type":"item","numeric-id":2949713,"id":"Q2949713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"969a560934fd7c3f72a396600a0de068890ba93a","datavalue":{"value":{"amount":"+0.8924952","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2277437$8418910A-C155-4724-8172-C1939D0744EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22eed11b0b0c9c9ec9c7b273fbd8edcda3ada453","datavalue":{"value":{"entity-type":"item","numeric-id":4397034,"id":"Q4397034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48ea5042b0139d1589fa6511764c0c35ddf6cc04","datavalue":{"value":{"amount":"+0.89111835","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2277437$201F7828-FDD5-4A1B-BA9F-F38230D3CA72","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2277437","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2277437"}}}}}