Week 8 & 9 - PC and Truth Table

Tags: Logic Philosophy PropositionalLogic TruthTables Source: Class Notes - Truth-Functional Logic

---

1. Introduction and Definitions

Truth-Functional Logic (also known as propositional or sentential logic) was developed in the 20th century by philosophers like Russell and Wittgenstein.

• Core Concept: It attempts to provide logic for truth-functional connectives.
• Truth-Functional Connective: A sentence functor that builds complex sentences out of simpler ones.
• The Rule: The truth value of the resulting complex sentence is determined solely by the truth values of its component sentences.

Non-Truth-Functional Connectives

Not all connectives in natural language are truth-functional. If the truth value of a sentence cannot be determined just by knowing the truth value of its components, it is non-truth-functional.

• Examples: “Necessary”, “Believes that”, “After”, “Before”, “It ought to be”.
• Translation: These are translated simply as atoms (single letters) in truth-functional logic because they create “truth-value gaps” in standard tables.

---

2. The Five Logical Connectives

There are five primary connectives used in this logical system. Connectives 1–4 are binary (connect two sentences), while Negation is unary (applies to one sentence).

Connective	Name	Symbol	Translation Example	Logic Form
Conjunction	And	&	It rains and it is humid.	$R\&S$
Disjunction	Or (Inclusive)	v	It rains or it is humid.	$R\vee S$
Implication	Material Implication	> or ⊃	If it rains then it is humid.	$R>S$
Equivalence	Material Equivalence	= or ≡	It rains if and only if it is humid.	$R=S$
Negation	Not	~	It doesn’t rain.	$\sim R$

Truth Conditions

• Conjunction ($p\&q$): True only if both components are true.
• Disjunction ($p\vee q$): False only when both components are false (inclusive “or”).
• Material Implication ($p>q$): False only when the antecedent ($p$) is true and the consequent ($q$) is false.
  • Note: This leads to the “paradox of material implication,” where a false proposition implies anything, and a true proposition is implied by anything.
• Equivalence ($p=q$): True when $p$ and $q$ share the same truth value.
• Negation ($\sim p$): Reverses the truth value; if $p$ is True, $\sim p$ is False.

Summary Table of Connectives

Here is how the truth values change for every possible combination of P and Q:

P	Q	∼P (Negation)	P&Q (Conj.)	P∨Q (Disj.)	P>Q (Imp.)	P=Q (Equiv.)
T	T	F	T	T	T	T
T	F	F	F	T	F	F
F	T	T	F	T	T	F
F	F	T	F	F	T	T

---

3. Translation Guide: Natural Language to Logic

Translating natural language requires identifying idiomatic structures.

Standard Translations

• “P only if Q”: $P>Q$ (Note: “Only if” introduces the consequent).
• “P if Q”: $Q>P$.
• “P is necessary for Q”: $Q>P$ (Necessary conditions are consequents).
• “P is sufficient for Q”: $P>Q$ (Sufficient conditions are antecedents).
• “P provided that Q” / “P on the condition that Q”: $Q>P$.
• “P just in case Q”: $P=Q$.
• “P unless Q”: $P\vee Q$ (or $\sim Q>P$).
• “Neither P nor Q”: $\sim (P\vee Q)$ OR $(\sim P\&\sim Q)$.
• “Not both P and Q”: $\sim (P\&Q)$ OR $(\sim P\vee \sim Q)$.

Quantifier Translations (Groups)

Assuming $A,B,C$ are atoms representing specific teams winning:

1. All teams win: $(A\&B)\&C$.
2. At least one team wins: $(A\vee B)\vee C$.
3. Exactly one team wins: $(A\&\sim B\&\sim C)\vee (B\&\sim A\&\sim C)\vee (C\&\sim A\&\sim B)$
4. At most one team wins: $(\sim A\&\sim B)\vee (\sim B\&\sim C)\vee (\sim A\&\sim C)$

---

4. Truth Tables: Construction and Analysis

Constructing the Table

• Number of Rows: Determined by the formula $2^n$, where $n$ is the number of atoms (simple sentences).
  • 1 atom = 2 rows.
  • 2 atoms = 4 rows.
  • 3 atoms = 8 rows.
• Assigning Values:
  • Column 1: $2^n/2$ True, then $2^n/2$ False.
  • Column 2: $2^n/4$ True, then $2^n/4$ False, etc..
  • Example (3 atoms): Column A is TTTTFFFF; Column B is TTFFTTFF; Column C is TFTFTFTF .

Classifying Sentences

By analyzing the column under the main connective, sentences are classified as:

1. Tautology: True in all rows (e.g., $A\vee \sim A$). This is a logical truth.
2. Contradiction: False in all rows (e.g., $A\&\sim A$). This is a logical falsehood.
3. Contingent: A mixture of True and False rows. The truth depends on the facts of the world.

• Col 3 (P∨∼P): All True → Tautology
• Col 4 (P&∼P): All False → Contradiction

P	∼P	P∨∼P (Law of Excluded Middle)	P&∼P (Contradiction)
T	F	T	F
F	T	T	F

---

5. Arguments and Validity

An argument is valid if there is no row in the truth table where the premises are all True and the conclusion is False.

Common Valid Forms

• Modus Ponens:
  • $A\supset B$
  • $A$
  • $\therefore B$
• Hypothetical Syllogism:
  • $A\supset B$
  • $B\supset C$
  • $\therefore A\supset C$

Common Invalid Forms

• Affirming the Consequent:

  • $A\supset B$
  • $B$
  • $\therefore A$ (Invalid because premise can be T and conclusion F).

• Visualizing Invalidity (Affirming the Consequent): Argument: If P then Q; Q is True; therefore P is True.

  • Look at Row 3. The Premises (P>Q and Q) are both True, but the Conclusion (P) is False. This proves the argument is Invalid.

Row	P (Concl)	Q (Premise 2)	P>Q (Premise 1)	Result
1	T	T	T	Valid Row
2	T	F	F	(Ignore, P1 is false)
3	F	T	T	INVALID (True Premises $\to$ False Concl)
4	F	F	T	(Ignore, P2 is false)

The Material Conditional Shortcut

A valid argument corresponds to a tautology. An argument is valid if and only if the material conditional formed by $[(Premise1\&Premise\mathrm{2...})\supset Conclusion]$ is a tautology.

---

6. Consistency of Sets

A set of sentences is consistent if and only if there is at least one row in the truth table where all the sentences in the set are True simultaneously.

• Example of Inconsistency: $S=\{A\supset B,A,\sim B\}$. There is no row where these are all true .
• Example of Consistency: $S=\{A\vee B,B\vee C,\sim A,\sim C\}$. There is a row (where B is True) that makes all members true .