Nonmonotonic Logics and Semantics Tarski gave a general semantics for deductive reasoning: a formula a may be deduced from a set A of formulas iff a holds in all models in which each of the elements of A holds. A more liberal semantics has been considered: a formula a may be deduced from a set A of formulas iff a holds in all of the "preferred" models in which all the elements of A hold. Shoham proposed that the notion of "preferred" models be defined by a partial ordering on the models of the underlying language. A more general semantics is described in this paper, based on a set of natural properties of choice functions. This semantics is here shown to be equivalent to a semantics based on comparing the relative "importance" of sets of models, by what amounts to a qualitative probability measure. The consequence operations defined by the equivalent semantics are then characterized by a weakening of Tarski's properties in which the monotonicity requirement is replaced by three weaker conditions. Classical propositional connectives are characterized by natural introduction-elimination rules in a nonmonotonic setting. The society, given a subset of those, the feasible outcomes, must come up with a the subset of those feasible outcomes that are acceptable socially, in view of the individual preferences. Different methods of social decision result in different functions from sets of feasible outcomes to sets of acceptable outcomes. Social Choice investigates the relations between those different methods for social decision and the choice functions they determine. Independently, Y. Shoham, in  [ 37 ] , proposed a general semantics for nonmonotonic reasoning, based on preferences among models. In  [ 28 ] , it is shown that they are exactly the choice functions that satisfy Contraction and 𝐏𝐚𝐭𝐡 ​ 𝐈𝐧𝐝𝐞𝐩𝐞𝐧𝐝𝐞𝐧𝐜𝐞 f ​ ( X ∪ Y ) = f ​ ( f ​ ( X ) ∪ Y ) . 𝐏𝐚𝐭𝐡 𝐈𝐧𝐝𝐞𝐩𝐞𝐧𝐝𝐞𝐧𝐜𝐞 𝑓 𝑋 𝑌 𝑓 𝑓 𝑋 𝑌 {\bf Path\ Independence}\ \ \ f(X\cup Y)=f(f(X)\cup Y). In  [ 2 ] , it is shown that, if ℳ ℳ {\cal M}  is finite, they are exactly the pseudo-rationalizable choice functions, i.e., those that may be defined by a finite set of binary preference relations > i subscript 𝑖 >_{i} on ℳ ℳ {\cal M}   by taking, for f ​ ( X ) 𝑓 𝑋 f(X) , the set of all elements of X 𝑋 X that are minimal in X 𝑋 X for at least one of the > i subscript 𝑖 >_{i} ’s. None of these results will be used in this paper. 5.3 Qualitative Measures A completely different generalization of Tarski’s semantic analysis will be reviewed now. Its origins may be traced to Dubois and Prade  [ 8 ] and Ben-David and Ben-Eliyahu  [ 4 ] . Up to small technical changes, our presentation will be that of Friedman and Halpern  [ 14 , 15 ] . The connection between both approaches is described in  [ 33 ] . Some more results concerning the link between plausibility measures and preferential relations may be found in  [ 10 ] . Suppose we had some way of measuring the size or the importance of sets of models. If X ∪ Y 𝑋 𝑌 X\cup Y is an order of magnitude greater than Y 𝑌 Y , it must be that X 𝑋 X is already greater than Y 𝑌 Y . (6) X ∪ Y > Y ⇒ X > Y 𝑋 𝑌 𝑌 ⇒ 𝑋 𝑌 X\cup Y>Y\>\Rightarrow\>X>Y Note that the definition of 𝒞 𝒞 {\cal C}  in  2 makes use of the relation > > only between sets with an empty intersection. Property  6 can therefore only have an indirect influence. The qualitative plausibility measures of Friedman and Halpern need not satisfy Property  6 . The results presented in Section  5.4 show that one may add this property without harm. Friedman and Halpern consider a property (A2) that implies the finitary version of  7 . The monotonic operation 𝒞 𝒞 {\cal C}   satisfies a ∈ 𝒞 ​ ( A ) 𝑎 𝒞 𝐴 a\in\mbox{${\cal C}$}(A) iff 𝒞 ​ ( A , ¬ a ) = 𝒞 𝐴 𝑎 absent \mbox{${\cal C}$}(A,\neg a)= ℒ ℒ {\cal L} , and therefore we may always remove double negations and is defined (up to removal of double negations) by: 𝒞 ​ ( A ) = A 𝒞 𝐴 𝐴 \mbox{${\cal C}$}(A)=A if A 𝐴 A is finite and does not contain an atomic proposition and its negation, and 𝒞 ​ ( A ) = ℒ 𝒞 𝐴 ℒ \mbox{${\cal C}$}(A)=\mbox{${\cal L}$} otherwise (i.e., if A 𝐴 A is infinite or contains an atomic proposition and its negation). Notice that this 𝒞 𝒞 {\cal C}   fails the Lindenbaum lemma: there are consistent sets but no maximal consistent set. Then, there is a set ℳ ℳ {\cal M} , a satisfaction relation ⊧ models \models that behaves classically for each of the existing connectives and a definability-preserving choice function f 𝑓 f that satisfies Contraction, Coherence and Local Monotonicity that defines 𝒞 𝒞 {\cal C} , i.e., such that 𝒞 ​ ( A ) = f ​ ( A ^ ) ¯ 𝒞 𝐴 ¯ 𝑓 ^ 𝐴 \mbox{${\cal C}$}(A)=\overline{f(\widehat{A})} , for any A ⊆ ℒ 𝐴 ℒ A\subseteq\mbox{${\cal L}$} . Proof: The proof proceeds exactly as the proof of the completeness part of Theorem  4 , except that, for the set ℳ ℳ {\cal M}  we take, not all theories, but only the maximal consistent sets of formulas. The proof proceeds exactly in the same way, as soon as we have proved Lemma  13 to replace Lemma  6 . The fact that the satisfaction relation behaves classically for the connectives follows from Lemma  12 . Lemma 13 For any A ⊆ ℒ 𝐴 ℒ A\subseteq\mbox{${\cal L}$} , A ^ ^ 𝐴 \widehat{A} is the set of all maximal consistent sets that include A 𝐴 A and A ^ ¯ = ¯ ^ 𝐴 absent \overline{\widehat{A}}= ⋂ B ⊆ ℒ 𝒞 ​ ( A , B ) subscript 𝐵 ℒ 𝒞 𝐴 𝐵 \bigcap_{B\subseteq\mbox{${\cal L}$}}\mbox{${\cal C}$}(A,B) . Nonmonotonic reasoning: from finitary relations to infinitary inference operations. Studia Logica , 53(2):161–201, 1994. [14] Nir Friedman and Joseph Y. Halpern. Plausibility measures and default reasoning. In Proceedings National Conference on Artificial Intelligence (AAAAI) , pages 1297–1304, 1996. [15] Nir Friedman and Joseph Y. Halpern. Plausibility measures and default reasoning. Journal of the ACM , 2000. To appear. [16] Dov M. Gabbay. Theoretical foundations for non-monotonic reasoning in expert systems. In Krzysztof R. Apt,