CS245 Lecture Notes - Lecture 3: Distributive Property, University Of Waterloo, Structural Induction
14 Apr 2016
School
Department
Course
Professor
Document Summary
Given: monday, january 25, due: tuesday, february 2, 10:00am. Sketch of solutions (1)(a) we have to show that the set of standard connectives, or any other ad- equate set of connectives, can be expressed solely in terms of connectives from the new set { , , }. Choose { , } as our reference adequate set of connectives (we proved in class that this is adequate). 0 p p ( p p) p. P p q (p p) p p q. If { , } were an adequate set of connectives, then it would be possible to express : P |=| fp, , i. e. , express p as a formula depending only on p, , and . However, note that if p = 1 then the lhs of ( ) is 0, while according to our observation the rhs of ( ) is 1. As we reached an impossibility, our original assumption, that { , } is adequate, is incorrect.
