{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:22:05Z","timestamp":1760440925276},"reference-count":20,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2010,7,12]],"date-time":"2010-07-12T00:00:00Z","timestamp":1278892800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"name":"PHC Polonium project \u201cMikolaj\u201d"},{"name":"ANR project \u201cSADA\u201d"},{"name":"Polish Ministry of Science and Higher Education","award":["NN206 376137"],"award-info":[{"award-number":["NN206 376137"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[2010,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider logical expressions built on the single binary connector of implication and a finite number of literals (Boolean variables and their negations). We prove that asymptotically, when the number of variables becomes large, all tautologies have the following simple structure: either a premise equal to the goal, or two premises which are opposite literals (\u00a9 2010 WILEY\u2010VCH Verlag GmbH &amp; Co. KGaA, Weinheim)<\/jats:p>","DOI":"10.1002\/malq.200810053","type":"journal-article","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T18:27:36Z","timestamp":1279045656000},"page":"388-396","source":"Crossref","is-referenced-by-count":4,"title":["Tautologies over implication with negative literals"],"prefix":"10.1002","volume":"56","author":[{"given":"Herv\u00e9","family":"Fournier","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dani\u00e8le","family":"Gardy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antoine","family":"Genitrini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marek","family":"Zaionc","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2010,7,12]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548304006273"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/0403019"},{"key":"e_1_2_1_4_2","doi-asserted-by":"crossref","unstructured":"P.Flajolet andR.Sedgewick Analytic Combinatorics (Cambridge University Press 2009).","DOI":"10.1017\/CBO9780511801655"},{"key":"e_1_2_1_5_2","doi-asserted-by":"crossref","unstructured":"H.Fournier D.Gardy A.Genitrini andM.Zaionc Classical and intuitionistic logic are asymptotically identical. In: Proc. Internat. Conf. on Computer Science Logic (CSL) LNCS Vol. 4646 pp. 177\u2013193 (Springer 2007).","DOI":"10.1007\/978-3-540-74915-8_16"},{"key":"e_1_2_1_6_2","doi-asserted-by":"crossref","unstructured":"D.Gardy Random Boolean expressions. Colloquium on Computational Logic and Applications Chamb\u00e9ry (France) June 2005. Proceedings in: Discrete Mathematics and Theoretical Computer Science AF pp. 1\u201336 (2006).","DOI":"10.46298\/dmtcs.3475"},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","unstructured":"D.Gardy andA.Woods And\/Or tree probabilities of Boolean function. First Colloquium on the Analysis of Algorithms Barcelona 2005. Proceedings in: Discrete Mathematics and Theoretical Computer Science AD pp. 139\u2013146 (2005).","DOI":"10.46298\/dmtcs.3355"},{"key":"e_1_2_1_8_2","doi-asserted-by":"crossref","unstructured":"A.Genitrini andJ.Kozik Quantitative comparison of Intuitionistic and Classical logics \u2013 full propositional system. In: International Symposium on Logical Foundations of Computer Science Florida (USA) Jan. 2009. Proceedings LNCS Vol. 5407 pp. 280\u2013294 (2009).","DOI":"10.1007\/978-3-540-92687-0_19"},{"key":"e_1_2_1_9_2","doi-asserted-by":"crossref","unstructured":"A.Genitrini J.Kozik andG.Matecki On the density and the structure of the Peirce\u2010like formulae. In: Proc. Fifth Colloquium on Mathematics and Computer Science Blaubeuren Germany September 2008. DMTCS Proceedings.","DOI":"10.46298\/dmtcs.3584"},{"key":"e_1_2_1_10_2","doi-asserted-by":"crossref","unstructured":"A.Genitrini J.Kozik andM.Zaionc Intuitionistic vs classical tautologies quantitative comparison. In: Proc. TYPES 2007 LNCS Vol. 4941 pp. 100\u2013109 (Springer 2008).","DOI":"10.1007\/978-3-540-68103-8_7"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1023\/B:STUD.0000032101.88511.93"},{"key":"e_1_2_1_12_2","doi-asserted-by":"crossref","unstructured":"J.Kozik Subcritical pattern languages for And\/Or trees. In: Proc. Fifth Colloquium on Mathematics and Computer Science Blaubeuren Germany September 2008. DMTCS Proceedings.","DOI":"10.46298\/dmtcs.3582"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199705)10:3<337::AID-RSA4>3.0.CO;2-X"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2005.06.022"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129599002959"},{"key":"e_1_2_1_16_2","doi-asserted-by":"crossref","unstructured":"M.S\u00f8rensen andP.Urzyczyn Lectures on the Curry\u2010Howard Isomorphism. Studies in Logic and the Foundations of Mathematics Volume 149 (Elsevier Science 2006).","DOI":"10.1016\/S0049-237X(06)80005-4"},{"key":"e_1_2_1_17_2","unstructured":"R.Statman On the Existence of Closed Terms in the Typed Lambda Calculus I. In: To H. B. Curry: essays on combinatory logic lambda calculus and formalism pp. 511\u2013534 (Academic Press 1980)."},{"key":"e_1_2_1_18_2","unstructured":"H.Wilf Generatingfunctionology. Second ed. (Academic Press 1994)."},{"key":"e_1_2_1_19_2","first-page":"523","article-title":"On the probability of absolute truth for And\/Or formulas","volume":"12","author":"Woods A.","year":"2006","journal-title":"Bulletin Symbolic Logic"},{"key":"e_1_2_1_20_2","first-page":"67","article-title":"On the asymptotic density of tautologies in logic of implication and negation","volume":"39","author":"Zaionc M.","year":"2005","journal-title":"Reports Math. Logic"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.01.002"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.200810053","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.200810053","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.200810053","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,16]],"date-time":"2023-10-16T06:27:27Z","timestamp":1697437647000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.200810053"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,7,12]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,8]]}},"alternative-id":["10.1002\/malq.200810053"],"URL":"https:\/\/doi.org\/10.1002\/malq.200810053","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"value":"0942-5616","type":"print"},{"value":"1521-3870","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,7,12]]}}}