Chapter 1.2 discrete math

This note covers fundamental logical concepts, including:

De Morgan's Laws

There are two main laws for negating compound statements:

1. Negation of AND: $\neg(p \land q) \equiv (\neg p) \lor (\neg q)$

   • "Not (both)" is equivalent to "At least one is not."

2. Negation of OR: $\neg(p \lor q) \equiv (\neg p) \land (\neg q)$

   • "Not (either)" is equivalent to "Neither."

These laws demonstrate how negating a conjunction (AND) produces a disjunction (OR) of negations, and vice-versa.

Tautologies and Contradictions

1. Tautology (t): A statement that is always true, regardless of its components' truth values. Example:
   $p \lor \neg p$

2. Contradiction (c): A statement that is always false, regardless of its components' truth values. Example:
   $p \land \neg p$

Key equivalences related to tautologies and contradictions:

• $p \land t \equiv p$

• $p \lor t \equiv t$

• $p \land c \equiv c$

• $p \lor c \equiv p$

Conditional Statements and Contrapositives

1. Conditional Statement: Expressed as $p \rightarrow q$ ("if p, then q").

   • It is logically equivalent to $\neg p \lor q$

   • It is only false when p is true and q is false (the promise is broken).

2. Contrapositive: The contrapositive of $p \rightarrow q$ is $\neg q \rightarrow \neg p$ ("if not q, then not p").

   • A conditional statement and its contrapositive are logically equivalent.

Logical Equivalence ($\equiv$)

The symbol $\equiv$ means "logically equivalent," indicating that two statements always have the same truth values in all possible scenarios (i.e., identical truth tables).

Area of Application

This refers to the real-world field or context where a logical principle or statement makes sense and can be applied (e.g., law enforcement, medicine, personal growth).