Regular Subgraphs in Graphs and Rooted Graphs and Definability in Monadic Second - Order Logic

We investigate the definability in monadic ∑₁¹ and monadic Π₁¹ of the problems REG_k, of whether there is a regular subgraph of degree k in some given graph, and XREG_k, of whether, for a given rooted graph, there is a regular subgraph of degree k in which the root has degree k, and their restrictions to graphs in which every vertex has degree at most k, namely REG_k^k and XREG_k^k, respectively, for k ≥ 2 (all our graphs are undirected). Our motivation partly stems from the fact (which we prove here) that REG_k^k and XREG_k^k are logspace equivalent to CONN and REACH, respectively, for k ≥ 3, where CONN is the problem of whether a given graph is connected and REACH is the problem of whether a given graph has a path joining two given vertices. We use monadic first - order reductions, monadic ∑₁¹ games and a recent technique due to Fagin, Stockmeyer and Vardi to almost completely classify whether these problems are definable in monadic ∑₁¹ and monadic Π₁¹, and we compare the definability of these problems (in monadic ∑₁¹ and monadic Π₁¹ with their computational complexity (which varies from solvable using logspace to NP - complete).     

Karl Menger's contributions to social thought

The work of Karl Menger in social science is briefly surveyed, in particular in the areas of marginal utility and diminishing value, utility, and uncertainty, a logic of imperatives based on deterrence, and a theory of voluntary associations in which cohesive groups are studied combinatorially.     

On the time to first failure in multicomponent exponential reliability systems

Consider an n-component reliability system having the property that at any time each of its components is either up (i.e., working) or down (i.e., being repaired). Each component acts independently and we suppose that each time the i^th component goes up it remains up for an exponentially distributed time having mean μ_i, and each time it goes down it remains down for an exponentially distributed time having mean υ_i. We further suppose that whether or not the system itself is up at any time depends only on which components are up at that time. We are interested in the distribution of the time of first system failure when all components are initially up at time zero. In section 2 we show that this distribution has the NBU (i.e., new better than used) property, and in Section 3 we make use of this and other results to obtain a lower bound to the mean time until first system failure.     

About membership functions estimation

A logical approach to fuzzy sets method originated by Giles is developed. The infinitely many-valued logic t_ω is taken as basic. We accept, it is correct to use the strong conjunction by the logical analysis of the summation of fuzzy items. Under some broad conditions it is proved. that the sum of many fuzzy variables is a variable whose membership function is approximately equal to $\text{?(x) =}\text{max}\text{{1 ?}\text{1}\text{2}\text{c(x ? α)}{}^2\text{, 0}}$, where a and c are some constant parameters. A method of estimation of the unknown parameters is developed in a general case. The proposed fuzzy method coincides with the method of maximum likelihood if used in problems of classical mathematical statistics.     

Completeness theorem for propositional probabilistic models whose measures have only finite ranges

A propositional logic is defined which in addition to propositional language contains a list of probabilistic operators of the form P_s (with the intended meaning the probability is at least s). The axioms and rules syntactically determine that ranges of probabilities in the corresponding models are always finite. The completeness theorem is proved. It is shown that completeness cannot be generalized to arbitrary theories.This research was supported by Ministarstvo za nauku, tehnologije i razvoj Republike Srbije, through Matematiki institut, under grant 1379Mathematics Subject Classification (2000): 03C70, 03B48     

A Modal Logic Based on Linearly Ordered f-Spaces

A modal logic associated with the -spaces introduced by Ershov is examined. We construct a modal calculus that is complete w.r.t. the class of all strictly linearly ordered -frames, and the class of all strictly linearly ordered -frames.     

On the polynomial-space completeness of intuitionistic propositional logic

We present an alternative, purely semantical and relatively simple, proof of the Statman's result that both intuitionistic propositional logic and its implicational fragment are PSPACE-complete.This paper was supported by grant 401/01/0218 of the Grant Agency of the Czech Republic. % Mathematics Subject Classification (2000):     

On the number of -equivalent non-isomorphic models

We prove that if is consistent then is consistent with the following statement: There is for every a model of cardinality which is -equivalent to exactly non-isomorphic models of cardinality . In order to get this result we introduce ladder systems and colourings different from the ``standard' counterparts, and prove the following purely combinatorial result: For each prime number and positive integer it is consistent with that there is a ``good' ladder system having exactly pairwise nonequivalent colourings.

     

电流控阈技术及三值电流型 CMOS施密特电路

本文以开关信号理论为指导 ,对电流型 CM OS电路中如何实现阈值控制进行研究. 建立实现阈 值控制电路的电流传输开关运算 ,并用于指导电流型 CMOS施密特电路的开关级设计 .用 PSPICE程序 模拟证明了所设计的电路具有理想的施密特电路特性.