3
$\begingroup$

Define a theory of propositional calculus as the set $T$ of axioms (expressed in propositional calculus) and a set of valid symbols.

What I would like to see are some examples of theories in propositional calculus and the respective models - what are they?

Are there any "real life" examples of theories in propositional calculus? (Not just the classical lets model the statement "today is raining" type theories..)

$\endgroup$
2
  • $\begingroup$ Propositional calculus is just a stepping stone to first-order logic (i.e. predicate calculus). It's not interesting by itself. $\endgroup$ Jun 2, 2012 at 19:02
  • 1
    $\begingroup$ I see. I am asking more or less because we covered in the classes theorems of soundness and completeness of propositional calculus. It is somehow hard to follow what we are doing there without being able to think of some models and what exactly is going on. $\endgroup$
    – Jernej
    Jun 3, 2012 at 9:39

1 Answer 1

5
$\begingroup$

A model of propositional calculus is the same as a Boolean algebra. They have a variety of applications, though mostly related to logic itself.

There's not much for the concept of "theory" to do in propositional calculus, because the only elements of the language that axioms could help giving meaning to are the proposition letters themselves. I suppose there are problem types in lattice and order theory that might in principle be formulated as "propositional theories", but usually it is more convenient to handle them using algebraic or graph-theoretic tools instead.

Later correction, after I got my brain into gear: Finitely axiomatized propositional theories are of paramount importance in computer science, specifically complexity theory. The problem of determining whether a given theory is consistent is known better as the SAT problem, and is the fundamental example of a NP-complete problem. (This is equivalent to determining whether a given formula can be proved from a finite set of axioms, which is the case if and only if the axioms plus the negation of the goal constitute an inconsistent theory).

As a simpler example, you could consider graph reachability -- that is, the problem given a directed graph and distinguished vertices $A$ and $B$ to find out whether there is a path from $A$ to $B$. To phrase this as a propositional theory, choose a proposition letter $\hat V$ for each vertex $V$, whose intuitive meaning is to be "$V$ is reachable from $A$". Now take as axioms the formula $\hat A$ plus $\hat P\to\hat Q$ for each edge $P\to Q$. Then $B$ is reachable exactly when $\hat B$ is a theorem.

On the other hand, this latter example is arguably too simple to really utilize the machinery of propositional logic. It is better suited as an example of a simple generic formal system, where we model the edges as rules of inference rather than axioms.

$\endgroup$
3
  • 1
    $\begingroup$ A propositional theory can be seen as a presentation for a boolean algebra, or a Heyting algebra in the case of intuitionistic logic. $\endgroup$
    – Zhen Lin
    Jun 2, 2012 at 19:49
  • $\begingroup$ Thanks for the clarification Henning. Is there a way to still show some theories with dummy models ? (Like sets of even numbers etc..) ? $\endgroup$
    – Jernej
    Jun 3, 2012 at 11:19
  • $\begingroup$ @Azoo: I have extended the answer. $\endgroup$ Jun 3, 2012 at 13:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .