# Formal Logic

## Contents

# Formal Logic¶

Logic is a systematic way of thinking. As humans, we constantly gain new information, combine it with that we already know, and build new ideas. The process of putting together existing information to learn new things is called **deduction**.

When working with logic and reasoning, we need to make sure

We are correct

Others can understand/verify we are correct

It doesn’t help to have the most amazing idea in history if no one understands it or believes it.

**Formal Logic** gives us a consistent framework to communicate ideas. This way, we can write out our reasoning in a way to anyone familiar with **Formal Logic** can understand.

## Deducing New Information¶

In logic, we use facts to deduce new information. A **fact** is something that is either `True`

or `False`

. There is no middle ground in **Formal Logic**. Everything must be either `True`

or `False`

.

We know the following facts to be `True`

.

Circle \(X\) has a radius equal to 3

If any circle has radius \(r\), then it has area \(\pi r^2\)

These are both facts. They are both known to be `True`

.

We can deduce new information. We can conclude that “the area of circle \(X\) is \(9\pi\)”. We combine the information from the two facts we know to create a new fact. When drawing a new conclusion, we normally use the word *therefore*.

We would say

Circle \(X\) has a radius equal to 3. If any circle has radius \(r\), then it has area \(\pi r^2\). Therefore, the area of circle \(X\) is \(9\pi\).

The word *therefore* is telling the reader that this information was **deduced** from the earlier facts.

The facts that we know at the start of a problem are called **information**. When we **deduce** something, both our information and logic must be correct.

For example, the following logic is correct but the information is incorrect.

Circle \(X\) has a radius equal to 3. If any circle has radius \(r\), then it has area \(2r\pi\). Therefore, the area of circle \(X\) is \(6\pi\).

The **deduction** was correct, but the information was wrong. Specifically, the area formula was incorrect. This is a failing of the starting information, not the reasoning.

Formal Logic uses information to draw conclusions. We must assume that our information is true. Justification of the information takes place outside the world of formal logic.

Our goal in Formal Logic is to be certain that our reasoning is correct.

## Boolean Algebra¶

It is great to talk about logic in the abstract, but we need a system to write things down formally. This allows us to communicate with others and verify our reasoning.

A **statement** is a sentence or expression that is either `True`

or `False`

. Statements will be written as either single variables or expressions involving variables.

We assign a meaning to each of our variables.

\(A\) is true if it is raining.

\(B\) is true if it is cloudy.

These variables can be either `True`

or `False`

. Our **information** at the start of the problem is which variables we know to be `True`

or `False`

.

We can put variables together using operators. If was want to say

It is raining and cloudy.

We can use the AND operator (\(\wedge\)) to combine the two variables.

\( \begin{align} A \wedge B \end{align} \)

The three most common operators are used on transitional english words.

AND uses the symbol \(\wedge\) and is formally called a

**conjunction**.OR uses the symbol \(\vee\) and is formally called a

**disjunction**.NOT uses the symbol \(\neg\) and is formally called a

**negation**.

Each operator has a formal name. This is to allow us to communicate about them more easily. It is clearer to say

The three primary operators of boolean algebra are conjunction, disjunction, and negation.

instead of

The three primary operators of boolean algebra are and, or, and not.

Neither sentence is wrong, but the second is much more confusing.

### Conjunction¶

The **conjunction** allows us to “and” two expressions together. This means we want to convey that *both* values must be true.

We describe operators using **Truth Tables**. A **Truth Table** shows the inputs of a function and its outputs. Since each variable can only be `True`

or `False`

, the truth table can capture every possible input and output.

\(P\) |
\(Q\) |
\(P \wedge Q\) |
---|---|---|

T |
T |
T |

T |
F |
F |

F |
T |
F |

F |
F |
F |

This table shows every possible input and output of the conjunction. We can apply it to a specific case by picking a row from the table.

We need information to evaluate an expression.

\(A\) is true if it is raining.

\(B\) is true if it is cloudy.

The statement \(A \wedge B\) is short for “It is raining and cloudy.”

We can look at each situation in the truth table.

\(A\) |
\(B\) |
\(A \wedge B\) |
Meaning |
---|---|---|---|

T |
T |
T |
It is raining and cloudy at the same time. |

T |
F |
F |
It is raining, but not cloudy. |

F |
T |
F |
It is cloudy, but not raining. |

F |
F |
F |
It is not cloudy and also not raining. |

The statement is only true when the situation it describes is actually happening. A **conjunction** is only `True`

when *both* inputs are `True`

.

### Disjunction¶

The **disjunction** allows us to “or” two expressions together. This means we want to convey that *at least one* of the values must be true.

The truth table for the disjunction is given below.

\(P\) |
\(Q\) |
\(P \vee Q\) |
---|---|---|

T |
T |
T |

T |
F |
T |

F |
T |
T |

F |
F |
F |

We need information to evaluate an expression.

\(A\) is true if it is raining.

\(B\) is true if it is cloudy.

The statement \(A \vee B\) is short for “It is raining or cloudy.”

We can look at each situation in the truth table.

\(A\) |
\(B\) |
\(A \vee B\) |
Meaning |
---|---|---|---|

T |
T |
T |
It is raining and cloudy at the same time. |

T |
F |
T |
It is raining, but not cloudy. |

F |
T |
T |
It is cloudy, but not raining. |

F |
F |
F |
It is not cloudy and also not raining. |

A **disjunction** is `True`

as long as *at least one* of it’s two inputs is `True`

.

### Negation¶

The **negation** allows us to “not” an expression. This means we want to convey that *the opposite* of the value must be true.

The truth table for the negation is given below.

\(P\) |
\(\neg P\) |
---|---|

T |
F |

F |
T |

We need information to evaluate an expression.

\(A\) is true if it is raining.

The statement \(\neg A\) is short for “It is not raining.” We want the opposite of raining to be happening.

A **negation** is `True`

when its input is `False`

.

Note

These three operators are so common, there are many different symbols used for them in different contexts.

Conjunction: \(A \wedge B\), \(A \cap B\), \(A * B\), \(AB\), \(A \& B\), \(A \&\& B\)

Disjunction: \(A \vee B\), \(A \cup B\), \(A + B\), \(A | B\), \(A || B\)

Negation: \(\neg A\), \(\sim A\), \(-A\), \(\bar{A}\), \(!A\)

### Truth Tables¶

Given an expression made up of variables and operators, we can *always* draw a truth table. This will show every possible outcome. Then we can figure out which row fits our situation and determine the results.

The truth table for \(A \vee (\neg B \wedge C)\) is given below. Partial columns are shown to clarify how the result was reached.

\(A\) |
\(B\) |
\(C\) |
\(\neg B\) |
\((\neg B \wedge C)\) |
\(A \vee (\neg B \wedge C)\) |
---|---|---|---|---|---|

T |
T |
T |
F |
F |
T |

T |
T |
F |
F |
F |
T |

T |
F |
T |
T |
T |
T |

T |
F |
F |
T |
F |
T |

F |
T |
T |
F |
F |
F |

F |
T |
F |
F |
F |
F |

F |
F |
T |
T |
T |
T |

F |
F |
F |
T |
F |
F |

This expression is `False`

in three cases and `True`

in five. That accounts for every possible input and output. This truth table can act as a **proof**. It is an exhaustive list of every possible input and output.

Truth Tables get very large very fast. Although they are always correct, they are also very difficult to make for large problems. This makes them impractical in most situations. The number of rows in a Truth Table with \(n\) variables is \(2^n\). The above expression had \(3\) variables, so it had \(2^{3}=8\) rows.

Even storing large truth tables on a computer can become impossible. If we used one bit per value, we would need \(n+1\) bits per row. One bit for each variable and one extra for the results. The formula for memory needed would be \((n+1)*2^{n}\) bits. If we had a problem with 45 variables, it would take 1,618,481,116,086,272 bits. That is 184 Terabytes.

Although truth tables always work, they are very infrequently practical.

A truth table **must** have one of the following three properties.

**Contingent**: the result of the truth table is dependent on the values of the input variables.**Tautology**: the result is always`True`

regardless of the inputs.**Contradictory**: the result is always`False`

regardless of the inputs.

### Conditionals¶

There are two additional operators that are very important in writing proofs. The first is the **conditional** operator. This is used to create a relationship between two variables.

The following Python code has an `if`

statement.

```
if x > 10:
y = 7
```

This code is telling us that when `x > 10`

is true, then we know `y`

will be set to 7 by the code. We can assign these to boolean variables.

\(A\) is true when

`x > 10`

is true\(B\) is true when

`y`

is assigned the value 7.

We would then say that this code execute \(A \implies B\). The \(\implies\) symbol is used for conditionals. It is also called the **implies** symbol.

The truth table for the conditional is given below.

\(P\) |
\(Q\) |
\(P \implies Q\) |
---|---|---|

T |
T |
T |

T |
F |
F |

F |
T |
T |

F |
F |
T |

The truth table is only `False`

on one row, the \(T \implies F\) row.

Think of the conditional as a kind of contract. It is `False`

when the contract is *broken*. It is `True`

when the contract is not broken.

We will start with a real world situation.

If your car is under 5,000 miles, then all repairs are paid for by the dealership.

We can define variables.

\(M\) means milage is under 5,000 miles.

\(W\) means all repairs are paid for by the dealership.

The statement is \(M \implies W\).

The first line of the truth table is when \(M=T\) and \(W=T\). In this situation, the car has a milage under 5,000 miles. The transmission breaks on the car and you take it to the dealership. The dealer fixes it for free because it is under warranty.

The second line of the truth table is when \(M=T\) and \(W=F\). In this situation, the car has a milage under 5,000 miles. The transmission breaks on the car and you take it to the dealership. The dealer refused to fit it and throws you out. The dealer **broke** the warranty contract they made with you. The **conditional** statement is `False`

because the warranty did not hold up as agreed. You can sue the dealership for breach of contact.

The third line of the truth table is when \(M=F\) and \(W=T\). In this situation, the car has a milage over 5,000 miles. The transmission breaks on the car and you take it to the dealership. The dealership tells you that they had a recall on that part and agrees to fix the car for free anyway. Even though the warranty did not apply, the dealership still decided to pay for all repairs. You got a lucky break, but no one **broke** their contracts.

The final line of the truth table is when \(M=F\) and \(W=F\). In this situation, the car has a milage over 5,000 miles. The transmission breaks on the car and you take it to the dealership. The dealership tells you that you need to pay for the repairs. That is reasonable, your car is out of warranty. You have to pay for the repairs. No one did anything wrong, the car was no longer under warranty.

### Bi-Conditionals¶

The **bi-conditional** is used when we want to say two values are the same. It is the logical way to say “equals” or “equivalent”. The english equivalent of the **bi-conditional** is to say “if and only if”.

For example,

X is even if and only if \(X \mod 2 = 0\)

These two statements are really the same. If \(X\) is even, then it obviously has not remainder when divided by two. Likewise, if we divide a number by two and it has no remainder then it must be even. The two are exactly the same.

The truth table for the **bi-conditional** is

\(P\) |
\(Q\) |
\(P \iff Q\) |
---|---|---|

T |
T |
T |

T |
F |
F |

F |
T |
F |

F |
F |
T |

The **bi-conditional** is `True`

when both inputs are the same. It is the boolean version of equivalence.

We can use truth tables to prove to expressions are equivalent. If they are, we can use them interchangeably.

An alternative definition of the **conditional** is proven by truth table.

\(A\) |
\(B\) |
\(A \implies B\) |
\(\neg A \vee B\) |
\((A \implies B) \iff (\neg A \vee B)\) |
---|---|---|---|---|

T |
T |
T |
T |
T |

T |
F |
F |
F |
T |

F |
T |
T |
T |
T |

F |
F |
T |
T |
T |

This expression is a **tautology**! It is true regardless of the values of \(A\) and \(B\). These two expressions are always equivalent.

We can show another **tautology** that defines the **bi-conditional** in terms of two conditionals.

\(A\) |
\(B\) |
\((A \implies B) \wedge (B \implies A)\) |
\(A \iff B\) |
\((A \implies B) \wedge (B \implies A)) \iff (A \iff B)\) |
---|---|---|---|---|

T |
T |
T |
T |
T |

T |
F |
F |
F |
T |

F |
T |
F |
F |
T |

F |
F |
T |
T |
T |

### Algebra on Logical Expressions¶

We can use truth tables to create rules, then use the rules to reason about expressions.

We showed by truth table the following formulas. The equals \(=\) symbols is used to state that these are proven the same by truth table.

\( \begin{align} (P \implies Q) =& (\neg P \vee Q) & \text{Rule 1}\\ (P \iff Q) =& (P \implies Q) \wedge (Q \implies P) & \text{Rule 2} \end{align} \)

We can use these to simplify expressions

\( \begin{align} (P \iff Q) =& (P \implies Q) \wedge (Q \implies P) &\text{By R1} \\ =& (\neg P \vee Q) \wedge (Q \implies P) &\text{By R2} \\ =& (\neg P \vee Q) \wedge (\neg Q \vee P) &\text{By R2} \end{align} \)

We can now state

\( \begin{align} (P \iff Q) =& (\neg P \vee Q) \wedge (\neg Q \vee P) \end{align} \)

This statement is proven by algebraic rules.

### DeMorgan’s Laws¶

**DeMorgan’s Laws** tell us how to distribute a negative into a conjunction or disjunction. They are proven by truth table below.

\( \begin{align} \neg ( P \vee Q) =& (\neg P) \wedge (\neg Q) & \text{DeMorgan 1} \\ \neg (P \wedge Q) =& (\neg P) \vee (\neg Q) & \text{DeMorgan 2} \end{align} \)

\(P\) |
\(Q\) |
\(\neg ( P \vee Q)\) |
\((\neg P) \wedge (\neg Q)\) |
DeMorgan 1 |
---|---|---|---|---|

T |
T |
F |
F |
T |

T |
F |
F |
F |
T |

F |
T |
F |
F |
T |

F |
F |
T |
T |
T |

\(P\) |
\(Q\) |
\(\neg ( P \wedge Q)\) |
\((\neg P) \vee (\neg Q)\) |
DeMorgan 2 |
---|---|---|---|---|

T |
T |
F |
F |
T |

T |
F |
T |
T |
T |

F |
T |
T |
T |
T |

F |
F |
T |
T |
T |