-1
$\begingroup$

Based on the explanations here [1] I know that 3-valued first order logic has many different versions, which differ in the definition of their operations (e.g. implication). All of these (as far as I know) are complete, i.e. any probable statement could be proven. Also these are (just as in the 2-valued case are Semi-decidable, i.e. the correctness of statement given axioms, could be proved, also wrong statements could not be disproved.) Also these are consistent, i.e. they don't contain contradiction.

Suppose I define my arbitrary 3-valued first order logic (by arbitrary, I mean, arbitrary $\Rightarrow$, AND, OR). Is it true that, it is

  • COMPLETE,

  • SEMI-DECIDABLE

  • CONSISTENT

for any $\Rightarrow$, AND, OR operations?

[1] http://en.wikipedia.org/wiki/Three-valued_logic

$\endgroup$

closed as off-topic by Kaveh, R B, David Eppstein, Sasho Nikolov, Tsuyoshi Ito Aug 30 '14 at 23:12

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Kaveh, R B, David Eppstein, Sasho Nikolov, Tsuyoshi Ito
If this question can be reworded to fit the rules in the help center, please edit the question.

6
$\begingroup$

Any logic defined semantically in a similar way is trivially consistent, as it has a model.

Any finite-valued logic has a faithful translation into classical logic, hence its set of valid formulas, or even the consequence relation, are recursively enumerable.

Completeness is a relationship between semantics and a proof system. You only gave the semantics, not any proof system, hence the question is meaningless. There exist complete recursively axiomatized proof systems for your kind of logic, but this is just another way to state that the logic is recursively enumerable.

$\endgroup$
  • $\begingroup$ Thanks Emil for your clarification! Could you say something about the consistency? Is there an example proof of completeness for a similar thing, that you can point me to? $\endgroup$ – Daniel Aug 10 '14 at 22:04
  • 1
    $\begingroup$ For example, complete calculi for several propositional 3-valued logics are presented in cs.tau.ac.il/~aa/articles/3valued_jsl.pdf , and completeness proofs for Hilbert and sequent calculi for a particular first-order 3-valued logic is given in section 6.2.1 of math.cas.cz/~jerabek/papers/phd.pdf . It would help a lot if you learn at least the basic notions of the theory of multi-valued logics, such as in plato.stanford.edu/entries/consequence-algebraic (propositional) or carlesnoguera.cat/files/ch2.pdf (both propositional and first-order). ... $\endgroup$ – Emil Jeřábek Aug 11 '14 at 12:29
  • 1
    $\begingroup$ ... (The theory is geared towards a different class of logics; 3-valued logics are often not algebraizable, e.g. Kleene’s logic. However, basic concepts of consequence relations, logical matrices, and algebraic semantics apply to them just fine.) $\endgroup$ – Emil Jeřábek Aug 11 '14 at 12:32

Not the answer you're looking for? Browse other questions tagged or ask your own question.