Propositional Logic: Introduction, Connectives, Validity, and Proofs

Introduction to Propositional Logic

• This week and next week focus on logic as a central theme of the course, specifically the simplest form: propositional logic (the logic of propositions).

• Plan for the weeks:

  • Introduction to how this works and why it’s useful

  • Introduction to propositional logic and its connectives

  • Propositional equivalences

  • How to establish truth of a logical formula by means of proofs

Validity of Arguments and Illustrative Examples

• Goal: determine whether a given set of facts and rules yields a valid conclusion.

• Example setup with two facts A and B:

  • A: It is raining.

  • B: If it is raining, then the grass is wet.

  • Question: Can we conclude that the grass is wet from A and B?

  • This is a valid argument known as modus ponens:

  • Let R denote "it is raining" and W denote "the grass is wet". Then B can be written as R \rightarrow W.

  • From A: R and B: R \rightarrow W, infer W.

  • Therefore, A and B ⊢ W (modus ponens).

• Example 2: Different observation, same rule

  • A: The grass is wet (W).

  • B: If it is raining, then the grass is wet (R → W).

  • Question: Can we conclude that it is raining (R) from A and B?

  • Answer: No. Knowing that the grass is wet does not guarantee that it rained; there could be another reason for wet grass.

• Example 3: Using a negation fact

  • A: The grass is not wet (¬W).

  • B: If it is raining, then the grass is wet (R → W).

  • Question: Can we conclude that it is not raining (¬R)?

  • Answer: Yes. This uses negation with a conditional: since (R → W) and ¬W, we infer ¬R via contrapositive (or modus tollens).

  • Intuition: If it were raining, then the grass would be wet; but we’re told the grass is not wet, so it cannot be raining.

• Example 4: A general statement and a particular instance

  • A: All lecture halls are uncomfortable. This is a universal claim: \forall x\,(LectureHall(x)\rightarrow Uncomfortable(x)).

  • B: Auditorium 2 is a lecture hall. This is a specific instance: LectureHall(Aud2).

  • Conclusion: Auditorium 2 is uncomfortable: Uncomfortable(Aud2).

  • This is valid by universal quantification (and will be explored in more depth in next week's lecture).

Propositional Logic: Core Concepts and Notation

• Logic is a branch of mathematics for precise reasoning about truth, useful for:

  • Establishing truth of mathematical observations

  • Evaluating program state in computing (conditions on variables, comparisons, etc.)

• Propositions are basic statements that can be true or false.

• Truth values: capital T denotes True, capital F denotes False.

• Some propositions are always true (tautologies) or always false (contradictions):

  • Example always true: "A triangle has three sides."

  • Example always false: "London is in Denmark."

• Some propositions depend on context and can be true or false depending on context, utterance, or scenario:

  • Examples: "It is sunny." or "There are five lights." (both context-dependent)

• Compound propositions are formed by combining basic propositions with logical connectives.

• Logical connectives discussed: not (¬), and (∧), or (∨), exclusive or (⊕), implication (→), and biconditional (↔).

• Basic propositions are often written as p, q, r, …; e.g., p could be "x is smaller than five" or "there are four lights".

• Next week will introduce predicate logic, which extends propositional logic with variables and quantifiers (e.g., ∀, ∃) to express statements about all or some values of a variable.

Constructing and Reading Propositions

• Example forms:

  • If it is sunny, then I go for a run: S \rightarrow G where S = "it is sunny" and G = "I go for a run".

  • If I go to the theater, then I do not go for a run: T \rightarrow \neg G where T = "I go to the theater".

  • A conjunction example: "It is sunny and I go for a run" corresponds to S \land G.

  • A simple negation: ¬p means "not p".

Proving and Deriving Truths: The Role of Proofs

• Proofs build new truths from a set of assumptions about the world or a program.

• Structure of mathematical reasoning:

  • Start with definitions of objects (numbers, formulas, etc.).

  • Use assumptions and logical rules to derive new properties or statements.

  • The resulting statements are typically called theorems or lemmas.

• The example with assumptions (R1, R2, R3) illustrates deriving a new truth via logical reasoning and known rules (including contrapositive).

• Key takeaway: proofs are the essential mechanism by which mathematics establishes truth, not just empirical observation.

Preview of Next Topics

• We will move from propositional logic to predicate logic, which introduces variables and quantification over those variables.

• In predicate logic, you can express statements like "for all x, P(x)" or "there exists an x such that Q(x)" and analyze logical consequences with those tools.

Summary of Practical and Philosophical Implications

• Logic provides a precise language to capture assumptions and derive consequences, reducing ambiguity.

• It underpins mathematical proofs and also underpins reasoning in programming and computer science.

• Understanding when an argument is valid (and when it is not) helps in sound reasoning and in detecting fallacies.

• The interplay between context, truth values, and logical structure highlights how some statements are context-dependent while others are universally determined by logical form.