Propositional Equivalences

Introduction

An important type of step used in a mathematical argument is the replacement of a statement with another statement with the same truth value. Because of this, methods that produce propositions with the same truth value as a given compound proposition are used extensively in the construction of mathematical arguments.

DEFINITION 1:

A compound proposition that is always true, no matter what the truth values of the propositional variables that occur in it, is called a tautology. A compound proposition that is always false is called a contradiction. A compound proposition that is neither a tautology nor a contradiction is called a contingency.

Examples:
"It is either raining or it is not raining" is a tautology: it is always true.
"It is both raining and not raining" is a contradiction. It cannot ever be true.
"It is raining and the sun is out" is a contingency: it might be true, or might not.

Logical Equivalences

Compound propositions that have the same truth values in all possible cases are called logically equivalent.

Example of a Tautology and a Contradiction
p ¬p p ∨ ¬p p ∧ ¬p
T F T F
F T T F

"It is red or not red" is always true; "It is both red and not red" is always false.

De Morgan's Laws
¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q

Row 1: "It's not raining and sunny" means that it is not raining or it's not sunny.
Row 2: "It's not raining or sunny" means that it is not raining and it's not sunny.
Using a truth table to demonstrate De Morgan's second law:

Truth Tables for ¬(p ∨ q) and ¬p ∧ ¬q
p q p ∨ q ¬(p ∨ q) ¬p ¬q ¬p ∧ ¬q
T T T F F F F
T F T F F T F
F T T F T F F
F F F T T T T

A whole bunch o' fundamental equivalences we can use as building blocks for more complex proofs:

Logical Equivalences
Equivalence Name
p ∧ T ≡ p
p ∨ F ≡ p 		Identity laws
p ∨ T ≡ T
p ∧ F ≡ F 		Domination laws
p ∨ p ≡ p
p ∧ p ≡ p 		Idempotent laws
¬(¬p) ≡ p Double negation law
p ∨ q ≡ q ∨ p
p ∧ q ≡ q ∧ p 		Commutative laws
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r) 		Associative laws
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) 		Distributive laws
p ∨ (p ∧ q) ≡ p
p ∧ (p ∨ q) ≡ p 		Absorption laws
p ∨ ¬p ≡ T
p ∧ ¬p ≡ F 		Negation laws
Logical Equivalences Involving Conditional Statements
p → q ≡ ¬p ∨ q
p → q ≡ ¬q → ¬p
p ∨ q ≡ ¬p → q
p ∧ q ≡ ¬(p → ¬q)
¬(p → q) ≡ p ∧ ¬q
(p → q) ∧ (p → r) ≡ p → (q ∧ r)
Using De Morgan's Laws

Negate: "You have studied hard and you will get an A."
Answer: "Either you have not studied hard or you will not get an A."

Negate: "You have slacked off or you have studied the wrong subject."
Answer: "You have not slacked off and you have not studied the wrong subject."

Constructing New Logical Equivalences

New logical equivalences can be constructed from already existing logical equivalences given that the truth value of the original compund proposition shouldn't change when replacing with the latter proposition.

Example Show that ¬ (p→ q) and p ∧ ¬q are logically equivalent

Solution We have
¬(p →q)≡ ¬(¬p ∨ q)
≡ ¬(¬p) ∧ ¬q
≡ p ∧ ¬q

Propositional Satisfiability

A compound proposition is satisfiable if there exists a combination of truth values that render it true.
("It is raining or it is sunny" and "It is not raining or it is not sunny") are mutually satisfiable.
("It is raining or it is sunny" and "It is not raining and it is not sunny") are not mutually satisfiable.

Applications of Satisfiability

There are many applications of this idea, in circuit design, robotics, software testing, genetics and more. One such application is to the game of...

Sudoku
A Sudoku Puzzle

NOT COVERED FURTHER SPRING 2018

Solving Satisfiability Problems

To systematically test for the truth of a compound proposition with 1000 variables involves 21000 propositions, the number: 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
Even a supercomputer will take longer than the life of the universe to solve such a problem. This problem is NP-complete.

Test Yourself!
  1. A statement that must always be true is called a
    1. proposition
    2. tautology
    3. non sequitur
    4. implication
  2. A proposition that is always false is called a
    1. futility
    2. contradiction
    3. tautology
    4. palindrome
  3. Which of the following is a logical equivalence?
    1. p ∧ q ≡ p ∧ ¬q
    2. p → q ≡ ¬p ∨ q
    3. p → q ≡ p ∨ q
  4. A compound proposition is satisfiable if
    1. it can never be true
    2. there is some combination of truth values for its variables that make it true
    3. if all truth values for its variables that make it true
    4. if it is satisfying to contemplate
  5. A portion of a circuit board that is not satisfiable is
    1. useless
    2. like a not gate
    3. energetic
    4. crucial
Answers

1. b; 2. b; 3. b; 4. b; 5. a;