Propositional Logic - Detailed Study Notes

PROPOSITIONAL LOGIC

INTRODUCTION AND MOTIVATION

• Importance of Abstraction in Mathematics: Criticism of mathematics for its abstraction is misdirected; abstraction is crucial for functionality.

  • Ian Stewart emphasizes that focusing on limited applications of ideas deprives mathematicians of powerful tools such as analogy, generality, and simplicity.

• Thought Provocation:

  • The boy and girl puzzle:

  • Child with black hair: "I am a boy".

  • Child with brown hair: "I am a girl".

  • At least one is lying. Identify each child's gender.

• Definition of Logic:

  • Logic is the study of arguments, where an argument consists of a sequence of statements with an intended conclusion derived from premises.

  • Premises are meant to prove or provide evidence for the conclusion.

• The Role of Logic:

  • Ensures sound arguments and maintains the integrity of mathematical reasoning.

  • Hermann Weyl's quote: "Logic is the hygiene the mathematician practices to keep his ideas healthy and strong."

• Philosophical Considerations:

  • Controversies regarding truth and sound arguments are fundamental philosophical discussions.

Challenging Pure Logical Reasoning

• Historical Context of Controversies in Mathematics:

  • Newton's infinitesimal viewed as nonsense by Berkeley.

  • Euler's formulas and Cauchy's critique led to new convergence criteria.

  • Riemann's assumptions about harmonic functions were later criticized by Weierstrass.

• Foundation of Mathematics:

  • Development of logical foundations aimed to settle controversies across mathematical concepts.

  • New conceptual foundations emerged to explain previously mysterious concepts.

  • Historical limitations in expressing these issues in the language of their times hampered resolution.

THE LOGIC OF COMPOUND STATEMENTS

Definition of a Statement

• Statement (Proposition):

  • A declarative sentence that is true or false, but not both.

  • Examples of notations used: small letters such as p, q.

Examples of Statements

1. "Logic and set theory is the cheapest course in Mathematics."

2. "I made a mistake in signing up for this course."

3. "London is in Denmark."

4. "Paris is in France."

5. "2 < 4."

• Importance of precision and clarity in important mathematical statements:

  • Example:

  • "Fred Smith's age is twenty years." (Ambiguous)

  • "Fred Smith is twenty years old." (Precise)

  • "Fred and Susan are married." (Ambiguous due to lack of clarity)

Exercise

• Classify the following expressions as statements or not:

  1. "Do not cheat and do not tolerate those who do."

  2. "This sentence is false."

  3. "Do your homework."

  4. "x is an even number."

  5. "Today is a nice day."

  6. "Is it going to snow tomorrow?"

  7. "4 < 3."

  8. "If x ≥ 2 then x^3 ≥ 1."

  9. "(a + b)^2 = a^2 + 2ab + b^2."

Compound Statements

• Truth Value: The truth or falsehood of a proposition.

• Law of the Excluded Middle: Every statement is either true or false, but not both.

• Formation of Compound Statements:

  • New complex statements formulated from old (compound) statements.

Logical Connectives

• Logical Connectives are operators that combine simple statements into compound statements. The main connectives are:

  1. Negation ($
     eg p$): "not p"

  2. Conjunction ($p { ext{and} } q$) or ($p igwedge q$): "p and q"

  3. Disjunction ($p { ext{or} } q$) or ($p igvee q$): "p or q (or both)"

  4. Exclusive Or ($p igoplus q$): "either p or q, but not both"

  5. Implication ($p
     ightarrow q$): "if p then q"

  6. Biconditional ($p
     ightarrow q$): "p if and only if q"

• Truth values for Connectives:

  • The truth value of a compound proposition depends only on the values of its components.

Conjunction

• Definition:

  • A logical conjunction yields a true value only when both statements are true.

• Truth Table for Conjunction:

  P	Q	$P igwedge Q$
  T	T	T
  T	F	F
  F	T	F
  F	F	F

• Example:

  • Let P = "It is raining today," and Q = "We are playing a soccer game tonight."

  • The conjunction $P igwedge Q$ states: "It is raining today and we are playing a soccer game tonight."

Disjunction

• Definition:

  • A logical disjunction yields a true value if either statement is true or both are true.

• Truth Table for Disjunction:

  P	Q	$P igvee Q$
  T	T	T
  T	F	T
  F	T	T
  F	F	F

• Example:

  • Let P = "My car is red," and Q = "It will rain today."

  • The disjunction $P igvee Q$ states: "My car is red or it will rain today."

  • Note that mathematical disjunction is inclusive, differing from everyday exclusive usage.

AVOIDING CONFUSION WITH "OR"

• Example: "Tonight I will see a play, or I will watch a movie":

  • Mathematical Usage: Inclusive, meaning either I will see a play or I will watch a movie (or both).

  • Everyday Usage: Exclusive, suggesting I will either see a play or watch a movie, not both.

Negation

• Definition:

  • Negation is an operator on the logical value of a proposition, turning true to false and vice versa.

• The negation of statement P is denoted by $
  eg P$ or $ ext{not }P$.

• Examples: If P = "Susan likes mushy bananas," then $ eg P$ could be expressed as:

  • "Not Susan likes mushy bananas."

  • "It is not the case that Susan likes mushy bananas."

  • Simply put, $
    eg P = "Susan does not like mushy bananas.""

• Truth Table for Negation:
  | P | $
  eg P$ |
  |---|---|
  | T | F |
  | F | T |

Conditional Connectives

• Formulation:

  • Conditional statements are formed using the conditional connective, drawing a distinction between the conditional and the implication relation.

  • The phrase “if P then Q” denotes the conditional connective.

  • The phrase “P implies Q” denotes the implication relation, differentiating between contemplation and assertion.

• Truth Table for Conditional:
  | P | Q | $P
  ightarrow Q$ |
  |---|---|---|
  | T | T | T |
  | T | F | F |
  | F | T | T |
  | F | F | T |

• Components:

  • Antecedent: P (the condition assumed).

  • Consequent: Q (the result stating).

Conditions and Variations of Conditional Statements

• Further ways to express conditionals:

  1. If P, Q;

  2. Q if P;

  3. P only if Q;

  4. Q provided P;

  5. Assuming that P, then Q;

  6. Q given that P;

  7. P is sufficient for Q;

  8. Q is necessary for P.

BICONDITIONAL CONNECTIVES

• Read as: P ↔ Q as “P if and only if Q,” often abbreviated as “iff.”

• Truth Table for Biconditional:
  | P | Q | $P
  ightarrow Q$ |
  |---|---|---|
  | T | T | T |
  | T | F | F |
  | F | T | F |
  | F | F | T |

• Example:

  • "I will go for a walk if and only if Fred will join me".

  • The truth holds if both statements are either true or both false.

• Note on Truth: Distinction between logical truth versus realities.

Exercise

• Translate statements into symbols: Let X = "The house is blue", F = "The house is 30 years old", G = "The house is ugly".

  1. If the house is 30 years old, then it is ugly.

  2. If the house is blue, then it is ugly or it is 30 years old.

  3. The house is 30 years old if it is blue, and it is not ugly if it is 30 years old.

  4. For the house to be ugly, it is necessary and sufficient that it is blue and 30 years old.

USING TRUTH TABLES

• Start-Up Question:

  • Let A = "I like to eat apples", B = "I like to eat pears", and C = "I like to eat peaches." Translate

  • $(A igvee B) igwedge C$ and $A igvee (B igwedge C)$ into words.

• Importance of Parentheses: To avoid ambiguity, parentheses or punctuation is critical in complex statements.

• Properly Formed Truth Table Example:

  • For the statement $(P
    ightarrow R) igwedge (Q igvee
    eg R)$, develop a truth table step by step:

  • Constructed Truth Table:
    | P | Q | R | $P
    ightarrow R$ | $Q igvee
    eg R$ | $(P
    ightarrow R) igwedge (Q igvee
    eg R)$ |
    |---|---|---|---|---|---|
    | T | T | T | T | T | T |
    | T | T | F | F | T | F |
    | T | F | T | T | F | F |
    | T | F | F | F | T | F |
    | F | T | T | T | T | T |
    | F | T | F | F | T | F |
    | F | F | T | T | F | F |
    | F | F | F | F | T | F |

Concepts to Conclude

• Tautology, Contradiction, and Contingency:

  • Tautology: True for every evaluation. E.g., $p igvee
    eg p$.

  • Contradiction: False for every evaluation. E.g., $p igwedge
    eg p$.

  • Contingency: Neither true nor false consistently across evaluations.

TAUTOLOGY

• Definition: A statement that is true in every valuation of its propositional variables.

• Example: E.g., "Argentina won the 2022 FIFA world cup" holds true for every scenario and team.

CONTRADICTION

• Definition: The negation of a tautology, necessarily false regardless of variable truth values.

• Example: "Irene has red hair and does not have red hair."

CONTINGENCY

• Definition: A proposition neither a tautology nor contradiction.

• Exercise: Verify whether $[(P igwedge Q)
  ightarrow R]
  ightarrow [P
  ightarrow (Q
  ightarrow R)]$ is a tautology or contradiction.

META STATEMENTS

• Definition: Statements reflecting relationships between two compound statements.

  • Example: If both "Ethel is tall" and "Agnes is short" are true, then "Ethel is tall" remains true.

  • Logical Implication: The phrase analog to conditional.

  • Logical Equivalence: The phrase analog to biconditional.

LOGICAL IMPLICATION

• Definition: A proposition $P$ logically implies $Q$ if the conjunction $P ightarrow Q$ is a tautology.

  • Notation: $P
    ightarrow Q$.

  • Necessitates that $Q$ is true whenever $P$ is true.

• Example:

  • Let P = "The sky is blue", and Q = "Grass is green".

  • The logical link exists through the established truth table; logical implications are not usually reversible.

Working with Logical Implication

• Example:

  • Let P = "It is not the case that, if Susan thinks Lisa is cute then she likes Lisa", and Q = "Susan thinks Lisa is cute or she likes Lisa".

  • It can be established that $P$ implies $Q$.

EXERCISE

• Formulate the following premises:

  1. $(P
     ightarrow Q) igwedge P
     ightarrow Q$ (Modus Ponens).

  2. $(P
     ightarrow Q) igwedge
     eg Q
     ightarrow
     eg P$ (Modus Tollens).

  3. $P igwedge Q
     ightarrow P$ (Simplification).

  4. $P
     ightarrow P igwedge Q$ (Addition).

  5. $(P igvee Q) igwedge
     eg Q
     ightarrow Q$ (Biconditional-conditional).

  6. $P
     ightarrow Q
     ightarrow P igwedge Q$ (Biconditional-conditional).

  7. $(P
     ightarrow Q) igwedge (Q
     ightarrow R)
     ightarrow P
     ightarrow R$.

LOGICAL EQUIVALENCE

• Two propositions are logically equivalent if they share identical truth tables, denoted as $P igtriangleq Q$.

FACTS/PROPERTIES OF LOGIC

• Key logical properties:

1. $(P
   ightarrow Q) igwedge P
   ightarrow Q$

2. $(P
   ightarrow Q) igwedge
   eg Q
   ightarrow
   eg P$

3. $P igwedge Q
   ightarrow P$

4. $(P igvee Q) igwedge
   eg P
   ightarrow Q$

5. $P igleftrightarrow Q
   ightarrow P
   ightarrow Q$

6. $(P
   ightarrow Q) igwedge (Q
   ightarrow P)
   ightarrow P igleftrightarrow Q$

7. $(P
   ightarrow Q) igwedge (R
   ightarrow S) igwedge (P igvee R)
   ightarrow Q igvee S$

INVERSE, CONVERSE, AND CONTRAPOSITIVES

• Given $P ightarrow Q$:

  • Converse: $Q
    ightarrow P$

  • Inverse: $
    eg P
    ightarrow
    eg Q$

  • Contrapositive: $
    eg Q
    ightarrow
    eg P$

VALID AND INVALID ARGUMENTS

• Definition of Argument:

  • An assertion that a set of premises leads to a conclusion, denoted as $P1, P2, …, P_n herefore Q$.

• Logical Validity:

  • An argument is valid if $Q$ is true whenever all premises $P1, P2, …, P_n$ are true.

• Example: A valid argument structure follows:

  • If $p
    ightarrow q$, $q
    ightarrow r$, then it implies $p
    ightarrow r$ (Law of Syllogism).

Example Argument Analysis

• Consider the following statements:

  • S1: If a student is single, then he eats quality food.

  • S2: If a student eats quality food, then he grows healthy.

  • Conclusion S: Thus, single students grow healthy.

  • Identifying the form $p
    ightarrow q, q
    ightarrow r herefore p
    ightarrow r$ validates the argument through its logical structure.

THE LOGIC OF QUANTIFIED STATEMENTS

PREDICATE

• Predicate:

  • A sentence containing variables, which becomes a true statement when those variables are instantiated with specific values.

  • Examples include "x + 2 = 7", "x is American", "x < y", etc.

• A predicate can be denoted as $P(x)$, $Q(x, y)$ denoting its nature.

DOMAIN OF A PREDICATE

• Each variable in a predicate belongs to its domain or universe of discourse:

  • In the predicate "n is an odd integer", 'n' belongs to all integers.

  • For the statement "n is a prime number", it encompasses all positive integers.

TRUTH SET OF A PREDICATE

• Definition: The truth set is the collection of all elements in the domain that satisfy the predicate.

• Example: For the predicate $Q(n)$ meaning "n is a factor of 8" with domain $Z$, the truth set comprises 1, 2, 4, 8, −1, −2, −4, −8.

QUANTIFIERS

• Existential Quantifier ($ ext{exists}$):

  • Symbol: $ orall xP(x)$.

  • Example: "There exists an integer such that…".

  • Truth statements like $ orall x ext{ with } P(x)$ yield definite truth values.

• Universal Quantifier ($ ext{for all}$):

  • Symbol: $
    eg orall xP(x)$ establishes potential falsity via existential negation.

  • Example: "For all integers x, there exists $P(x)$ that satisfy…".

STATEMENTS WITH MULTIPLE QUANTIFIERS

• Phrases can encapsulate several quantifiers simultaneously, such as $∀x∀y∃zP(x,y,z)$ to signify dependencies between multiple variables.

• Note that changing the order or swapping quantifiers can affect the statement's truth condition.

GENERALIZED DEMORGAN’S LAW FOR QUANTIFIERS

• If $
  eg orall xP(x)$ is false, then $ orall x
  eg P(x)$. Conclusively, if $
  eg orall xP(x)$ holds true, then $ orall
  eg P(x)$ must be erroneous.

MATHEMATICAL SYSTEMS, PROOFS

Fundamental Components

• A Mathematical System consists of:

  1. Axioms: Assumed true propositions.

  2. Definitions: Establish new concepts from conventional principles.

  3. Undefined Terms: Primitive concepts within the system framework.

• Theorem Definition: A proposition provable as true.

• Proof Definition: The argument establishing the truth of a proposition.

• Propositions: Statements lacking association with distinct theorems but are often correct.

• Lemma Definition: Intermediate proven propositions aiding in broader arguments.

• Corollary Definition: Easily derived from a proven theorem.

STRATEGIES FOR PROOFS

• Statements should be articulated with correct English grammar, proper punctuation, and the clarity required to depict logical flows.

• Proof Strategies:

  1. Direct Proof: Lead directly from premise to conclusion.

  2. Proof by Contrapositive: Convince by proving the inverse.

  3. Proof by Contradiction: Showcase inconsistency to prove the point.

  4. Proof by Induction: Utilize inductive reasoning based on previous truths.

DIRECT PROOFS

Process and Example

• Direct proofs assert the truth of $P
  ightarrow Q$ by assuming $P$ and linking it stepwise to conclusion $Q$.

• Example:

  1. Prove that if $x > 2$ and $y > 3$, then $x + y > 5$:

  • Assuming $x > 2$ and $y > 3$, add them to establish $x + y > 5$.

Proof Example

1. If a, b, and c are integers;

   • If $a || b$ and $b || c$, then $a || c$.

   • Proof:

     • Assuming $a||b$, we can express $b=ad$; for $b||c$, we express $c=be$.

     • Substitute for clarity: $c = a(de)$, asserting $a|c$.

PROOF BY CONTRAPOSITION

Process and Example

• Proof by contrapositive employs the relationship: $P
  ightarrow Q$ is valid if $
  eg Q
  ightarrow
  eg P$ holds true.

• Example:

  • Prove that if $x + y > 5$, then $x > 2$ or $y > 3$.

  • Establish $
    eg((x > 2) ∨ (y > 3))
    ightarrow
    eg(x + y > 5)$.

  • Infer $x + y
    leq 5$ leads to a restriction defining the earlier claim.

PROOF BY CONTRADICTION

Process and Examples

• Proof by contradiction utilizes the equivalency $
  eg(P
  ightarrow Q)$ forming $P igwedge
  eg Q$, leading to contradictions and affirming $P
  ightarrow Q$.

• Example Show: $igsqrt{2}$ is an irrational number by opponent assumption revealing mathematical contradiction.

PROOF BY INDUCTION

Concept and Steps

• Inductive reasoning allows proving statements across infinite integers asserting two steps for verification

1. Prove $P(1)$ is true.

2. Establish $P(n) ⇒ P(n + 1)$.

Example

• Prove $1 + 3 + … + (2n − 1) = n^2$ via induction:

  • Base case $P(1)=1$ valid.

  • Assume $P(k)$, leading transformation proving $P(k+1)$.

Exercise

• Prove further statements through mathematical induction: 1. Sum sequences and relationships between quadratic formations.

Conclusion

• Reflection on Mathematical Logic:

  • Examining logical statements solidifies understanding of truths, their relationships, implication structures, and validation mechanisms throughout mathematical reasoning.

QUESTIONS

• For any queries, feel free to ask.

P. A. KWABI (Ph.D.)
Propositional Logic Course
Kwame Nkrumah University of Science and Technology
Thank you for listening!