# What's the difference between predicate and propositional logic?

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?

Propositional logic (also called sentential logic) is logic that 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 refer 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 of 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.

• 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. Commented Oct 15, 2013 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? Commented Dec 12, 2013 at 3:46
• @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. Commented Dec 12, 2013 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”. Commented Jul 27, 2014 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]

Note: As Doug Spoonwood commented, there are formalizations of both propositional logic and predicate logic that dispense with axioms per se and rely entirely on rules of inference. A common presentation would invoke only modus ponens as the single rule of inference and multiple axiom schemas. The important point for a formal logic is that it should be possible to recognize (with finite steps) whether a claim in a proof is logically justified, either as an instance of axiom schemas or by a rule of inference from previously established claims.

• Non-axiomatic systems of propositional logic, such as natural deduction type systems, exist. Commented Jun 24, 2011 at 15:38
• if predicate logic is an extension and more flexible than propositional logic, then why do we use the latter? Commented Jun 13, 2018 at 7:42
• @Ooker: Since predicate logic extends propositional logic, we "use the latter" whenever we use the former. It often happens that properties of the propositional logic are inherited by its extensions, so studying propositional logic is worthwhile, and worth noticing when it suffices for an application without further extension. If I can offer an analogy, complex numbers are an extension of the natural numbers, so when the latter are sufficient for our purpose (e.g. making a restaurant reservation), it is useful to stick to simpler numbers (just as propositional logic is a simpler system). Commented Jun 13, 2018 at 11:36

A proposition is a statement that is having a truth value(either true or false) associated with it. Where a predicate is a statement whose truth value is dependent upon the variables. Example: $$P(n) : n$$ is an odd integer. Where a domain is a set of all integers. Here, $$P(n)$$ is dependent upon $$n$$.
Example $$3+3= 6$$ is a proposition.

• the only answer with a simple examle, thanks. Commented Sep 10, 2015 at 9:42

I think this example from "Overview of proposition and predicate logic " by Jan Kuper gives a suitable explanation. In proposition logic, we can express statements as a whole, and combinations of them. Intuitively, a statement is a sentence in which something is told about some reality, and which can be true or false about that reality. For example, if p is the statement ”Albert is at home”, and q means ”the door is locked”, then q→¬p says: ”if the door is locked, then Albert is not at home”.

In first-order predicate logic, a statement has a specific inner structure, consisting of terms and predicates. Terms denote objects in some reality, and predicates express properties of, or relations between those objects. For example, the same example as before might be expressed as Locked(d) → ¬AtHome(a). Here, Locked and AtHome are predicates, and d and a are terms, all with obvious meanings.

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.

• For $P$ to be equivalent to $Q\lor P$ means only that $Q$ implies $P$, not that $Q$ is equivalent to $P$. (And this is the case in both propositional and predicate logic.) Commented Aug 12, 2018 at 20:33

I think propositional logic consists of sentences names by sentence letters e.g $(P, Q, R, S)$ with logical connectives for compounds statements, it uses truth assignments to letters to whether it is true or false, with no quantifiers.

While predicate contains symbols, function, objects, relation and quantifiers.

• Welcome to math.SE! The question you're answering to is almost 5 years old, and your answer doesn't really add anything to the discussion (for instance, the accepted answer is far more detailed). If you want to improve this community, you should solve unanswered posts.
– user228113
Commented Jun 29, 2015 at 13:01