Logic

Introduction to propositional logic

A proposition is a statement that asserts something. Propositional logic abstracts propositions with propositional variables or atomic propositions. $p$ or $q$ are common variables for atomic propositions.

Compound propositions are made up of atomic propositions or other compound propositions.
Some examples:

Boolean functions and truth tables

Boolean functions are of the form $B^n \to B$, where $B = \{True, False\}$.
Example: $$ \begin{aligned} & B^2 = \{FF,FT,TF,TT\}\\ & \text{A function that could map } B^2 \text{ to } B \text{ is } h(x,y) = x \vee y \text{ where } x,y \in B. \end{aligned} $$ You can draw a truth table to show the possible outputs of a boolean function.
Here is the truth table for $x \vee y$:

$x \to y$ shows material implication. This means $x$ implies $y$. It is equivalent to $(\neg x) \vee y$.

Logical equivalence and laws of propositional logic

Boolean functions and logical equivalence

Propositions $P$ and $Q$ are logically equivalent if the proposition $P \Leftrightarrow Q$ is a tautology.
The truth table for $x \Leftrightarrow y$:

Both values have to be the same for $x \Leftrightarrow y$ to be true. $\Leftrightarrow$ shows equivalence.

A proposition is a tautology if it is true regardless of the values of atomic propositions. A tautology is a proposition which is always true.
$P \equiv Q$ shows two propositions, $P$ and $Q$, are equivalent.

Laws of propositional logic

Alternative notation

Logical AND: $x \wedge y$, $x \& y$, $x \cdot y$, $xy$.
Logical NOT: $\neg x$, $\bar{x}$.

Predicates and quantifiers

Introduction to predicates and quantifiers

A predicate is a statement about a variable which can be true or false but not both. For example $p(u)$ is a predicate and $u$ is a variable.

Variables can be bound by quantifiers.

For example, $p(u): u > 2$ and $u<17$ is a predicate. For $u \in \mathbb{Z}$, $p(0)$ is false and $p(15)$ is true.
$\exists u \;p(u)$ is true, as there exists an integer between 2 and 17, whereas $\forall u \:p(u)$ is false as it is not true for all integers.

When a quantifier applies to a variable, the variable is said to be bound. For example, $p(x): x^2 = 2$ is a predicate and the variable $x$ is not bound, so it is free. If it is said that $\exists x \in \mathbb{Z} \; p(x)$ then the variable is now bound to a quantifier and is no longer free.

It is possible for predicates to have multiple variables. $p(x,y): x^2 - y^2 = (x-y)(x+y)$, for example, has 2 variables. Given that $x,y \in \mathbb{Z}$, It can be said that $\exists x \exists y \; p(x,y)$ and also $\forall x \forall y \; p(x,y)$ as the statement holds true for all integers $x$ and $y$.

Alternation of quantifiers

$q(u,v):|u-v|=1$, $u,v \in \mathbb{Z}$.
$\forall u \; \exists v \; q(u,v)$ is true, as for every integer $u$ there exists another integer $v$ with a difference of 1.

$\exists v \; \forall u \; q(u,v)$ is false, as there does not exist a single integer $v$ which has a difference of 1 with every number $u$.
Despite having the same quantifiers, the order is important.

Laws of predicate logic

Quantification over finite sets

Consider a finite set of integers $A = \{1,2,3,4,5,...,n\}$.
$\forall x \in A\; P(x) \equiv P(1) \wedge P(2) \wedge ... \wedge P(n)$ and
$\exists x \in A \; P(x) \equiv P(1) \vee P(2) \vee ... \vee P(n)$ where $P(x)$ is a predicate.

Another example:
$S = \{a,b,c\}$
$\forall x \; \exists y \; f(x,y)$
You can expand this out using the methods above:
$(\exists y \; f(a,y))\wedge(\exists y \; f(b,y))\wedge(\exists y \; f(c,y))$
Then applying the method again:
$(f(a,a) \vee f(a,b) \vee f(a,c)) \wedge$
$(f(b,a) \vee f(b,b) \vee f(b,c)) \wedge$
$(f(c,a) \vee f(c,b) \vee f(c,c))$

Working with quantifiers

$\forall x \; \text{True} \equiv \text{True}$
$\exists x \; \text{True} \equiv \text{True}$
$\forall x \; \text{False} \equiv \text{False}$
$\exists x \; \text{False} \equiv \text{False}$

$\forall x \; (P(x) \wedge Q) \equiv (\forall x \; P(x)) \wedge Q$
$\exists x \; (P(x) \wedge Q) \equiv (\exists x \; P(x)) \wedge Q$
These are interchangeable with $\vee$.

De Morgan's laws for quantifiers:
$\neg(\forall x \; P(x)) \equiv \exists x \; \neg P(x)$
$\neg(\exists x \; P(x)) \equiv \forall x \; \neg P(x)$

$\forall x \; (P(x) \wedge Q(x)) \equiv (\forall x\; P(x))\wedge (\forall x \; Q(x))$
This will not work for $\exists$, as $\exists x \; (P(x) \wedge Q(x))$ means there exists an $x$ such that both $P(x)$ and $Q(x)$ are true, but if you try to split it like before you get $(\forall x\; P(x))\wedge (\forall x \; Q(x))$ and there is a possibility the values for $x$ will be different but still true for both predicates.

There is a similar rule for disjunction ($\vee$). This only works with $\exists$ in both directions. $\exists x\; (P(x) \vee q(x)) \equiv (\exists x \; P(x)) \vee (\exists x \; Q(x))$. This will work with $\forall$ in the backward direction for the same reason as the last one.

Uniqueness

Suppose you want to find if only one item in a set satisfies a predicate. To express "at least one item satisfies the predicate" you can use $\exists x \in S\; P(x)$ - there exists an $x$ such that $P(x)$. This checks there is an item that satisfies the predicate, but not that it is the only one - there could be multiple.

To check it is unique, you can use $\forall y \in S \; \forall z \in S \; [(P(y)\wedge P(z))\to y = z]$. This says for all $y$ and $z$ which belong to $S$, if both satisfy the predicate it is implied that they are equal. Combining the checks for an item which satisfies $P(x)$ and is unique, you get $(\exists x \in S\; P(x)) \wedge (\forall y \in S \; \forall z \in S \; [(P(y)\wedge P(z))\to y = z])$.

The second part can be simplified using the previously mentioned rules. $(P(y)\wedge P(z)) \to y=z$ can be changed into $\neg P(y) \vee \neg P(z) \vee y=z$ because implication is logically equivalent to $\neg x \vee y$. Now we have $(\exists x \in S\; P(x)) \wedge (\forall y \in S \; \forall z \in S \; [\neg P(y) \vee \neg P(z) \vee y=z])$.