02 Propositional Logic and Formulas

Lecture from: 23.09.2024 | Video: Videos ETHZ

Statements

A mathematical statement which is true is called a theorem, a lemma (=“smaller sub theorem”) or a corollary (=consequence of another theorem or lemma).

A mathematical statement not known (but believed) to be true or false is called a conjecture.

Propositional Logic

Equality and Equivalency

In school, you might have encountered expressions like $(a+b{)}^2=a^2+2ab+b^2$. However, according to the professor, the left-hand side (LHS) and the right-hand side (RHS) are not equal but rather equivalent. They would be equal if the same expression were written on both sides. They are equivalent because for any values of $a$ and $b$, both sides yield the same result. Therefore, it should be noted as $(a+b{)}^2\equiv a^2+2ab+b^2$.

Similarly, $0=2a-a-a$ is not actually equal, but equivalent. Thus, $0\equiv 2a-a-a$ is “more” correct.

Boolean values

In propositional (or boolean) logic you often use the symbols $0$ and $1$ for the truth values of true and false. These symbols are not to be understood as numbers but purely as symbols. For example the average of 0 and 1 doesn’t have a meaning (in this context).

Boolean variables

Now we’ll introduce (boolean) variables which can accept truth values as values. These variables are NOT statements.

Operations

Let us define the Boolean variables $A,B,C$ which can take the values $0$ (false) and $1$ (true). Now let us introduce “symbols” to define boolean operations.

Negation

The negation operation (NOT) flips the value of a Boolean variable:

$A$	$\neg A$
0	1
1	0

Or

The logical (inclusive) OR operation combines two Boolean variables. The result is true if at least one of the operands is true:

$A$	$B$	$A\vee B$
0	0	0
0	1	1
1	0	1
1	1	1

The formula for the OR operation is:

$$A\vee B=\{\begin{array}{ll}1& \text{if }A=1\text{ or }B=1\\ 0& \text{otherwise}\end{array}$$

And

The logical AND operation combines two Boolean variables. The result is true only if both operands are true:

$A$	$B$	$A\wedge B$
0	0	0
0	1	0
1	0	0
1	1	1

The formula for the AND operation is:

$$A\wedge B=\{\begin{array}{ll}1& \text{if }A=1\text{ and }B=1\\ 0& \text{otherwise}\end{array}$$

Combinations

The logical expression “not A or B” can be represented as:

$$\neg A\vee B$$

Truth Table for Implication ($\neg A\vee B$)

$A$	$B$	$\neg A\vee B$
0	0	1
0	1	1
1	0	0
1	1	1

This expression evaluates to true if either $B$ is true or $A$ is false.

Implication Symbol ”→”

The implication symbol "$\to$" represents logical implication, which can be read as “if A, then B.”

Truth Table for Implication ($A\to B$)

$A$	$B$	$A\to B$
0	0	1
0	1	1
1	0	0
1	1	1

Equivalency with Previous Expression

We can see the equivalency between $A\to B$ and $\neg A\vee B$ as follows:

$$A\to B\equiv \neg A\vee B$$

This means that the statement ”$A$ implies $B$” is logically the same as saying “either $A$ is false or $B$ is true.”

Tautology and Unsatisfiable

A formula that is always true, regardless of the truth values of its variables, is called a tautology and is denoted by the symbol $\top$. The formula itself isn’t inherently “true,” but it always resolves to true when evaluated with any combination of truth values for the Boolean variables. To determine whether a formula is a tautology, you substitute the Boolean variables into the formula and check if the formula resolves to true in every case.

On the other hand, a formula that always resolves to false, regardless of the truth values of its variables, is called unsatisfiable and is denoted by the symbol $\perp$. The formula itself isn’t inherently “false,” but it is impossible for the formula to be satisfied by any combination of truth values. In other words, there is no possible assignment of Boolean variables that can make the formula true.

A tautology or an unsatisfiable formula is not a statement.

Statement vs Formula Confusion

This distinction can be tricky, so it’s worth clarifying the difference between a statement (Aussage) and a formula (Formel). This explanation is based on lectures by Prof. Ueli Maurer, though other sources might define these terms differently.

Statement

A statement is an object that is strictly either true or false. It is static and unchanging in nature. Even if we do not know whether a statement is true or false, we know that it must be one of the two. There is no ambiguity in its truth value.

Example: Every even number can be written as the sum of two prime numbers. (Goldbach Conjecture)

This is a statement. It is either true or false, but as of now, we don’t know its truth value.

Formula

A formula, on the other hand, is a dynamic object. Its truth value can change depending on the values of the Boolean variables involved. Logic and logical symbols are typically used to express formulas. The truth value of a formula is evaluated based on a given set of conditions or assignments to its variables. A formula is not inherently true or false without specific inputs.

Example: $A\wedge B$

This is a formula that can be true or false depending on the truth values of $A$ and $B$.

When Can Formulas Be Statements?

A formula can be interpreted as a statement in a specific context where all the Boolean variables involved are determined and defined. For example, if you have Boolean variables $A$, $B$, and $C$ and a formula involving these variables, the formula becomes a statement when you assign specific values to $A$, $B$, and $C$. At that point, the formula will resolve to either true or false.

Example: If $A=1$ (true) and $B=0$ (false), then the formula $A\wedge B$ becomes a statement that evaluates to false.

Logical Consequence (Logical Modelling)

A logical consequence expresses the relationship between two formulas, where if the formula on the left-hand side (LHS) is true, then the formula on the right-hand side (RHS) must also be true. The key point is that the RHS might still be true even if the LHS isn’t. This concept is denoted by the symbol $\models$. Important: A logical consequence takes two formulas (LHS and RHS) and produces a statement out of this.

Example 1: $A\models B$ and $B\models A$ $⟺$ (if and only if) $A\equiv B$.

Example 2: $F\equiv \perp$ $⟺$ $\neg F\equiv \top$

Symbols Confusion

Let’s clarify when to use certain logical symbols and their distinctions. Each symbol has a specific role in formal logic, whether it relates formulas, statements, or is used to justify implications.

• $A\to B$ and $A\leftrightarrow B$:
  • These symbols are used between formulas and are themselves formulas.
  • $A\to B$: “If $A$, then $B$” (material implication).
  • $A\leftrightarrow B$: “A if and only if B” (biconditional).
• $A\Rightarrow B$ and $A\iff B$:
  • These symbols are used between statements and are themselves statements (either true or false).
  • $A\Rightarrow B$: “If $A$ is true, then $B$ must be true” (logical implication).
  • $A\iff B$: “A is true if and only if B is true” (logical equivalence).
• $A\dot{⟹}B$:
  • Similar to $A\Rightarrow B$ but provides justification or a reasoning step for the implication.
  • The dot emphasizes that the implication is being justified, rather than purely presented as a logical truth.
• $A\models B$:
  • This symbol expresses semantic entailment, meaning that if $A$ is true, then $B$ must be true in all models.
  • Used between formulas but is itself a statement.
• $A\equiv B$:
  • Used between formulas and states that they are logically equivalent, meaning they always have the same truth value.
  • This is a statement.

Continue here: 03 Logical Equivalence, Tautological Implication and Modus Ponens