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}≡a_{2}+2ab+b_{2}$.

Similarly, $0=2a−a−a$ is not actually equal, but equivalent. Thus, $0≡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$ | $¬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∨B$ |
---|---|---|

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 1 |

The formula for the OR operation is:

$A∨B={10 ifA=1orB=1otherwise $#### And

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

$A$ | $B$ | $A∧B$ |
---|---|---|

0 | 0 | 0 |

0 | 1 | 0 |

1 | 0 | 0 |

1 | 1 | 1 |

The formula for the AND operation is:

$A∧B={10 ifA=1andB=1otherwise $#### Combinations

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

$¬A∨B$**Truth Table for Implication ($¬A∨B$)**

$A$ | $B$ | $¬A∨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 "$→$" represents logical implication, which can be read as “if A, then B.”

**Truth Table for Implication ($A→B$)**

$A$ | $B$ | $A→B$ |
---|---|---|

0 | 0 | 1 |

0 | 1 | 1 |

1 | 0 | 0 |

1 | 1 | 1 |

**Equivalency with Previous Expression**

We can see the equivalency between $A→B$ and $¬A∨B$ as follows:

$A→B≡¬A∨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 $⊤$. 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 $⊥$. 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∧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∧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 $⊨$. __Important:__ A logical consequence takes two formulas (LHS and RHS) and produces a statement out of this.

**Example 1:**
$A⊨B$ and $B⊨A$ $⟺$ (if and only if) $A≡B$.

**Example 2:**
$F≡⊥$ $⟺$ $¬F≡⊤$

## 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→B$**and**$A↔B$**:- These symbols are used
**between formulas**and are themselves formulas. - $A→B$: “If $A$, then $B$” (material implication).
- $A↔B$: “A if and only if B” (biconditional).

- These symbols are used
**$A⇒B$**and**$A⇔B$**:- These symbols are used
**between statements**and are themselves**statements**(either true or false). - $A⇒B$: “If $A$ is true, then $B$ must be true” (logical implication).
- $A⇔B$: “A is true if and only if B is true” (logical equivalence).

- These symbols are used
**$A⟹˙ B$**:- Similar to $A⇒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.

- Similar to $A⇒B$ but
**$A⊨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**.

- This symbol expresses
**$A≡B$**:- Used
**between formulas**and states that they are**logically equivalent**, meaning they always have the same truth value. - This is a
**statement**.

- Used

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