[Discrete Mathematics] Logic and Proof

I. Logic and Proof

A proposition is a declarative sentence (that is, a sentence that declares a fact) that is either true or false, but not both.

A compound proposition that is always true, no matter what the truth values of the propositional variables that occur in it, is called a tautology.

A compound proposition that is always false is called a contradiction.

A compound proposition that is neither a tautology nor a contradiction is called a contingency.

The compound propositions p and q are called logically equivalent if $p \leftrightarrow q$ is a tautology. ( $p \equiv q$ )

Equivalence	Name
$p \lor F \equiv p$ $p \land T \equiv p$	Identity laws
$p \lor T \equiv T$ $p \land F \equiv F$	Domination laws
$p \lor p \equiv p$ $p \land p \equiv p$	Idempotent laws
$\lnot(\lnot p)) \equiv p$	Double negation law
$p \lor q \equiv q \lor p$ $p \land q \equiv q \land p$	Commutative laws
$(p \lor q) \lor r \equiv p\lor(q\lor r)$ $(p \land q) \land r \equiv p \land (q \land r)$	Associative laws
$p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$ $p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$	Distributive laws
$\lnot (p \land q) \equiv \lnot p \lor \lnot q$ $\lnot (p \lor q) \equiv \lnot p \land \lnot q$	De Morgan’s laws
$p \lor (p \land q) \equiv p$ $p \land (p \lor q) \equiv p$	Absorption laws
$p \lor \lnot p \equiv T$ $p \land \lnot p \equiv F$	Negation laws
Table of common Logical equivalence