PHIL222 Revision

Table of Contents

1. Propositional Logic Fundamentals

2. Truth Tables and Validity

3. Semantic Trees for Propositional Logic

4. Monadic Predicate Logic

5. General Predicate Logic

6. Translation Between Natural Language and Formal Logic

Propositional Logic Fundamentals

Basic Concepts

• Atomic propositions: These are the simplest forms of statements in logic that cannot be broken down further. Examples include statements like B: "The sky is blue" or A: "It is raining."

• Logical connectives: These are operators that combine one or more atomic propositions to form more complex logical expressions. The primary logical connectives include:

  • ¬ (negation): This operator reverses the truth value of a given proposition. If a proposition is true, negation makes it false, and vice versa.

  • ∧ (conjunction): This operator yields true only if both connected propositions are true. For example, the expression (A ∧ B) is true only when both A and B are true.

  • ∨ (disjunction): This operator yields true if at least one of the propositions is true. It can be divided into inclusive (A ∨ B is true when at least one of A or B is true) and exclusive cases.

  • → (implication): The expression (A → B) indicates that if A is true, then B must also be true, though B can be true independently of A.

  • ↔ (biconditional): The expression (A ↔ B) holds true if both A and B are either true or false together, indicating a strong relationship between the two propositions.

Well-Formed Formulas (WFFs)

• Rules for constructing valid formulas: A well-formed formula (WFF) is a string of symbols that is considered a valid expression in propositional logic. The rules for constructing WFFs are as follows:

  1. Every atomic proposition is a WFF by itself.

  2. If φ (phi) is a WFF, then ¬φ is also a WFF.

  3. If φ and ψ (psi) are both WFFs, then combinations of them like (φ ∧ ψ), (φ ∨ ψ), (φ → ψ), and (φ ↔ ψ) are themselves WFFs.

  4. No other combinations of symbols are considered WFFs.
     Examples from homework assignments include:

  • Valid: (A → ¬B) suggests that if A holds, then B must not hold; (A → (A → A)) is a tautology since A leads to A.

  • Invalid: ((A ∧ B)∧)A is malformed due to improper placement of brackets, and ABC contains multiple propositions without logical connectives.

Translation Exercises

• Key translation patterns: Understanding how to translate natural language into logical expressions is crucial. Notable patterns include:

  • "Only if P is Q" translates to Q → P, indicating that Q must be true whenever P is true.

  • "P if and only if Q" translates to P ↔ Q, asserting a mutual truth condition between P and Q.

  • "Unless P, Q" translates to ¬P → Q, meaning that if P does not hold, then Q must hold.

• Example translations:

  1. "Only if the sky is blue is snow white" translates to (W → B), suggesting that the condition of snow being white is contingent on the sky being blue.

  2. "If snow and roses are red, then roses are red and/or snow isn't" translates to ((W ∧ R) → (R ∨ ¬W)), indicating a conditional relationship based on the colors of roses and snow.

Truth Tables and Validity

Construction Method

• To effectively construct a truth table, follow these steps:

  1. List all possible truth value combinations for the atomic propositions involved in the formula.

  2. Calculate the truth values of the subformulas sequentially, ensuring clarity in each step.

  3. Determine the final truth value based on the last column of the truth table.

Example from Homework 2:
Consider the expression ((P ∨ Q) ↔ (P ∧ Q)):

Argument Validity

• An argument in logic is considered valid if there is no row in the truth table where all premises are true and the conclusion is false.
  Example from Homework 2:
  Consider the following argument:

1. A ∨ B

2. A → C
   ∴ (B → C) → C
   Testing the validity:

• The conclusion (B → C) → C is false only when (B → C) is true and C is false.

• If C is false, then according to A → C, A must also be false to avoid a truth contradiction.

• From A ∨ B with A being false, B must be true, leading to a contradiction, as (B → C) being true cannot hold while C is false.

• Therefore, since all attempts lead to contradictions, the argument is valid.

Semantic Trees for Propositional Logic

Tree Rules

• Rules for constructing semantic trees:

  • Conjunction (φ∧ψ): Write both φ and ψ in the same branch to indicate that both must be true.

  • Disjunction (φ∨ψ): Create a branch for each proposition φ and ψ, indicating that at least one must be true.

  • Implication (φ→ψ): Create a branching structure where ¬φ leads to ψ, highlighting the conditional relationship.

  • Negation of conjunction ¬(φ∧ψ): Introduce branches for ¬φ and ¬ψ, indicating that both propositions cannot be true together.

  • Biconditional (φ↔ψ): Create branches for (φ∧ψ) and (¬φ∧¬ψ) reflecting the requirement for mutual truth.

Example from Homework 3:
For ¬(A ↔ ¬A):

1. Start with ¬(A ↔ ¬A).

2. Branch to (A ∧ ¬¬A) or (¬A ∧ ¬¬A).

   • The first branch concludes with A and A (which closes as A and ¬A).

   • The second also results in a closure.

• Since all branches close, it confirms the expression is a tautology (always true).

Monadic Predicate Logic

Basic Concepts

• In monadic (or unary) predicate logic, we focus on properties of a single object from a domain, rather than relationships between multiple objects.

• Domain: This represents the set of objects being quantified over, such as the set of integers or all people.

• Extensions: These are specific subsets for which particular predicates hold true across the domain.

• Quantifiers used in this logic include:

  • Universal Quantifier (∀x): This quantifies over all objects in the domain, denoting that a predicate applies universally.

  • Existential Quantifier (∃x): This quantifies denoting that there exists at least one object in the domain for which the predicate is true.

Semantics

From Homework 6 Exercises 9.1.1:
Consider a domain {1,2,3,…}, where the referent of a is 1, and P represents the set of odd numbers {1,3,5,…}:

• The predicate Pa evaluates to True, indicating that the number 1 is included in the extension of P.

• The expression ∃xPx evaluates to True, confirming that there exists at least one odd number in the domain.

• Conversely, the expression ∀xPx evaluates to False, as not all numbers in the domain are odd.

Tree Rules for Quantifiers

• When working with quantifiers in trees, apply the following rules:

  • Universal Instantiation (∀xφ): This allows for the substitution of any constant 'a' in place of 'x', yielding φ(a/x).

  • Existential Instantiation (∃xφ): Introduce a new constant 'c' to demonstrate that φ holds true; write φ(c/x).

Example from Homework 7:
For the expression ∀xFx → ∃xFx:

1. Start with ¬(∀xFx → ∃xFx).

2. This simplifies to ∀xFx and ¬∃xFx.

3. From ¬∃xFx, deduce that ∀x¬Fx must be true.

4. Instantiate this with a new constant ‘a’ yielding Fa and ¬Fa, resulting in a contradiction and thus confirming that the original expression is a logical truth.

General Predicate Logic

Polyadic Predicates

• These predicates involve two or more arguments, such as Rxy representing a relationship between x and y (e.g. "x loves y").

From Homework 8:

• Consider the statement ∀x(Rxx → ∃yRxy): "If everything relates to itself, then everything relates to something."

• Testing validity using the tree method:

  1. Start with negation: ¬∀x(Rxx → ∃yRxy).

  2. This leads us to existences of a contradiction ∃x¬(Rxx → ∃yRxy).

  3. This simplifies to ¬(Raa → ∃yRay) for some constant a.

  4. Which indicates Raa is true (reflexive) while ¬∃yRay is also held true.

  5. This indicates R cannot relate to any y leading to an open model, hence illustrating that the statement is a logical truth as the tree must close.

Complex Examples

From Homework 8 Exercise 12.3.1(iv):
Consider the statement ∀x∃y∃zRyxz → ∃x∃yRxay:

• This can be interpreted as "If for every x there are y,z such that Ryxz, then there exist x and y such that Rxay".

• The tree method demonstrates that this statement is not logically true, resulting in a countermodel where the domain consists of {a} and the relation R is empty.

  • In this case, the premise is vacuously true as there are no elements in x to satisfy its conditions.

  • However, the conclusion remains false, concluding that premise does not guarantee a true conclusion.

Translation Between Natural Language and Formal Logic

Key Patterns

1. Names become constants in predicates; e.g., “Alice” translates to a, acting as a specific entity in logical statements.

2. Verbs become predicates; for example, “heard” translates to H, representing a relation or action.

3. Comparative adjectives: statements like “is taller than” translate to Txy, where x is compared to y.

4. Possession may be translated as “Mary's book” becoming Bm, dictating ownership logically.

• Examples from Homework 7:

  1. "Bill heard Alice" becomes Hba, indicating the relation of hearing.

  2. "Bill did not hear Alice" translates to ¬Hba, showing the negation of the previous statement.

  3. "Clare is taller than Dave, but she’s not taller than Edward" translates to Tcd ∧ ¬Tce, showing two conditional relationships.

  4. "Mary prefers Alice to Clare" translates to Pacm, indicating preference.

  5. "Edward is taller than Clare, but he's not tall" can be expressed as Tec ∧ ¬Te, showing comparison alongside a negation.

Complex Translations

From HW4:

1. "If Mary is sailing or Jenny is kite flying, then Bill and Ben are grumpy" → (Sm ∨ Kj) → (Gb ∧ Gb')

2. "Nothing is both green and red" → ¬∃x(Gx ∧ Rx)

3. "All red things that are not heavy are expensive" → ∀x((Rx ∧ ¬Hx) → Ex)

Summary of Key Techniques

1. For truth tables:

   • Systematically enumerate all possibilities

   • Identify counterexamples for invalid arguments

2. For semantic trees:

   • Apply rules systematically until branches close or remain open

   • Open branches provide countermodels

3. For predicate logic:

   • Pay attention to quantifier scope

   • For trees, instantiate existentials before universals

   • Look for smallest possible countermodels

4. For translations:

   • Identify the logical structure of the English sentence

   • Use appropriate predicates and constants

   • Be careful with word order and quantifier placement

These notes synthesize the key concepts across all homework assignments, showing the progression from basic propositional logic through to complex predicate logic with polyadic predicates. The examples demonstrate how to apply each technique to solve problems similar to those in the assignments.