Propositional Logic Study Notes
PROPOSITIONAL LOGIC NOTES
INTRODUCTION AND MOTIVATION
Abstract Nature of Mathematics:
Criticism of mathematics for its abstraction misses the point; abstraction is essential for its functionality.
Focusing narrowly on applications can limit understanding and impede the use of crucial mathematical tools: analogy, generality, and simplicity. - Ian Stewart
Initial Question:
Consider the following scenario:
A boy and a girl are talking.
Child with black hair states: "I am a boy."
Child with brown hair states: "I am a girl."
Logical Problem: At least one of them lied. Identify who is the boy and who is the girl.
Definition of Logic:
Logic is defined as the study of arguments.
An argument comprises a sequence of statements with one designated as a conclusion and the others as premises, where premises support or provide evidence for the conclusion.
It is important to engage in "sound arguments" in mathematics.
Hermann Weyl mentioned, "Logic is the hygiene the mathematician practices to keep his ideas healthy and strong."
Controversy Over Truth:
Debates exist regarding what constitutes truth and sound arguments, a core inquiry in philosophy.
Understanding reality requires pure reasoning and interpretations derived from societal influences, educational backgrounds, and peer dynamics.
All science and mathematics are intricately related to humanistic studies and humanistic approaches.
ARGUMENT AGAINST PURE LOGICAL REASONING
Historical Challenges:
Development of calculus faced controversies, such as Newton’s concept of infinitesimals, which was criticized by philosopher Berkeley.
Euler encountered rebuttals regarding his integral and series formulas, deemed nonsensical by standards at the time.
Cauchy introduced new convergence criteria that attacked Euler’s methods, and Riemann developed concepts around surfaces and manifolds.
Their reliance on assumptions, later dismissed, illustrates the dynamic evolution of mathematical foundations to clarify complex concepts.
Foundation Development:
Mathematicians eventually established a logical foundation for mathematics to address past controversies, but they did not have the language or ideas to resolve these issues during their time.
THE LOGIC OF COMPOUND STATEMENTS
Definition of a Statement:
A statement (or proposition) is a declarative sentence that is either true or false, but not both.
Symbols, typically small letters like p, q, represent propositions.
Examples of Statements:
True/False statements include:
"Logic and set theory is the cheapest course in Mathematics."
"I made a mistake in signing up for this course."
"London is in Denmark."
"Paris is in France."
"2 < 4."
Clarity in Mathematical Statements:
Clear and concise language is vital in mathematical expressions.
Examples:
Ambiguous: "Fred Smith’s age is twenty years."
Precise: "Fred Smith is twenty years old."
Ambiguous: "Fred and Susan are married."
Exercise: Classify the following as statements or not:
"Do not cheat and do not tolerate those who do."
"This sentence is false."
"Do your homework."
"x is an even number."
"Today is a nice day."
"Is it going to snow tomorrow?"
"4 < 3."
"If x ≥ 2 then x^3 ≥ 1."
"(a + b)^2 = a^2 + 2ab + b^2."
COMPOUND STATEMENTS
Definition of Truth Value:
The truth of a proposition is termed its truth value.
Law of the Excluded Middle: Every statement is either true or false, but not both.
Compound statements can be formulated from simple statements using logical connectives.
Definition of Compound Statement:
A combination of two or more simple statements yields a compound statement.
Example of forming a compound statement:
Combining: "I made a mistake signing up for this course" and "I did not study hard" results in: "I made a mistake signing up for this course OR I did not study hard."
Logical operators, also known as connectives, form compound statements from simple propositions.
CONNECTIVES AND TRUTH TABLES
Logical Connectives:
Negation:
Denotation: ¬p
Meaning: "not p"
Conjunction:
Denotation: p ∧ q
Meaning: "p and q"
Disjunction:
Denotation: p ∨ q
Meaning: "p or q (or both)"
Exclusive Or:
Denotation: p ⊕ q
Meaning: "either p or q, but not both"
Implication:
Denotation: p → q
Meaning: "if p then q"
Biconditional:
Denotation: p ↔ q
Meaning: "p if and only if q"
Truth Value Dependence:
The truth value of a compound proposition depends solely on the truth values of its components.
CONJUNCTION
Definition:
A logical conjunction of two propositions yields true if both statements are true; otherwise, it is false.
Denoted as p ∧ q.
Truth Table for Conjunction:
P | Q | P ∧ Q |
|---|---|---|
T | T | T |
T | F | F |
F | T | F |
F | F | F |
Example of Conjunction:
Let P = "it is raining today," and Q = "we are playing a soccer game tonight."
The statement P ∧ Q becomes: "It is raining today and we are playing a soccer game tonight."
DISJUNCTION
Definition:
A logical disjunction is true if either statement is true or both are true, false otherwise.
Denoted as p ∨ q.
Truth Table for Disjunction:
P | Q | P ∨ Q |
|---|---|---|
T | T | T |
T | F | T |
F | T | T |
F | F | F |
Example of Disjunction:
Let P = "My car is red," and Q = "It will rain today."
The statement P ∨ Q becomes: "My car is red or it will rain today."
Clarification of Exclusivity:
Everyday usage of 'or' is often exclusive; however, in mathematics, disjunction is inclusive.
Example to highlight difference:
"Tonight I will see a play, or I will watch a movie."
In mathematical terms, this means: "Either I will see a play, or I will watch a movie, or both."
NEGATION
Definition of Negation:
A negation is an operator that switches the truth value of a proposition: true becomes false and vice versa.
Denoted by ¬P or ∼P.
Example:
Let P = "Susan likes mushy bananas."
The negation ¬P can be expressed as:
"Not Susan likes mushy bananas."
"It is not the case that Susan likes mushy bananas."
Simply put, ¬P = "Susan does not like mushy bananas."
Truth Table for Negation:
P | ¬P |
|---|---|
T | F |
F | T |
CONDITIONAL CONNECTIVES
Conditional Statements:
Formed using conditional connectives that indicate an implication between two propositions.
Important distinction between the conditional connective and implication relation.
Conditional is using phrase "if P then Q"; implication speaks to the assertion of the relation.
Truth defined as P → Q being true when P is true and Q cannot simultaneously be false.
Truth Table for Conditional Statements:
P | Q | P → Q |
|---|---|---|
T | T | T |
T | F | F |
F | T | T |
F | F | T |
Examples:
If P = "It will rain today," and Q = "I will see a movie this evening," then P → Q = "If it rains today, then I will see a movie this evening."
Alternative phrasing examples include:
If P, then Q;
Q if P;
P only if Q;
Q provided P;
Assuming that P, then Q;
Q given P;
P is sufficient for Q;
Q is necessary for P.
BICONDITIONAL CONNECTIVES
Definition:
Denoted by P ↔ Q and reads as "P if and only if Q."
"If and only if" is abbreviated to "iff."
Truth Table for Biconditional Statements:
P | Q | P ↔ Q |
|---|---|---|
T | T | T |
T | F | F |
F | T | F |
F | F | T |
Example:
Phrase: "I will go for a walk if and only if Fred will join me."
The truth of the statement hinges on both occurrences happening or neither happening.
USING TRUTH TABLES
Setup for Translating Statements:
For example, adding the statement (A ∨ B) ∧ C can be expressed in words.
Parentheses or punctuation can mitigate ambiguities in written compound statements.
TAUTOLOGY
Definition:
A tautology is an expression that holds true under every possible valuation of its propositional variables.
Classic Example:
The statement P ∨ ¬P is generally recognized as a tautology.
Truth Table:
P | ¬P | P ∨ ¬P |
|---|---|---|
T | F | T |
F | T | T |
Example:
"Argentina won the 2022 FIFA World Cup" remains true irrespective of match outcomes.
Verify for instance: "Irene has red hair or she does not have red hair."
CONTRADICTION
Definition:
The negation of a tautology represents a contradiction; it is always false no matter the truth values of its propositions.
Example:
Statement P ∧ ¬P forms contradiction.
Truth Table:
P | ¬P | P ∧ ¬P |
|---|---|---|
T | F | F |
F | T | F |
Example:
Statement: "Irene has red hair and she does not have red hair."
CONTINGENCY
Definition:
A proposition that is neither a tautology nor a contradiction is termed a contingency.
META STATEMENT
Examples:
Logical implication and logical equivalence illustrated by relationships between compound statements.
Example: "If 'Ethel is tall' and 'Agnes is short' are both true, then 'Ethel is tall' must be true."
Equivalent expressions can also include: "Irving has brown hair or Mel has red hair" being equivalent to "Mel has red hair or Irving has brown hair."
LOGICAL IMPLICATION
Definition:
Denoted by P ⇒ Q, P logically implies Q if the proposition is a tautology.
Logical implication necessitates that whenever P is true, Q must also be true.
Example:
Let P = "The sky is blue." and Q = "Grass is green." The implication P → Q must hold true in all contexts.
LOGICAL EQUIVALENCE
Definition:
Two propositions P and Q are logically equivalent (denoted P ≡ Q) if they have the same truth tables.
Example:
Checking equivalence of ¬(p ∧ q) and ¬p ∨ ¬q to confirm logical equivalence.
FACTS/PROPERTIES OF LOGIC
Key properties including modus ponens, simplification, and biconditional relationships.
INVERSE, CONVERSE AND CONTRAPOSITIVES
Given P → Q, the following relations arise:
Q → P (Converse)
¬P → ¬Q (Inverse)
¬Q → ¬P (Contrapositive)
VALID AND INVALID ARGUMENTS
Definition:
An argument is a claim that a set of premises P1, P2, …, Pn leads to a conclusion Q.
Validity requires that Q is true whenever premises P1, P2, … are true. Invalid arguments are termed 'fallacies'.
ELEMENTARY NUMBER THEORY AND STATEMENT OF PROOFS
Mathematical Systems:
Consist of Axioms, Definitions, and Undefined Terms.
Theorem:
A statement that has been proven true, while a proof establishes truth.
Proposition:
A statement that does not associate with any theorem specifically.
Lemma and Corollary:
Intermediate propositions and statements emerging from proven theorems.
STRATEGIES FOR PROOFS
Writing in grammatically correct English with complete sentences is crucial. Strategies include direct proof, proof by contrapositive, proof by contradiction, and proof by induction.
DIRECT PROOFS
Simplest form of proof for statements in form P → Q. Requires assuming P and leading to Q.
Example:
Prove if x > 2 and y > 3 then x + y > 5. Verify through logical deduction to arrive at valid conclusions.
PROOF BY CONTRAPOSITION
Employs the equivalence P → Q ⇔ ¬Q → ¬P.
Assume Q is false and deduce implicative conclusions leading to contradiction of P being false.
Example Summary:
Show through logical steps negative statement leads back to P's truth.
PROOF BY CONTRADICTION
Based on the negation form ¬(P → Q) ⇔ P ∧ ¬Q.
Assume both premises true, leading to logical inconsistencies that negate assumption validity.
PROOF BY INDUCTION
Approach for statements involving positive integers. Steps include proving base case, assuming step for arbitrary case k, and proving for k+1.
EXERCISES
Practice exercises include classifications, proof constructions, and verification problems of logical implications and equivalences.
Challenge statements include determining the truth of assertions using truth tables and logical deductions.
End of Notes: Comprehensive understanding of propositional logic and arguments. Significant definitions and examples included for clarity.