Compound Propositions in Logic

Study Notes

Compound Propositions

Any logical operation can be applied to construct an arbitrarily complex compound proposition.
Simple propositions can become terms inside another proposition, forming compound propositions.
Examples of compound propositions: p ∧ q, r → t, (p ∧ q) → t, and (p ∧ q) ∨ (t ∧ r).
Parentheses indicate the order of evaluation in complex compound propositions.

Precedence in logical operations refers to the order in which operations are performed when there are multiple operations in an expression. In the absence of parentheses, the precedence of logical operations in standard formal logic is as follows:

Not operation (¬): The not operation (or negation) has the highest precedence, and it is evaluated first.
Conjunction (∧): The conjunction operation (logical and) has the next highest precedence, and it is evaluated next after the not operation.
Disjunction (∨): The disjunction operation (logical or) has a lower precedence than the conjunction operation and is evaluated after it.
Material implication (→): The material implication operation (if-then) has a lower precedence than the disjunction operation and is evaluated after it.
Material equivalence (↔): The material equivalence operation (if and only if) has the lowest precedence and is evaluated last.

Following the rules of precedence can help reduce the number of parentheses needed when writing complex compound propositions. For example, the expression "p ∨ q ∧ r" can be evaluated as "(p ∨ q) ∧ r" using the precedence rules, without the need for additional parentheses.

of Logical Operations

Precedence rules can reduce the number of parentheses needed.
The order of precedence is: ¬ (1), ∧ (2), ∨ (3), → (4), and ↔ (5).
Examples: p ∨ q ∧ r means p ∨ (q ∧ r), and (p ∨ q) ∧ r requires parentheses.

Logical Equivalence

A tautology is a proposition that is always true, e.g., p ∨ ¬p.
A contradiction is a proposition that is always false, e.g., p ∧ ¬p.
Two propositions are logically equivalent if they always have the same truth value, denoted by p ≡ q.
Formally, p and q are logically equivalent if and only if p ↔ q is a tautology.

Equivalence

Consider two compound propositions: p → q and ¬p ∨ q.
The truth values of both compound propositions are identical, making them equivalent.
This is an example of logically equivalent propositions.

Compound Propositions

Any logical operation can be applied to construct an arbitrarily complex compound proposition.
Simple propositions can become terms inside another proposition, forming compound propositions.
Examples of compound propositions: p ∧ q, r → t, (p ∧ q) → t, and (p ∧ q) ∨ (t ∧ r).
Parentheses indicate the order of evaluation in complex compound propositions.

Precedence of Logical Operations

Precedence rules can reduce the number of parentheses needed.
The order of precedence is: ¬ (1), ∧ (2), ∨ (3), → (4), and ↔ (5).
Examples: p ∨ q ∧ r means p ∨ (q ∧ r), and (p ∨ q) ∧ r requires parentheses.

Logical Equivalence

A tautology is a proposition that is always true, e.g., p ∨ ¬p.
A contradiction is a proposition that is always false, e.g., p ∧ ¬p.
Two propositions are logically equivalent if they always have the same truth value, denoted by p ≡ q.
Formally, p and q are logically equivalent if and only if p ↔ q is a tautology.

Equivalence

Consider two compound propositions: p → q and ¬p ∨ q.
The truth values of both compound propositions are identical, making them equivalent.
This is an example of logically equivalent propositions.