{"entities":{"Q1123883":{"pageid":1134632,"ns":120,"title":"Item:Q1123883","lastrevid":49298674,"modified":"2026-01-06T22:28:36Z","type":"item","id":"Q1123883","labels":{"en":{"language":"en","value":"Completeness proofs for propositional logic with polynomial-time connectives"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4110666"}},"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":"Q1123883$F64D3130-E8E0-425E-9120-BB1A2DB8D34E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"891a9cebee80ed7a25579e899403f5a23cb294c0","datavalue":{"value":{"text":"Completeness proofs for propositional logic with polynomial-time connectives","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1123883$1F22816D-B3A9-42CF-83C6-B2E6DB169057","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6375fd9f9c56fa33ea57a8b936e680918e040b79","datavalue":{"value":"0678.03004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123883$DA3B0F43-8B9F-4AA4-8F45-8488386A63A6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8f4aab0a0a82fc1dc474eea91507acfcf4a0da4d","datavalue":{"value":"10.1016/0168-0072(89)90044-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123883$44D5BB43-D79E-4335-BD25-96512CB8C9ED","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"33423fd214e41478017ece7904a590cfc211acb0","datavalue":{"value":{"entity-type":"item","numeric-id":752666,"id":"Q752666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123883$BE326F08-7862-4730-9A0F-09485ECA789B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2ab81d74da7d6cf4bb1c0c07253f943d18da01ee","datavalue":{"value":{"entity-type":"item","numeric-id":1123882,"id":"Q1123882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123883$054F3CEA-5CC0-4ACF-B420-2268767C2101","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f91a4bcbc93435aed71775d25a4c5cd09e26f12d","datavalue":{"value":{"entity-type":"item","numeric-id":122505,"id":"Q122505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123883$40DF316D-34D2-4A83-93F4-3D72A5AA2CEC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1123883$9D3554BB-9402-4743-BDEF-626C6A4D2ECF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e65f7926cca899756e75fb37821b8384bb62e22f","datavalue":{"value":"Atomic formulas are of the form P(t), where P are monadic predicate variables (which the authors call propositional variables) and t is a term. Composite formulas are constructed by \\(\\sim\\), \\&, \\(\\vee\\) and bounded quantfiers \\(\\forall x\\leq t\\), \\(\\exists x\\leq t\\), as well as \\(\\forall x\\in T\\), \\(\\exists x\\in T\\) at the end of the paper. When a bounding term is closed, i.e. does not contain individual variables, the corresponding quantifier can be expanded into \\& or \\(\\vee\\), which provides completeness and decidability theorem for closed formulas and obvious rules for \\(\\forall\\), \\(\\exists\\). In the presence of free individuum variables, decidability depends of admitted function symbols. The word ``polynomial'' in the title refers to these functions, not to a decision procedure for derivability.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123883$E68F58BC-584C-42EE-A592-A320D8471319","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"419d6f2b09c39920e34f63114ff159a2f0a01812","datavalue":{"value":"03B05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123883$E996A65A-18C8-4E9D-BA21-D0336DCF49B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"407654cf92f0702e03297e7fe541e25fa3f13c2d","datavalue":{"value":"03B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123883$6858C350-91FF-4F20-9B44-D01A06BABC12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d53cd5ab715340bbfc507bf5b4aac1b907f4465d","datavalue":{"value":"03B70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123883$632545B7-44B5-4CB2-B74B-24DE136FBD51","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b94f5ea649ee540c53783f3441d5ce5b195df354","datavalue":{"value":"4110666","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123883$96E6789D-7DA8-4A36-9B1D-EB6210EC87F1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d60dcf47f8b7196d791ff9c50f05d6b4b561e453","datavalue":{"value":"polynomial-time connectives","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123883$9BCE53CE-546A-46E2-8CFE-1944A79FA716","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"01a1a2ae4a0f0eeddf3884e30e64ddf242d347aa","datavalue":{"value":"extensions of propositional calculus","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123883$CCE8CC92-0CA1-470B-AF1C-5C5DBA44003E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6816fdf79dd11ac09d9af4886c02baab03d2cf9","datavalue":{"value":"completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123883$9E941044-D471-4D04-A664-22ECD61E3C8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48fe5da30f2000a910dd1a06f280ea2b3174328d","datavalue":{"value":"decidability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123883$0FD8D067-28EA-4867-B0E4-F37E31A09C1F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8f432bccb81d11b6d0c5be5373ba82abf19c1967","datavalue":{"value":{"entity-type":"item","numeric-id":454365,"id":"Q454365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123883$1DEE6DDE-DCF5-43CC-83D7-E12C6ED40605","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":"Q1123883$A3E060C6-F3E9-481F-AFC6-76D2FF257440","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0fc53045718a1dc520dda216a358aa8bbf95d1fa","datavalue":{"value":"https://doi.org/10.1016/0168-0072(89)90044-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1123883$A8631032-B641-4403-B27A-C94B7E66A18D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c625abfdfe5c3a422ad49fba1737ccbe45557a19","datavalue":{"value":"W1980622348","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123883$C18BCB91-71A8-44DD-A868-2AE484717DAC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a628cb64400cb3daffe7c8b3b6a4710e9daa6946","datavalue":{"value":{"entity-type":"item","numeric-id":3800030,"id":"Q3800030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123883$CD083122-06A4-4544-9E1B-A467A525F7E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbd46e00e025849b54a0892b5e385ef0d563478f","datavalue":{"value":{"entity-type":"item","numeric-id":1393228,"id":"Q1393228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123883$E4DE1C03-68C3-47F3-9EAF-0D1668F80AE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d986413722b76985e5563365eb3dfdce74a9084b","datavalue":{"value":{"entity-type":"item","numeric-id":4342082,"id":"Q4342082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123883$4401CA6F-2B54-47AE-A74A-0B052F595102","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30ed8c1c9b5cf85c3067f46e271b605235d5e997","datavalue":{"value":{"entity-type":"item","numeric-id":5339741,"id":"Q5339741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123883$A50065C7-CC4A-4BEA-A967-1C658C2E6618","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e17da60b7f6b4e22bbe7045d12697c8bb0702b06","datavalue":{"value":{"entity-type":"item","numeric-id":5604443,"id":"Q5604443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123883$91A1A7D8-C1D3-4D1D-AE7D-CB4AC4E7BEB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3c6d07dd80de4de8f6f1d51aa5d78e790a6fd51","datavalue":{"value":{"entity-type":"item","numeric-id":5812175,"id":"Q5812175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123883$6C60D152-9B80-4682-ABF0-CA62EBD4CD1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4fc0fbba62806d6611fde9901ad3ff3bed111c8f","datavalue":{"value":{"entity-type":"item","numeric-id":5509675,"id":"Q5509675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123883$ACE16138-C344-4196-80A5-C248A3B71F06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e21aa2c8417444bb3098b83ec743e607734c3bfb","datavalue":{"value":{"entity-type":"item","numeric-id":3285631,"id":"Q3285631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123883$66BEF76E-4D7D-49E6-BEC3-B55779EC7B6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"384c88ee747368e498e55b1ebc22017816448ffc","datavalue":{"value":{"entity-type":"item","numeric-id":2265415,"id":"Q2265415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123883$FF64E1F0-B6C5-4EF2-A1EE-AF3F46173C13","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"2f584f572bb16687ede14e0006f906c1505d80ac","datavalue":{"value":"Q126436871","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123883$C9F512BC-54C6-4376-ABD0-F8AC146F3B65","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1145d2f0cc0091b094360215c837a837a528e826","datavalue":{"value":{"entity-type":"item","numeric-id":2277437,"id":"Q2277437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9824dcb4bf73859ab64aec78ee9ebade9af337b5","datavalue":{"value":{"amount":"+0.7469027638435364","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1123883$A280E034-DAE8-423C-8AE2-A98886E06B2F","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":"2c77f9993a3b1ff9caec367adaa3e7f1c07bd67b","datavalue":{"value":{"amount":"+0.7375030517578125","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1123883$9809518F-30C5-40AF-BF99-6F4B40D791CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f312afd6628f63e151df6dcd2b686bd7105c8ae5","datavalue":{"value":{"entity-type":"item","numeric-id":4023306,"id":"Q4023306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"58474fcf0c2ad8a50765733550ba62d24cc6ac9c","datavalue":{"value":{"amount":"+0.7372164726257324","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1123883$4D26C467-FBA8-42E9-A316-83063DC9C009","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c5c9d532a78e12ac8859a04013deff4858a4010","datavalue":{"value":{"entity-type":"item","numeric-id":4467744,"id":"Q4467744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"772693475b7d3568e5a9f7d29562c86841b8f40d","datavalue":{"value":{"amount":"+0.7224443554878235","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1123883$6707D5FB-1A43-4939-802A-95B1218031A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b19d22db4242c1b49e8729ef13785669f30b2b7b","datavalue":{"value":{"entity-type":"item","numeric-id":4699334,"id":"Q4699334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3061e349ec1e465b23cd099200a560fe18bdc1ae","datavalue":{"value":{"amount":"+0.7182980179786682","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1123883$60DA4C63-74B7-4CB7-932B-A27CE94B169D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1123883","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1123883"}}}}}