Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

Упражнения В следующих упражнениях 1-10 предполагается, что задана к-значная (к>2) логика Поста. 1. Выяснить, выполняются ли следующие соотношения: а) N(Nx)=x; б) —i(—oc)=x; в) (х^у) = хуу. 2. Выяснить, выполняются ли следующие соотношения: а) (х^у) +^у=х&у: б) N(^+y)=(Nx) + (Ny); в) -n(N(^x^y))=(Nx)x(^y). 3. Доказать, что каждая функция f(xi,...,xyj ^-значной {к>2) логики Поста представима в виде: f(xi,...,xn)= V I (xj )&...& I (x „)&f(aj,a2,...,aj, (clj,q2, ••• jclyj) где дизъюнкция берётся по всевозможным наборам значений (ai,a2,... ,ап) переменных (xi,x2,... ,Хп). Правая часть такого представления функции называет­ ся совершенной дизъюнктивной нормальной формой (с.д.н.ф.). 4. Построить с.д.н.ф. для следующих функций: а) X vy, к=3; б) —х^у, к=3; в) Nx, к=5. 5. Выяснить, полна ли следующая система функций: {О, 1, 2,..., к-1,1о(х), Ii(x), hix),... , Ik .i(x), х&у xvyj. 6. Доказать, что имеет место соотношение: I/xJ=l+ max {х+а}. a^tk-l-j 7. Выяснить, образуют ли полную систему следующие системы функций: 1) {п, —ОС, 1о(х), Ii(x), l2(x),... , Ik -i(x), Х&у, хуу}, здесь п (0<п<к-\)- любое це­ лое неотрицательное число, не превосходящее к-\, т.е. 0<п<к-\; 2) {1, Nx, 1о(х), Ii(x), hix),... , Ik -i(x), х&у, хуу}; 3) {О, —ix, х&у, хуу}. 8. Построить с.д.н.ф. для следующих функций: а)х^у,к=3; б) xv( —x&y), к=3. 9. Выяснить, имеют ли место соотношения: а) х-у=х-х&у: 6) (Nx)-(Ny)=y-x: в) х-у=(х&у)-у. 10. Выяснить, имеют ли место соотношения: а) xx(y+z)=(x><y) + (xxz), к=2; xx(y+z)=(x><y)+(x><z), к=3. 11. Построить таблицы истинности в логиках L4 и Ls Лукасевича для сле­ дующих выражений: a) XV —а; б) Х&—ОС: b)ху(-^&у) ; г) -^^у; д) х&(—хуу); T )xv —av—^—x. 214