Chapter 1 Notations

1 Logic Operations

There are 4 operators, they are $\neg$, $\land$, $\lor$, $\Rightarrow$, the outcome of the operation is the Truth Table.

For proposition $\neg A$

A	0	1
$\neg$A	1	0

For compound proposition $A\land B$

$_A^B$	0	1
0	0	0
1	0	1

For compound proposition $A\lor B$

$_A^B$	0	1
0	0	1
1	1	1

For compound proposition $A\Rightarrow B$

$_A^B$	0	1
0	1	1
1	0	1

It might be confused for $A\Rightarrow B$, when $A=0$, no matter what the value of B is, the outcome of the operation is 1. This is because when precondition A is false, B will never violate A.

$A\Rightarrow B$: If it rains today (A), I will bring an umbrella (B)

When $A=0$, which means it doesn’t rain today, then if I take the umbrella (B=1), I don’t violate the promise, because we cannot verify whether I will take it when it rains. Also, if I didn’t take the umbrella (B=0), I still don’t violate.

When $A\Rightarrow B$, we say, B is a necessary condition of A (because when B=0 then A=0, we cannot go without B), A is an adequate condition of B (because A alone will decide B), and $A\Leftrightarrow B$ means A is both necessary and adequate for B and vice versa.

Exercises

1. pass
2. Solve
   (1) $\neg(A\land B)\Leftrightarrow \neg A \lor \neg B$

We can write the truth table

For $\neg(A\land B)$

$_A^B$	0	1
0	1	0
1	0	0

For $\neg A \lor \neg B$

$_A^B$	0	1
0	1	0
1	0	0

Q.E.D.

There are some other relationships that can also be proved by truth tables, and we should remember them

1. $\neg(A\land B)\Leftrightarrow \neg A \lor \neg B$
2. $\neg(A\lor B)\Leftrightarrow \neg A\land \neg B$
3. $(A\Rightarrow B) \Leftrightarrow (\neg B\Rightarrow \neg A)$
4. $(A\Rightarrow B) \Leftrightarrow \neg A\lor B$
5. $\neg (A\Rightarrow B)\Leftrightarrow A\land \neg B$

2 Set and Its Operators

Russell’s Paradox: Consider a set $R=\{X|X\notin X\}$, which means it contains sets that doesn’t contain themselves, then

• If $R\in R$, then R should satisfy $X\notin X$, hence $R\notin R$
• If $R\notin R$, then R satisfies $X\notin X$, hence $R\in R$

This creates a logical contradiction!