Source: This page was researched using GeeksforGeeks — Propositional Logic . The material below has been reorganized and rewritten for Discrete English.

Proposition Logic

Propositional logic is a system of formal logic that deals with statements that have a definite truth value.

What is a Proposition?

A proposition is a declarative statement that can be classified as either true or false, but not both at the same time.

✓

Example

“1 + 1 = 2” is a proposition because it has a definite truth value: True.

More Examples

The Sun rises in the East.

True

1 + 1 = 3.

False

“b” is a vowel.

False

What is Not a Proposition?

Not every sentence is a proposition. A sentence must have a definite truth value to qualify.

Questions, commands, and statements whose truth depends on an unspecified variable are generally not propositions.

“What time is it?”

Question

“Go outside.”

Command

x + 1 = 2

Open sentence

Types of Propositions

Atomic Propositions

An atomic proposition is a simple proposition that does not contain another proposition connected to it by a logical connective.

For example, let p represent: “It is raining.”

Compound Propositions

A compound proposition is created by combining propositions using logical connectives.

p ∧ q

If p means “It is raining” and q means “It is Friday,” then p ∧ q means “It is raining and it is Friday.”

Logical Connectives

Logical connectives allow us to combine propositions and construct more complex logical statements.

1. Negation

The negation of a proposition reverses its truth value.

¬p

If p is true, then ¬p is false. If p is false, then ¬p is true.

p	¬p
True	False
False	True

2. Conjunction

A conjunction combines two propositions with “and.”

p ∧ q

The conjunction is true only when both propositions are true.

p	q	p ∧ q
True	True	True
True	False	False
False	True	False
False	False	False

3. Disjunction

A disjunction represents “or.”

p ∨ q

The disjunction is false only when both propositions are false.

p	q	p ∨ q
True	True	True
True	False	True
False	True	True
False	False	False

4. Exclusive Or

The exclusive OR, commonly written as XOR, means that exactly one of the two propositions is true.

p ⊕ q

p	q	p ⊕ q
True	True	False
True	False	True
False	True	True
False	False	False

5. Implication

An implication expresses a conditional relationship: “if p, then q.”

p → q

Here, p is the hypothesis or premise, while q is the conclusion.

An implication is false only when the premise is true and the conclusion is false.

p	q	p → q
True	True	True
True	False	False
False	True	True
False	False	True

6. Biconditional

A biconditional expresses “if and only if,” commonly abbreviated as “iff.”

p ↔ q

The biconditional is true when both propositions have the same truth value.

p	q	p ↔ q
True	True	True
True	False	False
False	True	False
False	False	True

Next Predicate Logic

→