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
into one of the following three formulas: “¬[¬p→(q→¬r)]∨¬(q∧r)”,
“[¬¬p∨(q→¬r)]→¬(q∧r)” or “[¬p→(¬q∨¬r)]→¬(q∧r)”.
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”:
We may then substitute “¬p∧¬(¬q∨¬r)” for “¬[p∨(¬q∨¬r)]”
by De Morgan (¬(α∨β) ⟺ ¬α∧¬β):
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:
Finally, applying De Morgan’s law in its other form (¬(α∧β) ⟺ ¬α∨¬β), we replace
“¬(q∧r)” with “¬q∨¬r” obtaining
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)]→¬(q∧r)”, 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 “¬p∧q∧r” 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:
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:
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
“p∧q∧r∧s” instead of “(p∧q)∧(r∧s)”,
“p∧[q∧(r∧s)]”, 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:
For the same reason, “(¬q∧p)” can also be cut:
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:
In addition, it is readily seen that the second term of the disjunction (“p∧q”)
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 “p∧q”.
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
“[¬(q∧s)∨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
we could cut the formula “¬(p∧r)” along with the conjunction sign that
connects it with “q” getting
Similarly, on the basis of iv b), for example in
“p∧r∧[¬(p∧r)∨q]” we can delete “¬(p∧r)” together
with the disjunction sign that connects it to “q”, obtaining “p∧r∧q”.
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∨¬(s→p)]∧(s→¬p)}→(r∧s)”:
|
¬{¬[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 “r∧s” as, according to ii a), “r∨(r∧s)”
is equivalent to “r” (since the order of the disjunction’s terms is irrelevant, we can imagine the
latter rearranged so that “r” and “r∧s” 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:
Now we can eliminate “¬p∨p” by 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 β):
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:
Appling ii a) again (this time to “¬r∧¬p” and “¬p”), we delete the first
term of the disjunction thus maximally simplifying the formula:
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 (“p→s” is
in the place of α in the scheme). This makes it possible in the next line to delete the contradiction
“¬q∧q” 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.
Conjunctive normal form
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
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 “¬(p∨r)”:
|
[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∧(¬r∨s)”:
|
(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∨(¬r∧p)]∧[q∨(¬r∧p)]” is of the form ¬α∧α
making the whole conjunction always false.
Exercises
(Download the exercises as a PDF file.)
|
(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.
|
|
3)
|
(p→q) ∨ (r→q)
|
|
r → (p→q)
|
|
4)
|
p → (¬q∧r)
|
|
(p→¬q) ∧ (p→r)
|
|
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)
|
¬(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]
|
