Scribd
Upload
0 views2 pages

Logical Equivalence s

Uploaded by

sojiakai

The document outlines key concepts in Discrete Mathematics, specifically focusing on logical equivalences, implications, and set identities. It includes various laws such as double negation, commutative, associative, distributive, and DeMorgan's laws, along with logical implications like Modus Ponens and Modus Tollens. Additionally, it presents set identities that illustrate fundamental operations with sets, including identity, domination, and absorption laws.

Copyright:

© All Rights Reserved
Download as PDF, TXT or read online from Scribd
Download as pdf or txt

Logical Equivalence s

Uploaded by

sojiakai
0 views2 pages
The document outlines key concepts in Discrete Mathematics, specifically focusing on logical equivalences, implications, and set identities. It includes various laws such as double negation, commutative, associative, distributive, and DeMorgan's laws, along with logical implications like Modus Ponens and Modus Tollens. Additionally, it presents set identities that illustrate fundamental operations with sets, including identity, domination, and absorption laws.

Copyright

© © All Rights Reserved

Available Formats

PDF, TXT or read online from Scribd

Did you find this document useful?

Is this content inappropriate?

The document outlines key concepts in Discrete Mathematics, specifically focusing on logical equivalences, implications, and set identities. It includes various laws such as double negation, commutative, associative, distributive, and DeMorgan's laws, along with logical implications like Modus Ponens and Modus Tollens. Additionally, it presents set identities that illustrate fundamental operations with sets, including identity, domination, and absorption laws.

Copyright:

© All Rights Reserved
Download as PDF, TXT or read online from Scribd
Download as pdf or txt
0 views2 pages

Logical Equivalence s

Uploaded by

sojiakai
The document outlines key concepts in Discrete Mathematics, specifically focusing on logical equivalences, implications, and set identities. It includes various laws such as double negation, commutative, associative, distributive, and DeMorgan's laws, along with logical implications like Modus Ponens and Modus Tollens. Additionally, it presents set identities that illustrate fundamental operations with sets, including identity, domination, and absorption laws.

Copyright:

© All Rights Reserved
Download as PDF, TXT or read online from Scribd
Download as pdf or txt
You are on page 1/ 2

Computer Science & Engineering 235 – Discrete Mathematics

Logical Equivalences, Implications, Inferences, and Set Identities

1. ¬(¬p) ⇐⇒ p Double Negation


2.a. (p ∨ q) ⇐⇒ (q ∨ p) Commutative Laws
2.b. (p ∧ q) ⇐⇒ (q ∧ p)
2.c. (p ↔ q) ⇐⇒ (q ↔ p)
3.a. [(p ∨ q) ∨ r] ⇐⇒ [p ∨ (q ∨ r)] Associative Laws
3.b. [(p ∧ q) ∧ r] ⇐⇒ [p ∧ (q ∧ r)]
4.a. [p ∨ (q ∧ r)] ⇐⇒ [(p ∨ q) ∧ (p ∨ r)] Distributive Laws
4.b. [p ∧ (q ∨ r)] ⇐⇒ [(p ∧ q) ∨ (p ∧ r)]
5.a. (p ∨ p) ⇐⇒ p Idempotent Laws
5.b. (p ∧ p) ⇐⇒ p
6.a. (p ∨ 0) ⇐⇒ p Identity Laws
6.b. (p ∨ 1) ⇐⇒ 1
6.c. (p ∧ 0) ⇐⇒ 0
6.d. (p ∧ 1) ⇐⇒ p
7.a. (p ∨ 1) ⇐⇒ 1 Domination Law
7.b. (p ∧ 0) ⇐⇒ 0
8.a. ¬(p ∨ q) ⇐⇒ (¬p ∧ ¬q) DeMorgan’s Laws
8.b. ¬(p ∧ q) ⇐⇒ (¬p ∨ ¬q)
8.c. (p ∨ q) ⇐⇒ ¬(¬p ∧ ¬q)
8.d. (p ∧ q) ⇐⇒ ¬(¬p ∨ ¬q)
9. (p → q) ⇐⇒ (¬q → ¬p) Contrapositive
10.a. (p → q) ⇐⇒ (¬p ∨ q) Implication
10.b. (p → q) ⇐⇒ ¬(p ∧ ¬q)
11.a. (p ∨ q) ⇐⇒ (¬p → q)
11.b. (p ∧ q) ⇐⇒ ¬(p → ¬q)
12.a. [(p → r) ∧ (q → r)] ⇐⇒ [(p ∨ q) → r]
12.b. [(p → q) ∧ (p → r)] ⇐⇒ [p → (q ∧ r)]
13. (p ↔ q) ⇐⇒ [(p → q) ∧ (q → p)] Equivalence
14. [(p ∧ q) → r] ⇐⇒ [p → (q → r)] Exportation Law
15. (p → q) ⇐⇒ [(p ∧ ¬q) → c] Reductio ad Absurdum
16. (p ⊕ q) ≡ (p ∧ ¬q) ∨ (¬p ∧ q) Exclusive Or
17.a. p ∨ (p ∧ q) ≡ p Absorption Laws
17.b. p ∧ (p ∨ q) ≡ p

Table 1: Logical Equivalences

1
1. p ⇒ (p ∨ q) Addition
2. (p ∧ q) ⇒ p Simplification
3. (p → c) ⇒ ¬p Absurdity
4. [p ∧ (p → q)] ⇒ q Modus Ponens
5. [(p → q) ∧ ¬q] ⇒ ¬p Modus Tollens
6. [(p ∨ q) ∧ ¬p] ⇒ q Disjunctive Syllogism
7. p ⇒ [q → (p ∧ q)]
8.a. [p ↔ q) ∧ (q ↔ r)] ⇒ (p ↔ r) Transitivity
8.b. [p → q) ∧ (q → r)] ⇒ (p → r)
9.a. (p → q) ⇒ [(p ∨ r) → (q ∨ r)]
9.b. (p → q) ⇒ [(p ∧ r) → (q ∧ r)]
9.c. (p → q) ⇒ [(p → r) → (q → r)]
10.a. [(p → q) ∧ (r → s)] ⇒ [(p ∨ r) → (q ∨ s)] Constructive Dilemmas
10.b. [(p → q) ∧ (r → s)] ⇒ [(p ∧ r) → (q ∧ s)]
11.a. [(p → q) ∧ (r → s)] ⇒ [(¬q ∨ ¬s) → (¬p ∨ ¬r)] Destructive Dilemmas
11.b. [(p → q) ∧ (r → s)] ⇒ [(¬q ∧ ¬s) → (¬p ∧ ¬r)]

Table 2: Logical Implications

A∪∅=A Identity Laws


A∩U =A
A∪U =U Domination Laws
A∩∅=∅
A∪A=A Idempotent Laws
A∩A=A
(A) = A Complementation Law
A∪B =B∪A Commutative Laws
A∩B =B∩A
A ∪ (B ∪ C) = (A ∪ B) ∪ C Associative Laws
A ∩ (B ∩ C) = (A ∩ B) ∩ C
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) Distributive Laws
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
A∪B =A∩B De Morgan’s Laws
A∩B =A∪B
A ∪ (A ∩ B) = A Absorption Laws
A ∩ (A ∪ B) = A
A∪A=U Complement Laws
A∩A=∅

Table 3: Set Identities

You might also like