Математическая логика и теория алгоритмов

{ к - \ , если 0 ' й х < у й к - 1 , 9) х=>у=\ [ (А:1)-X + если 0 < , у < х < т - 1 . Вупражнениях 1--10 предполагается, чтозаданак-значная (fe2) логикаПоста. 1. Выяснить, выполняются ли следующие соотношения: а) N{Nx)=x; 6)1(1 х)=х; в) (x=>_y) =>•= x v y . 2. Выяснить, выполняются ли следующие соотношения: а) +1 у=х&у; 6) Л^(1 x+y)={Nx)+{Ny)i в)1 (Л^(1хх1 >'))=(Л^х)х(1 у ) . 3. Доказать, что канодая-функцияДх1,...,хп) А:-значной ( к > 2 ) ло­ гики Поста представима в виде: Дхь...рс„)= V / ( x i ) & . . . & / ( x „ ) & / ( a i , а з , - , о „ ) , где дизъюнкция берется по всевозмолсным наборам значений (а\,а2,...,а„) переменных (х\,х2,...^„). Правая часть такого представле­ ния функции называется совершенной дизъюнктивной нормальной формой (с.д.н.ф.), 4. Построить с.д.н.ф, для следующих функций: а) .xv_y, k=3; б) 1 к=3; в) Nx,к=5. 5. Выяснить, полна ли следующая система функций: {О, 1,2,..., к-1,1о{х), Ii(x), hix),..., xScy, 6. Доказать, что имеет место соотношение: //(х)=И- max {лч а}. 7. Выяснить, образуют ли полную систему следующие систе­ мы функций: ]) {н, 1 X, /о (х), /i(x), h-\{x), xScy, xyy}, здесь n (0< n<k - \ ) -любое целое неотрицательное число, не превосходящее /t-l; 2) {1, Nx, /о(х), /,(х), hix),...,h-\{x), х&у, xvj^}; 3) {0,1х, х&у, xv_y}. 8. Построить с.д.н.ф. для следующих функций: а)х-=:>у, к=3; б) xv(1 x&jO< ^=3, 215