Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'd heard of propositional logic for years, but until I came across this question, I'd never heard of predicate logic. Moreover, the fact that Introduction to Logic: Predicate Logic and Introduction to Logic: Propositional Logic (both by Howard Pospesel) are distinct books leads me to believe there are significant differences between the two fields. What distinguishes predicate logic from propositional logic?

share|improve this question
2  
-1; the definition of both terms is easily available on Wikipedia. –  Qiaochu Yuan Nov 9 '10 at 12:11
10  
That may be, but I prefer to get my answers from here, where I have greater faith in the community to vote up the correct responses. Am I wrong to prefer this forum to Wikipedia? Is the question off-topic? –  Alex Basson Nov 9 '10 at 23:42
6  
@QiaochuYuan The Wikipedia definitions do not properly highlight the differences between the two; +1 –  therin Nov 27 '12 at 22:14

3 Answers 3

up vote 23 down vote accepted

Propositional logic (also called sentential logic) is the logic the includes sentence letters (A,B,C) and logical connectives, but not quantifiers. The semantics of propositional logic uses truth assignments to the letters to determine whether a compound propositional sentence is true.

Predicate logic is usually used as a synonym for first-order logic, but sometimes it is used to refers to other logics that have similar syntax. Syntactically, first-order logic has the same connectives as propositional logic, but it also has variables for individual objects, quantifiers, symbols for functions, and symbols for relations. The semantics include a domain of discourse for the variables and quantifiers to range over, along with interpretations of the relation and function symbols.

Many undergrad logic books will present both propositional and predicate logic, so if you find one it will have much more info. A couple well-regarded options that focus directly on this sort of thing are Mendelson's book or Enderton's book.

This set of lecture notes by Stephen Simpson is free online and has a nice introduction to the area.

share|improve this answer
1  
I was very surprised to see a suggested edit to remove the sentence at the end of the answer. It required approximately 30 seconds for me to locate the updated location of the lecture notes. I would like to remind others that edits and suggested edits to other user's questions should be made extremely conservatively. –  Carl Mummert Oct 15 '13 at 16:57
    
“… but not quantifiers …”: but Isabelle/HOL (a proof assistant) uses quantifiers in propositions. Is this improper use of the word “proposition” within Isabelle/HOL? –  Hibou57 Dec 12 '13 at 3:46
2  
@Hibou57: this is what the "HOL" indicates in the name. They are using the term "proposition" in a standard way, but of course the logic of Isabelle/HOL is not propositional logic, it is a kind of type theory. Propositional logic, as it is usually understood, does not include quantifiers. –  Carl Mummert Dec 12 '13 at 12:46
    
“Propositional logic […] includes sentence […] and logical connectives, but not quantifiers. […] Predicate logic is usually used as a synonym for first-order logic”: seems confirmed by this PDF paper: “Mathematical Proof and Computer Science”. At “2.4 First‑Order Logic” it says “First‑order logic extends propositional logic with quantifiers”. –  Hibou57 Jul 27 at 21:52

Propositional logic is an axiomatization of Boolean logic. As such predicate logic includes propositional logic. Both systems are known to be consistent, e.g. by exhibiting models in which the axioms are satisfied.

Propositional logic is decidable, for example by the method of truth tables:

[Truth table -- Wikipedia]

and "complete" in that every tautology in the sentential calculus (basically a Boolean expression on variables that represent "sentences", i.e. that are either True or False) can be proven in propositional logic (and conversely).

Predicate logic (also called predicate calculus and first-order logic) is an extension of propositional logic to formulas involving terms and predicates. The full predicate logic is undecidable:

[First-order logic -- Wikipedia]

It is "complete" in the sense that all statements of the predicate calculus which are satisfied in every model can be proven in the "predicate logic" and conversely. This is a famous theorem by Gödel (dissertation,1929):

[Gödel's completeness theorem -- Wikipedia]

regards, hardmath

share|improve this answer
    
Non-axiomatic systems of propositional logic, such as natural deduction type systems, exist. –  Doug Spoonwood Jun 24 '11 at 15:38

Added to the already proposed answers, another track may be recursion. Looking at this:

P = (Q ∨ P)

Would one say this is True where both P and Q are the same or False otherwise, or would one says “don't know” as it presents an infinite recursion?

Seen as a proposition, this can be reduced to P = Q with P and Q given; seen as a predicate (predicate as in Prolog), this will be infinitely recursive.

Note: I came to this topic precisely due to an ambiguous interpretation of the example given above, which made me have the same question as the OP.

share|improve this answer

Your Answer

 
discard

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.