Computer Science 2209A/B Lecture Notes - Lecture 2: Boolean Function, Sheffer Stroke

• School: Western University
• Department: Computer Science
• Course: Computer Science 2209A/B
• Professor: Lila Kari

Document Summary

A remarkable property of the standard set of connectives ( , , , , ) is the fact that for every truth table p. Any set of connectives with the capability to express all truth tables is said to be adequate: post (1921) observed that the standard connectives are adequate. { , , } is an adequate set of connectives. A |=| aa b |=|a ba b |=|a ba b |=| a b a b |=|(a b) (b a). All the five standard connectives can be expressed in terms of , , , therefore { , , } is an adequate set of connectives. Corollary { , }, { , }, and { , } are adequate. Schroder showed in 1880 that each of the standard connectives is definable in terms of a single binary connective , where the truth table associated with is p q p q.