5
$\begingroup$

There is a lot of similarity between Propositional logic and Boolean algebraic expressions.

Similar aspects :

1) Both has variables of two states.

2) Operations of Boolean algebra and propositional logic are similar.

3) Simplification of formula expressed in logic can be minimized using Boolean algebra and vice versa.

My doubt is are they both same? If same, why studying differently? I mean why can't Propositional logic can be directly applied to digital logic instead of introducing Boolean algebra again(academically)?

$\endgroup$
  • 1
    $\begingroup$ Considering algebraic structure, both are Boolean algebras. Propositional logic has applications in logic and the two-element Boolean algebra that you mention has application in circuit designing. You can read this for more info : en.wikipedia.org/wiki/Boolean_algebra_(structure) $\endgroup$ – PleaseHelp Aug 18 '15 at 4:42
6
$\begingroup$

They are not the same, but I don't blame you for thinking that they are. The reason why it doesn't seem clear that they are the same is that you've only seen one example of each.

So let's step back, define them separately, and then look at some interesting examples.

Propositional logic is a branch of mathematics that studies propositions, their truth or falsity, and how they combine.

What you probably think of as "propositional logic" is actually just one kind of propositional logic, namely, classical logic. However, this is not the only kind of classical logic, and not the only one that is interesting in computer science.

Some theories are built on top of classical logic. Presburger arithmetic, for example, is the theory of natural numbers with addition. Tarski arithmetic is the theory of real closed fields. First-order logic is the theory of quantified variables over non-logical objects.

You can think of these logic systems as types of propositional logic, with more axioms to deal with the extra stuff. Many constraint-type problems are expressible in this framework; you can look up satisfiability modulo theories for more information on how this is used.

But there are also propositional logics which are not "classical". One example of a non-classical logic is intuitionistic logic. This is a logic which models constructive proofs, which is interesting, because constructive proofs are the same thing as well-behaved computer programs. ("Well-behaved" in this sense means there is no unbounded recursion.) They are also the basis for modern type systems, such as that of Haskell.

Constructive proofs (e.g. pick any proof from Euclid's Elements) are implementable as computer programs. Given some geometric objects as input, you could implement the proof (at least in principle) as a computer program which performs the construction.

You can't do that with non-constructive proofs. Let's look as an example to see what I mean. I'll prove that there are two irrational numbers, $a$ and $b$, such that $a^b$ is rational.

Consider $z = \sqrt{2}^\sqrt{2}$. This number is either rational or irrational.

Case 1: If $z$ is rational, then set $a = b = \sqrt{2}$, and the theorem is proven.

Case 2: If $z$ is irrational, set $a = z$ and $b = \sqrt{2}$. Then $a^b = 2$ and the theorem is proven.

QED

The reason why this proof isn't constructive is that it relies on the law of the excluded middle; $z$ must be either rational or irrational, but we don't (and, in a sense, can't) actually test which of them is true.

Intuitionistic logic systems tend to give you proof systems which are decidable. This is an extremely important practical concern. If you consider, for example, the Java bytecode verifier, or the type system for a programming language (both of which prove that some program is type-correct), they must terminate with an answer, so they must be based on a decidable proof system. By allowing propositions which are neither provable nor refutable, you avoid Gödel-like incompleteness.

That's just one example, of course. Other non-classical propositional logics include modal logics (which can be used to model situations where you have multiple agents who know different things; think about network protocols), and temporal logics (where the truth or falsity of a proposition may change over time).

The thing that connects all of them is the notion of a "proposition". Propositional logic can be thought of as the study of a family of logic systems, all of which deal with the notion of a mathematical statement which has a "truth"-type judgment.

Boolean algebra, on the other hand, is a purely algebraic system, characterised by a set of axioms. Saying "Boolean algebra" is like saying "group" or "field" in abstract algebra. Classical propositional logic satisfies the axioms, but so do other mathematical structures.

The subsets of a set $S$, for example, form a Boolean algebra; with the "not" operator corresponding to "set complement", "and" corresponding to "set intersection", and "or" corresponding to "set union". You can think of "true" as being $S$ and "false" being the empty set, but these are not the only "truth values" which the system models.

Lattices form Boolean algebras, and some lattices are important in computer science (e.g. Scott domains). Moreover, some important non-classical logic-like systems naturally form Boolean algebras, such as fuzzy logic.

So what I hope you can see is that while the two notions are related (some Boolean algebras model some propositional logics), they are not exactly the same thing. How they differ is part of what makes them interesting.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ The paragraph on "Intuitionistic logic systems tend ..." is wrong to misleading at best. 1) They don't tend to be decidable unless you mean proof check is decidable in which case so do classical systems. Generally intuitionistic systems are equiconsistent with their classical counterparts and you can convert classical statements into equiprovable forms in an intuitionistic logic via something like double negation translation. 2) Type checking being decidable doesn't avoid Godel-like incompleteness. You can apply Godel's proof just fine to any intuitionistic logic (such as Heyting algebra) $\endgroup$ – Jake Apr 29 at 21:06
  • $\begingroup$ So... I wrote this 5 years ago, and I'm honestly not sure what I meant by that. I think what was in my brain at the time was that if you need a decidable system (e.g. you're implementing a bytecode verifier or type checker), you want decidability, and you should use an intuitionistic logic. $\endgroup$ – Pseudonym Apr 30 at 4:50
1
$\begingroup$

You are cheating a bit by saying "Boolean algebraic expression" and "propositional logic expression" instead of "Boolean algebra" and "propositional logic". A Boolean algebra is a model of propositional logic, just like a Heyting algebra is a model of intuitionistic propositional logic. The main reason why some models are not Boolean algebras is that Boolean algebra refers to the structures defined within ZFC set theory (or any other given set theory), but it is possible to construct models which are only "meta" Boolean algebras, i.e. which have all the operations and first order properties of a Boolean algebra, but can't be proved to be isomorphic to a ZFC-defined Boolean algebra. This is actually more important for intuitionistic propositional logic, because people there have a more natural tendency to work outside of ZFC.


I intent to rewrite this answer later, give some references, explain it on a more practical level, explain the relation to the fact that Boolean and Heyting algebras are also partially ordered structures, and maybe also try to engage with the "Boolean algebraic expression" view intended and suggested by the question.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Is it correct to say that if Boolean algebra is a model of a logic then this logic is a propositional logic? When you say meta Boolean algebra, you mean abstract? You seem to put a stress on intuitionistic propositional logic: does it suggests there are intuitionistic logic which are not propositional? (ex. order higher than one) $\endgroup$ – Hibou57 Apr 29 at 20:17
  • 1
    $\begingroup$ @Hibou57 I don't mean abstract when I say meta. (However, often those meta models are very hypothetical and even worse than abstract. But not always, sometimes they are just: I really mean this (even if vague), and not its translation into ZFC.) By "meta", I just mean outside of ZFC set theory. For example, if you have a model of ZFC+some large cardinal axiom, then that model certainly cannot be defined within ZFC. But it can still be a "meta" model of a first order theory. ("meta", because the definition of being a model might also include the requirement to be defined within ZFC.) $\endgroup$ – Thomas Klimpel Apr 30 at 10:14
1
$\begingroup$

I would say an importante difference is at least: one cannot add an axiom to Boolean algebra, while one can add one or multiple axioms in a propositional logic, although there is not that much one could add, since all consistant and interesting axiom set are already known (modulo their interpretations).

— Edit —

Yesterday I though about two other important ones

Unless I’m wrong, a proposition is not necessarily reducible to True or False, while a Boolean expression, is. This is so, although both evaluates to the same domain, the domain they reduce to is not the same: Boolean for Boolean algebra, proposition (including truth judgment) for proposition calculus. The difference is that a Boolean is just a value in a set of two, while a proposition typically has a meaning attached to it, and this meaning would just vanish if it was reduced to True or False (it can still proved to be tautological). Evaluation and reduction are not the same. Everyone understand evaluation, but reduction is less common, so I would say it is like a rewriting. When one write P, it means P, not True or False (*), although P may be True or False. While when one write True or False or a Boolean expression, it means True or False, because that is the only thing of interest, in Boolean algebra.

(*) One would not be happy if someone was to replace his/her P by a Boolean, unless he/she is doing Boolean calculus in proposition calculus (which is possible too). But one would be very happy to witness that P may be replaced by Q, as exemple, showing P and Q means the same somehow. Anyway, deriving True or False from a proposition, would be useless: what one want, is a new valid proposition.

Also, I know some logic may have non‑logical constant or variable, but I’m unsure this is the case with proposition calculus. I guess yes, but I’m not sure. If it is indeed this way, then this is another difference: there are no non‑Boolean variable or constants in Boolean algebra.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.