03 Logical Equivalence, Tautological Implication and Modus Ponens

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\to B$, $A\wedge (A\to B)$, and $(A\wedge (A\to B))\to B$.

$A$	$B$	$A\to B$	$A\wedge (A\to B)$	$(A\wedge (A\to B))\to 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\to B$ evaluates to true when either $A$ is false or $B$ is true.
• $A\wedge (A\to B)$ combines $A$ with the implication $A\to B$. It is true only when both $A$ is true and $A\to B$ is true.
• $(A\wedge (A\to B))\to B$ evaluates whether the conjunction of $A$ and $A\to B$ logically entails $B$. The result is always true, meaning that this is a tautology.

Implicational Tautology

Since $(A\wedge (A\to B))\to B$ is always true, it is a tautology. This shows that whenever $A$ and $(A\to B)$ are true, $B$ must also be true. Thus, we can conclude:

$$(A\wedge (A\to B))\models B$$

This means that the truth of $B$ is a logical consequence of the truth of $A$ and $(A\to B)$. In other words, if the LHS (left-hand side) is true, the RHS (right-hand side) must also be true.

Basic Logic Equivalences

See lemma 2.1 in script (2024)

Idempotence: $A\vee A\equiv A$ $A\wedge A\equiv A$

Commutativity: $A\vee B\equiv B\vee A$ $A\wedge B\equiv B\wedge A$

Associativity: $(A\vee B)\vee C\equiv A\vee (B\vee C)$ $(A\wedge B)\wedge C\equiv A\wedge (B\wedge C)$

Absorption: $A\vee (A\wedge B)\equiv A$ $A\wedge (A\vee B)\equiv A$

Distributivity: $A\vee (B\wedge C)\equiv (A\vee B)\wedge (A\vee C)$ $A\wedge (B\vee C)\equiv (A\wedge B)\vee (A\wedge C)$

Double Negation: $\neg (\neg A)\equiv A$

De Morgan’s Laws: $\neg (A\wedge B)\equiv \neg A\vee \neg B$ $\neg (A\vee B)\equiv \neg A\wedge \neg 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:

1. Find a statement $R$.
2. Prove that $R$ is true.
3. 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\to B)\wedge B)\models 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:

1. Start with $S$: $n$ is not prime.

   • This means $n=a\cdot b$, where $a>1$ and $a<n$.

2. Apply this to $2^n-1$:

   • We know $n=ab$, so substitute this into the expression $2^{ab}-1$.

3. Factorize $2^{ab}-1$:

   $$2^{ab}-1=(2^a-1)\left(2^{a(b-1)}+2^{a(b-2)}+\cdots +1\right)$$

4. 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$:

1. Prove $S$: $n=143$ is not prime.

   We can factor 143 as:

   $$143=11\times 13$$

   Therefore, $143$ is composite.

2. 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\to U^k$ and $P:U^k\to 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 ($\exists$):

• Symbol: $\exists$
• Meaning: “There exists at least one element.”
• Example: $\exists x\in \mathbb{R},P(x)$ means “there exists an $x$ in the real numbers such that the predicate $P(x)$ holds true.”

Universal Quantifier ($\forall$):

• Symbol: $\forall$
• Meaning: “For all elements in the universe.”
• Example: $\forall x\in \mathbb{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