Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Propositional logic is able to represent the phrase "If every individual prefer any alternative x to alternative y..."? Namely, is the propositional logic able to manage the concept of "preference"?

share|cite|improve this question
For starters, propositional logic does not allow variables $x, y.$ As stated, it appears to me that preference of $x$ over $y$ is a predicate $P(x,y),$ not a proposition. Edit: second reading; not sure about my comment though. – user2468 Mar 17 '12 at 23:25
Sure: you just need a couple of unary predicate symbols $I$ and $A$ and a three-place predicate symbol $P$ and axioms describing how it works. The idea is that $I(x)$ and $A(x)$ are to formalize x is an individual and x is an alternative, and $P(x,y,z)$ is to formalize x prefers y to z. – Brian M. Scott Mar 17 '12 at 23:34
@Brian: Right. But it ought to be pointed out that this is not propositional logic anymore but predicate calculus (aka first-order logic). – Henning Makholm Mar 17 '12 at 23:52
@Henning: Absolutely. Somehow I managed to read it as predicate logic. (Probably because that’s what I was expecting in this context.) – Brian M. Scott Mar 18 '12 at 0:16
If I parse your statement every individual prefer any alternative x to alternative y... correctly, then you need predicate logic for expressing it. For example, I think the translation would be: $$\forall i,x,y . ( {\rm individual}(i) \land {\rm alternative}(x) \land {\rm alternative}(y) \implies {\rm prefer}(i, x,y)).$$ – user2468 Mar 18 '12 at 2:23
up vote 0 down vote accepted

Short answer:

No, propositional logic cannot meaningfully represent preference as a relationship that people have to other things. Yes, propositional logic can represent and probably "manage" the partial sentence in the question, depending on what precisely "manage" means; it just treats the first clause as an atomic proposition.

Long answer:

In case anyone is unclear, a language for propositional or sentential logic (PL) has only two types of symbols:

(i) propositonal constants. These denote expressions that can be assigned a truth-value. So a sentence that makes a claim, e.g., "Sue prefers Dave over Fred" would count, but none of the following would: "Does Sue prefer Dave over Fred?", "Shut the door", "Sue". Letters a, b, ..., p, q, ... are usually used to denote these symbols.

(ii) logical operators. These are the symbols that combine with propositions to form more complex propositions. They include negation, implication, conjunction, disjunction, and other less common ones. They appear in "Sue does not prefer Dave over Fred" and "If Sue prefers Dave over Fred, then Dave likes math and Fred doesn't like math", which might be denoted respectively ~p and q --> (r & ~s).

A language for first-order or predicate logic (FOL) keeps the logical operators but replaces the propositional constants with four other types of symbols: variables, function symbols, relation symbols, and quantifiers. This gives a much more powerful language.

As others pointed out in the comments, there are ways to capture at least some aspects of the concept of preference using FOL. With a first-order language, you can talk about individuals (whatever you want them to be), functions on individuals, relations on individuals, relationships among truth-values of formulas, and some quantificational relationships among relations on individuals. If you take preference to be a relation among certain kinds of individuals, you can use unary and ternary relation symbols to capture this. E.g., use, quoting Brian M. Scott's comment, 'a couple of unary predicate [or relation] symbols I and A and a three-place predicate symbol P and axioms describing how it works. The idea is that I(x) and A(x) are to formalize "x is an individual" and "x is an alternative", and P(x,y,z) is to formalize "x prefers y to z".'

But note that this might not capture everything that you want to capture about preference. For example, you might not be able to say everything about how "prefers" relates to other predicates, such as "favors", "hates", "is preferred over", or "thinks". FOL has limitations on the concepts that it can express. For example, you cannot express Dedekind completeness as a relation on sets of individuals in FOL because you can't quantify over sets of individuals. For an example in a different vein, the Lowenheim-Skolem theorem tells you that you cannot capture the concept of a countably infinite set in FOL (because a first-order theory can't distinguish between infinite cardinalities). Whether preference involves anything that FOL can't express or capture doesn't seem obvious or trivial. You can say things in natural language that are not expressible in FOL, and you can possibly think things that aren't expressible in natural language, so you aren't guaranteed success in either endeavor.

If you wanted to capture something about preference using PL, you would have to do this with the logical operators since they are the only thing that you can use to systematically affect the truth-values of propositions. The only thing that you can talk about with PL is relationships among truth-values of propositions. The sentence "Everyone prefers logic over calculus" makes a claim but doesn't (appear to) have any logical operators in it, so it would have to be represented with just a propositional constant, say, p. You couldn't even capture the relationship of p and "No one prefers calculus over logic" = q because both are just propositional constants. You could take as an axiom p <--> q, i.e., that p and q are equivalent, but this proposition wouldn't be provable from other facts like it would (or could) be in FOL. The problem is that, in PL, you can't look inside of your atomic propositions (the propositional constants) to reason about their parts. PL is only about how the truth-value of a complex proposition depends on the truth-values of its constituent propositions.

Cheers, Rachel

Edit: To answer the followup questions:

Yes, the logical operators for FOL are defined exactly as they are in PL. For example, in both logics, if p and q are propositions, or formulas (FOL calls propositions "formulas" or "well-formed formulas"), then p & q is a formula and is true when both p and q are true and is false otherwise. The difference is what the formulas themselves can look like. So if an inference was valid (or truth-preserving) in PL, it will still be valid in FOL because it works exactly the same way. Resolution is such a rule. PL is contained in FOL, but FOL can make valid inferences (and hence has rules) that weren't possible in PL.

I am not sure what you mean by the tableaux method being an inference rule. To me, this is a whole set of rules for constructing trees. It uses the idea that if a set of formulas S implies a formula p, then the set $S \cup \neg p$ is inconsistent, and you can derive a contradiction (and anything else) from it. On this subject, while PL is decidable (so the tableaux method can always terminate), FOL is not decidable in general (only some restricted fragments of it are). This means that there isn't a method (like tableaux) for FOL that can always tell you, by following some predetermined rules, whether or not some formula is provable from others. A system might allow every theorem to be proved, but there can't be a procedure for actually finding or constructing the proof. If you want to look up more on this, it was Hilbert's Entscheidungsproblem, and Church and Turing proved it impossible independently in 1936.

share|cite|improve this answer
Thank you. One last question: are Resolution and Tableaux method rule of inference for Predicate Logic? Namely, all the rules of inference of PL, are still rules of inference for FOL? – Mark Mar 18 '12 at 22:21
@Mark, the answer was a bit long for a comment, so I'm editing it into the answer. – Rachel Mar 19 '12 at 0:48
Thanks again! It is now clearer. – Mark Mar 19 '12 at 6:41

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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