DM-01

Course 1

Propositional Logic

Master the fundamentals of propositional logic, including propositions, logical connectives, truth tables, logical equivalences, and normal forms. These concepts form the foundation of discrete mathematics and are essential for computer science.

Learning Objectives

Understand the concept of propositions and distinguish them from other types of sentences
Master all logical connectives (negation, conjunction, disjunction, implication, biconditional) and their properties
Construct and interpret truth tables for compound propositions
Apply logical equivalences including De Morgan's laws to simplify propositions
Convert propositions to Disjunctive Normal Form (DNF) and Conjunctive Normal Form (CNF)
Recognize tautologies, contradictions, and contingencies

1. Propositions

Definition 1.1: Proposition

A proposition (or statement) is a declarative sentence that is either true or false, but not both.

We call the truth or falsity of a proposition its truth value, denoted by:

$T$ or $1$ for true
$F$ or $0$ for false

Example: Identifying Propositions

Determine which of the following are propositions:

"Washington, D.C., is the capital of the United States."
✓ Proposition - This is a declarative sentence with truth value T (true).
"What time is it?"
✗ Not a proposition - This is a question, not a declarative sentence.
"x + 2 = 5"
✗ Not a proposition - This is an open sentence. Its truth value depends on the value of x.
"Read this carefully."
✗ Not a proposition - This is a command, not a declarative sentence.
"2 + 2 = 5"
✓ Proposition - This is a declarative sentence with truth value F (false).

Remark

Paradoxes are not considered propositions. For example:

"This statement is false." (Liar's paradox)
"I am lying."

These sentences cannot be assigned a consistent truth value, so they are not propositions.

Definition 1.2: Propositional Variables

We use letters such as $p$ , $q$ , $r$ , $s$ , ... to represent propositional variables, which stand for propositions. The area of logic that deals with propositions is called propositional logic or propositional calculus.

2. Logical Connectives

Logical operators (or logical connectives) are used to form new propositions from existing propositions. These compound propositions are built using propositional variables and logical connectives.

Definition 1.3: Logical Connectives

The fundamental logical connectives are:

Name	Symbol	Read as	Example
Negation	$\neg p$	NOT p	It is not raining
Conjunction	$p \land q$	p AND q	It is raining and cold
Disjunction	$p \lor q$	p OR q	It is raining or cold
Exclusive Or	$p \oplus q$	p XOR q	Either p or q, but not both
Conditional	$p \rightarrow q$	IF p THEN q	If it rains, then it is wet
Biconditional	$p \leftrightarrow q$	p IF AND ONLY IF q	p is true iff q is true

Note

Precedence of Logical Operators:

When multiple operators appear without parentheses, they are evaluated in this order (highest to lowest):

\neg, \quad \land, \quad \lor, \quad \rightarrow, \quad \leftrightarrow

For example, $\neg p \land q \rightarrow r$ means $((\neg p) \land q) \rightarrow r$ .

Conditional Statements

The conditional statement $p \rightarrow q$ (also called an implication) is one of the most important connectives in logic.

Definition 1.4: Conditional Statement

For propositions $p$ and $q$ , the conditional statement $p \rightarrow q$ is false when $p$ is true and $q$ is false, and true otherwise.

In $p \rightarrow q$ :

$p$ is called the hypothesis (or antecedent, or premise)
$q$ is called the conclusion (or consequence)

Example: Conditional Statement Variations

For the implication $p \rightarrow q$ , we can define three related conditional statements:

Converse: $q \rightarrow p$
Inverse: $\neg p \rightarrow \neg q$
Contrapositive: $\neg q \rightarrow \neg p$

Important: The contrapositive is logically equivalent to the original implication, while the converse and inverse are equivalent to each other but not to the original.

Definition 1.5: Biconditional Statement

The biconditional statement $p \leftrightarrow q$ (read "p if and only if q" or "p iff q") is true when $p$ and $q$ have the same truth value, and false otherwise.

3. Truth Tables

A truth table displays the truth value of a compound proposition for all possible combinations of truth values of its propositional variables.

Theorem 1.1: Truth Table Size

For a compound proposition with $n$ distinct propositional variables, the truth table has $2^n$ rows.

Example: Truth Tables for Basic Connectives

Here are the truth tables for the fundamental logical connectives:

Negation ( $\neg p$ )

$p$	$\neg p$
T	F
F	T

Conjunction, Disjunction, and XOR

$p$	$q$	$p \land q$	$p \lor q$	$p \oplus q$
T	T	T	T	F
T	F	F	T	T
F	T	F	T	T
F	F	F	F	F

Conditional and Biconditional

$p$	$q$	$p \rightarrow q$	$p \leftrightarrow q$
T	T	T	T
T	F	F	F
F	T	T	F
F	F	T	T

Note: The conditional $p \rightarrow q$ is false only when the premise is true but the conclusion is false (highlighted in red).

4. Logical Equivalences

Definition 1.6: Tautology, Contradiction, and Contingency

Tautology: A proposition that is always true, e.g., $p \lor \neg p$
Contradiction: A proposition that is always false, e.g., $p \land \neg p$
Contingency: A proposition that is neither a tautology nor a contradiction

Definition 1.7: Logical Equivalence

Two propositions $p$ and $q$ are logically equivalent, denoted $p \equiv q$ , if $p \leftrightarrow q$ is a tautology.

Equivalently, $p \equiv q$ means $p$ and $q$ have the same truth value in all possible cases.

Theorem 1.2: Fundamental Logical Equivalences

The following logical equivalences are fundamental and frequently used:

Identity Laws:

$p \land T \equiv p$

$p \lor F \equiv p$

Domination Laws:

$p \lor T \equiv T$

$p \land F \equiv F$

Idempotent Laws:

$p \lor p \equiv p$

$p \land p \equiv p$

Double Negation Law:

$\neg(\neg p) \equiv p$

Commutative Laws:

$p \lor q \equiv q \lor p$

$p \land q \equiv q \land p$

Associative Laws:

$(p \lor q) \lor r \equiv p \lor (q \lor r)$

$(p \land q) \land r \equiv p \land (q \land r)$

Distributive Laws:

$p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$

$p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$

De Morgan's Laws:

$\neg(p \land q) \equiv \neg p \lor \neg q$

$\neg(p \lor q) \equiv \neg p \land \neg q$

Absorption Laws:

$p \lor (p \land q) \equiv p$

$p \land (p \lor q) \equiv p$

Negation Laws:

$p \lor \neg p \equiv T$

$p \land \neg p \equiv F$

Theorem 1.3: Conditional and Biconditional Equivalences

Implication Laws: $p \rightarrow q \equiv \neg p \lor q$

Contrapositive Law: $p \rightarrow q \equiv \neg q \rightarrow \neg p$

Biconditional Laws:

$p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p)$

$p \leftrightarrow q \equiv (p \land q) \lor (\neg p \land \neg q)$

Proof of De Morgan's Laws

We prove $\neg(p \land q) \equiv \neg p \lor \neg q$ using a truth table:

$p$	$q$	$p \land q$	$\neg(p \land q)$	$\neg p$	$\neg q$	$\neg p \lor \neg q$
T	T	T	F	F	F	F
T	F	F	T	F	T	T
F	T	F	T	T	F	T
F	F	F	T	T	T	T

Since the columns for $\neg(p \land q)$ and $\neg p \lor \neg q$ are identical (highlighted), the two propositions are logically equivalent. The second De Morgan's law can be proven similarly.

∎

Example: Simplifying Propositions

Simplify the proposition $(p \lor \neg q) \land (\neg p \lor \neg q)$

Solution:

$(p \lor \neg q) \land (\neg p \lor \neg q)$

$\equiv ((p \lor \neg q) \land \neg p) \lor ((p \lor \neg q) \land \neg q)$ (Distributive law)

$\equiv ((\neg p \land p) \lor (\neg p \land \neg q)) \lor ((p \land \neg q) \lor (\neg q \land \neg q))$ (Distributive law)

$\equiv (F \lor (\neg p \land \neg q)) \lor ((p \land \neg q) \lor \neg q)$ (Negation and Idempotent laws)

$\equiv (\neg p \land \neg q) \lor (p \land \neg q) \lor \neg q$ (Identity law)

$\equiv ((\neg p \land \neg q) \lor (p \land \neg q)) \lor \neg q$ (Associative law)

$\equiv ((\neg p \lor p) \land \neg q) \lor \neg q$ (Distributive law)

$\equiv (T \land \neg q) \lor \neg q$ (Negation law)

$\equiv \neg q \lor \neg q$ (Identity law)

$\equiv \neg q$ (Idempotent law)

5. Propositional Normal Forms

Definition 1.8: Literal and Clause

A literal is a variable or its negation, e.g., $p$ , $\neg q$
A conjunctive clause (or simply clause) is a conjunction of literals
A disjunctive clause is a disjunction of literals

Definition 1.9: Disjunctive Normal Form (DNF)

A formula is in Disjunctive Normal Form (DNF) if it is written as a disjunction of conjunctive clauses.

General form:

(L_{11} \land L_{12} \land \cdots \land L_{1k_1}) \lor (L_{21} \land L_{22} \land \cdots \land L_{2k_2}) \lor \cdots

where each $L_{ij}$ is a literal.

Example: $(p \land q) \lor (p \land \neg q) \lor (\neg p \land r)$

Definition 1.10: Conjunctive Normal Form (CNF)

A formula is in Conjunctive Normal Form (CNF) if it is written as a conjunction of disjunctive clauses.

General form:

(L_{11} \lor L_{12} \lor \cdots \lor L_{1k_1}) \land (L_{21} \lor L_{22} \lor \cdots \lor L_{2k_2}) \land \cdots

where each $L_{ij}$ is a literal.

Example: $(p \lor q) \land (p \lor \neg r) \land (\neg q \lor r)$

Definition 1.11: Minterm and Maxterm

Minterm: A conjunctive clause where each variable appears exactly once (either negated or not). For n variables, there are $2^n$ minterms.
Example with 3 variables: $p \land q \land \neg r$
Maxterm: A disjunctive clause where each variable appears exactly once (either negated or not). For n variables, there are $2^n$ maxterms.
Example with 3 variables: $p \lor \neg q \lor r$

Definition 1.12: Full Normal Forms

Full Disjunctive Normal Form: A DNF where every clause is a minterm
Full Conjunctive Normal Form: A CNF where every clause is a maxterm

Theorem 1.4: Existence of Normal Forms

Every compound proposition can be expressed in both DNF and CNF. Moreover, the full DNF and full CNF representations are unique (up to reordering of terms).

Example: Converting to DNF and CNF

Convert the proposition $p \rightarrow (q \land r)$ to DNF and CNF.

Step 1: Eliminate the implication

$p \rightarrow (q \land r) \equiv \neg p \lor (q \land r)$

Step 2: Apply distributive law for DNF (already in DNF)

$\neg p \lor (q \land r)$ is already in DNF form.

DNF: $\neg p \lor (q \land r)$

Step 3: Convert to CNF using distributive law

$\neg p \lor (q \land r)$

$\equiv (\neg p \lor q) \land (\neg p \lor r)$ (Distributive law)

CNF: $(\neg p \lor q) \land (\neg p \lor r)$

Example: Constructing Full DNF from Truth Table

Find the full DNF of a proposition with the following truth table:

$p$	$q$	Output
T	T	T
T	F	F
F	T	T
F	F	F

Solution: Take each row where the output is T (highlighted rows):

Row 1: $p \land q$ (both variables are true)
Row 3: $\neg p \land q$ (p is false, q is true)

Full DNF: $(p \land q) \lor (\neg p \land q)$

This can be simplified to just $q$ using factoring, but the full DNF representation is unique.

Practice Quiz

Propositional Logic Quiz

Questions

Correct

Accuracy

Which of the following is a proposition?

Easy

Not attempted

What is the negation of the proposition 'It is raining'?

Easy

Not attempted

For the implication

p \rightarrow q

, when is this statement false?

Medium

Not attempted

Which of the following is logically equivalent to

p \rightarrow q

Medium

Not attempted

What is the negation of

p \rightarrow q

Medium

Not attempted

De Morgan's law states that

\neg(p \land q)

is equivalent to:

Medium

Not attempted

A compound proposition that is always true is called a:

Easy

Not attempted

How many rows are needed in a truth table for a compound proposition with 4 propositional variables?

Easy

Not attempted

Which of the following is in Disjunctive Normal Form (DNF)?

Hard

Not attempted

The contrapositive of

p \rightarrow q

is:

Hard

Not attempted

Frequently Asked Questions

Why is 'p → q' true when p is false?

This is called vacuous truth or material implication. The statement "If p then q" only makes a claim about what happens when p is true. When p is false, the implication makes no claim, so it's considered vacuously true.

Example: "If I win the lottery (false), then I'll buy you a car." Since I didn't win the lottery, the promise is not broken regardless of whether I buy you a car.

What's the difference between 'or' in logic and everyday language?

In logic, $∨$ is inclusive OR: "p or q" means at least one is true (possibly both). In everyday language, "or" can be inclusive or exclusive depending on context.

Exclusive OR ( $⊕$ ) means exactly one is true, but not both. For example, "You can have tea or coffee" typically means exclusive or in a restaurant context.

How do I remember De Morgan's Laws?

Think: "Break the line, change the sign." When you negate a compound statement:

Break the line: Remove the parentheses and change $∧$ to $∨$ (or vice versa)
Change the sign: Negate each individual proposition

So $¬(p ∧ q)$ becomes $¬p ∨ ¬q$ .

What's the practical use of normal forms?

Normal forms are crucial in:

Digital circuit design: DNF corresponds to sum-of-products, CNF to product-of-sums
SAT solvers: Many automated theorem provers work with CNF
Database queries: SQL WHERE clauses often use DNF
Simplification: Standardized forms make it easier to compare and simplify propositions

Is the contrapositive always equivalent to the original implication?

Yes! $p → q$ is always logically equivalent to its contrapositive $¬q → ¬p$ . This is a fundamental truth in logic and is the basis for proof by contrapositive.

However, the converse ( $q → p$ ) and inverse ( $¬p → ¬q$ ) are NOT necessarily equivalent to the original statement (though they are equivalent to each other).

Example: "If it rains, the ground is wet" has the same meaning as "If the ground is not wet, it didn't rain."

How many logical equivalences do I need to memorize?

Focus on these essential ones:

De Morgan's Laws: For negating AND/OR
Distributive Laws: For rearranging expressions
Implication Law: $p → q ≡ ¬p ∨ q$
Double Negation: $¬¬p ≡ p$

The others (identity, domination, idempotent, etc.) are intuitive and can be derived from basic logic principles.

Propositional Logic

1. Propositions

2. Logical Connectives

Conditional Statements

3. Truth Tables

Negation (¬p\neg p¬p)

Conjunction, Disjunction, and XOR

Conditional and Biconditional

4. Logical Equivalences

5. Propositional Normal Forms

Practice Quiz

Frequently Asked Questions

Why is 'p → q' true when p is false?

What's the difference between 'or' in logic and everyday language?

How do I remember De Morgan's Laws?

What's the practical use of normal forms?

Is the contrapositive always equivalent to the original implication?

How many logical equivalences do I need to memorize?

Negation ( $\neg p$ )