Logic

Logic is a topic of interest in both math and philosophy. In math it forms much of the bedrock on which the entire discipline stands. An intuitive introduction to the most widely used basics is contained below.

Statements, Truth Tables, and Boolean Variables

A truth table for statements $A$ and $B$.

$A$	$B$	Image	In Words
T	T		The person is wearing a red shirt is a TRUE statement. The person is wearing blue pants is a TRUE statement.
T	F		The person is wearing a red shirt is a TRUE statement. The person is wearing blue pants is a FALSE statement.
F	T		The person is wearing a red shirt is a FALSE statement. The person is wearing blue pants is a TRUE statement.
F	F		The person is wearing a red shirt is a FALSE statement. The person is wearing blue pants is a FALSE statement.

Logic deals with the truth value of Statements. The statements allowed must be either true or false (never both at the same time). For instance the statement which follows.

"It is raining outside."

This statement is either true or false. It is either raining or it is not raining.

Often it is convenient to label our statements with letters much like variables in algebra. These variables can only take values of true or false and are called Boolean Variables. Lets define the statements $A$ and $B$ as follows.

Statement $A$

"The person is wearing a red shirt."

Statement $B$

"The person is wearing blue pants."

A Truth Table is a catalogue used to represent all the possible combinations of truth values of the statements being studied. Note all statements are either true (T) or false (F). The images and wordy explanations presented here are for learning purposes and are not part of the truth table structure.

Of course when a statement is false the result might be more subtle than the example illustrated to the right. For instance if $A$ is false perhaps the shirt is Yellow rather than missing entirely.

Basic Operations

It is useful to define operations on these Boolean Variables, so that we can do Boolean Arithmetic. Boolean Arithmetic is much like arithmetic on numbers except there are only two values, true and false (rather than an infinite set of numbers).

Negation (NOT)

The Negation of $A$ is written as $\lnot A$ and serves to invert the truth value of $A$. The word "NOT" is used to serve this purpose in English.

A truth table for the statement $\lnot A$.

$A$	$\lnot A$	Image	In Words
T	F		The person is wearing a red shirt is a TRUE statement. The person is NOT wearing a red shirt is a FALSE statement.
F	T		The person is wearing a red shirt is a FALSE statement. The person is NOT wearing a red shirt is a TRUE statement.

We can also write compound statements. In a Compound Statement we combine two or more statements we already know the truth values of with an operator. This is much like creating a compound sentence in English.

Conjunction (AND)

The Conjunction of two statements is written as $A\wedge B$. It gives true only when both $A$ and $B$ are true statements. The word "AND" is used to achieve this in English.

A truth table for the statement $A\wedge B$.

$A$	$B$	$A\wedge B$	Image	In Words
T	T	T		The person is wearing a red shirt is a TRUE statement. The person is wearing blue pants is a TRUE statement. The person is wearing a red shirt AND blue pants is a TRUE statement.
T	F	F		The person is wearing a red shirt is a TRUE statement. The person is wearing blue pants is a FALSE statement. The person is wearing a red shirt AND blue pants is a FALSE statement.
F	T	F		The person is wearing a red shirt is a FALSE statement. The person is wearing blue pants is a TRUE statement. The person is wearing a red shirt AND blue pants is a FALSE statement.
F	F	F		The person is wearing a red shirt is a FALSE statement. The person is wearing blue pants is a FALSE statement. The person is wearing a red shirt AND blue pants is a FALSE statement.

Disjunction (OR)

The Disjunction of two statements is written as $A\vee B$. It gives false only when both $A$ and $B$ are false statements. The word "OR" is used to achieve this in English. "OR" is ment in the inclusive sense, meaning that $A$ can be true, $B$ can be true, or both can be true at the same time.

A truth table for the statement $A\vee B$.

$A$	$B$	$A\vee B$	Image	In Words
T	T	T		The person is wearing a red shirt is a TRUE statement. The person is wearing blue pants is a TRUE statement. The person is wearing a red shirt OR blue pants is a TRUE statement.
T	F	T		The person is wearing a red shirt is a TRUE statement. The person is wearing blue pants is a FALSE statement. The person is wearing a red shirt OR blue pants is a TRUE statement.
F	T	T		The person is wearing a red shirt is a FALSE statement. The person is wearing blue pants is a TRUE statement. The person is wearing a red shirt OR blue pants is a TRUE statement.
F	F	F		The person is wearing a red shirt is a FALSE statement. The person is wearing blue pants is a FALSE statement. The person is wearing a red shirt OR blue pants is a FALSE statement.

Disjunction (XOR)

The other form of the disjunction (exclusive or, "XOR") is another useful operation. It is written $A\oplus B$. It is not popular in Math or Philosophy, but is very popular in computer programming. It is true only when one or the other of $A$ and $B$ are true, but not both at once.

A truth table for the statement $A\oplus B$.

$A$	$B$	$A\oplus B$	Image	In Words
T	T	F		The person is wearing a red shirt is a TRUE statement. The person is wearing blue pants is a TRUE statement. The person is wearing a red shirt (X)OR blue pants is a FALSE statement.
T	F	T		The person is wearing a red shirt is a TRUE statement. The person is wearing blue pants is a FALSE statement. The person is wearing a red shirt (X)OR blue pants is a TRUE statement.
F	T	T		The person is wearing a red shirt is a FALSE statement. The person is wearing blue pants is a TRUE statement. The person is wearing a red shirt (X)OR blue pants is a TRUE statement.
F	F	F		The person is wearing a red shirt is a FALSE statement. The person is wearing blue pants is a FALSE statement. The person is wearing a red shirt (X)OR blue pants is a FALSE statement.

Implication Operations

There are two more logic operations which are very useful in Math and Philosophy.

Conditional Statement (IF)

The Conditional Statement (also called Implication, or Material Implication) is the most difficult operation to understand. It is written $A\Rightarrow B$. It is always true unless A is true and B is false. In English we would call this an "IF statement" or an "IF THEN statement". It works like a promise. If you do $A$ then I will do $B$. If you do not do $A$ I can choose to do $B$ or not to do B without breaking my promise. However if you do $A$ I must do $B$ otherwise my promise is a lie. Consider the following statements.

Truth table for the statement: If $A$, then $B$.

$A$	$B$	$A\Rightarrow B$	In Words
T	T	T	You earn 100% on your exam, is a TRUE statement. You get 100% in the class, is a TRUE statement. IF you earn 100% on your exam, THEN you get 100% in the class, is a TRUE statement. Condition $A$ met, $B$ given, promise fulfilled.
T	F	F	You earn 100% on your exam, is a TRUE statement. You get 100% in the class, is a FALSE statement. IF you earn 100% on your exam, THEN you get 100% in the class, is a FALSE statement. Condition $A$ met, $B$ not given, promise broken.
F	T	T	You earn 100% on your exam, is a FALSE statement. You get 100% in the class, is a TRUE statement. IF you earn 100% on your exam, THEN you get 100% in the class, is a TRUE statement. Condition $A$ not met, nothing to fulfill, but $B$ was given anyway.
F	F	T	You earn 100% on your exam, is a FALSE statement. You get 100% in the class, is a FALSE statement. IF you earn 100% on your exam, THEN you get 100% in the class, is a TRUE statement. Condition $A$ not met, nothing to fulfill, $B$ not given.

Statement $A$

"You earn 100% on your exam."

Statement $B$

"You get 100% in the class."

The Conditional statement $A\Rightarrow B$ is the following. "If you earn 100% on your exam, then you get 100% in the class." If you earn 100% on your exam and you don't get 100% in the class then my conditional statement is a lie. If you earn 100% on your exam and get 100% in the class then I have told the truth. If you earn any other grade than 100% on your exam then I can give 100% in the class or not and the conditional statement is true, because I made no promise for any other grade than 100% on the exam. In the real world, other factors would be considered too (graded assignments, class participation, etc.), but that information is not part of the conditional statement given.

If the condition $A$ is true it implies the statement $B$ must be true for the compound statement to be true. If the condition $A$ is false then the compound statement implies nothing about B, so it can be true or false. The truth table follows.

The conditional statement can also be written as "$B$ IF $A$", and in a variety of other forms too. $A$ is often called the Premise or Hypothesis and $B$ the Conclusion.

Biconditional Statement (IFF)

Truth table for the statement: If and only if $A$, then $B$.

$A$	$B$	$A\Leftrightarrow B$	In Words
T	T	T	You earn 100% on your exam, is a TRUE statement. You get 100% in the class, is a TRUE statement. IF AND ONLY IF you earn 100% on your exam, THEN you get 100% in the class, is a TRUE statement. Condition $A$ met, $B$ given, promise kept.
T	F	F	You earn 100% on your exam, is a TRUE statement. You get 100% in the class, is a FALSE statement. IF AND ONLY IF you earn 100% on your exam, THEN you get 100% in the class, is a FALSE statement. Condition $A$ met, $B$ not given, promise broken.
F	T	F	You earn 100% on your exam, is a FALSE statement. You get 100% in the class, is a TRUE statement. IF AND ONLY IF you earn 100% on your exam, THEN you get 100% in the class, is a FALSE statement. Condition $A$ not met, but $B$ was given anyway, only if part of promise broken.
F	F	T	You earn 100% on your exam, is a FALSE statement. You get 100% in the class, is a FALSE statement. IF AND ONLY IF you earn 100% on your exam, THEN you get 100% in the class, is a TRUE statement. Condition $A$ not met, $B$ not given, promise kept.

Finally the Biconditional Statement. It is written $A\Leftrightarrow B$. In English we say "If and only If", sometimes abbreviated "IFF". This is what people usually mean when they use the word if in English. This statement is true if both $A$ and $B$ are true or if both $A$ and $B$ are false. It is false if $A$ and $B$ do not have the same truth value. It is like a promise which is only fulfilled if the condition is met.

BONUS EXAMPLE

A more mathematical example would be the following statements.

Statement $A$

"x in an even number."

Statement $B$

"x is divisible by 2."

It is clearly the case that these two statements are true or false at the same time, as the second statement is the definition of the first. Applying the biconditional with these will give exactly the truth table expected.

It is interesting to note that the biconditional and "XOR" are one negation away from having the same truth table. In fact in digital computers the XOR gate and a NOT gate are what is used to implement the biconditional, which is in turn used to check equality. This implementation is preferred so as to minimize the number of transistors required to make a gate that can check equality of binary digits.

Order of Operations, Logical Equivalence, Tautology and Contradiction

Comparison of the results.

$A$	$B$	$\lnot (A\Rightarrow B)$	$A\wedge \lnot B$
T	T	F	F
T	F	T	T
F	T	F	F
F	F	F	F

Truth table for the statement, $A\wedge \lnot B$.

$A$	$B$	$\lnot B$	$A\wedge \lnot B$
T	T	F	F
T	F	T	T
F	T	F	F
F	F	T	F

Truth table for the statement, $\lnot (A\Rightarrow B)$.

$A$	$B$	$A\Rightarrow B$	$\lnot (A\Rightarrow B)$
T	T	T	F
T	F	F	T
F	T	T	F
F	F	T	F

When more than one operation is used in a compound statement we follow an order of operations, much like with algebra. The order is brackets, negation, conjuntion, disjunction (OR), conditional, and finally biconditional. XOR is used mostly in computers and the practical implications of this are messy (bitwise operators vs boolean/logical operators). Check out this Wikipedia link if you are curious, otherwise forget about XOR for now. I'll remind you when it comes up in future lessons.

Here's an example of how to approach creating a truth table for the compound statement $\lnot (A\Rightarrow B)$. First we write down all possible combinations or truth values for the simple statements $A$, and $B$. Then we work our way through the order of operations writing the truth values of each increasingly complex statement as we build our way out to the whole statement. It's just like BEDMAS. Note we don't know the content of the statements $A$ and $B$, but that's okay. We just want to look at how the logic computes. We want to consider every combination of truth values, so we can quickly look up the answers in our table for specific examples at a later date.

We repeat similar procedures for $A\wedge \lnot B$. Note you can just continue the first table (instead of separating them) to avoid repeating yourself. That will bring the twelve columns represented here (in three separate tables) down to six (in a single table).

The final truth table values are the same for both of our expressions.

The statements are logically equivalent.

$A$	$B$	$\lnot (A\Rightarrow B)$	$A\wedge \lnot B$	$\lnot (A\Rightarrow B)\Leftrightarrow A\wedge \lnot B$
T	T	F	F	T
T	F	T	T	T
F	T	F	F	T
F	F	F	F	T

This means the two expressions are Logically Equivalent. We write this $\lnot (A\Rightarrow B)\equiv A\wedge \lnot B$. Some people use $\Leftrightarrow$ instead of $\equiv$. We will avoid this notation for clarity. Out of curiosity, lets consider what the truth table would look like for the statement $\lnot (A\Rightarrow B)\Leftrightarrow A\wedge \lnot B$.

This statement is always true, regardless of the choice of truth value for $A$ and $B$. Such a statement is called a Tautology. If instead we negate the statement to get $\lnot (\lnot (A\Rightarrow B)\Leftrightarrow A\wedge \lnot B)$ the new statement is now always false. This kind of statement is called a Contradiction. Template:Vpad

Quantifiers

There are 3 quantifiers generally used in mathematical logic. They are $\forall$ (For All/For Every, ie. all), $\exists$ (There Exists, ie. some), and $\nexists$ (The Does Not Exist, ie. none).

In example here are three statements. All humans are people. Some humans are named Alice. No humans are fish.

Generally it is preferred to find statements that apply to every case. Often the cases, where only some values work, can be subdivided to create new statements for which statements are true universally. The symbols will be explored further in Set Theory, where they are used extensively.

Applications

Logic is foundational in mathematics. It forms the framework in which proofs are done.

Beyond math, logic is also used extensively in Digital Circuits and computer programming.

It also makes up the foundation of how to make an argument and thus is an integral component in most academic pursuits.

Examples

The statements $A\Leftrightarrow B$ and $(A\Rightarrow B)\wedge (B\Rightarrow A)$ are logically equivalent.

$A$	$B$	$A\Leftrightarrow B$	$A\Rightarrow B$	$B\Rightarrow A$	$(A\Rightarrow B)\Leftrightarrow (B\Rightarrow A)$	$(A\Leftrightarrow B)\Leftrightarrow ((A\Rightarrow B)\Leftrightarrow (B\Rightarrow A))$
T	T	T	T	T	T	T
T	F	F	F	T	F	T
F	T	F	T	F	F	T
F	F	T	T	T	T	T

Truth table for $(A\Rightarrow B)\wedge (A\Rightarrow \lnot B)$.

$A$	$B$	$A\Rightarrow B$	$\lnot B$	$A\Rightarrow \lnot B$	$(A\Rightarrow B)\wedge (A\Rightarrow \lnot B)$
T	T	T	F	F	F
T	F	F	T	T	F
F	T	T	F	T	T
F	F	T	T	T	T

Finding A Truth Table

Find the truth table for the statement $(A\Rightarrow B)\wedge (A\Rightarrow \lnot B)$. Note the result is logically equivalent to $\lnot A$.

Showing Logical Equivalence

Show that the statements $A\Leftrightarrow B$ and $(A\Rightarrow B)\wedge (B\Rightarrow A)$ are logically equivalent and thus that the statement $(A\Leftrightarrow B)\Leftrightarrow ((A\Rightarrow B)\Leftrightarrow (B\Rightarrow A))$ is a tautology.

Exercises

Rules of Boolean Algebra

Below are the Rules of Boolean Algebra (often referred to as Rules of Replacement, Laws, or Identities). These rules are all the operations we need to do algebra on Boolean variables. For practise, please use truth tables to prove the logical equivalence of these statements. Please use the systematic (step by step) approach to building truth tables which is shown in the examples section.

${\begin{aligned}\lnot \lnot A&\equiv A&{\text{Double Negation}}\\(A\wedge B)\wedge C&\equiv A\wedge (B\wedge C)&{\text{Associativity of Conjunction}}\\(A\vee B)\vee C&\equiv A\vee (B\vee C)&{\text{Associativity of Disjunction}}\\A\wedge B&\equiv B\wedge A&{\text{Commutivity of Conjuntion}}\\A\vee B&\equiv B\vee A&{\text{Commutivity of Disjunction}}\\A\wedge (B\vee C)&\equiv (A\wedge B)\vee (A\wedge C)&{\text{Distribution of Conjunction over Disjunction}}\\A\vee (B\wedge C)&\equiv (A\vee B)\wedge (A\vee C)&{\text{Distribution of Disjunction over Conjunction}}\\A\wedge F&\equiv F&{\text{Annihilation for Conjunction}}\\A\vee T&\equiv T&{\text{Annihilation for Disjunction}}\\A\wedge T&\equiv A&{\text{Identity for Conjunction}}\\A\vee F&\equiv A&{\text{Identity for Disjunction}}\\A\wedge A&\equiv A&{\text{Idempotence for Conjunction}}\\A\vee A&\equiv A&{\text{Idempotence for Disjunction}}\\A\wedge (A\vee B)&\equiv A&{\text{Absorption of Disjunction by Conjunction}}\\A\vee (A\wedge B)&\equiv A&{\text{Absorption of Conjunction by Disjunction}}\\A\wedge \lnot A&\equiv F&{\text{Complimentation for Conjunction}}\\A\vee \lnot A&\equiv T&{\text{Complimentation for Disjunction}}\\\lnot (A\wedge B)&\equiv \lnot A\vee \lnot B&{\text{Demorgan's Law (Negation of Conjunction)}}\\\lnot (A\vee B)&\equiv \lnot A\wedge \lnot B&{\text{Demorgan's Law (Negation of Disjunction)}}\\\end{aligned}}$

Tautologies (Another Notation)

All of the above rules are tautologies as the left and right sides are logically equivalent. Which ones have a left or right side which is already a tautology or contradiction on its own? Hint no truth tables needed, its right in the rules.

Extra Practise

If you want more practise, try looking up rules of inference online and prove these rules using truth tables. Depending on the resource you find, you may have to learn other notations (like those common in philosophy) before you can practise.

Suggested Resources

Truth tables can be checked using Wolfram Alpha online. Logic Calculator with Example Check it out. We'll be using this tool to check our work often.

Next Topics

Set Theory

Boolean Algebra

Digital Circuits