PHIL222 - In Class Test 1
1. Syntax of Propositional Logic (L2)
1.1 Natural vs. Formal Languages
Natural Languages (English, Spanish, French)
Rich in expression but ambiguous (e.g., "I saw the man with the telescope").
Lack systematic structure, leading to multiple interpretations.
Formal Languages (Propositional Logic, Programming Languages)
Defined by:
Alphabet: A strict set of symbols (e.g., A, B, C, …, Z, ¬, ∧, ∨, →, ↔).
Formation Rules: Explicit rules for constructing well-formed formulas (wffs).
Examples:
Chess notation (algebraic: e4, Nf6).
Programming (Python:
if x > 0: print("Positive")).
1.2 Basic Propositions
Representation:
Single capital letters: A, B, C, …, Z.
Extended notation: A₁, B₂, C₃ if more are needed.
Characteristics:
Atomic: No internal logical structure (e.g., "A: It is raining").
Building blocks for complex statements.
1.3 Logical Connectives
Connective | Symbol | Meaning | Example |
|---|---|---|---|
Negation | ¬ or ~ | "Not" | ¬A ("It is not raining") |
Conjunction | ∧ | "And" | A ∧ B ("It is raining and cold") |
Disjunction | ∨ | "Or" (inclusive) | A ∨ B ("It is raining or cold") |
Conditional | → | "If…then" | A → B ("If it rains, then it is wet") |
Biconditional | ↔ | "If and only if" | A ↔ B ("It rains iff it is wet") |
1.4 Well-Formed Formulas (WFFs)
Recursive Definition:
Base Case: Any basic proposition (A, B, C) is a wff.
Inductive Step:
If α and β are wffs, then:
¬α (negation)
(α ∧ β) (conjunction)
(α ∨ β) (disjunction)
(α → β) (conditional)
(α ↔ β) (biconditional)
Nothing else is a wff.
Examples of WFFs:
P, ¬Q, (P ∧ Q), (¬P ∨ (Q → R))
Non-WFFs (Invalid Constructions):
P Q R (missing connectives)
((P ∧ Q)) (extra parentheses)
(P → ↔ Q) (ill-formed)
1.5 Parentheses and Main Connectives
Importance: Determines scope and logical structure.
Main Connective: The last connective applied in construction.
Example:
In (¬P ∧ (Q ∨ R)), the main connective is ∧.
In (P → (Q ∧ R)), the main connective is →.
2. Truth Tables and Logical Semantics (L3, L4)
2.1 Truth Tables for Connectives
Negation (¬)
A | ¬A |
|---|---|
T | F |
F | T |
Conjunction (∧)
A | B | A ∧ B |
|---|---|---|
T | T | T |
T | F | F |
F | T | F |
F | F | F |
Disjunction (∨) (Inclusive "or")
A | B | A ∨ B |
|---|---|---|
T | T | T |
T | F | T |
F | T | T |
F | F | F |
Conditional (→) (Material Implication)
A | B | A → B |
|---|---|---|
T | T | T |
T | F | F |
F | T | T |
F | F | T |
Biconditional (↔)
A | B | A ↔ B |
|---|---|---|
T | T | T |
T | F | F |
F | T | F |
F | F | T |
2.2 Evaluating Complex Propositions
Example: Evaluate (¬P ∧ (Q ∨ R)) where P=T, Q=F, R=F
Compute ¬P: T → F
Compute (Q ∨ R): F ∨ F → F
Final: F ∧ F → F
2.3 Logical Properties
Concept | Definition | Truth Table Check | Example |
|---|---|---|---|
Tautology | Always true | All rows = T | P ∨ ¬P |
Contradiction | Always false | All rows = F | P ∧ ¬P |
Contingent | Sometimes T, sometimes F | Mixed rows | P → Q |
Satisfiable | True in at least one case | At least one T row | P ∧ Q |
Valid Argument | No counterexamples | No row where premises=T and conclusion=F | Modus Ponens |
2.4 Argument Validity Testing (Joint Truth Tables)
Process:
List all possible truth assignments.
Check if there’s any row where all premises=T but conclusion=F.
If no such row exists, the argument is valid.
If such a row exists, the argument is invalid.
Example:
Premises:
H → D ("If Ragnar is a husky, then he is a dog")
H ("Ragnar is a husky")
Conclusion: D ("Ragnar is a dog")
Truth Table Check: No row where H→D=T, H=T, D=F ⇒ Valid.
2.5 Soundness
Definition: An argument is sound if:
It is valid (no counterexamples).
Its premises are actually true (real-world verification needed).
Example:
P1: "Snow is white" (T)
P2: "Grass is green" (T)
C: "Snow is white and grass is green" (T)
⇒ Sound argument.
3. Truth Trees (L5, L6)
3.1 Why Use Trees Over Truth Tables?
Truth Tables grow exponentially (2ⁿ rows for n variables).
Trees are more efficient for complex arguments.
Visual branching helps track logical dependencies.
3.2 Tree Rules for Connectives
Connective | Rule (If True) | Rule (If False) |
|---|---|---|
¬α | Branch to ¬α | Branch to α |
α ∧ β | Write α and β | Branch to ¬α or ¬β |
α ∨ β | Branch to α and β | Write ¬α and ¬β |
α → β | Branch to ¬α or β | Write α and ¬β |
α ↔ β | Branch to (α ∧ β) or (¬α ∧ ¬β) | Branch to (α ∧ ¬β) or (¬α ∧ β) |
3.3 Tree Construction Steps
Write premises + negation of conclusion at the top.
Apply non-branching rules first (e.g., ¬¬α → α).
Apply branching rules (e.g., α ∨ β splits into two paths).
Check for closure:
If a path contains α and ¬α, mark with × (closed).
If all paths close, the argument is valid.
If an open path remains, the argument is invalid (counterexample found).
3.4 Example: Testing Validity
Argument:
P1: A → B
P2: B → C
C: A → C
Tree Construction:
Write:
A → B
B → C
¬(A → C)
Apply rules:
¬(A → C) becomes A and ¬C (non-branching).
A → B branches into ¬A (closes with A) or B.
B → C branches into ¬B (closes with B) or C (closes with ¬C).
All paths close ⇒ Valid argument.
3.5 Applications of Trees
Validity Testing (Premises + ¬Conclusion).
Satisfiability (If any open path, the set is satisfiable).
Tautology Check (Negate the proposition; if all paths close, it’s a tautology).
Equivalence Testing (Check if α ↔ β is a tautology).
4. Summary of Key Concepts
4.1 Logical Relationships Between Propositions
Relation | Definition | Example |
|---|---|---|
Equivalent | Same truth values in all cases | P and ¬¬P |
Contradictories | Cannot both be true or both false | P and ¬P |
Contraries | Cannot both be true, but can both be false | "All S are P" vs. "No S are P" |
Subcontraries | Cannot both be false, but can both be true | "Some S are P" vs. "Some S are not P" |
4.2 Shortcuts for Efficient Evaluation
Truth Tables:
Start with simplest propositions.
Eliminate rows where premises are false.
Trees:
Apply non-branching rules first.
Check for early closure to save time.
Conclusion
These notes cover:
✅ Syntax of Propositional Logic (WFFs, connectives, parentheses).
✅ Truth Tables (Connectives, validity, soundness, tautologies).
✅ Truth Trees (Construction, validity testing, satisfiability).
✅ Logical Relationships (Equivalence, contradictories, contraries).
This provides a complete, detailed reference for PHIL222, integrating all lecture materials systematically. 🚀