Adequate Sets of Connectives
Adequate Sets of Connectives
Consider the connectives ¬, →, ∧, ∨, and ↔.
We have seen that ∧, ∨, and ↔ can all be expressed in terms of ¬ and →, so we only use ¬ and → in our official definition of formula.
Could we have used other connectives in the definition?
Definition
A set C of connectives is adequate if every formula is logically equivalent to a formula using only connectives from C.
Example
{¬, ∨} is an adequate set of connectives.
By definition, {¬, →} is adequate.
To see that {¬, ∨} is adequate, it suffices to show that → can be expressed in terms of ¬ and ∨.
Now for any formulas ϕ and ψ, (ϕ → ψ) (¬ϕ ∨ ψ).
Thus, {¬, ∨} is adequate.
Logical Consequence and Tautologies
Logical Consequence — Validity Revisited
Definition
Let Γ be a (possibly empty, possibly infinite, possibly finite) set of propositional formulas, and let ϕ be a propositional formula. We write Γ |= ϕ and say ϕ is a logical consequence of Γ if for every truth assignment e, if e is such that e(γ) = T for all γ ∈ Γ, then e(ϕ) = T.
Note that for finitely many formulas {ϕ1, . . . , ϕn} and a formula ϕ, we had already defined {ϕ1, . . . , ϕn} |= ϕ with this same definition.
Question
Which of the following formulas are tautologies?
1. ((P ∧ Q) → P)
2. (P ↔ ¬P)
3. ((P ∧ ¬P) → Q)
4. P
Disjunctive Normal Form
Relaxed Notation
You can check that for any formulas ϕ, ψ, and χ, we have
((ϕ ∧ ψ) ∧ χ) (ϕ ∧ (ψ ∧ χ))
For this reason, in situations when we are concerned with the formulas only up to truth equivalence, we will often write (ϕ ∧ ψ ∧ χ) as an abbreviation for ((ϕ ∧ ψ) ∧ χ).
More generally, for formulas ϕ1, . . . , ϕn, (ϕ1 ∧ . . . ∧ ϕn) abbreviates (. . . ((ϕ1 ∧ ϕ2) ∧ ϕ3) ∧ . . . ∧ ϕn).
Since we also have ((ϕ ∨ ψ) ∨ χ) (ϕ ∨ (ψ ∨ χ)) as well, we make the analogous abbreviations with ∨ in place of ∧.
Definition
For formulas ϕ and ψ, we refer to (ϕ ∧ ψ) as the conjunct of ϕ and ψ, and we refer to (ϕ ∨ ψ) as the disjunct of ϕ and ψ.
Disjunctive Normal Form
Up to truth equivalence, propositional formulas are completely described by their truth tables. However, as we’ve seen, truth tables for formulas in many variables are rather large.
The disjunctive normal form. (DNF) of a formula will be a formula that is truth equivalent to the original, but it will tell us exactly the rows of the truth table on which the formula is true.
Question
Which of the following formulas are in disjunctive normal form, over all variables occurring in the formula?
1. ((P ∧ ¬Q ∧ R) ∨ (¬P ∧ Q ∧ ¬R))
2. ((P ∧ ¬Q) ∨ (P ∧ R) ∨ (¬P ∧ Q))
3. ((P ∧ Q) ∨ (P ∧ ¬Q) ∨ (¬P ∧ Q) ∨ (P ∧ Q))
Uniqueness of the Disjunctive Normal Form
Disjunctive Normal Form
Theorem
For every propositional formula ϕ with propositional variables among P1, . . . , Pn, there is a formula ψ with propositional variables P1, . . . , Pn that is truth equivalent to ϕ and is in disjunctive normal form. Moreover, ψ is unique up to rearrangement of the DNF constituents.
Definition
If ψ ϕ and ψ is in disjunctive normal form, we call ψ the disjunctive normal form. of ϕ.