Logic §

Propositions are statements that are either true or false.

$p,q,r,s$ are propositions.

Conjunction §

Conjunction is the && operator in C++. We write it as $p\wedge q$.

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

Or §

Conjunction is the || operator in C++. We write it as $p\vee q$.

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

Not §

!= in C++.

$p$	$-p$
T	F
F	T

Conditional Proposition §

Pretty much the if statement in C++

$p⟹q$

Code §

if (p) 
	do q;

Truth Table §

$p$	$q$	$p⟹q$
T	T	T
T	F	F
F	T	T
F	F	T

Creating New Propositions §

Based on $p⟹q$, we can make 3 new propositions:

1. Converse: $q⟹p$
2. Inverse: $-p⟹-q$
3. Contrapositive $-q⟹-p$

The contrapositive is the only statement necessarily logically equivalent to the $p⟹q$.

Biconditional Proposition §

P happens if and only if q.

$$p⟺q$$

$p$	$q$	$p⟺q$
T	T	T
T	F	F
F	T	F
F	F	T

Logical Equivalence §

Two propositions produce the same ouput.

Example §

Is $p\wedge q$ logically equivalent to $-p\vee -q$?

p	q	$p\wedge q$	$-p\vee -q$
T	T	T	F
T	F	F	F
F	T	F	F
F	F	F	T

Nope.

DeMorgan’s Law §

$$\begin{array}{rl}-(p\wedge q)& \leftrightarrow -p\vee q\\ -(p\vee q)& \leftrightarrow -p\wedge -q\end{array}$$

Rules §

Addition §

Given $p$ is true, $p\vee q$ must be true.

Modus Ponens §

Given $p⟹q$ and $p$ is true, $q$ must be true.

Negating Quantifiers §

Examples §

$P(x)$: x is an accountant $Q(x)$: x owns a Porsche

All accountants own Porches:

$$\forall x(P(x)⟹Q(x))$$

To negate,

$$\exists x(P(x)⟹Q(x))$$

is not true.