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?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.
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:
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:
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):
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.
Added to the already proposed answers, another track may be recursion. Looking at this:
Would one say this is
Seen as a proposition, this can be reduced to
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.
Proposition is statement that is having truth value(either true or false) associated with it. Where as predicate is statement whose truth value is depend upon the variables. Example: P(n)- n is an odd integer. Where domain is set of all integers. Here, P(n) is depend upon n.
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.