1.2.4: More rules of Boolean Algebra
- Page ID
- 9848
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)It is certainly not true that all possible rules of Boolean algebra are given in Figure 2.2. For one thing, there are many rules that are easy consequences of the rules that are listed there. For example, although the table asserts only that \(\mathbb{F} \vee p\) ≡ p, it is also true that \(p \vee \mathbb{F}\) ≡ p. This can be checked directly or by a simple calculation:
\(p \vee \mathbf{F} \equiv \mathbf{F} \vee p \qquad\) Commutative Law
\(\equiv p \qquad\) Identity Law as given in the table
Additional rules can be obtained by applying the Commutative Law to other rules in the table, and we will use such rules freely in the future.
Another sort of easy extension can be applied to the Associative Law, (p ∨ q) ∨ r ≡p ∨ (q ∨ r). The law is stated for the ∨ operator applied to three terms, but it generalizes to four or more terms. For example
((p ∨ q) ∨ r) ∨ s
≡ (p ∨ q) ∨ (r ∨ s) by the Associative Law for three terms
≡ p ∨ (q ∨ (r ∨ s)) by the Associative Law for three terms
We will, of course, often write this expression as p ∨ q ∨ r ∨ s, with no parentheses at all, knowing that wherever we put the parentheses the value is the same.
One other thing that you should keep in mind is that rules can be applied in either direction. The Distributive Law, for example, allows you to distribute the p in p∨(q∧¬p) to get (p∨q)∧(p∨¬p). But it can also be used in reverse to ‘factor out’ a term, as when you start with (q ∨ (p → q)) ∧ (q ∨(q → p)) and factor out the q to get q ∨ ((p → q) ∧ (q → p)).
So far in this section, we have been working with the laws of Boolean algebra without saying much about what they mean or why they are reasonable. Of course, you can apply the laws in calculations without understanding them. But if you want to figure out which calculations to do, you need some understanding. Most of the laws are clear enough with a little thought. For example, if we already know that q is false, then p ∨ q will be true when p is true and false when p is false. That is, p ∨ F has the same logical value as p. But that’s just what the Identity Law for ∨ says. A few of the laws need more discussion.
The Law of the Excluded Middle, p ∨ ¬p ≡ T, says that given any proposition p, at least one of p or ¬p must be true. Since ¬p is true exactly when p is false, this is the same as saying that p must be either true or false. There is no middle ground. The Law of Contradiction, p ∧ ¬p ≡ F, says that it is not possible for both p and ¬p to be true. Both of these rules are obvious.
There are some who set out to question the law of there being no middle ground. Already in the 1920’s people like Tarski (who we will meet later) talked about other forms of logic where another value representing ‘unknown’ or ‘not proven’ also exists. You can also see this in some pro- gramming languages where they are referred to as ‘tri-state booleans’.
These so-called non-standard logics have been de- veloped and have also lead to things like ‘fuzzy logic’, which some consider quite controversial. Lotfi Zadeh is credited as the first person to refer to this type of logic as fuzzy logic in his work on ‘fuzzy sets’ in 1965. Zadeh was later quoted as saying: “Not being afraid to get em- broiled in controversy. ... That’s part of my character, too. I can be very stubborn. That’s probably been beneficial for the development of Fuzzy Logic.”
Source: en.Wikipedia.org/wiki/Lotfi_A._Zadeh
The Distributive Laws cannot be called obvious, but a few examples can show that they are reasonable. Consider the statement, “This card is the ace of spades or clubs.” Clearly, this is equivalent to “This card is the ace of spaces or this card is the ace of clubs.” But this is just an example of the first distributive law! For, let a represent the proposition
“This card is an ace”, let s represent “This card is a spade” and let c represent “This card is a club”. Then “This card is the ace of spades or clubs” can be translated into logic asa ∧ (s ∨ c), while “This card is the ace of spades or this card is the ace of clubs” becomes(a ∧ s) ∨ (a ∧ c). And the distributive law assures us that a ∧ (s ∨ c) ≡ (a ∧ s) ∨ (a ∧ c). The second distributive law tells us, for example, that “This card is either a joker or is the ten of diamonds” is logically equivalent to “This card is either a joker or a ten, and it is eitherajokeroradiamond”. That is, j∨(t∧d) ≡ (j∨t)∧(j∨d). The distributive laws are powerful tools and you should keep them in mind whenever you are faced with a mixture of ∧ and ∨ operators.
DeMorgan’s Laws must also be less than obvious, since people often get them wrong. Fortunately you get to practice them both in Reasoning & Logic, as well as in Computer Organisation, so you will soon get them right. More importantly perhaps they do also make sense. When considering ¬(p ∧ q), you should ask yourself, how can “p and q” failto be true. It will fail to be true if either p is false or if q is false (or both). That is, ¬(p ∧ q)is equivalent to (¬p) ∨ (¬q). Consider the sentence “A raven is large and black.” If a bird is not large and black, then it is not a raven. But what exactly does it mean to be “not (large and black)”? How can you tell whether the assertion “not (large and black)” is true of something? This will be true if it is either not large or not black. (It doesn’t have to be both—it could be large and white, it could be small and black.) Similarly, for “p or q” to fail to be true, both p and q must be false. That is, ¬(p ∨ q) is equivalent to (¬p) ∧ (¬q). This is DeMorgan’s second law.
Recalling that p → q is equivalent to (¬p) ∨ q, we can apply DeMorgan’s law to obtain a formula for the negation an implication:
¬(p → q) ≡ ¬((¬p)∨q)
≡ (¬(¬p)) ∧ (¬q)
≡ p ∧ ¬q
That is, p → q is false exactly when both p is true and q is false. For example, the negation of “If you have an ace, you win” is “You have an ace, and you don’t win”. Think of it this way: if you had an ace and you didn’t win, then the statement “If you have an ace, you win” was not true.
Exercises
- Construct truth tables to demonstrate the validity of each of the distributive laws.
- Construct the following truth tables:
a) Construct truth tables to demonstrate that ¬(p ∧ q) is not logically equivalent to (¬p) ∧(¬q).
b) Construct truth tables to demonstrate that ¬(p ∨ q) is not logically equivalent to (¬p) ∨(¬q).
c) Construct truth tables to demonstrate the validity of both DeMorgan’s Laws. - Construct truth tables to demonstrate that ¬(p → q) is not logically equivalent to any of the following.
a) (¬p) → (¬q)b) (¬p) → q
c) p → (¬q)
Refer back to this section for a formula that is logically equivalent to ¬(p → q). - Is ¬(p ↔ q) logically equivalent to (¬p) ↔ (¬q)?
- In the algebra of numbers, there is a distributive law of multiplication over addition: x(y + z) =xy + xz. What would a distributive law of addition over multiplication look like? Is it a valid law in the algebra of numbers?
6. The distributive laws given in Figure 2.2 are sometimes called the left distributive laws. Theright distributive laws say that (p ∨ q) ∧ r ≡ (p ∧ r) ∨ (q ∧ r) and that (p ∧ q) ∨ r ≡ (p ∨ r) ∧(q ∨ r). Show that the right distributive laws are also valid laws of Boolean algebra. (Note: In practice, both the left and the right distributive laws are referred to simply as the distributive laws, and both can be used freely in proofs.)
7.Show that p∧(q∨r∨s)≡(p∧q)∨(p∧r)∨(p∧s) for any propositions p,q,r, and s. In words, we can say that conjunction distributes over a disjunction of three terms. (Recall that the ∧ operator is called conjunction and ∨ is called disjunction.) Translate into logic and verify the fact that conjunction distributes over a disjunction of four terms. Argue that, in fact, con- junction distributes over a disjunction of any number of terms.
- There are two additional basic laws of logic, involving the two expression p ∧ F and p ∨ T. What are the missing laws? Show that your answers are, in fact, laws.
- For each of the following pairs of propositions, show that the two propositions are logically equivalent by finding a chain of equivalences from one to the other. State which definition or law of logic justifies each equivalence in the chain.
- For each of the following compound propositions, find a simpler proposition that is logically equivalent. Try to find a proposition that is as simple as possible.
a) (p ∧ q) ∨ ¬q b) ¬(p ∨ q) ∧ p c) p → ¬p
d) ¬p ∧ (p ∨ q) e) (q ∧ p) → q f) (p → q) ∧ (¬p → q) - Express the negation of each of the following sentences in natural English:a) It is sunny and cold.
b) I will have stroopwafel or I will have appeltaart.c) If today is Tuesday, this is Belgium.
d) If you pass the final exam, you pass the course.
- Apply one of the laws of logic to each of the following sentences, and rewrite it as an equivalent sentence. State which law you are applying.
a) I will have coffee and stroopwafel or appeltaart.b) He has neither talent nor ambition.
c) You can have oliebollen, or you can have oliebollen.
- Suppose it is simultaneously true that “All lemons are yellow” and “Not all lemons are yellow”. Derive the conclusion “Unicorns exist”. (If you get stuck, check out en.Wikipedia.org/wiki/ Principle_of_explosion.)