Lecture from: 25.09.2024  Video: Videos ETHZ
Logical Equivalence and Tautological Implication
To illustrate the concept of tautological implication, let’s examine the truth values of $A$, $B$, and various logical expressions involving them. Specifically, we will build a truth table for the expressions $A→B$, $A∧(A→B)$, and $(A∧(A→B))→B$.
$A$  $B$  $A→B$  $A∧(A→B)$  $(A∧(A→B))→B$ 

0  0  1  0  1 
0  1  1  0  1 
1  0  0  0  1 
1  1  1  1  1 
Observations from the truth table:
 $A→B$ evaluates to true when either $A$ is false or $B$ is true.
 $A∧(A→B)$ combines $A$ with the implication $A→B$. It is true only when both $A$ is true and $A→B$ is true.
 $(A∧(A→B))→B$ evaluates whether the conjunction of $A$ and $A→B$ logically entails $B$. The result is always true, meaning that this is a tautology.
Implicational Tautology
Since $(A∧(A→B))→B$ is always true, it is a tautology. This shows that whenever $A$ and $(A→B)$ are true, $B$ must also be true. Thus, we can conclude:
$(A∧(A→B))⊨B$This means that the truth of $B$ is a logical consequence of the truth of $A$ and $(A→B)$. In other words, if the LHS (lefthand side) is true, the RHS (righthand side) must also be true.
Basic Logic Equivalences
See lemma 2.1 in script (2024)
Idempotence: $A∨A≡A$ $A∧A≡A$
Commutativity: $A∨B≡B∨A$ $A∧B≡B∧A$
Associativity: $(A∨B)∨C≡A∨(B∨C)$ $(A∧B)∧C≡A∧(B∧C)$
Absorption: $A∨(A∧B)≡A$ $A∧(A∨B)≡A$
Distributivity: $A∨(B∧C)≡(A∨B)∧(A∨C)$ $A∧(B∨C)≡(A∧B)∨(A∧C)$
Double Negation: $¬(¬A)≡A$
De Morgan’s Laws: $¬(A∧B)≡¬A∨¬B$ $¬(A∨B)≡¬A∧¬B$
Proving a Statement using Modus Ponens
A typical proof pattern you’ll encounter in logic is called modus ponens. The idea is simple: suppose we want to prove a statement $S$.
Steps:
 Find a statement $R$.
 Prove that $R$ is true.
 Prove that $R⟹S$.
Once these are established, we can conclude that $S$ is true by modus ponens.
Important Note:
It’s crucial not to confuse the direction of implication. Proving $S⟹R$ and $R$ is true does not imply that $S$ is true.
Let’s use an example to illustrate this mistake.
Statement $S$: $1<0$
Let’s attempt to prove this (incorrectly):
 Step 1: Start with $1<0$.
 Step 2: From $1<0$, we can deduce $2<1$ (by adding 1 to both sides).
 Step 3: Next, we deduce $2>1$ by multiplying by $1$ (assuming $1<0$ makes $1$ negative).
Now, since $2>1$ is clearly true, one might wrongly conclude that $1<0$ (the original $S$) is true as well. This proof is wrong because we are not following the direction of implication correctly. $((a→B)∧B)⊨B$ is wrong.
Example
Statement: $2_{143}−1$ is not a prime.
This specific case might be difficult to prove directly, so in discrete mathematics, we often generalize the problem to explore broader patterns.
Generalized Statement:
Let’s generalize the problem by forming a new statement.
 Statement $S$: $n$ is not prime.
 Statement $T$: $2_{n}−1$ is not prime.
We aim to prove that if $S$ is true, then $T$ must also be true.
Proof Outline:

Start with $S$: $n$ is not prime.
 This means $n=a⋅b$, where $a>1$ and $a<n$.

Apply this to $2_{n}−1$:
 We know $n=ab$, so substitute this into the expression $2_{ab}−1$.

Factorize $2_{ab}−1$:
$2_{ab}−1=(2_{a}−1)(2_{a(b−1)}+2_{a(b−2)}+⋯+1)$ 
Conclusion: The expression $2_{ab}−1$ is factored into two terms, meaning $2_{n}−1$ (where $n=ab$) is not prime if $n$ is composite. This generalizes the idea that for composite numbers $n$, the expression $2_{n}−1$ is not prime.
Applying to $n=143$:

Prove $S$: $n=143$ is not prime.
We can factor 143 as:
$143=11×13$Therefore, $143$ is composite.

Apply the Generalized Result (Modus Ponens):
 We now know that $S$ is true ($143$ is not prime).
 From our generalized proof, $S⟹T$ (if $n$ is not prime, then $2_{n}−1$ is not prime).
By Modus Ponens:
 Since $S$ is true, we conclude that $T$ must be true.
Predicate Logic
In predicate logic, predicates are similar to functions, but they output truth values rather than numerical values. A predicate can be thought of as a symbol or alias that takes in a variable number of inputs from a universe $U$, and depending on these inputs, the predicate evaluates to either true or false.
Formally: $F:U_{k}→U_{k}$ and $P:U_{k}→0,1$
Predicate Quantifiers
Quantifiers are used to express the scope or extent of the predicates over elements in the universe $U$. The two most common quantifiers are:
Existential Quantifier ($∃$):
 Symbol: $∃$
 Meaning: “There exists at least one element.”
 Example: $∃x∈R,P(x)$ means “there exists an $x$ in the real numbers such that the predicate $P(x)$ holds true.”
Universal Quantifier ($∀$):
 Symbol: $∀$
 Meaning: “For all elements in the universe.”
 Example: $∀x∈R,P(x)$ means “for all $x$ in the real numbers, the predicate $P(x)$ holds true.”
A quantifier and predicate is a formula, whose truth value is often dependent on which universe we are talking about.
Continue here: 04 Quantifiers