﻿ 1.9 Logical transformations

### 1.9 Logical transformations

#### Disjunctive normal form

By using equivalence schemes, a formula can be transformed into another formula, completely different in appearance, which is logically equivalent to the first. Logically equivalent formulas have the same meaning – if the propositional letters in them are interpreted in a certain way (the same letters with the same sentences), the sentences obtained will express the same thing. The process of logical transformation is done by repeatedly replacing parts of the formula with logically equivalent parts based on certain equivalence schemes (the replaced part may be the entire formula). The principle of substitution of equivalents ensures that such substitutions produce formulas that are logically equivalent to the initial one. For example, on the basis of the equivalence scheme that in 1.8 Natural deduction we called material implication (α→β ⟺ ¬α∨β) we may transform

 (1) [¬p→(q→¬r)] → ¬(q∧r)

into one of the following three formulas: “¬[¬p→(q→¬r)]∨¬(qr)”, “[¬¬p∨(q→¬r)]→¬(qr)” or “[¬p→(¬q∨¬r)]→¬(qr)”. The first of these is obtained by replacing (1) as a whole (i.e. (1) is logically equivalent to the first formula based on this equivalence scheme). The second and third are obtained by replacing parts of (1) with logically equivalent formulas based on the same scheme (respectively, “¬p→(q→¬r)” with “¬¬p∨(q→¬r)” and “q→¬r” with “¬q∨¬r”).

If there is a series of such equivalence transformations, it is clear that the formula we will eventually reach will be logically equivalent to the initial one, since each formula will be equivalent to the previous one. For example, starting from (1) we could make the following transformations, each of which replaces a conditional with a formula containing a disjunction and a negation according to the equivalence scheme material implication:

 [¬p→(q→¬r)] → ¬(q∧r) ¬[¬p→(q→¬r)] ∨ ¬(q∧r) ¬[¬¬p∨(q→¬r)] ∨ ¬(q∧r) ¬[¬¬p∨(¬q∨¬r)] ∨ ¬(q∧r)

We may then apply double negation (α ⟺ ¬¬α) replacing “¬¬p” with “p”:

 ¬[p∨(¬q∨¬r)] ∨ ¬(q∧r)

We may then substitute “¬p∧¬(¬q∨¬r)” for “¬[p∨(¬q∨¬r)]” by De Morgan (¬(α∨β) ⟺ ¬α∧¬β):

 [¬p∧¬(¬q∨¬r)] ∨ ¬(q∧r)

De Morgan’s law can be applied one more time to the second conjunction in the brackets – “¬(¬q∨¬r)” can be replaced by “¬¬q∧¬¬r”:

 [¬p ∧ ¬¬q ∧ ¬¬r] ∨ ¬(q∧r)

All main connectives of the first disjunct are conjunctions, which is why we have not put parentheses around “¬¬q∧¬¬r”. Further, we can remove the pairs of negations in front of “q” and “r” by double negation:

 [¬p∧q∧r] ∨ ¬(q∧r)

Finally, applying De Morgan’s law in its other form (¬(α∧β) ⟺ ¬α∨¬β), we replace “¬(qr)” with “¬q∨¬r” obtaining

 (2) [¬p∧q∧r] ∨ ¬q ∨ ¬r

No parentheses around “¬q∨¬r” are needed because it is a disjunction that is connected to the rest of the whole formula by disjunction, i.e. the whole formula is a three-member disjunction. (2) is logically equivalent to the initial formula (1) – “[¬p→(q→¬r)]→¬(qr)”, as it is obtained from it by a series of equivalence transformations. (2) says the same as (1) but for the former it is much easier to see when it would be true and when false. Since it is a disjunction, (2) is true if and only if at least one of its disjuncts is true, which is so when “p” is false and “q” and “r” are true (then “¬pqr” is true), or when “q” is false (then “¬q” is true), or when “r” is false (then “¬r” is true).

(2) is in the so-called disjunctive normal form – a disjunction of conjunctions of propositional letters or negations of propositional letters. Below is a more typical example:

 (q∧r) ∨ (¬p∧¬q∧r) ∨ (s∧¬r)

This is a disjunction with three terms, each of which is a conjunction its members being either propositional letters or negations of propositional letters.

As a borderline case, conjunctions in a disjunctive normal form may have, so to speak, one member, i.e. may not be conjunctions, but single propositional letters or negations of such letters. Such are the following two formulas as well as (2) above:

 r ∨ (q∧s) ∨ ¬p
 ¬r ∨ ¬p

Again as a borderline case, the disjunction in a disjunctive normal form may have, so to speak, one member, i.e. may not be a disjunction of conjunctions (of propositional letters or their negations) but may consist of a single such conjunction. Such is, for example, the following formula:

 p∧q∧¬r∧w

Each formula can be converted to a disjunctive normal form. This is done through the following steps (applied more than once if necessary):

• Remove conditionals and biconditionals by the equivalence schemes of material implication (for conditionals) and material equivalence (for biconditionals):
 α→β ⟺ ¬α∨β ¬(α→β) ⟺ α∧¬β α↔β ⟺ (α∧β)∨(¬α∧¬β) α↔β ⟺ (α→β)∧(β→α)
• Remove negations before parentheses by De Morgan:
 ¬(α∨β) ⟺ ¬α∧¬β ¬(α∧β) ⟺ ¬α∨¬β
• Remove double negations by the equivalence scheme double negation:
 ¬¬α ⟺ α
• Convert conjunctions of disjunctions into disjunctions of conjunctions (the disjunctive normal form is a disjunction of conjunctions) by the following form of the equivalence scheme distribution:
 α∧(β∨γ) ⟺ (α∧β)∨(α∧γ)

Above, we used the convention if the members of a conjunction or a disjunction are more than two, not to group them with parentheses. This is a practice we adhered to in truth-value analysis and truth tables but which we temporarily abounded in natural deduction. For example, under this convention, we write “pqrs” instead of “(pq)∧(rs)”, “p∧[q∧(rs)]”, or any other possible way to group the conjuncts of this conjunction with parentheses. We will proceed similarly with disjunctions.

Now let us transform to disjunctive normal form the following rather complex formula:

 ¬(¬[¬(p→¬q)→¬(r∧p)]∧{[(q∧s)→p]→q})

Applying De Morgan to the whole formula, we obtain:

 ¬¬[¬(p→¬q)→¬(r∧p)] ∨ ¬{[(q∧s)→p]→q}

We remove the double negation before the first disjunct:

 [¬(p→¬q)→¬(r∧p)] ∨ ¬{[(q∧s)→p]→q}

Applying material implication to the second disjunct, we obtain:

 [¬(p→¬q)→¬(r∧p)] ∨ {[(q∧s)→p]∧¬q}

By the other form of material implication, applied to the first disjunct, we get:

 ¬¬(p→¬q) ∨ ¬(r∧p) ∨ {[(q∧s)→p]∧¬q}

We remove the double negation before the first member of the disjunction and apply De Morgan to the second (formally these are two steps):

 (p→¬q) ∨ ¬r ∨ ¬p ∨ {[(q∧s)→p]∧¬q}

By material implication, we decompose the two conditionals to disjunction and negation:

 ¬p ∨ ¬q ∨ ¬r ∨ ¬p ∨ {[¬(q∧s)∨p]∧¬q}

We apply distribution to the last member of the main disjunction. (That the distributed “¬q” stands on the right side of the disjunction in the square brackets is irrelevant – we can imagine it written on the left, since, because of the equivalence scheme commutation, the order of the terms of a conjunction does not matter.)

 ¬p ∨ ¬q ∨ ¬r ∨ ¬p ∨ [¬q∧¬(q∧s)] ∨ (¬q∧p)

We remove the negation before the parentheses in the square brackets using De Morgan:

 ¬p ∨ ¬q ∨ ¬r ∨ ¬p ∨ [¬q∧(¬q∨¬s)] ∨ (¬q∧p)

Applying distribution to the formula in the square brackets, we get:

 ¬p ∨ ¬q ∨ ¬r ∨ ¬p ∨ (¬q∧¬q) ∨ (¬q∧¬s) ∨ (¬q∧p)

The whole expression is now in disjunctive normal form. Let us rearrange the members of the disjunction a little:

 ¬p ∨ ¬p ∨ ¬q ∨ (¬q∧¬q) ∨ ¬r ∨ (¬q∧¬s) ∨ (¬q∧p)

The formula can be simplified continuing to be in disjunctive normal form. We can remove one of the repeating “¬p” by the equivalence scheme tautology (α∨α ⟺ α):

 ¬p ∨ ¬q ∨ (¬q∧¬q) ∨ ¬r ∨ (¬q∧¬s) ∨ (¬q∧p)

We can also remove one of the two “¬q” in “¬q∧¬q” by the other form of the same equivalence scheme (α∧α ⟺ α):

 ¬p ∨ ¬q ∨ ¬q ∨ ¬r ∨ (¬q∧¬s) ∨ (¬q∧p)

Now we can remove one of the two repetitive “¬q”:

 ¬p ∨ ¬q ∨ ¬r ∨ (¬q∧¬s) ∨ (¬q∧p)

The formula can be further simplified. To this end, we are introducing the following equivalence scheme, whose logical validity can be easily verified by a truth table or a truth-value analysis:

 α∨(α∧β) ⟺ α

If we rearrange the members of the disjunction as follows

 ¬p ∨ ¬q ∨ (¬q∧¬s) ∨ (¬q∧p) ∨ ¬r

it becomes clear that using the introduced equivalence scheme the part “¬q∨(¬q∧¬s)” can be replaced by “¬q”, i.e. the disjunct “(¬q∧¬s)” can be eliminated:

 ¬p ∨ ¬q ∨ (¬q∧p) ∨ ¬r

For the same reason, “(¬qp)” can also be cut:

 ¬p ∨ ¬q ∨ ¬r

Now the disjunctive normal form is as simple as possible. It turns out that the initial complex formula does not express anything other than that at least one of the sentences p, q, or r is false!

If the disjunctive normal form we come up with is more complex, it is advisable to arrange the letters in the conjunctions in alphabetical order. This makes it easier to see if there are duplicate expressions, which can lead to simplification. For example, if we have come to the formula

 (q∧p∧¬s) ∨ (p∧q) ∨ (p∧¬s∧q)

by arranging the letters in the conjunctions in alphabetical order, we get the formula

 (p∧q∧¬s) ∨ (p∧q) ∨ (p∧q∧¬s)

that makes it easy to see that the first and last members of the disjunction are the same and therefore one of them can be deleted:

 (p∧q∧¬s) ∨ (p∧q)

In addition, it is readily seen that the second term of the disjunction (“pq”) is part of the first term, and therefore the first term can be deleted by the scheme α∨(α∧β) ⟺ α, so that the expression eventually boils down to “pq”.

In the example before the last, we first converted the initial complex formula to disjunctive normal form and then simplified it. However, simplifications could have been made during the process of transformation to disjunctive normal form. Generally, this is preferable because it makes the conversion to disjunctive normal form much easier. In the example in question, a simplification could have been made as soon as we came to the formula

 ¬p ∨ ¬q ∨ ¬r ∨ ¬p ∨ {[¬(q∧s)∨p]∧¬q}

Here, the last term of the disjunction can be deleted by the scheme α∨(α∧β) ⟺ α, since it is a conjunction of “¬q” and some other formula while there being another occurrence of “¬q” that is a term of the whole disjunction (“¬q” is in the place of α in the scheme and “[¬(qs)∨p]” is in the place of β).

The following is a list of equivalence schemes that may be used for simplifications. They are grouped in pairs and their logical validity can be easily verified by truth tables or truth-value analysis.

 i a) α ∨ α ⟺ α b) α ∧ α⟺ α

 ii a) α ∨ (α∧β)⟺ α b) α ∧ (α∨β)⟺ α

 iii a) α ∨ (β∧¬β)⟺ α (also α ∨ (β∧¬β∧γ) ⟺ α) b) α ∧ (β∨¬β)⟺ α (also α ∧ (β∨¬β∨γ) ⟺ α)

 iv a) α ∨ (¬α∧β)⟺ α ∨ β b) α ∧ (¬α∨β)⟺ α ∧ β

iii a) enables us to delete contradictions of the form β∧¬β or formulas containing such contradictions when they are members of disjunctions, and iii b) enables us to delete tautologies of the form β∨¬β or formulas containing such tautologies when they are members of conjunctions. For example, by iii a) we may eliminate the second, third, and last terms of the following disjunction:

 (p∧q∧r) ∨ (q∧¬q∧r) ∨ (¬p∧q∧p∧r) ∨ (q∧r∧¬s) ∨ (r∧¬r)

Based on iv a), for example in the formula

 (p∧r) ∨ [¬(p∧r)∧q]

we could cut the formula “¬(pr)” along with the conjunction sign that connects it with “q” getting

 (p∧r) ∨ q

Similarly, on the basis of iv b), for example in “pr∧[¬(pr)∨q]” we can delete “¬(pr)” together with the disjunction sign that connects it to “q”, obtaining “prq”.

The same simplifications can be made to formulas of the type ¬α∨(α∧β) and ¬α∧(α∨β), in which the negation is related to the occurrence of the repeating formula that is outside the parentheses rather than inside. The results are ¬α∨β and ¬α∧β respectively, the grounds for the simplifications being again the two schemes iv but with an additional application of double negation because by double negation ¬α∨(α∧β) and ¬α∧(α∨β) are logically equivalent to ¬α∨(¬¬α∧β) and ¬α∧(¬¬α∨β) respectively, and the latter are equivalent to ¬α∨β and ¬α∧β on the basis of iv.

As a further example, let us convert to disjunctive normal form and at the same time simplify the formula “{¬[r∨¬(sp)]∧(s→¬p)}→(rs)”:

 ¬{¬[r∨¬(s→p)]∧(s→¬p)} ∨ (r∧s) Imp ¬¬[r∨¬(s→p)] ∨ ¬(s→¬p) ∨ (r∧s) De M r ∨ ¬(s→p) ∨ ¬(s→¬p) ∨ (r∧s) DN

Here we can delete “rs” as, according to ii a), “r∨(rs)” is equivalent to “r” (since the order of the disjunction’s terms is irrelevant, we can imagine the latter rearranged so that “r” and “rs” stand side by side):

 r ∨ ¬(s→p) ∨ ¬(s→¬p) ii a) r ∨ (s∧¬p) ∨ (s∧¬¬p) Imp (twice) r ∨ (s∧¬p) ∨ (s∧p) DN

The formula is in disjunctive normal form and is much simpler than the initial expression but can be further simplified if we apply distribution in the opposite direction to the one in which we usually apply it:

 r ∨ [s ∧(¬p∨p)] Distr

Now we can eliminate “¬pp” by iii b):

 r ∨ s iii b)

Two of the equivalence schemes used in logical transformation – De Morgan and distribution – are also valid for conjunctions and disjunctions with more than two terms. So far, De Morgan has only been used in these two forms:

 ¬(α∨β) ⟺ ¬α∧¬β ¬(α∧β) ⟺ ¬α∨¬β

However, they can be considered special cases of equivalence schemes valid for conjunctions and disjunctions with any number of members:

 ¬(α∨β∨γ...) ⟺ ¬α∧¬β∧¬γ... ¬(α∧β∧γ...) ⟺ ¬α∨¬β∨¬γ...

That these equivalence schemes are logically valid is evident from the truth conditions of the logical connectives of disjunction and conjunction. Whatever the number of its terms, a disjunction is true if and only if at least one of them is true. So, its negation will be true if and only if none of them is true. In turn, a conjunction is true if and only if each of its terms is true. So, its negation will be true if and only if at least one of them is not true.

Distribution has so far been used in one of these two forms:

 α∧(β∨γ) ⟺ (α∧β)∨(α∧γ) α∨(β∧γ) ⟺ (α∨β)∧(α∨γ)

If in (α∨β)∧(γ∨δ) α∨β is distributed in γ∨δ according to the first equivalence scheme, we obtain

 [(α∨β)∧γ] ∨ [(α∨β)∧δ]

Now, if the same form of distribution is applied to the expressions in the two pairs of square brackets, we get:

 (α∧γ) ∨ (β∧γ) ∨ (α∧δ) ∨ (β∧δ)

Shifting the two middle members of the disjunction, we get:

 (α∧γ) ∨ (α∧δ) ∨ (β∧γ) ∨ (β∧δ)

Thereby we have proven the validity of the following extended form of distribution:

 (α∨β) ∧ (γ∨δ) ⟺ (α∧γ) ∨ (α∧δ) ∨ (β∧γ) ∨ (β∧δ)

(The scheme is analogous to the distributive law in arithmetic: if we imagine disjunction as addition and conjunction as multiplication, each member in the first pair of parentheses is combined with each in the second.)

It is quite similarly shown that the extended variant of the other form of distribution is also valid:

 (α∧β) ∨ (γ∧δ) ⟺ (α∨γ) ∧ (α∨δ) ∧ (β∨γ) ∧ (β∨δ)

(If we again imagine disjunction as addition and conjunction as multiplication, this is not valid in arithmetic.)

As an example of using the extended forms of De Morgan and distribution, let us convert to disjunctive normal form and simplify the following formula:

 ¬[¬(p∧q∧r)→(r∧p)] ∧ (p→s)

First, we break down the two conditionals:

 ¬(p∧q∧r) ∧ ¬(r∧p) ∧ (¬p∨s)

Then we apply De Morgan twice (once in its extended form):

 (¬p∨¬q∨¬r) ∧ (¬r∨¬p) ∧ (¬p∨s)

Here we can delete the conjunction’s first term (“¬p∨¬q∨¬r”) by ii b), since its second term (“¬r∨¬p”) is a part of it (“¬r∨¬p” corresponds to α in ii b) and “¬q” to β):

 (¬r∨¬p) ∧ (¬p∨s)

Appling distribution in its expanded form:

 (¬r∧¬p) ∨ (¬r∧s) ∨ (¬p∧¬p) ∨ (¬p∧s)

We remove one of the repetitive “¬p” in the third term:

 (¬r∧¬p) ∨ (¬r∧s) ∨ ¬p ∨ (¬p∧s)

Appling ii a) to the last two terms results in the elimination of the last term:

 (¬r∧¬p) ∨ (¬r∧s) ∨ ¬p

Appling ii a) again (this time to “¬r∧¬p” and “¬p”), we delete the first term of the disjunction thus maximally simplifying the formula:

 (¬r∧s) ∨ ¬p

In order to transform an expression to disjunctive normal form, it is sufficient to use only this form of distribution: α∧(β∨γ) ⟺ (α∧β)∨(α∧β). However, for the sake of simplification it is sometimes appropriate to use its other form – α∨(β∧γ) ⟺ (α∨β)∧(α∨β). Here is an example:

 [q→(p→s)] ∧ [(p→s)∨q] [¬q∨(p→s)] ∧ [(p→s)∨q] (p→s) ∨ (¬q∧q) p → s ¬p ∨ s

In the transition from the second to the third line, we have used distribution not in the direction normally used in the transformation to disjunctive normal form (“ps” is in the place of α in the scheme). This makes it possible in the next line to delete the contradiction “¬qq” on the basis of iii a).

We can use logical transformations to prove that or check if two expressions are logically equivalent. They are such if they can be converted to the same expression (perhaps in disjunctive normal form).

In addition, we may use logical transformations to prove that, or check if, an expression is a tautology. If a member of a disjunction is the negation of another of its members, i.e. if the disjunction contains α∨¬α, then it is a tautology. For a disjunctive normal form this means that one of its members is a propositional letter and the other is its negation. For example, it is clear that “(p∧¬r)∨s∨¬s” is a tautology as “s∨¬s” always has the value T, thus making the entire disjunction always true (a tautology). Of course, if we want to know if an expression is a tautology through logical transformations and come to a formula that is obviously a tautology without being in disjunctive normal form, we do not need to continue with the transformations. For example, this would be the case if it has the form α→α, α↔α, or is a disjunction containing α∨¬α.

Practice shows that in most cases converting a formula to disjunctive normal form is easiest if the transformations are made so to speak from the outside in, i.e. when we first transform the formula as a whole, then its main parts, then the parts of those parts, etc., rather than in the opposite direction or arbitrarily.

Unlike the disjunctive normal form, which is a disjunction of conjunctions of propositional letters or their negations, the conjunctive normal form is a conjunction of disjunctions of propositional letters or their negations. Here are examples of formulas in conjunctive normal form:

 (q∨r) ∧ (¬p∨¬q∨r) ∧ (s∨¬r) r ∧ (q∨s) ∧ ¬p p ∨ q ∨ r ∨ ¬w ¬r ∧ p

When simpler, a formula can be in both disjunctive and conjunctive normal form. This is the case with the last two formulas above. The formula before the last can be regarded as a conjunctive normal form with one single member (the whole disjunction) or as a disjunctive normal form with four members – each a propositional letter or a negation of a propositional letter. The last formula can be regarded as a conjunctive normal form with two members (a propositional letter and a negation thereof) and as a disjunctive normal form with a single member (the whole conjunction).

Any formula of propositional logic can be reduced to conjunctive normal form. The equivalence schemes through which this is done are the same as in the reduction to disjunctive normal form, except that, as a rule, the following form of distribution is used, which converts disjunctions into conjunctions:

 α ∨ (β∧γ) ⟺ (α∨β) ∧ (α∨γ)

or its extended version

 (α∧β) ∨ (γ∧δ) ⟺ (α∨γ) ∧ (α∨δ) ∧ (β∨γ) ∧ (β∨δ)

Furthermore, when the main logical connective is biconditional, it is more convenient to eliminate the latter by this version of material equivalence:

 α ↔ β ⟺ (α→β) ∧ (β→α)

rather than by

 α ↔ β ⟺ (α∧β) ∨ (¬α∧¬β)

since the subsequent elimination of the two conditionals results in an expression of the form (¬α∨β)∧(¬β∨α), which is a conjunction of disjunctions (not a disjunction of conjunctions as is the right hand side of the second equivalence scheme).

As an example, let us reduce to conjunctive normal form the formula

 ¬(p∨r) ↔ [q→(r∧¬s)]

First, we eliminate the biconditional in the way suggested above – we convert the formula into a conjunction of conditionals and then eliminate the conditionals too:

 {¬(p∨r)→[q→(r∧¬s)]} ∧ {[q→(r∧¬s)]→¬(p∨r)} {¬¬(p∨r) ∨ [q→(r∧¬s)]} ∧ {¬[q→(r∧¬s)] ∨ ¬(p∨r)}

We remove the double negation, convert the two conditionals into disjunctions, and apply De Morgan’s law to the formula “¬(pr)”:

 [p ∨ r ∨ ¬q ∨ (r∧¬s)] ∧ {[q∧¬(r∧¬s)] ∨ (¬p∧¬r)}

We delete “r∧¬s” in the first main term by ii a) and apply De Morgan and double negation in the second:

 (p ∨ r ∨ ¬q) ∧ {[q∧(¬r∨s)] ∨ (¬p∧¬r)}

We apply distribution in the second main term distributing “¬p∧¬r” into “q∧(¬rs)”:

 (p ∨ r ∨ ¬q) ∧ [(¬p∧¬r) ∨ q] ∧ [(¬p∧¬r) ∨ ¬r ∨ s]

By ii a), we delete “¬p∧¬r” in the last term:

 (p ∨ r ∨ ¬q) ∧ [(¬p∧¬r) ∨ q] ∧ (¬r ∨ s)

Finally, we apply distribution to the second term distributing “q” in “¬p∧¬r”:

 (p ∨ r ∨ ¬q) ∧ (q ∨ ¬p) ∧ (q ∨ ¬r) ∧ (¬r ∨ s)

The formula is already in conjunctive normal form. To see if it can be further simplified, we rearrange the members of the disjunctions in alphabetical order:

 (p ∨ ¬q ∨ r) ∧ (¬p ∨ q) ∧ (q ∨ ¬r) ∧ (¬r ∨ s)

None term contains another, so no shortenings can be made by ii b) – this is the simplest conjunctive normal form we can get by our rules.

Like reduction to disjunctive normal form, reduction to conjunctive normal form can be used to see if two formulas are logically equivalent. In addition, it can be used to show that a formula is a contradiction. This will be the case if the conjunction obtained contains as members a propositional letter and its negation. For example, the formula “(p∨¬r)∧s∧¬s” is a contradiction because of its part “s∧¬s”. Of course, if we are interested in whether a formula is a contradiction and in the process of transformation it gets the form of an obvious contradiction before it is in conjunctive normal form, we need not proceed further. For example, we do not need to reduce the formula

 p ∧ ¬q ∧ ¬[q∨(¬r∧p)] ∧ [q∨(¬r∧p)]

to the conjunctive normal form to make sure it is contradictory, since its last two terms “¬[q∨(¬rp)]∧[q∨(¬rp)]” is of the form ¬α∧α making the whole conjunction always false.

 (1) For each formula, determine whether it is in disjunctive normal form, in conjunctive normal form, in both, or in neither.
 1) s ∨ ¬q ∨ s ∨ ¬r 2) (¬p∧r) ∨ (q∧¬q) ∨ s 3) (r∨¬q) ∧ ¬p ∧ (q∨¬(r∨q)∨¬s) 4) ¬q ∨ ¬(p∧q) ∨ (¬r∧q) 5) ¬r ∧ q ∧ ¬s ∧ r 6) ¬q ∨ (¬r∧s∧p) ∨ ¬r 7) q ∧ (r∨¬s∨¬p) ∧ ¬r 8) ¬(r∧q) ∨ (¬p∧q) ∨ r 9) (p∧¬q∧r) ∨ p ∨ ¬q ∨ r 10) (p∧q) ∨ (p∧¬q) ∨ ¬(p∧q) ∨ (¬p∧¬q)
 (2) Convert the following formulas to disjunctive normal form and simplify them as much as possible:
 1) (p∧¬p∧q) ∨ [q∧(q∨r)] ∨ q 2) ¬q → {¬p ∧ [q∨(¬p∧¬q)]} 3) ¬[¬(q→r)∨(r∧q)] ∨ ¬(p→q) 4) ¬q → {(r→q) → ¬[¬r∧(¬q∨¬p)]} 5) (p↔q) ∧ (q↔r) 6) (¬p→q) ∧ (¬p→¬q) 7) ¬{[p∧(p→q)]→(q∧¬r)} → q 8) [(p∧¬q)∨¬p] → ¬[(r∨q)→¬q] 9) s ↔ (q∧r) 10) (p∧q) ↔ (q→r) 11) [(r→¬s)→r] ∧ {(r∧s)∨[¬r→¬(p→q)]} 12) (p∧¬r∧p) ∨ {[(q→q)→(p→q)] → q} 13) (p↔q) → (r↔q) 14) [p∧¬(s→q)] ∨ [(p∨q)∧(s∨p)] ∨ (s∧¬q) 15) [(p→q)→p] ↔ ¬p 16) [(p→q)→q] ∧ ¬(p→¬q) 17) {¬[r∨¬(s→p)] ∧ (s→¬p)} → (r∧s) 18) p → [q↔(r∧s)] 19) ¬(¬r→¬{q∨¬[p∨¬(q∨r)]}) 20) p ↔ (r↔q)
 (3) Determine by logical transformations if the following pairs of formulas are logically equivalent.
 1) ¬(¬p→q) ¬(¬q→p)
 2) (p→q) → ¬p ¬p ∧ ¬q
 3) (p→q) ∨ (r→q) r → (p→q)
 4) p → (¬q∧r) (p→¬q) ∧ (p→r)
 5) (p∨q) ∧ ¬(p∧q) p ↔ ¬q
 6) p → [(p∧¬q)→r] r ∨ q ∨ ¬p
 7) (p∧¬q) → r ¬r → (¬p∨q)
 8) (p∧q) → (r∧s) [(p∨q)→s] ∧ [¬r→(¬q∧¬p)]
 9) ¬p ∧ ¬q ∧ ¬r ∧ ¬s ¬(¬p→s) ∧ ¬(¬q→r)
 (4) Determine by logical transformations which of the following five sentences are logically equivalent:
 1) John will take to drinking, if he gets fired or Mary leaves him. 2) John will take to drinking, if he gets fired, or he will take to drinking if Mary leaves him. 3) John will take to drinking, if he gets fired and Mary leaves him. 4) John will take to drinking if he gets fired, but he will also take to drinking if Mary leaves him. 5) If John gets fired, then if Mary leaves him, he will take to drinking.
 (5) Prove by logical transformations that the following formulas are tautologies.1
 1) ¬(p∨q) → ¬p 2) (p→q) → [(r∨p)→(r∨q)] 3) [p∨(q∧¬r)] → [(p∨q)∧(r→p)] 4) [(p→q)∧(r→s)] → [(p∨r)→(q∨s)] 5) ¬p → ¬(p∧q) 6) ¬p → [(p→q)∨q] 7) [p∧(q∨r)] → [(p∧q)∨(p∧r)] 8) [(p→q)∨r] → ¬[(p∧¬q)∧¬r]

1. The formulas are the same as in exercise (1) from 1.4 Indirect proof. You can compare the two methods.