💡 A mathematical statement that is either true or false is also called a proposition.

💡 A true proposition is often called a theorem, a lemma, or a corollary. A proposition not known to be true or false is often called a conjecture or an assumption.

💡 (Informal.) A proof of a statement $S$ is a sequence of simple, easily verifiable, consecutive steps. The proof starts from a set of axioms (things postulated to be true) and known (previously proved) facts. Each step corresponds to the application of a derivation rule to a few already proven statements, resulting in a newly proved statement, until the final step results in $S$.

💡 The logical values (constants) “true” and “false” are usually denoted as 1 and 0, respectively.

💡 Logical operators:

1. The negation (logical NOT) of a proposition $A$, denoted as $\neg A$, is true if and only if $A$ is false.
2. The conjunction (logical AND) of two propositions $A$ and $B$, denoted $A\wedge B$, is true if and only if both $A$ and $B$ are true.
3. The disjunction (logical OR) of two propositions $A$ and $B$, denoted $A\vee B$, is true if and only if $A$ or $B$ (or both) are true.

💡 (Informal.) The implication of two propositions $A$ and $B$, denoted as $A\to B$, is equivalent to $\neg A\vee B$.

💡 (Informal.) The two-sided implication of two propositions $A$ and $B$, denoted as $A\leftrightarrow B$, is equivalent to $(A\to B)\wedge (B\to A)$.

💡 A correctly formed expression involving the propositional symbols $A$, $B$, $C$,… and logical operators is called a formula (of propositional logic).

💡 Two formulas $F$ and $G$ (in propositional logic) are called equivalent, denoted as $F\equiv G$, if they correspond to the same function, i.e., if the truth values are equal for all truth assignments to the propositional symbols appearing in $F$ or $G$ .

📌 1) $A\wedge A\equiv A$ and $A\vee A\equiv A$ (idempotence)

2) $A\wedge B\equiv B\wedge A$ and $A\vee B\equiv B\vee A$ (commutativity of $\wedge$ and $\vee$)

3) $(A\wedge B)\wedge C\equiv A\wedge (B\wedge C)$ and $(A\vee B)\vee C\equiv A\vee (B\vee C)$ (associativity)

4) $A\wedge (A\vee B)\equiv A$ and $A\vee (A\wedge B)\equiv A$ (absorption)

5) $A\wedge (B\vee C)\equiv (A\wedge B)\vee (A\wedge C)$ (first distributive law)

6) $A\vee (B\wedge C)\equiv (A\vee B)\wedge (A\vee C)$ (second distributive law)

7) $\neg \neg A\equiv A$ (double negation)

8) $\neg (A\wedge B)\equiv \neg A\vee \neg B$ and $\neg (A\vee B)\equiv \neg A\wedge \neg B$ (de Morgan’s rules).

💡 A formula $G$ is a logical consequence of a formula $F$, denoted

$$F\models G,$$

if for all truth assignments to the propositional symbols appearing in $F$ or $G$, the truth value of $G$ is 1 if the truth value of $F$ is 1.

💡 Two formulas $F$ and $G$ are equivalent if and only if each one is a logical consequence of the other, i.e.,

$$F\equiv G⟺F\models G\text{ and }G\models F.$$

💡 A formula $F$ (in propositional logic) is called a tautology or valid if it is true for all truth assignments of the involved propositional symbols. One often writes $\models F$ to say that $F$ is a tautology.

💡 A formula $F$ (in propositional logic) is called satisfiable if it is true for at least one truth assignment of the involved propositional symbols, and it is called unsatisfiable otherwise.

💡 The symbol $\top$ is sometimes used to denote a tautology, and the symbol $\perp$ is sometimes used to denote an unsatisfiable formula. One sometimes writes $F\equiv \top$ to say that $F$ is a tautology, and $F\equiv \perp$ to say that $F$ is unsatisfiable. For any formula $F$ we have

$$F\vee \neg F\equiv \top \text{ and }F\wedge \neg F\equiv \perp .$$

📌 A formula $F$ is a tautology if and only if $\neg F$ is unsatisfiable.

📌 For any formulas $F$ and $G$, $F\to G$ is a tautology if and only if $F\models G$.

💡 A $k$-ary predicate $P$ on $U$ is a function $U^k⟶\{0,1\}.$

💡 For a universe $U$ and a predicate $P(x)$ we define the following logical statements:

• $\forall xP(x)$ stands for: $P(x)$ is true for all $x$ in $U$.
• $\exists xP(x)$ stands for: $P(x)$ is true for some $x$ in $U$, i.e., there exists an $x\in U$ for which $P(x)$ is true.

More generally, for a formula $F$ with a variable $x$, which for each value $x\in U$ is either true or false, the formula $\forall xF$ is true if and only if $F$ is true for all $x$ in $U$, and the formula $\exists xF$ is true if and only if $F$ is true for some $x$ in $U$.

💡 Some useful rules:

• $\forall xP(x)\models \exists xP(x)$
• $\forall xP(x)\wedge \forall xQ(x)\equiv \forall x(P(x)\wedge Q(x))$
• $\exists x(P(x)\wedge Q(x))\models \exists xP(x)\wedge \exists xQ(x)$
• $\neg \forall xP(x)\equiv \exists x\neg P(x)$
• $\neg \exists xP(x)\equiv \forall x\neg P(x)$
• $\exists y\forall xP(x,y)\models \forall x\exists yP(x,y)$

📌 For any two formulas $F$ and $G$, if $F\models G$, then

$$F\text{ is valid}⟹G\text{ is valid}$$

is true.

💡 The proof step of composing implications is as follows: If $S⟹T$ and $T⟹U$ are both true, then one concludes that $S⟹U$ is also true.

📌 $\ast (A\to B)\wedge (B\to C)\models A\to C.$ (transitivity of $\to$)*

💡 A direct proof of an implication $S⟹T$ works by assuming $S$ and then proving $T$ under this assumption.

💡 An indirect proof of an implication $S⟹T$ proceeds by assuming that $T$ is false and proving that $S$ is false, under this assumption.

📌 $\neg B\to \neg A\models A\to B.$

💡 A proof of a statement $S$ by use of the so-called modus ponens proceeds in three steps:

1. Find a suitable mathematical statement $R$.
2. Prove $R$.
3. Prove $R⟹S$.

📌 $A\wedge (A\to B)\models B$.

💡 A proof of a statement $S$ by case distinction proceeds in three steps:

1. Find a finite list $R_1,\dots ,R_k$ of mathematical statements (the cases).
2. Prove that one of the $R_i$ is true (one case occurs).
3. Prove $R_i⟹S$ for $i=1,\dots ,k$.

📌 For every $k$ we have

$$(A_1\vee \dots \vee A_k)\wedge (A_1\to B)\wedge \dots \wedge (A_k\to B)\models B.$$

💡 A proof by contradiction of a statement $S$ proceeds in three steps:

1. Find a suitable mathematical statement $T$.
2. Prove that $T$ is false.
3. Assume that $S$ is false and prove (from this assumption) that $T$ is true (a contradiction).

📌 $(\neg A\to B)\wedge \neg B\models A$.

💡 Consider a set $\mathcal{X}$ of parameters and for each $x\in \mathcal{X}$ a statement, denoted $S_x$. An existence proof is a proof of the statement that $S_x$ is true for at least one $x\in \mathcal{X}$. An existence proof is constructive if it exhibits an $a$ for which $S_a$ is true, and otherwise it is non-constructive.

📖 The Pigeonhole Principle: If a set of $n$ objects is partitioned into $k<n$ sets, then at least one of these sets contains at least $\lceil \frac{n}{k}\rceil$ objects.

💡 Consider a set $\mathcal{X}$ of parameters and for each $x\in \mathcal{X}$ a statement, denoted $S_x$. A proof by counterexample is a proof of the statement that $S_x$ is not true for all $x\in \mathcal{X}$, by exhibiting an $a$ (called counterexample) such that $S_a$ is false. This corresponds to an existence proof.

💡 Proof by induction:

1. Basis step. Prove $P(0)$.
2. Induction step. Prove that for any arbitrary $n$ we have $P(n)⟹P(n+1)$.

📖 For the universe $\mathbb{N}$ and an arbitrary unary predicate $P$ we have

$$P(0)\wedge \forall n(P(n)\to P(n+1))⟹\forall nP(n).$$