How big is BCI fragment of BCK logic

Details How big is BCI fragment of BCK logic How big is BCI fragment of BCK logic

2011-12-03

arxiv.org/abs/1112.0643v1

Computer Science

Logic in Computer Science

Scientific paper

We investigate quantitative properties of BCI and BCK logics. The first part of the paper compares the number of formulas provable in BCI versus BCK logics. We consider formulas built on implication and a fixed set of $k$ variables. We investigate the proportion between the number of such formulas of a given length $n$ provable in BCI logic against the number of formulas of length $n$ provable in richer BCK logic. We examine an asymptotic behavior of this fraction when length $n$ of formulas tends to infinity. This limit gives a probability measure that randomly chosen BCK formula is also provable in BCI. We prove that this probability tends to zero as the number of variables tends to infinity. The second part of the paper is devoted to the number of lambda terms representing proofs of BCI and BCK logics. We build a proportion between number of such proofs of the same length $n$ and we investigate asymptotic behavior of this proportion when length of proofs tends to infinity. We demonstrate that with probability 0 a randomly chosen BCK proof is also a proof of a BCI formula.

Affiliated with

Also associated with

No associations

Rating

How big is BCI fragment of BCK logic does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with How big is BCI fragment of BCK logic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and How big is BCI fragment of BCK logic will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-697865