[Discrete Mathematics] Logic and Proof

I. Logic and Proof


1. Propositional Logic

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

Name Meaning Notation
negation not p $\lnot p$
disjunction p or q $p \lor q$
conjunction p and q $p \land q$
conditional if p, then q $p \rightarrow q$
biconditional p if and only if q $p \leftrightarrow q$

2. Propositional Equivalences

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

3. Predicates and Quantifiers

To be done


Discrete Mathematics and Its Applications 7th Edition, Kenneth H. Rosen

Khuyên dùng


Speak Your Mind