Scribd
Upload
5 views3 pages

Logic Connectives and Simplification Guide

The document outlines basic logical connectives including negation, conjunction, disjunction, implication, and biconditional, along with their relationships and simplification rules. It provides detailed negation equivalences and simplification techniques, including identity, domination, and absorption laws. Additionally, several worked examples illustrate the application of these concepts in simplifying logical expressions.

Uploaded by

Adeel Bhatti
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views3 pages

Logic Connectives and Simplification Guide

The document outlines basic logical connectives including negation, conjunction, disjunction, implication, and biconditional, along with their relationships and simplification rules. It provides detailed negation equivalences and simplification techniques, including identity, domination, and absorption laws. Additionally, several worked examples illustrate the application of these concepts in simplifying logical expressions.

Uploaded by

Adeel Bhatti
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Handout: Connectives, Negation, and Simplification in

Logic

1. Basic Connectives
• Negation (¬p): “Not p”

• Conjunction (p ∧ q): “p and q”

• Disjunction (p ∨ q): “p or q”

• Implication (p → q): “If p, then q”

• Biconditional (p ↔ q): “p if and only if q”

2. How They Are Connected


• p ∧ q: True only if both are true.

• p ∨ q: True if at least one is true.

• p → q: Equivalent to (¬p ∨ q).

• p ↔ q: Equivalent to (p → q) ∧ (q → p).

3. Negations
¬(p ∧ q) ≡ (¬p ∨ ¬q)
¬(p ∨ q) ≡ (¬p ∧ ¬q)
¬(p → q) ≡ (p ∧ ¬q)
¬(p ↔ q) ≡ (p ∧ ¬q) ∨ (¬p ∧ q)

1
4. Simplification Rules

p∧T ≡p p∨F ≡p (Identity)


p∨T ≡T p∧F ≡F (Domination)
p∨p≡p p∧p≡p (Idempotent)
¬(¬p) ≡ p (Double Negation)
p∨q ≡q∨p p∧q ≡q∧p (Commutative)
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r) (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) (Associative)
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) (Distributive)
¬(p ∧ q) ≡ (¬p ∨ ¬q) ¬(p ∨ q) ≡ (¬p ∧ ¬q) (De Morgan)
p ∨ (p ∧ q) ≡ p p ∧ (p ∨ q) ≡ p (Absorption)
p → q ≡ (¬p ∨ q) (Implication)
¬(p → q) ≡ (p ∧ ¬q) (Negation of Implication)
p ∧ ¬p ≡ F p ∨ ¬p ≡ T (Contradiction/Tautology)

5. Worked Examples
Example 1
Simplify (p ∨ q) ∧ (p ∨ ¬q).
(p ∨ q) ∧ (p ∨ ¬q) ≡ p ∨ (q ∧ ¬q) Distributive
≡p∨F Complement
≡p Identity

Example 2
Simplify (p ∧ q) ∨ (p ∧ ¬q).
(p ∧ q) ∨ (p ∧ ¬q) ≡ p ∧ (q ∨ ¬q) Distributive
≡p∧T Excluded Middle
≡p Identity

Example 3
Simplify ¬(p → q) ∨ (r ∧ ¬r).
¬(p → q) ∨ (r ∧ ¬r) ≡ ¬(¬p ∨ q) ∨ (r ∧ ¬r) Implication
≡ (p ∧ ¬q) ∨ (r ∧ ¬r) De Morgan
≡ (p ∧ ¬q) ∨ F Complement
≡ p ∧ ¬q Identity

2
Example 4
Simplify (p → q) ∧ (p → ¬q) ∧ p.

(p → q) ∧ (p → ¬q) ∧ p ≡ (¬p ∨ q) ∧ (¬p ∨ ¬q) ∧ p Implication


≡ (¬p ∨ (q ∧ ¬q)) ∧ p Distributive
≡ (¬p ∨ F ) ∧ p Complement
≡ ¬p ∧ p Identity
≡F Contradiction

Example 5
Simplify ¬(p ∨ (q ∧ ¬r)) ∨ (p ∧ r).

¬(p ∨ (q ∧ ¬r)) ∨ (p ∧ r) ≡ (¬p ∧ ¬(q ∧ ¬r)) ∨ (p ∧ r) De Morgan


≡ (¬p ∧ (¬q ∨ r)) ∨ (p ∧ r) De Morgan
≡ (¬p ∧ ¬q) ∨ (¬p ∧ r) ∨ (p ∧ r) Distributive
≡ (¬p ∧ ¬q) ∨ ((¬p ∨ p) ∧ r) Factor r
≡ (¬p ∧ ¬q) ∨ (T ∧ r) Excluded Middle
≡ (¬p ∧ ¬q) ∨ r Identity

You might also like