An Introduction to Propositional Logic
Logic and Its Importance
Logic is the foundation of computer science and enables computers to make decisions based on whether
statements are true or false. Propositional logic is a formal system used to express and reason about these
statements.
Propositions
A proposition is a declarative sentence that can be definitively assigned a truth value of either true or false.
Example: "The robot is blue."
Propositions are often represented by variables, such as P , Q, or R.
Logical Operators
Logical operators are used to modify or combine propositions to create more complex logical formulas.
Negation (NOT)
Symbol: ¬ (or sometimes ∼)
Meaning: Reverses the truth value of a proposition. If P is true, ¬P is false. If P is false, ¬P is true.
Example: If P is "The robot is blue," then ¬P is "The robot is not blue."
Conjunction (AND)
Symbol: ∧ (or sometimes ⋅)
Meaning: True only if both propositions are true.
Example: If P is "The robot is blue" and Q is "The robot has an antenna," then P ∧ Q is "The robot is
blue and has an antenna." This is true only when the robot is both blue and has an antenna.
Disjunction (OR)
Symbol: ∨ (or sometimes +)
Meaning: True if at least one of the propositions is true (inclusive OR).
Example: If P is "The robot is blue" and Q is "The robot has an antenna," then P ∨ Q is "The robot is
blue or has an antenna." This is true if the robot is blue, or if it has an antenna, or if it is both blue and
has an antenna.
1/5
Exclusive OR (XOR)
Symbol: ⊕
Meaning: True if exactly one of the propositions is true, but not both.
Example: If P is "The robot is blue" and Q is "The robot has an antenna," then P ⊕ Q is "The robot is
blue or has an antenna, but not both." This is true if the robot is blue and has no antenna, or if it has
an antenna and is not blue. It is false if the robot is both blue and has an antenna, or if it is neither
blue nor has an antenna.
Implication (IF...THEN...)
Symbol: → (or sometimes ⊃)
Meaning: P → Q is read as "If P , then Q" or "P implies Q." It asserts that if P is true, then Q must
also be true.
Truth Condition: P → Q is false only when P is true and Q is false. In all other cases, it is true.
If P is false, P → Q is always true, regardless of the truth value of Q. This is because the
implication makes no claim about what happens when the premise (P ) is false.
Example: If P is "It is my birthday" and Q is "I will eat cake," then P → Q is "If it is my birthday, then
I will eat cake." This statement is false only if it is your birthday and you do not eat cake. It is true if it is
your birthday and you eat cake, or if it is not your birthday (whether you eat cake or not).
Biconditional (IF AND ONLY IF)
Symbol: ↔ (or sometimes ≡)
Meaning: P ↔ Q is read as "P if and only if Q." It asserts that P and Q have the same truth value.
Truth Condition: P ↔ Q is true if P and Q are both true, or if P and Q are both false. It is false if
one is true and the other is false.
Example: If P is "The robot is blue" and Q is "The robot has an antenna," then P ↔ Q is "The robot
is blue if and only if the robot has an antenna." This is true if the robot is blue and has an antenna, or
if the robot is not blue and does not have an antenna. It is false if the robot is blue but has no
antenna, or if it is not blue but has an antenna.
Truth Tables
Truth tables are used to systematically determine the truth value of a complex logical formula for all
possible combinations of truth values of its propositional variables.
Structure: A truth table lists the propositional variables in columns and all possible combinations of
their truth values (True/False) in rows. A final column shows the resulting truth value of the entire
formula for each row.
2/5
Example: P ∧Q
P Q P ∧Q
T T T
T F F
F T F
F F F
Example: P ∨Q
P Q P ∨Q
T T T
T F T
F T T
F F F
Example: P →Q
P Q P →Q
T T T
T F F
F T T
F F T
Logical Equivalence
Two logical formulas are considered logically equivalent if they have the same truth value for all possible
truth assignments of their variables. This means their truth tables are identical.
3/5
Symbol: ≡
Example: The video demonstrates that P → Q is logically equivalent to ¬P ∨ Q.
Let's verify this with truth tables:
Truth Table for P → Q:
P Q P →Q
T T T
T F F
F T T
F F T
Truth Table for ¬P ∨ Q:
P Q ¬P ¬P ∨ Q
T T F T
T F F F
F T T T
F F T T
Since the columns for P → Q and ¬P ∨ Q are identical, the two formulas are logically equivalent:
P → Q ≡ ¬P ∨ Q.
4/5
Example of Non-Equivalence: P → Q is NOT logically equivalent to Q → P (this is called the
converse).
Truth Table for P → Q:
P Q P →Q
T T T
T F F
F T T
F F T
Truth Table for Q → P:
P Q Q→P
T T T
T F T
F T F
F F T
The truth tables are different, so P → Q is not logically equivalent to Q → P .
Conclusion
Propositional logic provides a precise language for expressing logical relationships that are fundamental to
computation. Understanding propositions, logical operators, truth tables, and logical equivalence allows for
clear and unambiguous reasoning about the conditions under which statements are true or false.
5/5