Note: we will typically use {true,false} as the set of boolean values. However, we will freely switch to {T,F} or to {1,0} and you are going to have to be able to roll with it. So true/T/1 are the "true" values, and false/F/0 are the "false" values.
In algebra, a variable stands for a number. In propositional/boolean logic a variable stands for a true/false value.
Note: We will purposely use both terms!! The world does!
In algebra, the basic operations are +, -, *, /, and - for negation, as in "$-x$". These are functions, though they might not look like it. When we write "$x*y$", it means "$\text{mult}(x,y)$". We write these as operators for historical reasons and because it's more convenient for human manipulation. (Note: there are, in fact, programming languages that explicitly write these arithmetic operators as functions!) In propositional/boolean logic we have as basic operations "not", "and", "or" and some others. They are functions too, but they are what are called boolean functions, i.e. their inputs are boolen values and their output are boolean values:
Since the boolean operators are functions, we can talk about their domains and ranges. Unlike arithmetic operators for the integers or reals, the domains and ranges of the boolean operators are finite, and that allows us to specify these functions completely by tables. You should be used to looking at tables of function values from high school. They typically gave some values of the function, because with integer or real inputs there are infinitely many possible input values. For boolean functions, however, we can list all input values with their associated outputs in a finite table. For boolean functions, we call these truth tables.
| not | and | or | implication | equivalence | exclusive or |
|---|---|---|---|---|---|
There are different notations for these operations. We will use the standard notation (as shown below), but in circumstances where you are entering expressions using only ASCII values, we have another set of notation.
| operator name |
standard notation |
SI242 ASCII notation |
C/C++/Java notation |
|---|---|---|---|
| not | ¬ | ~ | ! |
| and | ∧ | & | && |
| or | ∨ | | | || |
| implies | ⇒ | => | n/a |
| equivalence | ⇔ | <=> | == |
| xor | ⊕ | xor | ^ |
[In Computer Architecture you will have a different notation (+ for "or", an overline bar for "not", and variables/parethisized-expressions sitting next to one another, like we do with multiplication in algebra, for "and"). You'll have to be flexible enough to adapt!]
NavyBeatsArmy => DinnerOnMe.
Suppose Navy loses. To keep your word, do you have to treat
them to dinner? Would you fail to keep your word if you did?
Clearly the answer is no in both cases. If Navy loses, you
keep your word
no matter what you do. In fact, the only way to fail to keep
your word is for Navy to win and you to not treat your friend
to dinner. So the implication is satisfied in all cases,
except when the left hand side is true, and the right hand
side is false.
Important: A truth table is nothing more than a table that lists the values of a boolean function for every possible combination of values for the inputs. The convention in this class will be to list the rows in lexicographic order, i.e. dictionary order. So false comes before true. When there are multiple arguments, you find the left-most position in which two inputs differ to make your decision. This order is particularly nice because, if you use 0 for false and 1 for true, the input values for each row list the binary numbers in increasing order starting from zero.
To find the value of an application of a propositioinal logic operator, you just look it up in the table. So, for example, to determine the value of "false⇔false", I look at the row in the ⇔-table where a and b are both false (first row), and see that the final column has "true", which means the the value of the expression is "true".
ACTIVITY (worksheet)
What is the value of ...
A note on proof
"Proof" is going to be an important topic of this course; one
that runs as a thread through everything we do.
Perhaps the most basic form of proof is what we might call
"Proof by calculation". You've been doing this in algebra for
years already. If someone asks you to prove that 15% of 88.30
is greater than 12.50, you would simply show them the
calculation .15*88.30 = 13.2450 > 12.50. The point is that
this kind of caclulation is so basic, that we all consider it to be
self-explanatory. I could do it myself if I didn't want to
take your word for it. It will be the same for propositional
logic. Each of these calculations like
"false⇔false evaluates to true" is a proof of a result. A
boring proof, but there you go. It's "boring" because it is a
one step proof with the justification always being "because
that's what the table in the definition says".
It's important to recognize what's going on here, though,
because the idea that we always bottom out with "because
that's what the definition says" is important. When we get an
proof down to that level, there is no arguing and no room for
disagreement ... unless you can't agree on what the definition
actually is. In mathematics, this shouldn't happen often. In
life, however, this happens very often.
In propositional logic, there is no such distinction, and no need for the equals sign. A propositional formula like $a \wedge (\neg b \vee c)$ evalutes to a true/false value already, so there is no need for equals signs, and no need to distinguish between expressions and equations!
However, we are going to want to prove things about formulas (and maybe even give algorithms to compute with formulas) and that requires formally defining the term. Our previous definitions (boolean variable, boolean function and propositional logic operators) hopefully just plain made sense. They are very simple definitions. Formulas are more difficult to define, because formulas are made up of formulas, which are in turn made up of formulas, etc. To define this sort of thing we need a recursive definition. We'll state it here, and hopefully it'll make sense.
With this definition, we can prove that, for example, $(a)\wedge((\neg(b))\vee (c))$ is a propositional formula. Let's see how that works.
Note: If you want to prove that something "is an X", the typical approach is to got back to the definitions of "X" and show, point by point, that the "something" you have meets those requirements. That's precisely what we've done with the above proof.
Importantly, to prove that $F$ is a propositional formula required us to turn around and prove that smaller pieces are propositional formulas. This is the essence of a recursive definition: $F$ is a propositional formula because something smaller is a propositional formula, which is because something even smaller is a propositional formula ... it looks like it's turtles all the way down. However, if you look closely, you see that this process always bottoms out at Point 1 of the definition (variables are propositional formulas) which is not "recursive". This is called the "base case" of the definition. We will have more to say about recursive definitions in the future!Important: Remember, an expression tree is a concise representation of the proof that a sequence of characters is a propositional formula. So if you are asked to prove that something like $\neg((a)\Rightarrow (b))$ is a propositional formula ... just draw its expression tree.
ACTIVITY
| level | operator(s) | associativity |
|---|---|---|
| 1 | $\neg$ | N/A |
| 2 | $\wedge$ | left-to-right |
| 3 | $\vee,\Rightarrow,\oplus$ | left-to-right |
| 4 | $\Leftrightarrow$ | left-to-right |
ACTIVITY