About the difference between the propositional logic and the (first order) predicate logic->
- can you give me one or more remarkable examples which underly the differences and the similarities between the two?
[Math] Propositional logic vs predicate logic: examples
examples-counterexamplesfirst-order-logiclogicpredicate-logicpropositional-calculus
Related Solutions
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'll speak about their grammatical differences, leaving their proof- and model-theoretic differences for someone more qualified to discuss. Each of these logics has a vocabulary $V$, which is the set of symbols out of which its well-formed formulas (e.g. terms, sentences) are generated. One usually singles out a subset of $V$ as the set of logical vocabulary $V_L$. It is these $V_L$s that distinguish logics at the ground level, making it very transparent which is an extension of which. Let's see:
$V_L$(PL) = { '$\lnot$' , '$\land$' }
$V_L$(FOL) = $V_L$(PL) $\cup$ { '=' , ' $\forall_1$ ' } where $\forall_1$ quantifies over individuals
$V_L$(SOL) = $V_L$(FOL) $\cup$ { ' $\forall_2$' } where $\forall_2$ quantifies over properties (of individuals)
$V_L$(HOL) = $V_L$(FOL) $\cup$ { ' $\forall_n$' } where $\forall_n$ quantifies over yet higher-order properties
$V_L$(TT) = $V_L$(_OL) $\cup$ { ' $\lambda$' } where _OL is a _-order logic (usually _ > 0)
Of course, each of these systems could be defined in different ways, choosing different sets of logical vocabulary. This is just one way of going about it. Now, as you already said, each of these logics extends the ones coming before it. With this vocabulary talk we can give precise meaning to that:
Def. Logic A is an extension of logic B iff $V_L$(B) $\subset$ $V_L$(A).
In the event that the converse doesn't hold, A is said to be a proper extension of B.
Lastly, for specific examples of differences, consider these formulas:
PL: '$\phi \lor \lnot \phi$'
FOL: '$\forall x (x = x)$'
SOL: '$(a = b) \equiv \forall P (P(a) \leftrightarrow P(b))$'
TT: $\forall x ([\lambda x. x](x) = x)$
Each of these sentences is also valid for logics following it (the other direction doesn't hold, of course). Notice that higher-order logic is left out, because there is no sentence $\phi$ s.t. HOL $\models \phi$ but SOL $\not\models \phi$, due to the fact that the power-set operation is SOL-expressible (Hintikka 1995).
For corrections/suggestions, please leave a comment or simply edit this post.
Best Answer
The obvious difference is that predicate logic allows for quantifiers. E.g.