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

98 a) (xvly)==>z\ b)(х=>у)=>{1у:^1хУ, в) (x=i'y}=>(x&y::^x). 18. Выразите х=>(у= z j без = и отрицаний, стоящих перед скобками. 19. Для формулы 1 xvyvl Z найдите равносильную ей формулу, содержащ>то только связку 20. Для формулы xvyvz найдите шесть равносильных ей формул, содержащих только связки I =i>. 21. Для формулы (х=у)=>2шмш равносильную, содержащую: а) только связки J v, б) только связки J(&-, в) только связки J =>. 22. Для формулы x=^y=>z найдите равносильную, содержащую; а) только связки Jv ; б) только связки J i&. 23. Найдите простейшие равносильные формулы для заданных формул; si)xvx&yt&.z&t; S)x&]yv]xvx\ в) (]xvysz)&yvy\ г) (x=:>ysz)=>yv]y, ji)x\/x&y&y&(tvxvx)\ s)xvx&y&y&y=:>y&z&xvx\ m)x=xs X', •3)x=xsx=x\ тл) X=> X=> X=> X', 'К)х=>(х=:>х)=:>х\ л) x:^(x=:>(x=> x)). 24. Для формулы x=i-y&z найдите равносильную, содержащую: а) только связки /, &, б) только связки I v, в) только связки I =>. 25. Упростите, насколько это возможно; а) {x\/yvzj&{xvy\/jzj; б) (zvtvly)&z&(xvltvl z)\ ^)xv(y&t&z)\ т) (tvzvy)&(tv7t); д) xi&(yvx) &z; e) л: v(x vlx) v(z viz) v t; m)z&(lxvzvt)&y&(yvlz)\ г) z&lzvtvxvy\ yi) z&Jz&y)\ K)x&y&ly&(tv]xvy); л) x&y&zvy&z&xvx=>yvly^ u)yvlyvz&y=x&lx. 26. Докажите, что связки v недостаточно для выражения любой булевой функции. 27. Докажите, что каждая из пар связок (=:>, v), (&, s) не является достаточной для выражения любой булевой функции. 28. Покажите, что для выражения любой булевой функции недостаточно: а) связки б) связки в) связки =, г) связок и =, д) связок &, =>.