Topic: Logical equivalence

Definition: two compound statements A and B are said to be logically equivalent if they always have the same truth table. We denote it by

Ex:

Note: in the truth table of A and B, the statement variables must be placed in the same sequence, in order to compare tables correctly.

Theorem 2: The compound statements A and B are logically equivalent if and only if the compound statement A ↔ B is a tautology. (In a sense, A and B are logically “equal”.)

Laws of propositional algebra are the examples of logically equivalent statements.

Let p, q and be the statement variables, let t denote any tautology and let с denote any contradiction.

1. Properties of c and t:

1.1 p ˅ c ≡ p 1.2 p ˄ t ≡ p

1.3 p ˅ t ≡ t 1.4 p ˄ c ≡ c

2. Properties of negation:

2.1 ~ t ≡ c 2.2 ~ c ≡ t

2.3 p ˅ ~ p ≡ t 2.4 p ˄ ~ p ≡ c

2.5 ~ (~p) ≡ p

Other lows (properties of connectives) are also familiar from the set algebra and the 2-element. Boolean algebra: commutative, associative, idempotent, distributive, De Morgan’s laws. For example, property 1.1 says the following:

- “any statement p or any permanently false statement с is a true statement if and only if p is true”.

- “the truth value of any statement p is the same as the value of p or false statement c, never mind what are the meanings of p and c.”

Now we can talk about propositional algebra:

{set of propositions} + { ˅, ˄, ~}. It’s laws are just patterns for making compound statements (sentences of natural language) with the same truth values.

Note:

- In propositional algebra connectives “→” and “↔” are considered as shorthand notations for some compositions made of ˅, ˄, ~.

- “≡” replaces the words “have the same truth values (= truth table)”.

Using these properties it is possible to transform statements of natural language without changing their true/false value.

Ex1: Given a compound statement:

Write the negation of this statement:

Ex2: Statement:

Write this negation:

Ex3: Prove that:

It’s contrapositive statement:

(Why? Because we proved in Ex3 that both p → q and ~p → ~q have the same truth table. Our common sense tells the same here.)

Ex4: Given

It is certainly true.

It’s contrapositive statement is also true (by Ex3).

Ex5: Prove that:

In this case it is easier to use the contrapositive statement, which is

“If n is not odd then n² is not odd” ≡ “If n is even the n² is even”

Proof of this statement: If n is even then n = 2k for some int k. Now n² = (2k)² =4k² = 2 * (2k²). So n² is even.

Proof: It is easy to check by making truth tables that p ↔ q ≡ (p → q) ˄ (q → p).

So in order to prove the original statement (theorem), we must prove both “If n² is odd then n is odd” is true and “If n is odd then n² is odd” is true.

The first statement (p → q) was proved in Ex5.

So we just prove here the statement “If n is odd then n² is odd”. If n is odd then it must have the form n = 2k+1 for some int k. But then n² = (2k +1)² = 4k² +4k +1. Hence, n² is odd. This is the proof of the statement (q → p).