We generalize the ordinary concept of a multiple-valued matrix by introducing non-deterministic matrices (Nmatrices), in which non-deterministic computations of truth-values are allowed. It is shown that some important logics for reasoning under uncertainty (in particular: many paraconsistent logics) can be characterized by finite Nmatrices, although they have only infinite characteristic ordinary (deterministic) matrices. It is further shown that there is no $n$ such that the use of finite Nmatrices for characterizing logics can be reduced to those with less than $n$ truth-values. A generalized compactness theorem that applies to all finite Nmatrices is then proved. Finally, a strong connection is established between the admissibility of the cut rule in canonical Gentzen-type propositional systems, non-triviality of such systems, and the existence of sound and complete non-deterministic two-valued semantics for them. This connection is used for providing a complete solution for the old Tonk problem of Prior.