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
Trueregardless of the inputs.Contradictory: the result is always
Falseregardless 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 > 10is true\(B\) is true when
yis 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 |