1

To start talking about anything, we need a collection of symbols (a formal-alphabet). Any string of these symbols is called a formula. A formal-grammar is a collection of rules (called formation-rules) that divide formulas into two groups: those that obey the grammar (called well-formed formulas or wffs) and those that do not. Given a formal-alphabet $\mathcal{A}$ and a formal-grammar $\mathcal{G}$, the collection of all wffs formed from $\mathcal{A}$ according to $\mathcal{G}$ is a formal-language.

A proposition $p$ is a basic entity that can take one of two values (called truth-values): true (T) or false (F). Logical-connectives are symbols used to construct new propositions (called compound-propositions) from existing ones (called atomic-propositions). For example, given two atomic-propositions $p$ and $q$, we can form the compound-proposition $p\wedge q$, which takes the truth-value true when both $p$ and $q$ are true, and truth-value false otherwise. Combining two propositions, there are $2^{2^2}=16$ different compound-propositions, and therefore 16 distinct binary-logical-connectives shown in the next table:

$p$	$q$	$C_0$	$C_1$	$C_2$	$C_3$	$C_4$	$C_5$	$C_6$	$C_7$	$C_8$	$C_9$	$C_{10}$	$C_{11}$	$C_{12}$	$C_{13}$	$C_{14}$	$C_{15}$
T	T	F	F	F	F	F	F	F	F	T	T	T	T	T	T	T	T
T	F	F	F	F	F	T	T	T	T	F	F	F	F	T	T	T	T
F	T	F	F	T	T	F	F	T	T	F	F	T	T	F	F	T	T
F	F	F	T	F	T	F	T	F	T	F	T	F	T	F	T	F	T

You can see that the $C_8$ connective is the one used in our previous example (true only when both $p$ and $q$ are true), it is denoted with the symbol $\wedge$ and called AND. Other binary-connectives are also commonly denoted with special symbols and given identifying names. For example, $C_0$ is denoted with $\perp$ and called contradiction, $C_1$ with $\downarrow$ and called NOR, $C_6$ with $\oplus$ and called XOR, $C_7$ with $\uparrow$ called NAND, $C_9$ with $\iff$ called XNOR, $C_{11}$ with $\to$ called IMPLY, $C_{14}$ with $\vee$ called OR, and $C_{15}$ with $\top$ and called tautology.

A compound-proposition may also be constructed from a single atomic-proposition. There are 4 different combinations, and therefore 4 unary-logical-connectives, shown in the next table:

$p$	$\mathrm{id}(p)$	$\neg p$	$\top p$	$\perp p$
T	T	F	T	F
F	F	T	T	F

The names of these unary-connectives, in order of appearance, are identity, negation, tautology, and contradiction.

In general, a compound-proposition may be constructed by combining any number $n$ (called the arity of the connective) of atomic-propositions, yielding $2^{2^n}$ distinct n-ary-logical-connectives.

We can apply logical-connectives to compound-propositions by enclosing them in parenthesis. For example, $\neg (\neg p)$ or $(\neg p)\wedge (\neg q)$. For the first, you can see that since negation is applied to $\neg p$, the truth-values of $\neg (\neg p)$ are true when $p$ is true and false when $p$ is false. For the second, the truth-values of $(\neg p)\wedge (\neg q)$ are the same that $C_1$, that in fact is the negation of $C_{14}$.

$p$	$q$	$\neg p$	$\neg q$	$(\neg p)\wedge (\neg q)$	$C_1$
T	T	F	F	F	F
T	F	F	T	F	F
F	T	T	F	F	F
F	F	T	T	T	T

If two propositions have the same truth-values, we call them logically-equivalent. To write these logical-equivalences we use the symbol $\equiv$. For example, like we saw $\neg (\neg p)$ is a proposition equivalent to $\mathrm{id}(p)$, or in symbols $\neg (\neg p)\equiv \mathrm{id}(p)$, and $(\neg p)\wedge (\neg q)$ is equivalent to $C_1$ (or $\downarrow$), i.e. $(\neg p)\wedge (\neg q)\equiv p\downarrow q$. The latter is one of a well-known pair of equivalences called De-Morgan’s-laws, the other is the dual equivalence $(\neg p)\vee (\neg q)\equiv p\uparrow q$. Since $\downarrow$ and $\uparrow$ are besides the negation of $\vee$ and $\wedge$ respectively, the De Morgan’s laws are often written as $(\neg p)\wedge (\neg q)\equiv \neg (p\vee q)$ and $(\neg p)\vee (\neg q)\equiv \neg (p\wedge q)$. Other two important equivalences (important enough to receive a name) are $p\to q\equiv (\neg q)\to (\neg p)$ called the contrapositive-law, and $p\iff q\equiv (p\to q)\wedge (q\to p)$ called the biconditional-law (for this reason the XNOR connective is often called the biconditional).

The number of connectives grows exponentially with arity ($2^{2^n}$), but luckily, the great majority of these connectives can be constructed, via equivalences, using other connectives. For example, using $\neg$ and $\wedge$ we can write the NOR connective using the De-Morgan’s-law $p\downarrow q\equiv (\neg p)\wedge (\neg q)$ (and the OR as the negation of that), or the IMPLY as $p\to q\equiv \neg (p\wedge \neg q)$ (and using this, the biconditional using the biconditional-law), etc. Continuing in this manner, we end up finding that we can write all the connectives just using $\neg$ and $\wedge$. Any collection of connectives that let us construct from them all the connectives is called a functional-complete-collection (or FCC). If we add the OR connective for example, the collection $\neg ,\wedge$ and $\vee$ is also a FCC, but the OR connective is redundant since we can construct it using the other two. A FCC that does not contain redundancies is called a minimal-FCC. Examples of minimal-FCCs are $\{\neg ,\wedge \}$, $\{\neg ,\vee \}$, $\{\neg ,\to \}$, and just $\{\uparrow \}$ or just $\{\downarrow \}$ (yes, even though there are $2^{2^n}$ n-ary-connectives, we can write them all using just the NAND (or NOR) connective).

Using lowercase letters (that represent atomic-propositions), parentheses, and any FCC (e.g. $\{\neg ,\wedge \}$) we can write any proposition. So a collection of symbols of this type ${\mathcal{A}}_{prop}=(\{\neg ,\wedge ,(,),p,q,r,s,\dots \})$ constitutes a formal-alphabet where any proposition is a formula of it, and is called (just like any formal-alphabet $\mathcal{A}$ such that any proposition is a formula of $\mathcal{A}$) a propositional-formal-alphabet.

While all propositions are formulas of a propositional-formal-alphabet like ${\mathcal{A}}_{prop}$, with it we can write many formulas that are not propositions (e.g. $\wedge p$ or $q((\neg$). This is where a formal-grammar becomes useful. We can use it to mark as wffs only those formulas that represent valid propositions, yielding a formal-language consisting solely of valid propositions. Such a formal-language is called a propositional-formal-language, and the formal-grammar used to select the valid propositions is called a propositional-formal-grammar.

An example of a propositional-formal-grammar ${\mathcal{G}}_{prop}$ over ${\mathcal{A}}_{prop}$ consists of the following formation-rules:

1. Any lowercase letter (e.g. $p$, $q$) is a well-formed formula.
2. If $\varphi$ is a wff, then $(\neg \varphi )$ is a wff.
3. If $\varphi$ and $\psi$ are wffs, then $(\varphi \wedge \psi )$ is a wff.

Using ${\mathcal{G}}_{prop}$, we can generate expressions like $(\neg (p\wedge q))$, but not $(\wedge pq)$ or $\neg p\wedge$ (which are formulas, but not wffs) creating from ${\mathcal{A}}_{prop}$ a propositional-formal-language ${\mathcal{L}}_{prop}$.

A predicate $P$ is a statement containing a number $n$ of variables ($x_1,x_2,\dots ,x_n$) called its arity. A predicate containing just one variable (e.g. $P(x)=$”$x$ is even”) is called unary, and one of two variables (e.g. $Q(x,y)=$”$x$ is the capital of $y$”) binary. In general, if we have a predicate of $m$ variables, and we specify the value of only $n$, it becomes a new predicate of $m-n$ variables, and when we specify all the $m$ variables it becomes a proposition. So a proposition is a predicate of $m-m=0$ variables in this context. For example, if we specify the value of $y$ as “Italy”, the binary predicate $Q(x,y)=$”$x$ is the capital of $y$” becomes the unary predicate $R(x)$=”$x$ is the capital of Italy”. And then, if we also specify the value of $x$ it becomes a proposition (the true proposition “Rome is the capital of Italy” if we specify $x$ as “Rome”, and the false proposition “Madrid is the capital of Italy” if we specify $x$ as “Madrid” for example).