Logical Operators

Introduction

Logical operators: fundamental tools in discrete mathematics. Facilitate construction, manipulation, and evaluation of propositions. Enable formal reasoning and proof development. Basis for digital logic, computer science, and mathematical logic.

"Logic is the anatomy of thought." -- John Locke

Basic Logical Operators

Conjunction (AND)

Symbol: ∧. Operation: true if both operands true, else false. Usage: combines statements requiring simultaneous truth.

Disjunction (OR)

Symbol: ∨. Operation: true if at least one operand true, else false. Inclusive by default in classical logic.

Negation (NOT)

Symbol: ¬. Operation: inverts truth value. True becomes false and vice versa. Unary operator.

Implication (Conditional)

Symbol: →. Operation: false only if antecedent true and consequent false. Otherwise true. Expresses "if...then" statements.

Biconditional (If and Only If)

Symbol: ↔. Operation: true if both operands have same truth value. Expresses equivalence.

Truth Tables

Definition and Purpose

Tabular representation of operator output for all input combinations. Basis for evaluating logical expressions.

Truth Table for Conjunction

Truth Table for Implication

Logical Equivalences

Definition

Two statements logically equivalent if identical truth values under all valuations. Foundation for simplifying logical expressions.

De Morgan's Laws

Negation of conjunction and disjunction:

¬(P ∧ Q) ≡ ¬P ∨ ¬Q¬(P ∨ Q) ≡ ¬P ∧ ¬Q

Other Equivalences

Idempotent: P ∧ P ≡ P, P ∨ P ≡ PCommutative: P ∧ Q ≡ Q ∧ P, P ∨ Q ≡ Q ∨ PAssociative: (P ∧ Q) ∧ R ≡ P ∧ (Q ∧ R), (P ∨ Q) ∨ R ≡ P ∨ (Q ∨ R)

Compound Statements

Definition

Statements formed by combining propositions with logical operators. Evaluate overall truth based on operator semantics.

Construction

Use parentheses to clarify order. Example: (P ∨ Q) ∧ ¬R.

Evaluation

Apply truth tables recursively to subcomponents.

Implication and Biconditional

Implication (Conditional)

Symbol: →. Meaning: "If P then Q". False only if P true and Q false. Called material implication.

Biconditional

Symbol: ↔. True when both operands share truth value. Expresses logical equivalence.

Contrapositive

Contrapositive of P → Q is ¬Q → ¬P. Logically equivalent to original implication.

Negation

Definition

Unary operator. Inverts truth values. ¬P true if P false, false if P true.

Double Negation

¬(¬P) ≡ P. Negating twice restores original statement.

Interaction with Other Operators

Via De Morgan's laws, negation distributes over conjunction and disjunction with inversion.

Boolean Algebra

Overview

Algebraic structure modeling logical operators. Set of elements with operations ∧, ∨, ¬ satisfying axioms.

Axioms

Commutativity, associativity, distributivity, identity, complements.

Application

Simplifies logical expressions. Basis for digital circuit design.

Applications of Logical Operators

Mathematical Proofs

Construct hypotheses, conclusions, and deductions.

Computer Science

Programming conditionals, control flow, database queries.

Digital Electronics

Logic gates implement operators physically. Design of circuits and processors.

Common Operator Properties

Commutativity

P ∧ Q ≡ Q ∧ P, P ∨ Q ≡ Q ∨ P

Associativity

(P ∧ Q) ∧ R ≡ P ∧ (Q ∧ R), (P ∨ Q) ∨ R ≡ P ∨ (Q ∨ R)

Distributivity

P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R), P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)

Formal Proof Techniques

Direct Proof

Assume premises true, derive conclusion using logical operators.

Proof by Contradiction

Assume negation of conclusion, derive contradiction.

Proof by Contrapositive

Prove contrapositive statement instead of direct implication.

Limitations and Boundaries

Classical Logic Constraints

Truth-functional: operators depend only on truth values, not content.

Non-classical Logics

Modal, intuitionistic logics modify or reject some classical operator rules.

Expressive Limits

Cannot capture notions like belief, uncertainty, or vagueness without extensions.

References

• Enderton, H. B., A Mathematical Introduction to Logic, Academic Press, Vol. 1, 2001, pp. 1-320.
• Rosen, K. H., Discrete Mathematics and Its Applications, McGraw-Hill, 7th Ed., 2012, pp. 45-110.
• Boolos, G. S., Burgess, J. P., & Jeffrey, R. C., Computability and Logic, Cambridge University Press, 5th Ed., 2007, pp. 50-130.
• Huth, M., & Ryan, M., Logic in Computer Science: Modelling and Reasoning about Systems, Cambridge University Press, 2nd Ed., 2004, pp. 23-90.
• Stoll, R. R., Set Theory and Logic, Dover Publications, 2012, pp. 100-150.