2
$\begingroup$

The connective $∧$ (conjunction) in propositional logic is essentially the same as ∩ (intersection) in set theory if one thinks of 'false' as 'not a member' and 'true' as 'a member'. De Morgan's laws, commutative laws, idempotent laws, etc apply in three of them. Truth tables exist in both propositional logic and Boolean algebra--membership tables exist in set theory. Why?

Is it because the variables in these systems are binary (true-false, in the set-not in the set, $0$-$1$)and the relationship between variables that have only two possible values given the defined operators is the same regardless of what the two choices are?

If I prove something about an expression in propositional logic, is it valid to conclude that the same holds for its corresponding Boolean expression? Is Karnaugh map valid for simplifying logical expressions too?

Do these systems share axioms?

$\endgroup$

1 Answer 1

4
$\begingroup$

The answer is a resounding "yes" ! They're all shadows of the same thing, which is that "they're all" boolean algebras.

To make it clearer : if you have a set $X$, then the powerset $\mathcal{P}(X)$ (set of all subsets) is a boolean algebra with $\land$ given by $\cap, \lor$ given by $\cup$, $\neg$ given by $(-)^c$ (complement in $X$). Then you can check the most basic rules, or axioms of boolean algebras. This you "have to do by hand" in a sense, but it's pretty much trivial. Once you have done this, any formula you can prove from the axioms of boolean algebras holds for subsets of a set $X$, that is, for the membership relation.

Similarly, if you have a set $V$ of propositional variables and look at the set $\mathrm{Frm}$ of propositional formulas based on these variables, then it's not quite a boolean algebra, but it's almost one. Indeed, if you quotient it by the relation $\varphi\sim\psi \iff \varphi$ is equivalent to $\psi$, then all the operations $\land, \lor,\neg$ pass to the quotient, and then you do get a boolean algebra. Again, you only have to check the axioms.

How you do that will depend on what you mean by equivalent (syntactically equivalent, i.e. there is a formal proof of $\vdash \varphi \leftrightarrow \psi$; or semantically equivalent, i.e. any interpretation of $V$ gives the same result for $\varphi$ and $\psi$ - it turns out that these two meanings of "equivalent" are equivalent [no pun intended], but it's a theorem, and if you don't know it, then depending on your definition the proofs will look different), but it will work no matter what. Therefore again, any formula you can prove from the axioms of boolean algebras will necessarily hold (up to equivalence) for formulas.

These two results are called "soundness".

However your question actually goes in the reverse direction and asks "if I can prove something in propositional logic, does it then hold for boolean expressions ?"; I interpret boolean expressions to mean "does it then hold for all boolean algebras ?" (it turns out that this is the same as asking that there is a syntactical proof of it). Now this question is somehow the "converse" of soundness : you're asking for completeness. But lucky you, it turns out that these semantics are complete !

What does this mean ? Well again there are two things at hand here, so two theorems :

If a law of the form $p=q$ expressible only with $\cap, \cup,(-)^c$ holds for all powersets $\mathcal{P}(X)$, then when you translate it with $\land \leftrightarrow \cap, \lor \leftrightarrow \cup, \neg\leftrightarrow (-)^c$, it holds for all boolean algebras and therefore holds for "boolean expressions".

If you can prove that two propositional formulas $\varphi$ and $\psi$ are equivalent, then their obvious translation in boolean expressions can be proved to be equal using the boolean axioms (which is the same as to say it holds for all boolean algebras)

There is even better (or worse, depending on your point of view) : if you have two boolean expressions $p(x_1,...,x_n), q(x_1,...x_n)$, then they can be proved equal from the boolean algebra axioms if and only if for all assignments $x_i\mapsto 0$ or $1$, they give the same result : this is the result that justifies the use of truth tables, because to check that two expressions are the same it suffices to check it against every assignment to $0,1$.

I'll go a bit further and note that this all depends crucially on using classical logic and so specifically the law of excluded middle, that states that $x\lor \neg x$ always holds. If you remove that law, you enter the realm of intuitionistic logic, and a lot of what I just said breaks down : you can salvage some parts by changing some stuff, but you completely lose the ability to use truth tables for instance.

$\endgroup$

You must log in to answer this question.

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