Propositional Logic Note

Propositional Function

Definition

A sentence expressed in a way that would assume the value of true or false.

Link to original

Truth table

Definition

$p$	$q$	$\neg p$	$p\vee q$	$p\wedge q$	$p\to q$	$p\leftrightarrow q$
T	T	F	T	T	T	T
T	F	F	F	T	F	F
F	T	T	F	T	T	F
F	F	T	F	F	T	T

Facts

$p\to q\equiv \neg p\vee q$

De Morgan's Laws

Definition

$\neg (p\wedge q)\equiv \neg p\vee \neg q$ $\neg (p\vee q)\equiv \neg p\wedge \neg q$

Link to original

Contraposition

Definition

$p\to q\equiv \neg q\to \neg p$

Link to original

Associative Property: $(p\vee q)\vee r\equiv p\vee (q\vee r)$

Distributive Property: $p\vee (q\wedge r)\equiv (p\vee q)\wedge (p\vee r)$

Link to original

Duality in Logic

Definition

In logic, functions or relations $A$ and $B$ are considered dual if $A(\neg x)=\neg B(x)$. follows are dual

• $\forall \leftrightharpoons \exists$
• $\wedge \leftrightharpoons \vee$
• $p\leftrightharpoons \neg p$
• $<\leftrightharpoons \ge$

Link to original

Tautology

Definition

$t$

A formula or assertion that is true in every possible interpretation

Facts

$\forall$ proposition $p$ $p\vee \neg p\equiv t$ $t\vee p\equiv t$ $t\wedge p\equiv p$

$(p\to q)\wedge (p\to r)\to (p\to r)\equiv t$^[The law of transitivity]

Link to original

Contradiction

Definition

$c$

A formula or assertion that is false in every possible interpretation

Facts

$\forall$ proposition $p$ $p\wedge \neg p\equiv c$ $c\vee p\equiv p$ $c\wedge p\equiv c$

Link to original

Implication

Definition

$p\Rightarrow q$

If the antecedent is true, then the consequent must also be true

Link to original

Necessity

Definition

Suppose $p\Rightarrow q$, then $q$ is necessary for $p$

Link to original

Sufficiency

Definition

Suppose $p\Rightarrow q$, then $p$ is sufficient for $q$

Link to original

Necessary and Sufficient Condition

Definition

$p\Rightarrow q\wedge q\Rightarrow p$

$p$ is necessary for $q$ and $p$ is sufficient for $q$

Link to original