discrete mathematics precedence of logical operators

efinition of De Morgan’s law:

The complement of the union of two sets is equal to the intersection of their complements and the complement of the intersection of two sets is equal to the union of their complements. These are called De Morgan’s laws.

For any two finite sets A and B;

(i) (A U B)' = A' ∩ B' (which is a De Morgan's law of union).

(ii) (A ∩ B)' = A' U B' (which is a De Morgan's law of intersection).



Proof of De Morgan’s law: (A U B)' = A' ∩ B'

Let P = (A U B)' and Q = A' ∩ B'

Let x be an arbitrary element of P then x ∈ P ⇒ x ∈ (A U B)'

⇒ x ∉ (A U B)

⇒ x ∉ A and x ∉ B

⇒ x ∈ A' and x ∈ B'

⇒ x ∈ A' ∩ B'

⇒ x ∈ Q

Therefore, P ⊂ Q …………….. (i)

Again, let y be an arbitrary element of Q then y ∈ Q ⇒ y ∈ A' ∩ B'

⇒ y ∈ A' and y ∈ B'

⇒ y ∉ A and y ∉ B

⇒ y ∉ (A U B)

⇒ y ∈ (A U B)'

⇒ y ∈ P

Therefore, Q ⊂ P …………….. (ii)

Now combine (i) and (ii) we get; P = Q i.e. (A U B)' = A' ∩ B'



Proof of De Morgan’s law: (A ∩ B)' = A' U B'

Let M = (A ∩ B)' and N = A' U B'

Let x be an arbitrary element of M then x ∈ M ⇒ x ∈ (A ∩ B)'

⇒ x ∉ (A ∩ B)

⇒ x ∉ A or x ∉ B

⇒ x ∈ A' or x ∈ B'

⇒ x ∈ A' U B'

⇒ x ∈ N

Therefore, M ⊂ N …………….. (i)

Again, let y be an arbitrary element of N then y ∈ N ⇒ y ∈ A' U B'

⇒ y ∈ A' or y ∈ B'

⇒ y ∉ A or y ∉ B

⇒ y ∉ (A ∩ B)

⇒ y ∈ (A ∩ B)'

⇒ y ∈ M

Therefore, N ⊂ M …………….. (ii)

Now combine (i) and (ii) we get; M = N i.e. (A ∩ B)' = A' U B'


Examples on De Morgan’s law:

1. If U = {j, k, l, m, n}, X = {j, k, m} and Y = {k, m, n}.

Proof of De Morgan's law: (X ∩ Y)' = X' U Y'.

Solution:

We know, U = {j, k, l, m, n}

X = {j, k, m}

Y = {k, m, n}

(X ∩ Y) = {j, k, m} ∩ {k, m, n}

= {k, m}

Therefore, (X ∩ Y)' = {j, l, n} ……………….. (i)

Again, X = {j, k, m} so, X' = {l, n}

and Y = {k, m, n} so, Y' = {j, l}

X' ∪ Y' = {l, n} ∪ {j, l}

Therefore, X' ∪ Y' = {j, l, n} ……………….. (ii)

Combining (i)and (ii) we get;

(X ∩ Y)' = X' U Y'. Proved



2. Let U = {1, 2, 3, 4, 5, 6, 7, 8}, P = {4, 5, 6} and Q = {5, 6, 8}.
Show that (P ∪ Q)' = P' ∩ Q'.

Solution:

We know, U = {1, 2, 3, 4, 5, 6, 7, 8}

P = {4, 5, 6}

Q = {5, 6, 8}

P ∪ Q = {4, 5, 6} ∪ {5, 6, 8}

= {4, 5, 6, 8}

Therefore, (P ∪ Q)' = {1, 2, 3, 7} ……………….. (i)

Now P = {4, 5, 6} so, P' = {1, 2, 3, 7, 8}

and Q = {5, 6, 8} so, Q' = {1, 2, 3, 4, 7}

P' ∩ Q' = {1, 2, 3, 7, 8} ∩ {1, 2, 3, 4, 7}

Therefore, P' ∩ Q' = {1, 2, 3, 7} ……………….. (ii)

Combining (i)and (ii) we get;

(P ∪ Q)' = P' ∩ Q'

1. SEMINOR
ON
•Precedence of Logical Operators
•Logical Equivalences
•De Morgan’s Laws

2. Precedence of Logical Operators
•Asinarithmetic,anorderingisimposedontheuseoflogical
operatorsincompoundpropositions
•Wewillgenerallyuseparenthesestospecifytheorderinwhich
logicaloperatorsinacompoundpropositionaretobeapplied.
pqr(p)(q(r))
•To avoid unnecessary parenthesis, the following precedences hold:
1.Negation ()
2.Conjunction ()
3.Disjunction ()
4.Implication ()
5.Biconditional ()

3. Logical Equivalences:
•Definition:Compound propositions that have the same truth values
in all possible cases are called logically equivalent.
•Propositions pand qare logically equivalentif pqis a tautology.
•Informally, p and q are equivalent if whenever p is true, q is true, and vice
versa
•Notation: p q(pis equivalent to q), p q, and p q
•Alert: is not a logical connective

4. Logical Equivalences:
•Are the propositions (p q) and (pq) logically equivalent?
•To find out, we construct the truth tables for each:
p q pq ppq
0 0
0 1
1 0
1 1
The two columns in the truth table are identical, thus we conclude that
(p q) (pq)
Example

5. Important equivalences
•In these equivalences, T denotes the compound proposition that is always
true and F denotes the compound proposition that is always Logical
Equivalences.
Identity laws
p ∧T ≡ p Identity laws
p ∨F ≡ p
Domination laws
p ∨T ≡ T
p ∧F ≡ F
Idempotent laws
p ∨p ≡ p
p ∧p ≡ p
Double negation law
¬(¬p) ≡ p
Commutative laws
p ∨q ≡ q ∨p
p ∧q ≡ q ∧p

6. Associative laws
(p ∨q) ∨r ≡ p ∨(q ∨r)
(p ∧q) ∧r ≡ p ∧(q ∧r)
Distributive laws
p ∨(q ∧r) ≡ (p ∨q) ∧(p ∨r)
p ∧(q ∨r) ≡ (p ∧q) ∨(p ∧r)
De Morgan’s laws
¬(p ∧q) ≡ ¬p ∨¬q
¬(p ∨q) ≡ ¬p ∧¬q
Absorption laws
p ∨(p ∧q) ≡ p
p ∧(p ∨q) ≡ p
Negation laws
p ∨¬p ≡ T
p ∧¬p ≡ F

7. Using Logical Equivalences:
Show that (qp) (pq) q
0. (qp) (pq)
1.(qp) (pq) Implication Law
2.(qp) (pq) De Morgan’s
& Double negation
3. (qp) (qp) Commutative Law
4.q(pp) Distributive Law
5.q1 Identity Law
q Identity Law
Example

8. Involving Conditional Statements.
•p → q ≡ ¬p ∨q
•p → q ≡ ¬q → ¬p
•p ∨q ≡ ¬p → q
•p ∧q ≡ ¬(p → ¬q)
•¬(p → q) ≡ p ∧¬q
•(p → q) ∧(p → r) ≡ p → (q ∧r)
•(p → r) ∧(q → r) ≡ (p ∨q) → r
•(p → q) ∨(p → r) ≡ p → (q ∨r)
•(p → r) ∨(q → r) ≡ (p ∧q) → r

9. Biconditional Statements.
•p ↔ q ≡ (p → q) ∧(q → p)
•p ↔ q ≡ ¬p ↔ ¬q p ↔ q ≡ (p ∧q) ∨(¬p ∧¬q)
•¬(p ↔ q) ≡ p ↔ ¬q

10. De Morgan’s Laws
•The two logical equivalences known as De Morgan’s laws are particularly
important. They tell us how to negate conjunctions and how to negate
disjunctions.
•In particular, the equivalence
•¬(p ∨q) ≡ ¬p ∧¬q tells us that the negation of a disjunction is formed by
taking the conjunction of the negations of the component propositions.
Similarly, the equivalence ¬(p ∧q) ≡ ¬p ∨¬q tells us that the negation of a
conjunction is formed by taking the disjunction of the
•negations of the component propositions. Example 5 illustrates the use of
De Morgan’s laws.

11. EXAMPLE 5
UseDeMorgan’slawstoexpressthenegationsof“Miguelhasacellphone
andhehasalaptopcomputer”and“HeatherwillgototheconcertorSteve
willgototheconcert.”
Solution:
•Letpbe“Miguelhasacellphone”andqbe“Miguelhasalaptop
computer.”
•Then“Miguelhasacellphoneandhehasalaptopcomputer”canbe
representedbyp∧q.
•BythefirstofDeMorgan’slaws,¬(p∧q)isequivalentto¬p∨¬q.
•Consequently,wecanexpressthenegationofouroriginalstatementas
“Migueldoesnothaveacellphoneorhedoesnothavealaptopcomputer.”
•Letrbe“Heatherwillgototheconcert”andsbe“Stevewillgotothe
concert.”
•Then“HeatherwillgototheconcertorStevewillgototheconcert”can
berepresentedbyr∨s.
•BythesecondofDeMorgan’slaws,¬(r∨s)isequivalentto¬r∧¬s.
•Consequently,wecanexpressthenegationofouroriginalstatementas
“HeatherwillnotgototheconcertandStevewillnotgototheconcert.”