7 found
Order:
  1. First Order Quantifiers in Monadic Second Order Logic.H. Jerome Keisler & Wafik Boulos Lotfallah - 2004 - Journal of Symbolic Logic 69 (1):118-136.
    This paper studies the expressive power that an extra first order quantifier adds to a fragment of monadic second order logic, extending the toolkit of Janin and Marcinkowski [JM01].We introduce an operation existsn on properties S that says "there are n components having S". We use this operation to show that under natural strictness conditions, adding a first order quantifier word u to the beginning of a prefix class V increases the expressive power monotonically in u. As a corollary, if (...)
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark  
  2. Strong Convergence in Finite Model Theory.Wafik Boulos Lotfallah - 2002 - Journal of Symbolic Logic 67 (3):1083-1092.
    In [9] we introduced a new framework for asymptotic probabilities, in which a $\sigma-additive$ measure is defined on the sample space of all sequences $A = $ of finite models, where the universe of An is {1, 2, .., n}. In this framework we investigated the strong 0-1 law for sentences, which states that each sentence either holds in An eventually almost surely or fails in An eventually almost surely. In this paper we define the strong convergence law for formulas, (...)
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark  
  3.  34
    Almost Everywhere Elimination of Probability Quantifiers.H. Jerome Keisler & Wafik Boulos Lotfallah - 2009 - Journal of Symbolic Logic 74 (4):1121 - 1142.
    We obtain an almost everywhere quantifier elimination for (the noncritical fragment of) the logic with probability quantifiers, introduced by the first author in [10]. This logic has quantifiers like $\exists ^{ \ge 3/4} y$ which says that "for at least 3/4 of all y". These results improve upon the 0-1 law for a fragment of this logic obtained by Knyazev [11]. Our improvements are: 1. We deal with the quantifier $\exists ^{ \ge r} y$ , where y is a tuple (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  4.  23
    Minimal Complete Propositional Natural Deduction Systems.Amr Elnashar & Wafik Boulos Lotfallah - 2018 - Journal of Philosophical Logic 47 (5):803-815.
    For each truth-functionally complete set of connectives, we construct a sound and complete natural deduction system containing no axioms and the smallest possible number of inference rules, namely one.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  5.  9
    Shrinking Games and Local Formulas.H. Jerome Keisler & Wafik Boulos Lotfallah - 2004 - Annals of Pure and Applied Logic 128 (1-3):215-225.
    Gaifman's normal form theorem showed that every first-order sentence of quantifier rank n is equivalent to a Boolean combination of “scattered local sentences”, where the local neighborhoods have radius at most 7n−1. This bound was improved by Lifsches and Shelah to 3×4n−1. We use Ehrenfeucht–Fraïssé type games with a “shrinking horizon” to get a spectrum of normal form theorems of the Gaifman type, depending on the rate of shrinking. This spectrum includes the result of Lifsches and Shelah, with a more (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  6.  19
    Completeness and Interpolation of Almost‐Everywhere Quantification Over Finitely Additive Measures.João Rasga, Wafik Boulos Lotfallah & Cristina Sernadas - 2013 - Mathematical Logic Quarterly 59 (4-5):286-302.
  7.  24
    Strong 0-1 Laws in Finite Model Theory.Wafik Boulos Lotfallah - 2000 - Journal of Symbolic Logic 65 (4):1686-1704.
    We introduce a new framework for asymptotic probabilities of sentences, in which we have a σ-additive measure on the sample space of all sequences A = {A n } of finite models, where the universe of A n is {1,2... n}, and use this framework to strengthen 0-1 laws for logics.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark