Proof Search in Hajek's Basic Logic

Details Proof Search in Hajek's Basic Logic Proof Search in Hajek's Basic Logic

2006-05-22

arxiv.org/abs/cs/0605094v1

Computer Science

Logic in Computer Science

26 pages

Scientific paper

We introduce a proof system for Hajek's logic BL based on a relational hypersequents framework. We prove that the rules of our logical calculus, called RHBL, are sound and invertible with respect to any valuation of BL into a suitable algebra, called omega[0,1]. Refining the notion of reduction tree that arises naturally from RHBL, we obtain a decision algorithm for BL provability whose running time upper bound is 2^O(n), where n is the number of connectives of the input formula. Moreover, if a formula is unprovable, we exploit the constructiveness of a polynomial time algorithm for leaves validity for providing a procedure to build countermodels in omega[0,1]. Finally, since the size of the reduction tree branches is O(n^3), we can describe a polynomial time verification algorithm for BL unprovability.

Affiliated with

Also associated with

No associations

Rating

Proof Search in Hajek's Basic 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 Proof Search in Hajek's Basic Logic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Proof Search in Hajek's Basic Logic will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-16082