Дискретная математика

97 9. 1), Записать в сокраохенном виде, т. е. по возможности опустив скобки следующие формулы: а) (((lx)=:>(yv(lz))j=((y&x)v(ly)))\ б) (((xv(ly))vz)=:>((lx)&y))\ в) ((x=>y)=:>(z=:>(lz)))\ ^)((((lx)sy) &(y V( Iz))) • д) ((((x^(]y))v(]z))vz)&(x=>y)); ) (A=i>(B=>(C^D))). 2). В приводимых далее сокращенных записях формул восстановить опущенные скобки: а) xsy v]z&c^ ]х; б) ly=^y:::^Z=Z&t\ в) xsy=lyvly&x-, г) X=>y=:i']x&yvz\ д) Х=у=:> zvlx&l yvx\ е) Х&1 y&z=:>x=:>lxvx=y. 10. Найти простейшие (содержащие минимально возможное число вхождений переменных) равносильные формулы для заданных формул: a) x&(xvy) vx&y\ b)xvlx&y, b) Ixvx&y, т)x&(lxvy)\ д) lx&(xvy)\ e)xvx\^c&xc&y&z', ж) x&xi&yyy=>xi&yyyvx&xc&z-, з) (xv(y&lz))v(lx&(lyvz))\ и) (x&y)vz&tv(lxvly)\ v)x&yv(z=>z)-, n)xvlz&y=:>zvlz\ u) x=>x=x=:>x=:>x. 11. Законы де Моргана для п переменных можно записать в виде: " " I \ JS LX ,) равносильно v O-^i); i=l i=l n n J V Xj) равносильно &( I x j ) . )=; i=i Для n~2 эти равносильности доказаны (например, с помощью таблищ>1 истинности). Доказать их для любого п индукцией по числу переменных. 12. Доказать, что сёzcfe? равносильно (xvy)&(xvz)&{xvt). /7 п 13. Доказать, 4TQXV( равносильно .=1 п п 14. Доказать, что jc< £Y v y'/J равносильно v (xc&yi). i=i '=1 15. Запишите x ^ ( y ^ ^ ) без связки Запишите ответ так, чтобы связка 7 не стояла перед скобками. 16. Запишите ( y z ^ z ) ^ l x без связки :=>. Запишите результат в форме, не содернсащей 7 перед скобками. 17. Запишите каясдую из следующих формул без связки а окончательный результат без связки 7, стоящей перед скобками: