03-truth-tables.Rmd

# Truth Tables

`r newthought("In this")` chapter we'll introduce the last few concepts we need from deductive logic, and we'll learn a useful technique in the process: truth tables.


## Connectives

Complex propositions can be built up out of other, simpler propositions:

- Aegon is a tyrant **and** Brandon is a wizard.
- **Either** Aegon is a tyrant **or** Brandon is a wizard.
- **It's not true that** Aegon is a tyrant.

```{marginfigure, echo=TRUE}
Notice, we call *it's not true that* a connective even though it doesn't actually connect two propositions together.
```

Here we've used two simple propositions to build up longer, more complex ones using the terms *and*, *either/or*, and *it's not true that*. Such terms are called ***connectives***.

The three connectives just listed are the only ones we'll need in this book. Each has a name and a shorthand symbol:

```{r echo=FALSE}
df <- data.frame(
  Name = c("conjunction", "disjunction", "negation"),
  English = c("and", "either/or", "it's not true that"),    
  Symbol = c("$\\wedge$", "$\\vee$", "$\\neg$"),
  Example = c("$A \\wedge B$", "$A \\vee B$", "$\\neg A$")
)
knitr::kable(df)
```

Here are some more examples of complex propositions:

- $F \wedge \neg G$: Florida is warm and Geneva is not.
- $\neg J \vee \neg K$: Either Jing won't come to the party or Kamal won't come.

`r newthought("Sometimes")` we also need parentheses, to avoid ambiguity. Consider an example from arithmetic:
$$ 4 \div 2 \times 2 = 1. $$
Is this equation true? That depends on what you mean. Does the division operation come first, or the multiplication? So we use parentheses to clarify: $4 \div (2 \times 2) = 1$, but $(4 \div 2) \times 2 = 4$.

In logic we use parentheses to prevent ambiguity similarly. Consider:
$$ A \vee B \wedge C. $$
This proposition is ambiguous, it has two interpretations. In English we can distinguish them with a comma:

- Either Aegon is a tyrant or Brandon is a wizard, and Cerci is the queen.
- Either Aegon is a tyrant, or Brandon is a wizard and Cerci is the queen.

Notice how these statements make different claims. The first takes a definite stand on Cerci: she is the queen. It only leaves open the question whether Aegon is a tyrant or Brandon is a wizard. Whereas the second statement takes no definite stand on any of our three characters. Maybe Aegon is a tyrant, maybe not. Maybe Brandon is a wizard and Cerci is the queen, maybe not.

In logic we use parentheses to clarify which interpretation we mean:

- $(A \vee B) \wedge C$.
- $A \vee (B \wedge C)$.

Notice how the first statement is primarily an $\wedge$ statement. It uses $\wedge$ to combine the simpler statements $C$ and $A \vee B$ together. Whereas the second statement is primarily a $\vee$ statement. It uses $\vee$ to combine $A$ with $B \wedge C$.

We call the last connective used to build up the statement the ***main connective***.

- $(A \vee B) \wedge C$: main connective is $\wedge$.
- $A \vee (B \wedge C)$: main connective is $\vee$.

Two more examples:

- $\neg (A \vee B)$: main connective is $\neg$.
- $\neg A \vee B$: main connective is $\vee$.

Technically, the last example should have parentheses to prevent ambiguity, like so: $(\neg A) \vee B$. But things get cluttered and hard to read if we add parentheses around every negation. So we have a special understanding for $\neg$ in order to keep things tidy.

```{marginfigure, echo=TRUE}
This special understanding for $\mathbin{\sim}$ mirrors the one for minus signs in arithmetic.
```

```{block, type="info"}
The negation symbol $\mathbin{\sim}$ only applies to the proposition immediately following it.
```

So in the proposition $\neg A \vee B$, the $\neg$ only applies to $A$. And in $\neg (A \wedge B) \vee C$, it only applies to $A \wedge B$.


## Truth Tables

The  truth of a complex proposition built using our three connectives depends on the truth of its components. For example, $\neg A$ is false if $A$ is true, and it's true if $A$ is false:

```{r echo=FALSE}
df <- data.frame(
    A = c("T", "F"),
    NotA = c("F", "T")
)
colnames(df) <- c("$A$", "$\\neg A$")
knitr::kable(df, align = "c", caption="Truth table for $\\neg$")
```

Slightly more complicated is the rule for $\&$:

```{r echo=FALSE}
df <- data.frame(
    A = c("T", "T", "F", "F"),
    B = c("T", "F", "T", "F"),
    AandB = c("T", "F", "F", "F")
)
colnames(df) <- c("$A$", "$B$", "$A \\wedge B$")
knitr::kable(df, align = "c", caption="Truth table for $\\wedge$")
```

There are four rows now because $\&$ combines two propositions $A$ and $B$ together to make the more complex proposition $A \& B$. Since each of those propositions could be either true or false, there are $2 \times 2 = 4$ possible situations to consider.

Notice that in only one of these situations is $A \& B$ true, namely the first row where both $A$ and $B$ are true.

The truth table for $\vee$ ("either/or") is a little more surprising:

```{r echo=FALSE}
df <- data.frame(
    A = c("T", "T", "F", "F"),
    B = c("T", "F", "T", "F"),
    AandB = c("T", "T", "T", "F")
)
colnames(df) <- c("$A$", "$B$", "$A \\vee B$")
knitr::kable(df, align = "c", caption="Truth table for $\\vee$")
```

Now the complex proposition is always true, except in one case: the last row where $A$ and $B$ are both false. It makes sense that $A \vee B$ is false when both sides are false. But why is it true when both sides are true? Doesn't "Either $A$ or $B$" mean that *just one* of these is true?

Sometimes it does have that meaning. But sometimes it means "Either A or B, *or both*." Consider this exchange:

> X: What are you doing tomorrow night?\
> Y: I'm either going to a friend's house or out to a club. I might even do both, if there's time.

Person Y isn't necessarily changing their mind here. They could just be clarifying: they're doing at least one of these things, possibly even both of them. 

Although it's common to use "either/or" in English to mean *just* one or the other, in logic we use the more permissive reading. So $A \vee B$ means *either $A$, or $B$, or both*.

We can always convey the stricter way of meaning "either/or" with a more complex construction:
$$(A \vee B) \wedge \neg (A \wedge B).$$
That says:
$$ \mbox{Either $A$ or $B$ is true, and it's not the case that both $A$ and $B$ are true}.$$
Which is just a very explicit way of saying: either one or the other, but not both.

We can even verify that the complex construction captures the meaning we want, by using a truth table. We start with an empty table, where the header lists all the formulas we use to build up to the final, complex one we're interested in:

```{r echo=FALSE}
df <- data.frame(
    A = rep("$\\;$", 4),
    B = rep(" ", 4),
    AorB = rep(" ", 4),
    AandB = rep(" ", 4),
    NotAandB = rep(" ", 4),
    Whole = rep(" ", 4)
)
colnames(df) <- c("$A$", "$B$", "$A \\vee B$", "$A \\& B$", "$\\neg(A \\wedge B$)", "$(A \\vee B) \\wedge \\neg (A \\wedge B)$")
knitr::kable(df, align = "c")
```

Then we fill in the possible truth values for the simplest propositions, $A$ and $B$:

```{r echo=FALSE}
df <- data.frame(
    A = c("T", "T", "F", "F"),
    B = c("T", "F", "T", "F"),
    AorB = rep(" ", 4),
    AandB = rep(" ", 4),
    NotAandB = rep(" ", 4),
    Whole = rep(" ", 4)
)
colnames(df) <- c("$A$", "$B$", "$A \\vee B$", "$A \\& B$", "$\\neg(A \\wedge B$)", "$(A \\vee B) \\wedge \\neg (A \\wedge B)$")
knitr::kable(df, align = "c")
```

Next we consult the truth tables above for $\&$ and $\vee$ to fill in the columns at the next level of complexity:

```{r echo=FALSE}
df <- data.frame(
    A = c("T", "T", "F", "F"),
    B = c("T", "F", "T", "F"),
    AorB = c("T", "T", "T", "F"),
    AandB = c("T", "F", "F", "F"),
    NotAandB = rep(" ", 4),
    Whole = rep(" ", 4)
)
colnames(df) <- c("$A$", "$B$", "$A \\vee B$", "$A \\& B$", "$\\neg(A \\wedge B$)", "$(A \\vee B) \\wedge \\neg (A \\wedge B)$")
knitr::kable(df, align = "c")
```

Then move up to the next level of complexity. To fill in the column for $\neg(A \wedge B)$, we consult the column for $A \wedge B$ and apply the rules from the table for $\neg$:

```{r echo=FALSE}
df <- data.frame(
    A = c("T", "T", "F", "F"),
    B = c("T", "F", "T", "F"),
    AorB = c("T", "T", "T", "F"),
    AandB = c("T", "F", "F", "F"),
    NotAandB = c("F", "T", "T", "T"),
    Whole = rep(" ", 4)
)
colnames(df) <- c("$A$", "$B$", "$A \\vee B$", "$A \\& B$", "$\\neg(A \\wedge B$)", "$(A \\vee B) \\wedge \\neg (A \\wedge B)$")
knitr::kable(df, align = "c")
```

Finally, we consult the columns for $A \vee B$ and $\neg(A \wedge B)$, and the table for $\&$, to fill in the column for $(A \vee B) \wedge \neg(A \& B)$:

```{r echo=FALSE}
df <- data.frame(
    A = c("T", "T", "F", "F"),
    B = c("T", "F", "T", "F"),
    AorB = c("T", "T", "T", "F"),
    AandB = c("T", "F", "F", "F"),
    NotAandB = c("F", "T", "T", "T"),
    Whole = c("F", "T", "T", "F")
)
colnames(df) <- c("$A$", "$B$", "$A \\vee B$", "$A \\& B$", "$\\neg(A \\wedge B$)", "$(A \\vee B) \\wedge \\neg (A \\wedge B)$")
knitr::kable(df, align = "c")
```

Complex constructions like this are difficult at first, but don't worry. With practice they quickly become routine.


## Logical Truths & Contradictions

Some  propositions come out true in every row of the truth table. Consider $A \vee \neg A$ for example:

```{r echo=FALSE}
df <- data.frame(
    A = c("T", "F"),
    NotA = c("F", "T"),
    AorNotA = c("T", "T")
)
colnames(df) <- c("$A$", "$\\neg A$", "$A \\vee \\neg A$")
knitr::kable(df, align = "c")
```

Such propositions are especially interesting because they *must* be true. Their truth is guaranteed, just as a matter of logic. We call them ***logical truths***, or ***tautologies***.

The other side of this coin is propositions that are false in every row of the truth table, like $A \wedge \neg A$:

```{r echo=FALSE}
df <- data.frame(
    A = c("T", "F"),
    NotA = c("F", "T"),
    AandNotA = c("F", "F")
)
colnames(df) <- c("$A$", "$\\neg A$", "$A \\wedge \\neg A$")
knitr::kable(df, align = "c")
```

These propositions are called ***contradictions***.

Notice that the negation of a contradiction is a logical truth. For example, consider the truth table for $\neg (A \wedge \neg A)$:

```{r echo=FALSE}
df <- data.frame(
    A = c("T", "F"),
    NotA = c("F", "T"),
    AandNotA = c("F", "F"),
    NotAandNotA = c("T", "T")
)
colnames(df) <- c("$A$", "$\\neg A$", "$A \\wedge \\neg A$", "$\\neg (A \\wedge \\neg A)$")
knitr::kable(df, align = "c")
```


## Mutual Exclusivity & Truth Tables

Truth  tables can be used to establish that two propositions are mutually exclusive. A very simple example is the propositions $A$ and $\neg A$:

```{r echo=FALSE}
df <- data.frame(
    A = c("T", "F"),
    NotA = c("F", "T")
)
colnames(df) <- c("$A$", "$\\neg A$")
knitr::kable(df, align = "c")
```

There is no row in the table where both propositions are true. And if two propositions can't both be true, they are mutually exclusive by definition.

A slightly more complex example is the pair of propositions $A \vee B$ and $\neg A \wedge \neg B$. Their truth table (\@ref(tab:avbnaanb)) also has no row where $A \vee B$ and $\neg A \wedge \neg B$ are both true. So they are mutually exclusive.

```{r avbnaanb, echo=FALSE}
df <- data.frame(
    A = c("T", "T", "F", "F"),
    B = c("T", "F", "T", "F"),
    NotA = c("F", "F", "T", "T"),
    NotB = c("F", "T", "F", "T"),
    AorB = c("T", "T", "T", "F"),
    NotAandNotB = c("F", "F", "F", "T")
)
colnames(df) <- c("$A$", "$B$", "$\\neg A$", "$\\neg B$", "$A \\vee B$",
                  "$\\neg A \\wedge \\neg B$")
knitr::kable(df, align = "c", caption = "The propositions $A \\vee B$ and $\\neg A \\wedge \\neg B$ are mutually exclusive.")
```


## Entailment & Equivalence

Truth  tables can also be used to establish that an argument is valid. Here's a very simple example:

```{block, type="argument", echo=TRUE}
$A \wedge B$.\
Therefore, $A$.
```

Obviously it's not possible for the premise to be true and the conclusion false, so the argument is valid (if a bit silly). Accordingly, there is no line of the truth table where $A \wedge B$ comes out true, yet $A$ comes out false:

```{r echo=FALSE}
df <- data.frame(
    A = c("T", "T", "F", "F"),
    B = c("T", "F", "T", "F"),
    AandB = c("T", "F", "F", "F")
)
colnames(df) <- c("$A$", "$B$", "$A \\wedge B$")
knitr::kable(df, align = "c")
```

The only line where $A \wedge B$ comes out true is the first one. And on that line $A$ is true too. So the argument from $A \wedge B$ to $A$ is valid.

One more example:

```{block, type="argument", echo=TRUE}
$A \vee B$.\
$\neg A$.\
Therefore, $B$.
```

This argument is valid because the first premise says that at least one of the two propositions $A$ and $B$ must be true, and the second line says it's not $A$. So it must be $B$ that's true, as the conclusion asserts. And once again there is no line of the truth table where both $A \vee B$ and $\neg A$ are true, yet $B$ is false:

```{r echo=FALSE}
df <- data.frame(
    A = c("T", "T", "F", "F"),
    B = c("T", "F", "T", "F"),
    NotA = c("F", "F", "T", "T"),
    AveeB = c("T", "T", "T", "F")
)
colnames(df) <- c("$A$", "$B$", "$\\neg A$", "$A \\vee B$")
knitr::kable(df, align = "c")
```

The only line where both $A \vee B$ and $\neg A$ are true is the third row, and $B$ is true on that row. So once again the truth table tells us this argument is valid.

In the [previous chapter][Visualizing Propositions] we introduced the concept of logical entailment. $A$ logically entails $B$ when it's impossible for $A$ to be true and $B$ false. When one proposition entails another, there is no line of the truth table where the first proposition is true and the second is false.

`r newthought("Sometimes")` entailment goes in both directions: the first proposition entails the second *and the second entails the first*. For example, not only does $A \wedge B$ entail $B \wedge A$, but also $B \wedge A$ entails $A \wedge B$.

We say such propositions are ***logically equivalent***. In terms of truth tables, their columns match perfectly, they are identical copies of T's and F's.

```{r echo=FALSE}
df <- data.frame(
    A = c("T", "T", "F", "F"),
    B = c("T", "F", "T", "F"),
    AandB = c("T", "F", "F", "F"),
    BandA = c("T", "F", "F", "F")
)
colnames(df) <- c("$A$", "$B$", "$A \\wedge B$", "$B \\wedge A$")
knitr::kable(df, align = "c")
```

A more complex example is the propositions $\neg (A \vee B)$ and $\neg A \wedge \neg B$:

```{r echo=FALSE}
df <- data.frame(
    A = c("T", "T", "F", "F"),
    B = c("T", "F", "T", "F"),
    NotA = c("F", "F", "T", "T"),
    NotB = c("F", "T", "F", "T"),
    AorB = c("T", "T", "T", "F"),
    NotAorB = c("F", "F", "F", "T"),
    NotAandNotB = c("F", "F", "F", "T")
)
colnames(df) <- c("$A$", "$B$", "$\\neg A$", "$\\neg B$", "$A \\vee B$", 
                  "$\\neg(A \\vee B)$", "$\\neg A \\wedge \\neg B$")
knitr::kable(df, align = "c")
```

Here again the columns under these two propositions are identical.


## Summary

Connectives  can be used to build more complex propositions, like $A \wedge B$ or $A \vee \neg B$. We introduced three connectives:

- $\neg A$ means it's not true that $A$.
- $A \wedge B$ means both $A$ and $B$ are true.
- $A \vee B$ means either $A$ is true, or $B$ is true, *or both are true*.

In a complex proposition, the main connective is the last one used to build it up from simpler components. In $A \vee \neg B$ the main connective is the $\vee$.

An argument's validity can be established with a truth table, if there's no row where all the premises have a T and yet the conclusion has an F.

Truth tables can also be used to establish that two propositions are mutually exclusive, if there is no row of the table where both propositions have a T.

Logically equivalent propositions entail one another. When two propositions have identical columns in a truth table, they are logically equivalent.


## Exercises {-}

#.	Using the following abbreviations:

    $$
      \begin{aligned}
         A &= \mbox{Asha loves Cerci},\\
         B &= \mbox{Balon loves Cerci},
      \end{aligned}
    $$

    translate each of the following into logicese (e.g. $\neg A \vee B$).

    a.	Asha doesn't love Cerci.
    b.	Asha loves Cerci and Balon loves Cerci.
    c.	Asha loves Cerci but Balon does not.
    d.  Neither Asha nor Balon loves Cerci.

#. For each pair of propositions, use a truth table to determine whether they are mutually exclusive.

    a. $A \wedge B$ and $A \wedge \neg B$.
    #. $A$ and $\neg B$.
    #. $A \vee \neg A$ and $A \wedge \neg A$.
	
#. For each pair of propositions, use a truth table to determine whether they are logically equivalent.

    a. $\neg A \vee B$ and $\neg (A \wedge \neg B)$.
    #. $A$ and $(A \wedge B) \vee (A \wedge \neg B)$.
    #. $A$ and $(B \wedge A) \vee (B \wedge \neg A)$.

#. The proposition $A \vee (B \wedge C)$ features three simple propositions, so its truth table has 8 rows. Fill in the rest of the table:

    ```{r echo=FALSE}
    df <- data.frame(
        A = c("T", "T", "T", "T", "F", "F", "F", "F"),
        B = c("T", "T", "F", "F", "T", "T", "F", "F"),
        C = c("T", "F", "T", "F", "T", "F", "T", "F"),
        BandC = c("", "", "", "", "", "", "", ""),
        AorBandC = c("", "", "", "", "", "", "", "")
    )
    colnames(df) <- c("$A$", "$B$", "$C$", "$B \\wedge C$", 
                      "$A \\vee (B \\wedge C)$")
    knitr::kable(df, align = "c")
    ```

#. Use a truth table to determine whether the propositions $A \vee (B \wedge C)$ and $(A \vee B) \wedge (A \vee C)$ are equivalent.

#. True or false: if $A$ and $B$ are mutually exclusive, then $A$ and $\neg B$ are logically equivalent.

#.  If we are considering two compatible propositions $A$ and $B$, the truth-table has $4$ rows. If there are three compatible propositions $A$, $B$, and $C$, there are $8$ rows.

    a. How many rows are there if we have four compatible propositions?
    #. In general, how many rows are there for $n$ compatible propositions?
    #. How many rows are there if we have three propositions $A$, $B$, and $C$, but $A$ and $B$ are not compatible (they are mutually exclusive). Assume the other pairs are compatible.

#. Suppose a family has two children.

    a. How many possible ways are there for their birthdays to be distributed among the $12$ months of the year?
    #. Suppose we know the two siblings were born in different months. How many possibilities are there then?
    #. Suppose another family has three children. We don't know whether any of them have the same birth-month. How many possibilities are there in this case?