Syntax and semantics of propositional logic

Propositional Logic: Introduction

Syntax and semantics of propositional logic

From natural language to propositional notation In the first examples of reasoning in everyday life, we have already seen that, in addition to a natural language, a more formal language is also possible to describe patterns of reasoning. Here letters such as \(p\), \(q\), \(r\) and \(s\) are used to symbolise propositions; they are called the propositional letters or propositional variables. We mainly use these letters for propositions that we do not want to analyse further or that can no longer be expressed in terms of simpler propositions; we speak of simple propositions or atomic propositions. An example sentence is "Johnny is crying." The proposition "Johnny is in pain and he is crying" is a multiple proposition or compound proposition, which consists of two sub-propositions "Johnny is in pain" and "He is crying." The connective word "and" is an example of a logical operator or connective.

Connectives In propositional logic the following connectives are used to produce new propositions or sentences: \[\begin{array}{lll} \hline \textit{logical symbol} & \textit{in natural language} & \textit{technical name} \\ \hline \neg & \text{not} & \text{negation}\\ \land & \text{and} & \text{conjunction}\\ \lor & \text{or} & \text{disjunction}\\ \leftarrow & \text{if }\ldots\text{ then} & \text{implication}\\ \leftrightarrow & \text{if and only if} & \text{equivalence}\\ \hline \end{array}\]

In this theory page and following pages we will go deeper into the connectives. In addition to the propositional variables and the logical operator, there are additional symbols. These are the parentheses \((\) and \()\); we use them to indicate priority in the order of application. More formally, we now give the following definition:

Alphabet An alphabet of propositional logic consists of

a set of propositional variables;
logical symbols: \(\neg\), \(\land\), \(\lor\), \(\rightarrow\), \(\leftrightarrow\);
auxiliary symbols: the brackets \((\) and \()\).

Using symbols from the alphabet, we can now construct compound expressions in propositional logic using fixed rules. These are called logical formulas (in short: formulas) or sentences. In general, we use lowercase Greek letters as variables to represent formulas.

\(\phantom{x}\)

inductive definition of a logic formula Logical formulas can be created using the following rules:

Each propositional letter is a formula;
If \(\varphi\) and \(\psi\) are formulas, then \(\quad\neg\,\varphi\), \(\quad\varphi\land \psi \), \(\quad\varphi\lor\psi \), \( \quad\varphi\rightarrow\psi \), \(\quad \varphi\leftrightarrow\psi\quad \), and \(\quad(\varphi)\quad\) are also formulas;
Nothing else is a formula.

BNF specification The so-called BNF specification (Backus Naur Form) of the language of propositional logic is as follows:

Let \(\mathcal{P}\) be a set of propositional letters and \(p\in\mathcal{P}\). \[\varphi ::= p \;|\; \neg\,\varphi \;|\; \varphi\land\psi \;|\; \varphi\lor\psi \;|\; \varphi\rightarrow\psi \;|\; \varphi\leftrightarrow\psi\;|\; (\varphi) \]

Less symbols Strictly speaking, in the language of propositional logic, the conditional connectives, i.e., implication and equivalence, are not strictly necessary. After all: implication \(p\rightarrow q\) means \(\neg\,p \lor q\) and equivalence \(p\leftrightarrow q\) means \((p\rightarrow q) \land (q\rightarrow p)\). But without the conditional connectives, the translation of expressions in natural language to propositions becomes unnecessarily complicated.

More symbols Some also want to add the symbolic constants true and false to the alphabet, for example, the symbol \(\bot\) for an evidently false statement, also referred to as falsum. The symbol \(\top\) denotes an evidently true statement, also referred to as verum. Actually, these are then connectives without an argument. For now, we do not include them in the alphabet. We will only introduce falsum, the statement that is always false, when we discuss reasoning via natural deduction.

Precedence of connective The following conventions apply to the order of application of connectives:

Negation ( \(\neg\) ) binds the strongest, then conjunction ( \(\land\) ), then disjunction ( \(\lor\) ), then implication ( \(\to\) ) and finally equivalence ( \(\leftrightarrow\) ). Moreover, the convention holds that implication is associative from right to left. That means we can write \(p\rightarrow q \rightarrow r \land s \) instead of \( p \rightarrow \bigl(q\rightarrow ( r \land \neg s)\bigr)\). But with brackets we can always indicate which priorities we use in formulas. For example, \((p\land q)\lor r\) and \(p \land (q\lor r)\) are built according to different construction rules: with \((p\land q)\lor r\), you first build the formula \(p\land q\) from \(p\) and \(q\), and hereafter use it together with \(r\) to create the final formula; for \(p \land (q\lor r)\), you first build the formula \(q\lor q\) from \(q\) and \(r\), and hereafter use it together with \(p\) to create the final formula. They are also essentially different propositions: if \(p\) and \(q\) are false and \(r\) is true, then the first proposition is true, but the second is false according to the rules of the game.

Truth value, valuation of a formula, and truth table Characteristic of a proposition is that it is a meaningful, declarative sentence, which may or may not be true. The truth value of a proposition is true, denoted \(1\), if it is a true statement; the truth value of a proposition is false, denoted \(0\), if it is a false statement. Sometimes we don't yet know whether a proposition variable is true; then we leave it in the middle or wait for more information.

To define the semantics (i.e., meaning) of a formula, we need the notion of valuation. This is a function that assigns a truth value (true or false) to all propositional variables. Based on the truth values of the propositional variables that appear in a formula, we can then determine the truth value of the entire formula. If a propositional variable occurs several times in a formula, enter the same truth value for each occurrence. If \(p\) and \(q\) are propositional variables for which the valuation \(v\) is known, then we define the following valuations for the connectives negation, conjunction and disjunction:

\(v(\neg\,p)=\left\{\begin{array}{ll} 0 & \text{if }v(p)=1\\ 1 & \text{if } v(p)=0\end{array}\right.\)
\(v(p\land q)=\left\{\begin{array}{ll} 1 & \text{if }v(p)=1\text{ and }v(q)=1 \\ 0 & \text{otherwise}\end{array}\right.\)
\(v(p\lor q)=\left\{\begin{array}{ll} 0 & \text{if }v(p)=0\text{ and }v(q)=0 \\ 0 & \text{otherwise}\end{array}\right.\)

The calculation of the truth value of compound proposition uses the following truth table, which you read row by row, with behind the vertical bar the truth values of the mentioned formulas given the truth values of the partial formulas to the left of the vertical bar \[\begin{array}{c|c} \varphi & \neg\,\varphi\\ \hline 0 & 1\\ 1 & 0\end{array}\] \[\begin{array}{cc|cccc} \varphi & \psi & \varphi\land \psi & \varphi\lor \psi & \varphi\rightarrow\psi & \varphi\leftrightarrow\psi\\ \hline 0 & 0 & 0 & 0 & 1 & 1\\ 0 & 1 & 0 & 1 & 1 & 0\\ 1 & 0 & 0 & 1 & 0 & 0\\ 1 & 1 & 1 & 1 & 1 & 1 \end{array}\] Note that if \(\psi\) is true, i.e., has the truth value \(1\), under the implication \(\varphi\rightarrow \psi\) the truth value \(1\) is stated regardless of the truth value of \(\varphi\). In natural language, it feels strange that when you say "saying yes implies agreeing" that "agreeing" doesn't necessarily mean that "saying yes" happened. "Saying no" feels more like "disagreeing" in this natural situation. But in propositional logic, the logical consequence of \(p\rightarrow q\) is only \(\neg \, q\rightarrow \neg\, p\). It cannot be that \(p\) is true, but \(q\) is false.

Logical equivalence Two logical formulas are called (logically) equivalent when each evaluation of the two formulas gives identical results, i.e., when their truth tables are equal to each other.

Examples The formulas \(p\) and \(\neg\,\neg\, p\) are equivalent. \[\begin{array}{c|cc} p & \neg\,p & \neg\,\neg\, p\\ \hline 0 & 1 & 0\\ 1 & 0 & 1\end{array}\]

The formulas \(\neg(p\land q)\) and \(\neg\,p\land \neg q\) are not equivalent because there is a valuation that gives different results: if \(p\) is true and \(q\) is false, then \(\neg(p\land q)\) is true and \(\neg\,p\land \neg q\) is false.