Theory and Applications of Two-Valued Nondeterministic Matrices
       ===============================================================

The first part of the talk will be devoted to extending the concept
of a multiple-valued non-deterministic matrix (in which non-deterministic
computations of truth values are allowed) to languages with quantifiers.
We describe the difficulties involved in applying here the two main
classical approaches to the semantics of first-order logic, the objectual
and the substitutional, and solve the difficulties in the case of the latter.
Then  we turn to the particular (but important) two-valued case, and explore
the effects in this context of each of the four standard Gentzen-type rules
for the classical quantifiers. As an example, a sound and complete
two-valued non-deterministic semantics is provided for a family of
first-order proof-systems which results from adding various combinations
of these rules to the simplest paraconsistent logic.

   In the second part of the talk we return to the propositional case,
and discuss the problem of expressiveness of sets of connectives
in the context of propositional two-valued non-deterministic matrices.
Functional completeness is proved for a set consisting of the usual
deterministic implication and a certain non-deterministic negation, and it
is shown that this is the simplest functionally complete set. These
results are proved for a purely extensional notion of expressiveness,
in which probablities of choices are not taken into account. We end the talk
with a discussion of a possible new theory  which combines
two-valued nondeterministic matrices with probability theory.