13. Expressive Adequacy

Question 1

Equivalence (Revisited 2)

Answer 1

1) True in precisely the same situations
2) Same Building Blocks and Same Truth Tables
3) ≈ Mathematical Symbol, not PL

Question 2

The Duality of ∧ and ∨

Answer 2

A) α ∨ β ≈ ¬(¬α ∧ ¬β)
B) α ∧ β ≈ ¬(¬α ∨ ¬β)

Notice change from ∧ to ∨
These have the same truth tables

Question 3

The Laws of De Morgan (2)

Answer 3

A) ¬(α ∨ β) ≈ ¬α ∧ ¬β
B) ¬(α ∧ β) ≈ ¬α ∨ ¬β

Notice change from ∧ to ∨
Similar to distributive property
These have the same truth tables

Question 4

Economizing Connectives (4)

Answer 4

A) We work with three connectives ∧, ∨ and ¬
B) Given α ∧ β ≈ ¬(¬α ∨ ¬β) we can work only with ∨ & ¬
b) treat ∧ as an abbreviation
C) Given α ∨ β ≈ ¬(¬α ∧ ¬β) we can work only with ∧ and ¬
c) treat ∨ as an abbreviation
D) A more economical (minimal) alphabet, but larger WFF

Question 5

Exclusive Disjunction Truth-Conditional (4)

Answer 5

A) Binary and propositional connective (Symbol ⊕)
Connects two expressions/sentences
B) Truth condition: If A=1 & B=1 then Conclusion=0
If A=0 & B=0 then Conclusion=0
If A=1 & B=0 then Conclusion=1
If A=0 & B=1 then Conclusion=1
C) “A or B but not Both”
D) ⊕ An Abbreviation of other connectives:
α ⊕ β ≈ (α ∨ β) ∧ ¬(α ∧ β)

Question 6

Expressive Adequacy (2)

Answer 6

A) Given ∧, ∨ and ¬, we can define every truth function
B) Together, they are expressively adequate/functionally complete

Question 7

Associative ∧ and ∨ (4)

Answer 7

A) ∧ and ∨ are associative
B) The brackets do not matter:
b1) ((α ∨ β) ∨ γ) ≈ (α ∨ (β ∨ γ)) ≈ α ∨ β ∨ γ
b2) ((α ∧ β) ∧ γ) ≈ (α ∧ (β ∧ γ)) ≈ α ∧ β ∧ γ
C) Syntactically ambiguous, but not Semantically
D) They have the same Truth Table

Question 8

Basic Conjunctions

Answer 8

A) One-to-one correspondence between valuations and conjunctions of wff.

EX: Consider the atoms P, Q and R
Valuation: P := 1, Q := 1, R := 1 Conjunction: P ∧ Q ∧ R
valuation: P := 1, Q := 0, R := 1 Conjunction: P ∧ ¬Q ∧ R Valuation: P := 0, Q := 0, R := 1 Conjunction: ¬P ∧ ¬Q ∧ R Valuation: P := 0, Q := 0, R := 0 Conjunction: ¬P ∧ ¬Q ∧ ¬R

Question 9

Expressive Adequacy (5)

Answer 9

A) 3 Connectives ∧, ∨, ¬ expressively adequate (EA)
i.e. gives us enough to express every truth-function.
B) 2 Connectives ∨ and ¬ EA, since they can define ∧
C) 2 Connectives ∧ and ¬ EA, since they can define ∨
D) 1 Connective ↓ EA, since it can define ∧, ∨, ¬
E) 1 Connective ↑ EA, since it can define ∧, ∨, ¬

Question 10

Nor

Answer 10

A) Binary and propositional connective (Symbol ↓)
B) Truth Condition:
If A=0 & B=0 then Conclusion=1
If A or B is 1 then Conclusion=0
C) α ↓ β ≈ ¬α ∧ ¬β ≈ ¬(α ∨ β)
D) Can define NOT: ¬α ≈ α ↓ α
E) Can define AND: α ∧ β ≈ (α ↓ α) ↓ (β ↓ β)

Question 11

NAND / Sheffer Stroke

Answer 11

A) Binary and propositional connective (Symbol ↑)
B) Truth Condition:
If A or B is 0 then Conclusion=1
If A=1 & B=1 then Conclusion=0
C) α ↑ β ≈ ¬α ∨ ¬β ≈ ¬(α ∧ β)
D) Can define NOT: ¬α ≈ α ↑ α
E) Can define OR: α ∨ β ≈ (α ↑ α) ↑ (β ↑ β)