Introduction to Propositions and Logic

Propositions

• A proposition is a declarative sentence that is either true or false, not both.
• Truth-value indicates whether a proposition is true (T) or false (F).

Examples of Propositions

• "The Moon is made of green cheese" is false (F).
• "Riyadh is the capital of Saudi Arabia" is true (T).
• "1 + 0 = 1" is true (T).

Non-Propositions

• "Sit down!" is an imperative and not a declarative statement, so it is not a proposition.
• "x + 1 = 2" varies in truth depending on x, thus not a proposition.
• "What time is it?" is a question, not a proposition.

Propositional Variables

• Propositional variables are denoted by letters such as p, q, r, s.
• Truth values: T for true and F for false.

Compound Propositions

• Formed by combining existing propositions using logical operators (connectives).

Logical Operators

• Negation (¬ ~): Unary operation reflecting the opposite truth value.
• Conjunction (∧): True if both propositions are true.
• Disjunction (∨): True if at least one proposition is true.
• Implication (→): Denotes a conditional relationship.
• Biconditional (↔): True if both propositions share the same truth value.

Negation

• Denoted as ￢p, meaning "It is not the case that p."
• Example: Negation of "Michael’s PC runs Linux" is "Michael's PC does not run Linux."

Truth Tables

• Used to show truth-value relationships between propositions.
• Number of rows in a truth table is 2^n, where n is the number of propositions.

Truth Table for Negation

• For a proposition p:
  • If p is T, then ￢p is F.
  • If p is F, then ￢p is T.

Conjunction (AND) and Disjunction (OR)

• Conjunction p ∧ q: True only when both p and q are true.
• Disjunction p ∨ q: False only when both p and q are false.

Truth Table for Two Propositions

• Displays outcomes for conjunction and disjunction:
  • p | q | p ∧ q | p ∨ q
  • T | T | T | T
  • T | F | F | T
  • F | T | F | T
  • F | F | F | F

Truth Table for Three Propositions

• Evaluated similarly, with 2^3 = 8 rows:
  • p | q | r | p ∧ q | p ∨ r
  • Truth values vary based on combinations of T and F.

Corollary

• A disjunction is true if at least one proposition is true.
• A conjunction is true only when all propositions are true.

Example Propositions

• For p = "Rebecca’s PC has more than 16 GB free space" and q = "The processor runs faster than...":
  • Conjunction: p ∧ q (true if both statements hold).
  • Disjunction: p ∨ q (true if at least one statement holds).