Elementary Foundations An Introduction to Topics in Discrete Mathematics (Sylvestre)

Converting language to symbols

As we have already begun to do, we will use letters to represent (possibly variable) logical statements and substatements. To complete the conversion from verbose language to compact symbolism, we will introduce symbols to represent the Five basic connectives.

Using variables to represent statements and the above symbols to represent connectives allows us to isolate the task of analyzing logical structure, without being distracted or influenced by the content of the statements,

Logical Analysis

We will now leave the English language behind and concentrate on logical statements consisting only of variables and connectives.

Given a logical statement, view the variables as inputs and the truth value of the entire statement as an output. We would like a systematic way to determine how the truth value of the output changes as we vary the truth values of the inputs.

If a statement involves a finite number of variables, then since each variable can have one of only two possible truth values, there are a finite number of different combinations of input truth values for the statement. So we can test each combination one after the other to determine all possible outputs. Arrange this analysis in a table with all possibilities for the input variables on the left and the resulting outputs on the right.

Propositional Calculus

Logical equivalence gives us something like an “equals sign” that we can use to perform logical “calculations” and manipulations, similar to algebraic calculations and manipulations. To enable us to do such calculations, we first need a “tool chest” of basic logical equivalences to use therein.

Disjunctive Normal Form

It is often desired (e.g. in computer programming or logic circuit design) to reverse the process: starting with a desired truth table, can we construct a Boolean polynomial with the same outputs?

In the solution to the above worked example, it might seem like we should take a conjunction of the two conjunctions instead of a disjunction, since we see an output of \(1\) in the first row and in the fourth row. However, we cannot be in the input “state” described by those two rows simultaneously, since neither \(x\) nor \(y\) can be both \(1\) and \(0\) simultaneously. So you should think of it this way instead: if we see an output state of \(1\text{,}\) then we know we must be either in the input state of the first row or of the fourth row.