Premium
Tautologies over implication with negative literals
Author(s) -
Fournier Hervé,
Gardy Danièle,
Genitrini Antoine,
Zaionc Marek
Publication year - 2010
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.200810053
Subject(s) - negation , mathematics , premise , simple (philosophy) , binary number , discrete mathematics , combinatorics , arithmetic , computer science , epistemology , philosophy , programming language
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 (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)