Formal Logic
Introduction
In this section we will consider the topic of Propositional Calculus, which is a formal system in which propositions can be formed by combining atomic propositions using logical connectives, and in which a system of formal proof rules establishes certain formulae as "theorems" [1].
Logic is fundamental to all theoretical computer science. It has applications in Artificial Intelligence, Relational Databases, and will assist in better understanding programming language syntax, computability, and logic programming.
This section has the following content:
* Operations
* * Negation
* * Conjunction
* * Disjunction
* * Exclusive Or
* Arguments
* * Conditional
* * Biconditional
* * Converse, Contrapositive and Inverse
* * Tautologies and Contradictions
* * Normal Forms
* Analysis
* * Analysis through Truth Tables
* * Contradiction and Consistency
* Laws of Propositional Calculus
* * Negation introduction
* * Negation elimination
* * Double negative elimination
* * Conjunction introduction
* * Conjunction elimination
* * Disjunction introduction
* * Disjunction elimination
* * Biconditional introduction
* * Biconditional elimination
* * Modus ponens (conditional elimination)
* * Conditional proof (conditional introduction)
*Proofs
Operations
The basic operations in Propositional Calculus are:
- NOT, or Negation
- AND, or Conjuction
- OR, or Disjunction
Negation ¬
Negation of a statement inverts the value of the statement in the following ways:
p | ¬p
------------
T | F
F | T
In the above table, we can see that the operation is very straight forward. True, when negated, becomes False. And False, when negated, become True.
Conjunction ∧
The conjunction (also known as AND) of two statements is the intersection of their values. For example, if p and q are statements, then the conjunction of p and q would look like this:
p | q | p ∧ q
----------------------
T | T | T
T | F | F
F | T | F
F | F | F
Thus, only when both p and q are True, does the conjunction of p and q resolve to True.
Disjunction ∨
The disjunction (also known as OR) of two statements is the union of their values. For example, if p and q were statements, then the disjunction of p and q would be as follows:
p | q | p ∨ q
----------------------
T | T | T
T | F | T
F | T | T
F | F | F
Notice that when at least one of the statements is True, the disjunction resolves to True, and only when both terms are False, does the disjunction resolve to False.
Exclusive Disjunction ⊕
The disjunction is by its very nature, inclusive, as it resolves to True if either statement are True, or if both are true. However, if we need to make sure that one and only one of the statements is True, then we use the Exclusive Disjunction (also known as Exclusive OR or XOR). If p and q are each statements, then the exclusive disjunction of p and q is as follows:
p | q | p ⊕ q
--------------------------
T | T | F
T | F | T
F | T | T
F | F | F
Notice here that only where either p is false and q is true, or q is false and p is true, does the exclusive disjunction resolve as True.
Arguments
An argument is in the form:
p1, p2, p3, p4, ..., pm {operator} c
Where p1, p2 and so on are one or more premises. The operator could be a conditional, biconditional, tautology or some other operator which we will discuss below. Then c is the conclusion.
The set of statements before the operator has many interchangeable names: - Antecedent - Conjunction of statements - Hypothesis - Premises
Conditional ==>
When one statement's value is dependant on the value of another statement, we indicate this with the conditional ( ==> ), and we read it as "implies". Thus p ==> q is read as "p implies q". In this example, the statements to the left of the conditional, in this case p, is referred to as the hypothesis, and the statements to the right of the conditional, in this case q, as the conclusion. The Truth table for "p ==> q" is as follows:
p | q | p ==> q
--------------------------
T | T | T
T | F | F
F | T | T
F | F | T
Notice here that the argument resolves to True when q is True, or when both p and q are equivalent.
Biconditional <==>
When there is a bi-directional conditional relationship, in other words, p is conditional on q which is conditional on p, we use the biconditional <==>. This is read as "if and only if". Thus p <==> q is read as "p, if and only if, q".
Note: Sometimes "if and only if" is written in the short-hand "iff".
The Truth table for the Biconditional relationship of two statements is as follows:
p | q | p <==> q
--------------------------
T | T | T
T | F | F
F | T | F
F | F | T
Note here that the biconditional only resolves to True when both statements are equivalent.
Terminology
Before continuing too far with Propositional Calculus, it is important to keep the following terminology in mind:
- Implication: The natural argument, p ==> q
- Converse: The reversal of the argument, q ==> p
- Contrapositive: The complete negation of the converse, ¬q ==> ¬p
- Inverse: The complete negation of the implication, ¬p ==> ¬q
Tautologies and Contradictions
A tautology is a statement that is always Frue. For example:
p ∨ ¬p
This will always resolve to True. Let's prove this through the use of a Truth table:
p | ¬p | p ∨ ¬p
-------------------------------
T | F | T
F | T | T
Notice here that the argument always resolves as True, which is the characteristic of a tautology.
A contradiction is a statement that is always False.For example:
p ∧ ¬p
This will always resolve to True. Let's prove this through the use of a Truth table:
p | ¬p | p ∧ ¬p
-------------------------------
T | F | F
F | T | F
Notice here that the argument always resolves as False, which is the characteristic of a contradiction.
Note: A set of statements ( p1, p2, p3, ..., pm) is inconsistent if a contradiction can be drawn as a valid consequence of this set.
Normal Forms
DNF and CNF are very useful forms for use in proving theorems. We use various laws and equivalences to convert arguments into DNF or CNF for use in proofs.
Disjunctive Normal Form (DNF)
Disjunctive Normal Form (DNF) is a sequence of disjunctions ( ∨ ), where each disjunction is made up of conjunctions ( ∧ ) of one or more literals.
Examples of DNF:
(p ∧ q) ∨ (p ∧ ¬r)
(a ∧ b) ∨ (c ∧ ¬d ∧ e) ∨ (¬ f ∧ g) ∨ (h ∧ ¬j)
Conjunctive Normal Form (CNF)
Conjunctive Normal Form (CNF) is a sequence of conjunctions ( ∧ ), where each conjunction is made up of disjunctions ( ∨ ) of one or more literals.
Examples of CNF:
(p ∨ q) ∧ (p ∨ ¬r)
(a ∨ b ∨ c ∨ ¬d ∨ e) ∧ (¬ f ∨ g) ∧ (h ∨ i)
Analysis
Analysis through Truth Tables
When we have an argument we wish to analyze, one method is through the use of Truth tables. There are three steps to take when performing analysis in this manner:
- Step 1: Translate the hypothesis and the conclusion into symbolic form.
- Step 2: Write the truth table for the hypothesis and the conclusion.
- Step 3: Determine if all the hypotheses are true and the conclusion false. If this is the case, the argument is invalid. Otherwise, the argument is valid.
Note: An argument is invalid only when there is a situation where all the premises/hypotheses are true, but the conclusion is false.
Let's consider an example:
Description: If it does not rain or if it is not foggy then the regatta will be held and the lifeboat demonstration will go on. If the regatta is held then the trophy will be awarded.
Step 1: Translate into symbolic form
-----------------------------------------------------
let p be "It rains"
let q be "It is foggy"
let r be "The regatta will be held"
-> ¬p ∧ ¬q ==> r
Step 2: Write the Truth Table
-------------------------------------------
p | q | r | ¬p ∧ ¬q | ¬p ∧ ¬q ==> r
------------------------------------------------------
T | T | T | F | T
T | T | F | F | T
T | F | T | F | T
T | F | F | F | T
F | T | T | F | T
F | T | F | F | T
F | F | T | T | T
F | F | F | T | F
In the above truth table, we see that the argument is valid, as the situation does not exist where all premises are true and the conclusion is false.
Laws of Propositional Calculus
One of the main uses of a propositional calculus is to determine relations of logical equivalence between propositional formulae. These relationships are determined by means of the laws of propositional calculus. The laws are combined in sequences to produce proofs. We will now take a look at the more common of these laws of Propositional Calculus.
Rules of Replacement
Conjunction introduction
Law:
premise: p
premise: q
infer: p ∧ q
If we have the need to introduce a conjunction, such as when we are attempting to achieve DNF or CNF (see Normal forms above), we use the law of Conjunction Introduction to deduce p ∧ q given p and given q.
Conjunction elimination
Law:
premise: p ∧ q
infer: p
premise: p ∧ q
infer: q
If we need to simplify a conjunction into a single parameter, we can use the law of Conjunction elimination. Thus, if we have p ∧ q, we can simplify that into either p or q.
Disjunction introduction
Law:
premise: p
infer: p ∨ q
Here, we can produce a disjunction from a single term using the law of Disjunction Introduction. This is useful if we are trying to achieve DNF or CNF (see Normal forms above).
Disjunction elimination
Law:
premise: p ∨ q
premise: p ==> r
premise: q ==> r
infer: r
We are able to simplify a disjunction if both parameters in the disjunction imply a third value (r). Thus, if we have (p ∨ q), p ==> r, q ==> r, then we can simplify p ∨ q into r.
Biconditional introduction
Law:
premise: p ==> q
premise: q ==> p
infer: p <==> q
If we have the situation where both p implies q as well as q implies p, then we can simplify this into a single statement of p if and only if (iff) q, thus introducing a biconditional.
Biconditional elimination
Law:
premise: p <==> q
infer: p ==> q
infer: q ==> p
If we need to decompile a biconditional statement into two imply statements, we can use the law of Biconditional Elimination to convert p iff q into p implies q, q implies p.
Modus ponens (conditional elimination)
Law:
premise: p
premise: p ==> q
infer: q
This strangely named law is used to infer a tautology for q and remove a condition statement where we have p implies q and the tautology p.
Conditional proof (conditional introduction)
Law:
premise: q
infer: p ==> q
infer: p
This is the corollary of modus ponens. From the tautology q, we can introduce the conditional statement p implies q as well as the additional tautology p.
Rules of Inference
Negation introduction
Law:
premise: p ==> q
premise: p ==> ¬q
infer: ¬p
So if we know that p implies q and if we also know that p implies not-q, then from that information we can infer, or deduce not p using the law of Negation Introduction.
Negation elimination
Law:
premise: ¬p
infer: p ==> r
If we need to remove a negative statement, we can do so by introducing an additional parameter, (r), such that p implies r, given the premise not p.
Double negative elimination
Law:
premise: ¬¬p
infer: p
As is the case in algebra with double negatives, when we have NOT(NOT(p)), we can remove the double negative and be left with just p.
Proofs
To construct a proof, we string together Propositional Logic Laws. Each line in the proof, by convention, is numbered with sequential numbers starting from 1. Next to each step we justify the progression with the name of the law being used.
Example:
Prove that : A implies A
Proof:
1 A premise
2 A ∨ A From (1) by disjunction introduction
3 (A ∨ A) ∧ A From (1) and (2) by conjunction introduction
4 A From (3) by conjunction elimination
5 A ==> A Summary of (1) through (4)
6 A From (5) by conditional proof
Exercises
A. Construct Truth Tables for
- ¬(p ∧ q)
- ¬(p ∨ q) ∧ ¬(q ∨ p)
- (p ==> q) ∧ (q ==> r) ==> (p ==> r)
B. Prove that "it rained", given that
- If it does not rain or if it is not foggy, then the regatta will be held and the lifeboat demonstration will go on.
- If the regatta is held then the trophy will be awarded.
- The trophy was not awarded.
C. Determine if the following arguments are valid.
- All birds are mammals and the platypus is a bird. Therefore, the platypus is a mammal.
- Blodwin works hard. If Blodwin works hard then she is a dull girl. If Blodwin is a dull girl she will not get the job. Therefore Blodwin will not get the job.