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.

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..)

share|improve this question
    
Propositional calculus is just a stepping stone to first-order logic (i.e. predicate calculus). It's not interesting by itself. –  Yuval Filmus Jun 2 '12 at 19:02
    
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. –  Jernej Jun 3 '12 at 9:39
add comment

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
A propositional theory can be seen as a presentation for a boolean algebra, or a Heyting algebra in the case of intuitionistic logic. –  Zhen Lin Jun 2 '12 at 19:49
    
Thanks for the clarification Henning. Is there a way to still show some theories with dummy models ? (Like sets of even numbers etc..) ? –  Jernej Jun 3 '12 at 11:19
    
@Azoo: I have extended the answer. –  Henning Makholm Jun 3 '12 at 13:48
    
Thank you very much for your help. –  Jernej Jun 3 '12 at 14:33
add comment

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.