Propositional calculus - Semantics and Logical Consequence

Semantics and Valid Arguments Interpretations and Valuations An interpretation (also called a valuation) is a systematic way of assigning truth values to formulas. Specifically, an interpretation assigns either true (T) or false (F) to every formula—and it must assign exactly one value, never both. In classical logic, we work with Boolean valuations, which use only these two truth values. This is important: classical logic operates with a complete dichotomy—every proposition is either true or false, with no middle ground. Counting Interpretations If you're working with $n$ distinct propositional symbols, there are exactly $2^n$ possible interpretations. Why? Because each symbol can independently be assigned either true or false, giving us $2 \times 2 \times ... \times 2$ ($n$ times) = $2^n$ combinations. For example, with two symbols P and Q, there are $2^2 = 4$ possible interpretations: P = T, Q = T P = T, Q = F P = F, Q = T P = F, Q = F This combinatorial fact is crucial for understanding why truth tables have exactly $2^n$ rows for $n$ propositional variables. Semantic Notions Now that we understand interpretations, we can define some fundamental semantic concepts: Semantic Consequence A formula $\phi$ is a semantic consequence of a set of formulas $\Gamma$ if there is no interpretation in which all the formulas in $\Gamma$ are true while $\phi$ is false. In other words, whenever all the premises are satisfied (true), the conclusion must also be satisfied. We write this as: $\Gamma \models \phi$ The key insight: semantic consequence is about the logical structure—it tells us that the premises genuinely entail the conclusion. Tautologies and Logical Validity A formula is logically valid (or a tautology) if it is true under every possible interpretation. This is the strongest form of truth—it's necessarily true given the logical structure alone. Common tautologies include: $P \vee \neg P$ (the law of excluded middle) $(P \rightarrow Q) \rightarrow (P \rightarrow Q)$ (any statement implies itself) $\neg(P \wedge \neg P)$ (the law of non-contradiction) Consistency and Contradiction A formula is consistent if there exists at least one interpretation that makes it true. It's possible, even if not always true. A formula is inconsistent (or a contradiction) if it is false under every possible interpretation. No interpretation can make it true—it's necessarily false. The formula $P \wedge \neg P$ is a classic contradiction: it asserts both that P is true and that P is false simultaneously, which is logically impossible. Arguments: Structure, Validity, and Soundness What is an Argument? An argument consists of a set of premises (the starting claims) and a single conclusion (the claim being inferred). The premises are presented as support for the conclusion—we're claiming that the conclusion follows from the premises. Validity: The Core Logical Concept An argument is valid if and only if there is no interpretation in which all the premises are true and the conclusion is false. This is crucial: validity is about logical structure, not about whether the premises are actually true. An argument can be logically valid even if it starts with false premises. What matters is that if the premises were true, the conclusion would have to be true as well. Think of it this way: an argument is valid when it's impossible for the premises to be true while the conclusion is false. The contrapositive is useful too: an argument is invalid if there exists at least one interpretation where all premises are true but the conclusion is false. Such an interpretation is called a counterexample. Example: Valid vs. Invalid Consider this argument: Premise 1: All cats are animals Premise 2: Fluffy is a cat Conclusion: Fluffy is an animal This is valid. There's no way for both premises to be true and the conclusion false. Now consider this argument: Premise 1: All cats are animals Premise 2: Fluffy is an animal Conclusion: Fluffy is a cat This is invalid. We can imagine a world where both premises are true (cats are animals, and Fluffy is an animal—say, a dog) but the conclusion is false (Fluffy is not a cat). Soundness: Validity Plus True Premises An argument is sound if and only if it is valid and all of its premises are actually true. This is the gold standard for arguments: they must have both the right logical structure (validity) and correct starting points (true premises). An argument that is valid but has at least one false premise is unsound—it may have impeccable logic, but it's built on faulty foundations. Classical Valid Argument Forms Certain patterns of reasoning are so reliable that logicians recognize them as valid forms. Here are the main ones you should know: Modus Ponens Form: From $P$ and $P \rightarrow Q$, infer $Q$. This says: if you know P is true, and you know that P implies Q, then Q must be true. This is perhaps the most fundamental valid argument form in logic. Example: If it's raining, the ground is wet. It's raining. Therefore, the ground is wet. Modus Tollens Form: From $\neg Q$ and $P \rightarrow Q$, infer $\neg P$. This is the "contrapositive" version: if you know Q is false, and you know that P implies Q, then P must be false (because if P were true, Q would have to be true). Example: If you studied hard, you passed the exam. You didn't pass the exam. Therefore, you didn't study hard. Disjunctive Syllogism Form: From $P \vee Q$ and $\neg P$, infer $Q$. This uses elimination: you know one of two things is true, and you rule out one option, so the other must be true. Example: Either it's a cat or it's a dog. It's not a cat. Therefore, it's a dog. Hypothetical Syllogism Form: From $P \rightarrow Q$ and $Q \rightarrow R$, infer $P \rightarrow R$. This chains implications together: if P leads to Q, and Q leads to R, then P leads to R. Example: If you study, you understand the material. If you understand the material, you pass the exam. Therefore, if you study, you pass the exam. Constructive Dilemma Form: From $P \rightarrow Q$, $R \rightarrow S$, and $P \vee R$, infer $Q \vee S$. This says: you have two conditional statements and you know at least one of their antecedents is true, so at least one of their consequents must be true. Example: If you go to the beach, you'll have fun. If you go to the movies, you'll enjoy yourself. Either you go to the beach or you go to the movies. Therefore, either you'll have fun or you'll enjoy yourself. Destructive Dilemma Form: From $P \rightarrow Q$, $R \rightarrow S$, and $\neg Q \vee \neg S$, infer $\neg P \vee \neg R$. This is the contrapositive version of constructive dilemma: you have two conditionals, and you know at least one of their consequents is false, so at least one of their antecedents must be false. Example: If you skip class, you'll fall behind. If you procrastinate, you'll stress out. Either you won't fall behind or you won't stress out. Therefore, either you didn't skip class or you didn't procrastinate.