Propositional Logic: Well-Formed Formulas, Binding Priorities, and Truth Tables

Evaluation of Course Logistics and Schedule

• Test Scheduling: All tests for this course are held on Wednesday. This detail is emphasized due to a previous error in the paper outline.

• Final Week Preparation: The course includes a previous year's exam for practice during the final week.

• Resource Access: Assignments, tests, and solutions from two years ago are available on Moodle for revision and guidance.

• Assignment Caution: Students must ensure they submit the current year's version of an assignment; submitting a previous year's version by mistake is a common error.

Fundamentals of Propositional Logic

• Definition of a Proposition: A proposition is a statement that can be either true or false.

  • Structurally, a proposition should typically contain a subject, a verb, and an object.

  • Examples: "I win the lottery" is a proposition because it has a truth value. Isolated words like "lottery" or "win" are not propositions.

• Temporal Simplification: In this course, logic excludes considerations of the past, present, or future tenses.

• Applications of Logic: It is a core subject in mathematics and philosophy. For this course, it provides the essential building blocks for expressing programming concepts and mathematical proofs.

Logical Connectors and Sentence Structure

• Conclusion Markers: Keywords such as "therefore," "so," "hence," and "thus" indicate that a conclusion is being drawn from preceding sentences or facts.

• The Logical Role of the Full Stop: Most of the time, a full stop acts as the logical connector AND ($\wedge$).

  • If a series of facts are separated by full stops, they can be visualized as a list where every full stop is replaced by "and."

• Structure of an Argument: An argument composed of multiple premises and a conclusion is expressed as: $\text{Sentence 1} \wedge \text{Sentence 2} \wedge \dots \rightarrow \text{Conclusion}$.

• Implied Conditionals: In English, the word "then" is often omitted in "If… then" structures. For logic conversion, it should be treated as: $\text{If buy bitcoin then get rich}$.

Case Study: Analyzing a Logical Argument (Bitcoin)

• The Argument: "If you buy bitcoin you get rich. I don't buy bitcoin therefore I'm not rich."

• Step 1: Identifying Propositions:

  • Let $P = \text{I buy bitcoin}$

  • Let $Q = \text{I get rich}$

• Step 2: Logical Translation of Sentences:

  • Sentence 1: If you buy bitcoin you get rich: $P \rightarrow Q$

  • Sentence 2: I don't buy bitcoin: $\neg P$

  • Conclusion: I'm not rich: $\neg Q$

• Step 3: Creating the Formula:

  • The total argument is structured as $\text{(Sentence 1 and Sentence 2) implies Conclusion}$.

  • Full Formula: $((P \rightarrow Q) \wedge \neg P) \rightarrow \neg Q$

• Step 4: Evaluating Validity with a Truth Table:     | $P$ | $Q$ | $P \rightarrow Q$ | $\neg P$ | $(P \rightarrow Q) \wedge \neg P$ | $\neg Q$ | $((P \rightarrow Q) \wedge \neg P) \rightarrow \neg Q$ |     | :--- | :--- | :--- | :--- | :--- | :--- | :--- |     | $T$ | $T$ | $T$ | $F$ | $F$ | $F$ | $T$ |     | $T$ | $F$ | $F$ | $F$ | $F$ | $T$ | $T$ |     | $F$ | $T$ | $T$ | $T$ | $T$ | $F$ | $F$ |     | $F$ | $F$ | $T$ | $T$ | $T$ | $T$ | $T$ |

• Conclusion of Argument: The argument is invalid because there is an $F$ (false value) in the final column.

• Practical Explanation: The argument fails because even if you do not buy Bitcoin ($P = F$), you could still become rich ($Q = T$) through other means. The salesperson is falsely implying that buying Bitcoin is the only way to get rich.

Well-Formed Formulas (WFFs)

• Definition: A Well-Formed Formula (WFF) is a sequence of symbols that follows specific syntax rules.

• Syntactic Correctness:

  • Invalid syntax examples: Putting two AND symbols together ($\wedge \wedge$) or placing two propositions together without a connector (e.g., $QP$).

  • Valid syntax: Two NOT symbols can be placed together ($\neg \neg P$).

• Recursive Construction: If you take any two formulas, you can build a new one by combining them with any logical operator ($\neg, \wedge, \vee, \rightarrow, \leftrightarrow, \oplus$) and brackets.

Order of Operations and Binding Priorities

• Analogy to Mathematics: Much like BODMAS/BedMASS ($\text{Brackets, Exponents, Division, Multiplication, Addition, Subtraction}$), logic follows a strict order of operations.

• Binding Priorities (Decreasing Order):

  1. Brackets: Always performed first.

  2. Not ($\neg$): Highest priority operator.

  3. And ($\wedge$)

  4. Exclusive Or ($\oplus$)

  5. Or ($\vee$)

  6. Implies ($\rightarrow$): Lowest priority among the listed connectives.

• Direction of Binding: Operations of the same priority bind from left to right.

  • Example: $P \wedge Q \wedge R$ is the same as $(P \wedge Q) \wedge R$.

• Use of Brackets: When coding or building complex formulas, brackets should be used to ensure clarity even if they are not strictly required by binding rules.

Classifications of Logical Results

• Valid (Tautology): A formula is valid if the final column of the truth table contains only true ($T$) values. This indicates the logic is always true regardless of input.

• Satisfiable but Not Valid: A formula is satisfiable if there is at least one $T$ in the final column, but it also contains at least one $F$.

• Contradiction (Unsatisfiable): A formula is a contradiction if the final column contains only false ($F$) values. It is never true.

Practice Exercise: Contradiction Check

• WFF to Evaluate: $(P \wedge Q) \wedge \neg P \wedge \neg Q$

• Truth Table Steps:

  • Assume inputs $P$ and $Q$ cover the 4 possible combinations.

  • $P \wedge Q$ is only true when both are $T$.

  • $\neg P$ and $\neg Q$ invert the original values.

  • Building the formula left-to-right:

    1. $(P \wedge Q) \wedge \neg P$ results in all $F$ values (since $\neg P$ is false when $P$ and $Q$ are both true).

    2. Finishing with $\wedge \neg Q$ leaves the final result as all $F$.

• Final Result: This specific formula is a contradiction (unsatisfiable).