Day: September 28, 2020

Posted on

202009281158 Logic the Basics

Notation and notion

\begin{array}{ccc} \hline \textrm{\textbf{Statement connective}} & \qquad \qquad & \textrm{\textbf{Abbreviation}} \\ \hline \\ \textrm{\small{AND}} & & \wedge \\ \textrm{\small{OR}} & & \vee \\ \textrm{\small{IMPLIES}} & & \Rightarrow \\ \textrm{\small{IF AND ONLY IF}} & & \Leftrightarrow \\ \textrm{\small{IT IS NOT THE CASE}} & & \neg \\ \end{array}

\begin{array}{ccc} \hline & \qquad\qquad & \textrm{\textbf{Parenthesized expressions}} \\ \hline \\ (\textrm{\textbf{highest precedence}}) & & \textrm{\small{NOT}}\enspace (\neg ) \\ & & \textrm{\small{AND}}\enspace (\wedge )\textrm{,\,} \textrm{\small{OR}}\enspace (\vee ) \\ & & \textrm{\small{IMPLIES}}\enspace (\Rightarrow ) \\ (\textrm{\textbf{lowest precedence}}) & &\textrm{\small{IF AND ONLY IF}} \enspace (\Leftrightarrow ) \\ \end{array}

Truth tables

\begin{array}{c|c|c|c|c|c} \hline & & \textrm{\textbf{\scriptsize{AND}}} & & & \textrm{\textbf{\scriptsize{OR}}} \\ \hline P & Q & P\wedge Q & P & Q & P\vee Q \\ \hline \textrm{T} & \textrm{T} & \textrm{T} & \textrm{T} & \textrm{T} & \textrm{T} \\ \textrm{T} & \textrm{F} & \textrm{F} & \textrm{T} & \textrm{F} & \textrm{T} \\ \textrm{F} & \textrm{T} & \textrm{F} & \textrm{F} & \textrm{T} & \textrm{T} \\ \textrm{F} & \textrm{F} & \textrm{F} & \textrm{F} & \textrm{F} & \textrm{F} \\ \end{array}

\begin{array}{c|c|c|c|c} \hline & \textrm{\textbf{\scriptsize{NOT}}} & & & \textrm{\textbf{\scriptsize{IMPLIES}}} \\ \hline P & \neg P & P & Q & P\Rightarrow Q \\ \hline \textrm{T} & \textrm{F} & \textrm{T} & \textrm{T} & \textrm{T} \\ \textrm{F} & \textrm{T} & \textrm{T} & \textrm{F} & \textrm{F} \\ & & \textrm{F} & \textrm{T} & \textrm{T} \\ & & \textrm{F} & \textrm{F} & \textrm{T} \\ \end{array}

\begin{array}{c|c|c|c|c|c} \hline & & \textrm{\textbf{\scriptsize{IF AND ONLY IF}}} & & & \textrm{\textbf{\scriptsize{EXCLUSIVE-OR}}} \\ \hline P & Q & P\Leftrightarrow Q & P & Q & P\veebar Q \\ \hline \textrm{T} & \textrm{T} & \textrm{T} & \textrm{T} & \textrm{T} & \textrm{F} \\ \textrm{T} & \textrm{F} & \textrm{F} & \textrm{T} & \textrm{F} & \textrm{T} \\ \textrm{F} & \textrm{T} & \textrm{F} & \textrm{F} & \textrm{T} & \textrm{T} \\ \textrm{F} & \textrm{F} & \textrm{T} & \textrm{F} & \textrm{F} & \textrm{F} \\ \end{array}

\begin{array}{c|c|c|c|c|c} \hline & & \textrm{\textbf{\scriptsize{NOR}}} & & & \textrm{\textbf{\scriptsize{NAND}}} \\ \hline P & Q & P\downarrow Q & P & Q & P\uparrow Q \\ \hline \textrm{T} & \textrm{T} & \textrm{F} & \textrm{T} & \textrm{T} & \textrm{F} \\ \textrm{T} & \textrm{F} & \textrm{F} & \textrm{T} & \textrm{F} & \textrm{T} \\ \textrm{F} & \textrm{T} & \textrm{F} & \textrm{F} & \textrm{T} & \textrm{T} \\ \textrm{F} & \textrm{F} & \textrm{T} & \textrm{F} & \textrm{F} & \textrm{T} \\ \end{array}

Logical equivalence

a. (rule of double negation)

\neg\neg\, P\equiv P

b. (or-form of an implication)

P\Rightarrow Q\equiv \neg\, P\vee Q

c. (contrapositive of an implication)

P\Rightarrow Q\equiv \neg\, Q\Rightarrow \neg\, P

d. (de Morgan’s laws)

\neg\, (P\vee Q) \equiv \neg\, P\wedge \neg\, Q;

\neg\, (P\wedge Q)\equiv \neg\, P\vee \neg\, Q

e. (rule for direct proof)

(P\wedge R\Rightarrow Q)\equiv (R\Rightarrow (P\Rightarrow Q))

f. (rule for proof by contradiction)

(P\wedge \neg\, Q\Rightarrow O) \equiv (P\Rightarrow Q)

g. (rule for proof by cases)

(P\vee R\Rightarrow Q) \equiv \big[ (P\Rightarrow Q)\wedge (R\Rightarrow Q)\big]

Boolean laws of logic

\begin{array}{cc} \textrm{1a} \qquad & P\vee Q \equiv Q\vee P \\ \textrm{1b} \qquad & P\wedge Q\equiv Q\wedge P\\ \textrm{2a} \qquad & (P\vee Q)\vee R \equiv P\vee (Q\vee R)\\ \textrm{2b} \qquad & (P\wedge Q) \wedge R \equiv P\wedge (Q\wedge R) \\ \textrm{3a} \qquad & P\vee (Q\wedge R) \equiv (P\vee Q)\wedge (P\vee R) \\ \textrm{3b} \qquad & P\wedge (Q\vee R) \equiv (P\wedge Q)\vee(P\wedge R) \\ \textrm{4a} \qquad & P\vee O \equiv P \\ \textrm{4b} \qquad & P\wedge I\equiv P \\ \textrm{5a} \qquad & P\vee \neg\, P \equiv I\\ \textrm{5b} \qquad & P\wedge \neg\, P \equiv O \\ \end{array}

(1a) and (1b) are known as communicative laws, (2a) and (2b) as associate laws, and (3a) and (3b) as distributive laws.

Predicate validity

\begin{array}{cc} \textrm{Q1} \qquad & \exists\, y\,\forall\, x\enspace P(x,y) \Leftrightarrow \forall\, x\,\exists\, y\enspace P(x,y) \\ \textrm{Q2} \qquad & \neg\,\forall\, x\enspace P(x) \Leftrightarrow \exists\, x\enspace \neg\, P(x) \\ \textrm{Q3} \qquad &\neg\,\exists\, x\enspace P(x) \Leftrightarrow \forall\, x\enspace \neg\, P(x) \\ \end{array}

Boolean laws for set theory

\begin{array}{cccc} & \textrm{Union} & & \textrm{Intersection} \\ \textrm{S1a} & \quad A\cup B = B\cup A & \textrm{S1b} &\quad A\cap B=B\cap A \\ \textrm{S2a} & \quad (A\cup B)\cup C = A\cup (B\cup C) & \textrm{S2b} & \quad (A\cap B)\cap C=A\cap (B\cap C) \\ \textrm{S3a} & \quad A\cup (B\cap C) = (A\cup B)\cap (A\cup C) & \textrm{S3b} & \quad A\cap(B\cup C) = (A\cap B) \cup (A\cap C)\\ \textrm{S4a} & \quad A\cup \emptyset =A & \textrm{S4b} & \quad A\cap \mathrm{U}=A \\ \textrm{S5a} & \quad A\cup A' = \mathrm{U} & \textrm{S5b} & \quad A\cap A' = \emptyset \\ \textrm{S6a} & \quad A\cup \mathrm{U} = \mathrm{U} & \textrm{S6b} & \quad A\cap \emptyset = \emptyset \\ \textrm{S7a} & \quad A\cup A = A & \textrm{S7b} & \quad A\cap A =A \\ \textrm{S8a} & \quad \mathrm{U}' = \emptyset & \textrm{S8b} & \quad \emptyset' = \mathrm{U} \\ \textrm{S9a} & \quad (A')' = A & & \\ \textrm{S10a} & \quad (A\cup B)' = A' \cap B' & \textrm{S10b} &\quad (A\cap B)' = A' \cup B' \\ \textrm{S11a} & \quad A\cap (A\cup B) = A & \textrm{S11b} &\quad A\cup (A\cap B) = A \\ \textrm{S12a} & \quad A\subseteq A\cup B & \textrm{S12b} & \quad A\cap B\subseteq B \\ \textrm{S13} & \quad A\subseteq B\Leftrightarrow B'\subseteq A' & & \\ \textrm{S14} & \quad A\subseteq B \Leftrightarrow A'\cup B = \mathrm{U} & & \\ \textrm{S15} & \quad A\subseteq B \Leftrightarrow A\cap B' = \emptyset & & \\ \textrm{S16} & \quad A\subseteq B\Leftrightarrow A\cup B & & \\ \textrm{S17} & \quad A\subseteq B\Leftrightarrow A\cap B = A & & \\ \textrm{S18} & \quad A\subseteq B\,\wedge\, B\subseteq D \Rightarrow A\subseteq D & & \\ \end{array}

Remarks. Statements (S1a) and (S1b) are called the commutative laws; (S2a) and (S2b) the associative laws; (S3a) and (S3b) the distributive laws; (S4a) and (S4b) the identity laws; (S5a) and (S5b) the complement laws; (S7a) and (S7b) the idempotent laws; (S8a) and (S8b) the universal/empty set complement law; (S10a) and (S10b) the De Morgan's laws; (S11a) and (S11b) the absorption laws; and (S18) the transitive law.