Logic

1 Propositional Logic

1.1 Propositions

A declarative statement, i.e. either true or false

1.2 Compound propositions

Logical operators or logical connectives

• Precedence

1. $\neg$
2. $\wedge$
3. $\vee$
4. $\to$
5. $\leftrightarrow$

• Negation

$p$	$\neg p$
T	F
F	T

• Conjunction

$p$	$q$	$p\wedge q$
T	T	T
T	F	F
F	T	F
F	F	F

• Disjunction

$p$	$q$	$p\vee q$
T	T	T
T	F	T
F	T	T
F	F	F

• Exclusive Or

True when exactly one of $p$ and $q$ is true

$p$	$q$	$p\oplus q$
T	T	F
T	F	T
F	T	T
F	F	F

• Implication

$p$ is a sufficient condition of $q$

$p$	$q$	$p\to q$
T	T	T
T	F	F
F	T	T
F	F	T

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

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

• Biconditional

$p$ if and only if $q$

$p$	$q$	$p\leftrightarrow q$
T	T	T
T	F	T
F	T	F
F	F	T

• Converse

The converse of $p\to q$ is $q\to p$, equivalent to inverse

$p$	$q$	$p\to q$	$q\to p$
T	T	T	T
T	F	F	T
F	T	T	F
F	F	T	T

• Inverse

The inverse of $p\to q$ is $\neg p\to \neg q$, equivalent to converse

$p$	$q$	$\neg p$	$\neg q$	$p\to q$	$\neg p\to \neg q$
T	T	F	F	T	T
T	F	F	T	F	T
F	T	T	F	T	F
F	F	T	T	T	T

• Contrapositive

The contrapositive of $p\to q$ is $\neg q\to \neg p$

$p$	$q$	$\neg p$	$\neg q$	$p\to q$	$\neg q\to \neg p$
T	T	F	F	T	T
T	F	F	T	F	F
F	T	T	F	T	T
F	F	T	T	T	T

1.3 Propositional Equivalences

• Tautology

A compound proposition that is always true, e.g. $p\vee \neg p$

$p$	$\neg p$	$p\vee \neg p$
T	F	T
F	T	T

• Contradiction

A compound proposition that is always false, e.g. $p\wedge \neg p$

$p$	$\neg p$	$p\wedge \neg p$
T	F	F
F	T	F

• Contingency

A compound proposition that is neither a tautology or contingency, e.g. $p\to \neg p$

$p$	$\neg p$	$p\to \neg p$
T	F	F
F	T	T

1.4 Logical Equivalent

The compound propositions $p$ and $q$ are called logically equivalent if $p\leftrightarrow q$ is a tautology, i.e. $p\equiv q$

• Identity Laws

$$\begin{array}{r}p\wedge T\equiv p\\ p\vee F\equiv p\end{array}$$

• Domination Laws

$$\begin{array}{r}p\vee T\equiv T\\ p\wedge F\equiv F\end{array}$$

• Idempotent Laws

$$\begin{array}{r}p\vee p\equiv p\\ p\wedge p\equiv p\end{array}$$

• Double Negation Laws

$$\neg (\neg p)\equiv p$$

• Commutative Laws

$$\begin{array}{r}p\vee q\equiv q\vee p\\ p\wedge q\equiv q\wedge p\end{array}$$

• De Morgan’s Laws

$$\begin{array}{r}\neg (p\wedge q)\equiv \neg p\vee \neg q\\ \neg (p\vee q)\equiv \neg p\wedge \neg q\end{array}$$

$p$	$q$	$p\vee q$	$\neg (p\vee q)$	$\neg p$	$\neg q$	$\neg p\wedge \neg q$	$\neg (p\vee q)\leftrightarrow \neg p\wedge \neg q$
T	T	T	F	F	F	F	T
T	F	T	F	F	T	F	T
F	T	T	F	T	F	F	T
F	F	F	T	T	T	T	T

• Associative Laws

$$\begin{array}{r}(p\vee q)\vee r\equiv p\vee (q\vee r)\\ (p\wedge q)\wedge r\equiv p\wedge (q\wedge r)\end{array}$$

• Distributive Laws

$$\begin{array}{r}p\vee (q\wedge r)\equiv (p\vee q)\wedge (p\vee r)\\ p\wedge (q\vee r)\equiv (p\wedge q)\vee (p\wedge r)\end{array}$$

• Absorption Laws

$$\begin{array}{r}p\vee (p\wedge q)\equiv p\\ p\wedge (p\vee q)\equiv p\end{array}$$

• Negation Laws

$$\begin{array}{r}p\vee \neg p\equiv T\\ p\wedge \neg p\equiv F\end{array}$$

2 Predicate Logic

• Quantifiers

$$\begin{array}{r}\forall xP(x)=P(x_1)\wedge P(x_2)\wedge \cdots \wedge P(x_n)\\ \exists xP(x)=P(x_1)\vee P(x_2)\vee \cdots \vee P(x_n)\end{array}$$

• Quantifiers with Restricted Domains

$$\begin{array}{rl}& \text{for }{U}_1\subseteq U_2\\ & Q(x)=\{x\in U_2\mid Q(x)\text{ is true}\}\\ & \\ & \forall x\in U_1(P(x))\\ & \equiv \forall x\in U_2(Q(x)\to P(x))\\ & \\ & \exists x\in U_1(P(x))\\ & \equiv \exists x\in U_2(Q(x)\wedge P(x))\end{array}$$

• Distribution

$$\begin{array}{r}\forall x(Q(x)\wedge P(x))\equiv \forall xQ(x)\wedge \forall xP(x)\\ \exists x(Q(x)\vee P(x))\equiv \exists xQ(x)\vee \exists xP(x)\end{array}$$

• De Morgan’s Laws for Quantifiers

$$\begin{array}{r}\neg \forall xP(x)\equiv \exists x\neg P(x)\\ \neg \exists xQ(x)\equiv \forall x\neg Q(x)\end{array}$$

• Nested Quantifiers

$$\begin{array}{r}\forall x\exists y(x+y=0)\equiv \mathrm{T}\\ \exists x\forall y(x+y=0)\equiv \mathrm{F}\end{array}$$

• Null Quantifications

$$\begin{array}{r}\forall x(A\wedge P(x))\equiv A\wedge \forall xP(x)\\ \forall x(A\vee P(x))\equiv A\vee \forall xP(x)\\ \exists x(A\wedge P(x))\equiv A\wedge \exists xP(x)\\ \exists x(A\vee P(x))\equiv A\vee \exists xP(x)\end{array}$$ $$\forall xP(x)\wedge \forall xQ(x)\equiv \forall x\forall y(P(x)\wedge Q(y))$$

Does not work for implication

3 Inference and Proofs

3.1 Proof Terminology

• Theorem
  • A statement that can be shown to be true
• Axiom
  • A statement that is assumed to be true
• Lemma
  • A less important theorem
• Proof
  • A valid argument that establish the truth of a theorem
• Corollary
  • A theorem that can be established directly from a theorem
• Conjecture
  • A statement that is proposed to be a true statement

3.2 Rules of Inference for Propositional Logic

• Modus Ponens

$$\begin{array}{rl}& p\\ & p\to q\\ & \therefore q\end{array}$$

• Modus Tollens

$$\begin{array}{rl}& \neg q\\ & p\to q\\ & \therefore \neg p\end{array}$$

• Hypothetical Syllogism

$$\begin{array}{rl}& p\to q\\ & q\to r\\ & \therefore p\to r\end{array}$$

• Disjunctive Syllogism

$$\begin{array}{rl}& p\vee q\\ & \neg p\\ & \therefore q\end{array}$$

• Addition

$$\begin{array}{rl}& p\\ & \therefore p\vee q\end{array}$$

• Simplification

$$\begin{array}{rl}& p\wedge q\\ & \therefore p\end{array}$$

• Conjunction

$$\begin{array}{rl}& (p)\wedge (q)\\ & \therefore p\wedge q\end{array}$$

• Resolution

$$\begin{array}{rl}& p\vee q\\ & \neg p\vee r\\ & \therefore q\vee r\end{array}$$

3.3 Rules of Inference for Predicate Logic

• Universal Instantiation

$$\begin{array}{rl}& \forall xP(x)\\ & \therefore P(c)\end{array}$$

• Universal Generalization

$$\begin{array}{rl}& P(c)\text{ for an arbitrary }c\\ & \therefore \forall xP(x)\end{array}$$

• Existential Instantiation

$$\begin{array}{rl}& \exists xP(x)\\ & \therefore P(c)\text{ for some element }c\end{array}$$

• Existential Generalization

$$\begin{array}{rl}& P(c)\text{ for some element }c\\ & \therefore \exists xP(x)\end{array}$$

3.4 Direct Proof

For $p\to q$, we assume $p$ is true, then we show $q$ is true in the final step

3.5 Proof by Contraposition

Since $p\to q\equiv \neg q\to \neg p$, we take $\neg q$ as a hypothesis and show that $\neg p$ must follow

3.6 Proof by Contradiction

To prove $p$ is true
Assume $p$ is false, i.e. $\neg p$ is true
Then derive a contradiction, which means the assumption that $\neg p$ is true is false
Therefore $p$ is true

3.6.1 Proof by Contradiction for Conditional Statement

To prove $p\to q$
Assume $\neg (p\to q)\equiv \neg (\neg p\vee q)\equiv p\wedge \neg q$
Arrive at a contradiction, i.e. $p\wedge \neg q\to F$