Logics in Computer Science (CoSc3141)
CHAPTER TWO
PROPOSITIONAL LOGIC (PART II)
2.6. Derivation rules for propositional logic
To test whether a wff P1∧P2∧P3∧ … ∧Pn → Q is a tautology, we could build a truth table or use
algorithm Tautology Test. Instead, we will turn to formal logic, which uses a system of derivation
rules that manipulate wffs in a truth-preserving manner. You begin with the hypotheses P1, P2, P3,
…, Pn (assumed true) and attempt to apply the manipulation rules in such a way as to end up with
the conclusion Q (which must then also be true because truth is preserved under the rules).
Definition: Proof sequence
A proof sequence is a sequence of wffs in which each wff is either a hypothesis or the result of
applying one of the formal system’s derivation rules to earlier wffs in the sequence.
Using formal logic to prove that Q is a valid conclusion from P1, P2, P3, …, Pn, we must produce
a proof sequence of the form:
P1 (hypothesis)
P2 (hypothesis)
.
.
Pn (hypothesis)
wff1 (obtained by applying a derivation rule to earlier wffs)
wff2 (obtained by applying a derivation rule to earlier wffs)
.
.
Q (obtained by applying a derivation rule to earlier wffs)
The derivation rules for propositional logic fall into two categories, equivalence rules and
inference rules. Equivalence rules allow individual wffs to be rewritten, while inference rules allow
new wffs to be derived from previous wffs in the proof sequence.
Equivalence rules: states that certain pairs of wffs R and S are equivalent (equivalency is
discussed under chapter one).
If R ≡ S, then R ↔ S is a tautology and that S can be substituted for R in any wff with no change
to the truth value of that wff. Equivalence rules are, therefore, truth-preserving; a true wff remains
true if such a substitution is done within it.
1 of 10 Kotebe Metropolitan University Department of Computer Science
Logics in Computer Science (CoSc3141)
The following table lists the equivalence rules we will use in our formal system for propositional
logic, (Additional rules could be formulated based on other tautologies).
Equivalence Rules
Expression Equivalent to Name/Abbreviation for Rule
P ∨Q Q ∨P Commutative - comm
P ∧Q Q ∧P
( P∨Q ) ∨R P ∨ (Q ∨R ) Associative - ass
( P ∧Q ) ∧R P ∧ (Q ∧R )
(P ∨Q)′ P′ ∧Q′ De Morgan’s Laws - De
(P ∧Q)′ P′ ∨Q′ Morgan
P→Q P′ ∨Q Implication - imp
P (P′)′ Double negation - dn
P↔Q (P → Q) ∧ (Q → P) Definition of equivalence - equ
For example: Suppose that one hypothesis of a propositional argument can be symbolized as
(A′ ∨B′ ) ∨C
Then a proof sequence for the argument could begin with the following steps:
1. ( A′ ∨B′ ) ∨C hyp (hypothesis)
2. ( A∧B )′ ∨C 1, De Morgan
3. ( A∧B ) → C 2, imp
The justification given for each step is not a required part of the proof sequence, but it does confirm
that the step is a legitimate one. Step 1 is a hypothesis. Step 2 is derived from step 1 by applying
one of De Morgan’s Laws. Step 3 is derived from step 2 by using the implication rule that P → Q
is equivalent to P′ ∨Q, where P is the wff A ∧B, and Q is the wff C.
The equivalence rules allow substitution in either direction. That is, in the above example we
replaced A′ ∨B′ with (A ∧B)′, but in some other proof sequence, using the same rule, we might
replace (A ∧B)′ with A′ ∨B′.
Notice that in the above example and table, the symbol ′ (apostrophe) is used for the negation
instead of ¬.
Inference rules: says that if one or more wffs that match the first part of the rule pattern are already
part of the proof sequence, we can add to the proof sequence a new wff that matches the last part
of the rule pattern.
2 of 10 Kotebe Metropolitan University Department of Computer Science
Logics in Computer Science (CoSc3141)
You have seen how to test the validity of arguments by using truth tables. But in practice, testing
the validity of an argument using a truth table becomes more difficult as the number of component
statements increases. Therefore, in such cases, we are forced to use the formal proof. The formal
proof regarding the validity of an argument relies on logical rules called rules of inferences. A
formal proof consists of a sequence of finite statements comprising the premises and the
consequence of the premises called the conclusion. The presence of each statement must be
justified by a rule of inferences. It is obvious that we repeatedly apply these rules to justify the
proof of complex arguments. Below are a few examples of some of these rules together with their
classical names.
1. Modes Ponens (mp): P, P → Q ├ Q
2. Modes Tollens (mt): ¬Q,P→Q├¬P
3. Conjunction (con): P, Q ├ P ∧ Q
4. Simplification (sim ): P ∧ Q ├ P, Q
5. Addition (add): P ├ P ∨ Q
6. Hypothetical Syllogism (hs): P → Q, Q → R ├ P → R
7. Disjunctive Syllogism (ds): ¬ P, P ∨ Q ├ Q
Unlike equivalence rules, inference rules do not work in both directions. We cannot “reverse” the
addition rule in above (#5); from P ∨Q, we cannot infer either P or Q.
For example, suppose that A → (B ∧C ) and A are two hypotheses of an argument. A proof
sequence for the argument could begin with the following steps:
1. A → (B ∧C ) hyp
2. A hyp
3. B ∧C 1, 2, mp
The justification at step 3 is that steps 1 and 2 exactly match the pattern required for modus
ponens, where P is A and Q is B ∧C. Modus ponens says that Q can be derived from P and P ∧Q.
3 of 10 Kotebe Metropolitan University Department of Computer Science
Logics in Computer Science (CoSc3141)
Example1: Using propositional logic, prove that the argument
A ∧ (B→ C) ∧ [ ( A ∧B ) → ( D ∨C′ ) ] ∧B → D is valid.
We must produce a proof sequence that begins with the hypotheses and ends with the conclusion.
There are four hypotheses, so this gives us lots of “ammunition” to use in the proof. The beginning
of the proof is easy enough because it just involves listing the hypotheses:
1. A hyp
2. B → C hyp
3. ( A∧B ) → ( D ∨C′ ) hyp
4. B hyp
Our final goal is to arrive at D, the conclusion. But without even looking ahead, there are a couple
of fairly obvious steps we can take that may or may not be helpful.
5. C 2, 4, mp
6. A ∧B 1, 4, con
7. D ∨C′ 3, 6, mp
At least at this point we have introduced D, but it’s not by itself. Note that from step 5 we have C,
which we haven’t made use of. Now, look at the form of step 7; it’s a disjunction, and the
implication rule says that we can transform a disjunction of a certain form into an implication. The
disjunction must have a negated wff on the left. We can do that:
8. C′ ∨D 7, comm
9. C → D 8, imp, so
10. D 5, 9, mp
Example 2:- Use propositional logic to prove: (A′ ∨B) ∧ (B → C ) → (A → C ). The following
proof sequence will do.
1. A′ ∨B hyp
2. B → C hyp
3. A → B 1, imp
4. A → C 2, 3, hs
4 of 10 Kotebe Metropolitan University Department of Computer Science
Logics in Computer Science (CoSc3141)
Without use of the new rule, we could still have produced a proof sequence by essentially proving
the new rule as part of this proof:
1. A′ ∨B hyp
2. B → C hyp
3. A → B 1, imp
4. A hyp
5. B 3, 4, mp
6. C 2, 5, mp
Additional rules thus can shorten proof sequences but at the expense of having to remember
additional rules! Other additional rules are the following.
Exercise! Using propositional logic, prove the validity of the argument.
[(A∨B′) → C ] ∧( C → D ) ∧ A → D
2.7 Deduction Method
Suppose the argument we seek to prove has the form
P1∧P2∧P3∧ … ∧Pn → (R → S)
where the conclusion is itself an implication. Instead of using P1 ,P2 , P3 , … , Pn as the hypotheses
and deriving R → S, the deduction method lets us add R as an additional hypothesis and then derive
S. In other words, we can instead prove
P1∧P2∧P3∧ … ∧Pn∧R → S
This change is to our advantage because it gives us one more hypothesis, i.e., additional
ammunition for the proof, and it simplifies the desired conclusion. The deduction method approach
agrees with our understanding of implication. For example, use propositional logic to prove:
[ A → ( A→ B ) ] → ( A → B )
Using the deduction method, we get two hypotheses instead of one, and we want to derive B.
1. A → ( A→ B ) hyp
2. A hyp
5 of 10 Kotebe Metropolitan University Department of Computer Science
Logics in Computer Science (CoSc3141)
3. A → B 1, 2, mp
4. B 2, 3, mp
Exercise: Use propositional logic to prove the validity of the following argument using deduction
method.
(A → B) ∧ (B→ C) → (A → C)
2.8. Verbal arguments
An argument in English that consists of simple statements can be tested for validity by a two-step
process:
i. Symbolize the argument using propositional wffs.
ii. Prove that the argument is valid by constructing a proof sequence for it using the
derivation rules for propositional logic.
The first step, translating the argument from verbal to symbolic form, is often the most difficult.
Look for keys in the verbal representation of the argument. “If… then” and “either… or” indicate
implication and disjunction, respectively. A period (or sometimes a semicolon) signifies the end
of a hypothesis. The separate hypotheses are joined by conjunctions. “Therefore” is a big key
word; it indicates the end of the hypotheses and announces that the conclusion is about to be stated.
For example, consider the argument, “If interest rates drop, the housing market will improve.
Either the federal discount rate will drop or the housing market will not improve. Interest rates will
drop. Therefore, the federal discount rate will drop.” Using
I - Interest rates drop.
H - The housing market will improve.
F - The federal discount rate will drop.
the argument is
(I → H) ∧ (F ∨H′) ∧ I → F
A proof sequence to establish validity is
1) I → H hyp
2) F ∨H′ hyp
3) I hyp
6 of 10 Kotebe Metropolitan University Department of Computer Science
Logics in Computer Science (CoSc3141)
4) H′ ∨F 2, comm
5) H → F 4, imp
6) I → F 1, 5, hs
7) F 3, 6, mp
2.9. Normal forms of Propositional Logic
2.9.1. Definition of terms
➢ Propositional variables are also referred as atoms.
➢ literal is either an atom or its negation
➢ A clause is an expression (formula) formed from a finite collection of literals (atoms or
their negations) that is true either whenever at least one of the literals that form it is true (a
disjunctive clause, the most common use of the term), or when all of the literals that form
it are true (a conjunctive clause, a less common use of the term). That is, it is a finite
disjunction or conjunction of literals, depending on the context.
2.9.2. Negation Normal Form(NNF)
A formula is in NNF if ¬ appears only in front of the propositional variables. For every formula F
there is another formula F′ in NNF so that F ≡ F′. However, there are negations hidden inside →
and ↔. In practice, these symbols are also expected to be removed while producing NNF.
For example:
In NNF: ¬ A ∧¬ B
Not in NNF: ¬ (A ∨B )
Any formula can be transformed into an equivalent formula in NNF. To convert to NNF, apply the
following rules as long as possible.
Step 1: Eliminate bi-implications: (F ↔ G ) ≡ (F → G ) ∧ (G → F )
Step 2: Eliminate implications: (F → G ) ≡ (¬F ∨G )
Step 3: Push negations downward: ¬ (F ∧G ) ≡ (¬F ∨¬G )
¬ (F ∨G ) ≡ (¬F ∧¬G )
Step 4: Eliminate multiple negations: ¬ ¬ F ≡ F
For example, converting the formula (¬ (A ∧ ¬ B )∧C ) to its NNF will involve the following steps
(¬ (A ∧ ¬ B )∧C )
≡ ((¬A ∨ ¬ ¬ B )∧C )
≡ ((¬A ∨B )∧C )
7 of 10 Kotebe Metropolitan University Department of Computer Science
Logics in Computer Science (CoSc3141)
Remember the following equivalences in normal forms of a propositional logic.
P → Q ≡ ¬ P ∨Q
P→Q≡¬Q→¬P
P → ( Q→ R ) ≡ (P ∧Q ) → R
P → ( Q→ R ) ≡ (P → Q ) → ( Q → R )
P ↔ ¬ Q ≡ ¬ (P ↔ Q )
P ↔ ( Q↔ P ) ≡ Q
P ↔ Q ≡ (P → Q )∧( Q → P )
P ↔ Q ≡ (P ∧Q )∨ (¬ P ∧¬ Q )
P ↔ Q ≡ (P ∨¬ Q )∧ (¬ P ∨Q )
2.9.3. Conjunctive Normal Form (CNF)
A formula is in conjunctive normal form (CNF) if it is a conjunction of one or more clauses, where
a clause is a disjunction of literals. A formula is in conjunctive normal form (CNF) if it is a
conjunction of disjunctions of literals. CNF is an AND of ORs. The only propositional connectives
a formula in CNF can contain are and, or, and not. The not operator can only be used as part of a
literal, which means that it can only precede a propositional variable or a predicate symbol.
For example, all of the following formulas in the variables A, B, C, D, E, and F are in conjunctive
normal form:
i. ( A∨¬ B ∨¬ C ) ∧ (¬ D ∨E ∨F )
ii. ( A∨B ) ∧C
iii. A ∨B
iv. A
The third formula is in conjunctive normal form because it is viewed as a "conjunction" with just
one conjunct, namely the clause A ∨B. Incidentally, the last two formulas are also in disjunctive
normal form. The following formulas are not in conjunctive normal form:
¬ ( B∨C ), since an OR is nested within a NOT
( A∧B ) ∨C
A ∧( B∨ ( C ∧D )), since an AND is nested within an OR
8 of 10 Kotebe Metropolitan University Department of Computer Science
Logics in Computer Science (CoSc3141)
Every formula can be equivalently written as a formula in conjunctive normal form. In particular,
this is the case for the three non-examples just mentioned; they are respectively equivalent to the
following three formulas, which are in conjunctive normal form:
(¬B ∧¬C )
( A∨C) ∧ (B ∨C)
A ∧( B∨D) ∧(B ∨E )
Every propositional formula can be converted into an equivalent formula that is in CNF. This
transformation is based on rules about logical equivalences: the double negative law, De Morgan's
laws, and the distributive law.
To convert to CNF, apply the following rules as long as possible.
Step 1: Eliminate bi-implications: (F ↔ G ) ≡ (F → G ) ∧ (G → F )
Step 2: Eliminate implications: (F → G ) ≡ (¬F ∨G )
Step 3: Push negations downward: ¬ (F ∧G ) ≡ (¬F ∨¬G ), ¬ (F ∨G ) ≡ (¬F ∧¬G )
Step 4: Eliminate multiple negations: ¬ ¬ F ≡ F
Step 5: Push disjunctions downward: (F ∧G )∨H ≡ (F ∨H ) ∧ (G ∨H )
For example, consider ( p→ ( ¬ q ∧r )) ∧ (p → ¬ q), then the following steps converts to CNF
≡ ( (¬ p ∨ ¬ q ) ∧ (¬ p ∨r )) ∧ (¬ p ∨ ¬ q)
≡ (¬ p ∨ ¬ q )∧ (¬ p ∨r ) ∧ (¬ p ∨ ¬ q)
Exercise!
Convert the following formulas into CNF
i. ¬ ((p → q) → ((q → r ) → (p → r )))
ii. (p → ( ¬ q → r )) ∧ (p → ¬ q) → (p → r )
2.9.4. Disjunctive Normal Form (DNF)
A disjunctive normal form (DNF) is a standardization (or normalization) of a logical formula
which is a disjunction of conjunctive clauses; it can also be described as an OR of ANDs. A logical
formula is considered to be in DNF if and only if it is a disjunction of one or more conjunctions of
one or more literals. As in conjunctive normal form (CNF), the only propositional operators in
9 of 10 Kotebe Metropolitan University Department of Computer Science
Logics in Computer Science (CoSc3141)
DNF are and, or, and not. The not operator can only be used as part of a literal, which means that
it can only precede a propositional variable. For example, all of the following formulas are in DNF:
i. ( A∧¬ B ∧¬ C ) ∨ (¬ D ∧E ∧F )
ii. ( A∧B ) ∨C
iii. A ∧B
iv. A
However, the following formulas are not in DNF:
¬ ( B∨C ), since an OR is nested within a NOT
A ∨( B∧ ( C ∨D )), since an OR is nested within an AND
Converting a formula to DNF involves using logical equivalences, such as the double negative
elimination, De Morgan's laws, and the distributive law.
To convert to CNF, apply the following rules as long as possible.
Step 1: Eliminate bi-implications: (F ↔ G ) ≡ (F → G ) ∧ (G → F )
Step 2: Eliminate implications: (F → G ) ≡ (¬F ∨G )
Step 3: Push negations downward: ¬ (F ∧G ) ≡ (¬F ∨¬G )
¬ (F ∨G ) ≡ (¬F ∧¬G )
Step 4: Eliminate multiple negations: ¬ ¬ F ≡ F
Step 5: Push conjunctions downward: (F∨G )∧H ≡ (F ∧H ) ∨ (G ∧H )
Assignment Two
1. Show that the following arguments are valid or fallacy. (2PTS)
a. If I am wealthy, then I am happy. I am happy. Therefore, I am wealthy.
b. If John drinks beer, he is at least 18 years old. John does not drink beer. Therefore,
John is not yet 18 years old.
2. Using propositional logic, prove the validity of the argument. (4PTS)
a. [( A∨B′ ) → C ] ∧( C → D ) ∧A → D
b. S→R∧ (P∨ Q) → ¬R∧ (¬S) → (¬Q→R) ∧P → Q
3. Convert the following formulas into CNF.(4PTS)
a. ¬ ((p → q) → ((q → r ) → (p → r )))
b. (p → ( ¬ q → r )) ∧ (p → ¬ q) → (p → r )
10 of 10 Kotebe Metropolitan University Department of Computer Science
