Discrete Mathematics, Rosen, vs Mathematical Analysis of Thought by Boole

discrete mathematicspropositional-calculus

This is only partly a question – when I started with Discrete Math textbook by Ken Rosen, it opened by defining Propositions – examples included The Capital of Canada is Toronto.

When I started reading about conjunctions and disjunctions, I was confused – I did not understand why they existed.

For example, a conjunction is defined as a proposition that is true when both its constituents are true; and false otherwise. A truth table was also given illustrating this.
Given the examples in the textbook, I did not understand if:

the conjunction operation itself resulted in the resultant compound proposition being true or false; or
if the resultant compound proposition's truth table (in reality) resulted in us defining the operation as a conjunction.

The book did not help much in understanding this, since the propositions it gave did not seem to have any relation with each other.

I wanted to understand this better, and I had the Mathematical Analysis of Thought book by George Boole. I read the first chapter this morning, and it arrives at propositions in a very different way.

Boole describes all the reasoning process of a human, as simply classifications of objects into different classes.

So if you have items belonging to a Universe; X and Y are objects of two different types in that Universe; x and y are operations that select objects of type X and Y from this Universe;

then xy is the act of first selecting objects of type Y from the Universe; and then selecting x elements from the result of the first act. We can understand this as an intersection of two sets, X and Y.
x+y is the act of selecting x from the Universe; and then also selecting y from the Universe. This is the union of two sets, X and Y

Thus, for Boole, x and y are classification operations, that are abstract forms of reasoning by the brain.

From this point of view, a Proposition is something like saying object a is of Type A. It is the act of classification. A conjunction or a disjunction seem to be, thus, acts of classification which are a combination of other such acts executed in sequence. In Boole's view, he is modeling the brain's reasoning with this approach.

It appears this approach makes as much sense as starting with "A Proposition is a statement that is true or false", no? Or am I misunderstanding propositions?

Best Answer

I don't quite understand what your question is but I think your confusion is natural. One thing that I think introductions to propositional logic don't really emphasize is that in practice the propositions we care about have free variables and these variables are important for understanding what is going on semantically.

For simplicity, let's consider propositions with a single free variable $x$ whose domain of discourse is the integers $\mathbb{Z}$. An example of such a proposition is $x > 3$; this proposition is true for some integers (e.g. $x = 4$) and false for others (e.g. $x = 2$), and defines a function $\mathbb{Z} \to \{ T, F \}$ from the set of integers to the set of truth values. This function can in turn be identified with the subset of $\mathbb{Z}$ for which it returns the value $T$; in other words, semantically we can identify the "meaning" of a proposition with one free variable with the subset of the domain of discourse on which that proposition is true.

From this point of view,

the conjunction of two propositions takes the intersection of their truth subsets; for example $x > 3 \text{ and } x < 10$ takes the intersection of the set $\{ 4, 5, 6, \dots \}$ with the set $\{ 9, 8, 7, \dots \}$ and produces the set $\{ 4, 5, 6, 7, 8, 9 \}$.
the disjunction of two propositions takes the union of their truth subsets; for example $x = 3 \text { or } x = 10$ takes the union of the set $\{ 3 \}$ and the set $\{ 10 \}$ and produces the set $\{ 3, 10 \}$.

The significance of truth tables from this point of view is that they tell you how to take the conjunction or disjunction of two propositions if you think of them in terms of the functions $\mathbb{Z} \to \{ T, F \}$ they define. So, understanding this point of view requires learning how to switch between three different perspectives on what a proposition is:

A proposition is a statement about an object or objects in the domain of discourse.
A proposition is a (certain kind of) function from the domain of discourse to $\{ T, F \}$.
A proposition is a (certain kind of) subset of the domain of discourse.

Once you get used to propositional logic this sort of switching will become second nature, but it's often poorly explained and can be confusing in the beginning. From here we can generalize to more than one free variable; for example the proposition $x < y$ has two free variables and defines a subset of $\mathbb{Z}^2$, namely the set of pairs of integers $(x, y)$ such that $x < y$.

Related Solutions

[Math] A Proof relating to the Disjunctive normal form

This example is for explanation of what a Disjunctive Normal form is, On purpose i don't simplify the resulting formula, The question is about homework and it should stay homework.

suppose you have the truth table:

P  Q    Value
T  T      T
T  F      T
F  T      F
F  F      T

and you want to transform that into a formula in the Disjunctive Normal form.

First add to the true values the formula that makes that row valid

P Q Value formula
T T T $ (P \land Q )$
T F T $ (P \land \neg Q )$
F T F ------------------ (this value is false so don't mention formula)
F F T $ (\neg P \land \neg Q )$

(sorry had some problems with the layout)

and then or them together

$ (P \land Q ) \lor (P \land \neg Q ) \lor (\neg P \land \neg Q ) $

And this formula is in Disjunctive Normal form.

notice this formula can be simplified but that is out of scope for this answer, see
http://en.wikipedia.org/wiki/Disjunctive_normal_form
and http://en.wikipedia.org/wiki/Karnaugh_map for that.

Good luck

[Math] New to discrete mathematics – Disjunctive normal form

Here is a concrete example:

Suppose we have the following truth-table ($P * Q$ is some arbitrary formula involving atomic propositions $P$ and $Q$):

\begin{array}{cc|c} P & Q & P * Q\\ \hline T & T & T\\ T & F & T\\ F & T & F\\ F & F & T\\ \end{array}

Note that the formula is true in rows 1,2, and 4. In row 1, $P$ and $Q$ are both true, so we generate the corresponding expression $P \land Q$. In row 2, $P$ is true and $Q$ is false, so we generate the term $P \land \neg Q$. Row 4 corresponds to $\neg P \land \neg Q$.

If we now disjunct all these terms together, we get:

$$(P \land Q) \lor (P \land \neg Q) \lor (\neg P \land \neg Q)$$

Now see what happens if we put this expression back on a truth-table:

\begin{array}{cc|c|c|c|c} P & Q & P \land Q & P \land \neg Q & \neg P \land \neg Q & (P \land Q) \lor (P \land \neg Q) \lor (\neg P \land \neg Q)\\ \hline T & T & T & F & F & T\\ T & F & F & T & F & T\\ F & T & F & F & F & F\\ F & F & F & F & T & T\\ \end{array}

Note how each of the disjuncts is true in exactly the one row that it was generated from, and thus how the disjunction is true in exactly those rows where the original expression $P * Q$ is true. Thus, we can describe $P * Q$ with the formula $(P \land Q) \lor (P \land \neg Q) \lor (\neg P \land \neg Q)$. I think you will understand why this process will always work, no matter what the function that needs to be described looks like, and no matter how many atomic propositions are involved.

One last thing: if there is no row where the formula is true, then with this process you would not get any terms. However, this also means that the original formula is a contradiction, and we can always describe a contradiction with $P \land \neg P$ .. which is in DNF.

Best Answer

Related Solutions

[Math] A Proof relating to the Disjunctive normal form

[Math] New to discrete mathematics – Disjunctive normal form

Related Question