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

25. Запишите каждую из следующих форм без пропозициональной связки а окончательный результат без связки —i, стоящей перед скобками: а) (AvS)^>C', б) (А^В)^(—\В^—Л)', в) (А^В)^(А&В^А). 26. Выразите без^ , = и отрицаний, стоящих перед скобками. 27. Для формы -AvBv-nC найдите равносильную ей форму, содержащую только связку 28. Для формы AvBvC найдите шесть равносильных ей форм, содержащих только связки —1, 29. Для формы (А=В)^С найдите равносильную, содержащую: а) только связки —1, v, б) только связки —1, &•, в) только связки —1, 30. Для формы А^В^>С найдите равносильную, содержащую: а) только связки —1, v; б) только связки —i, &. 31. Найдите простейшие равносильные пропозициональные формы для заданных форм: а) А vA&B&C&D; б) А&-^В v-nA vA; в) f-iA vB^J &В vB; г) (А=>ВК:) =>В vlB; д) А vA&B&B&(D vA vA); е) А vA&B&B&B^B&C&A vA; ж)А=А=А; з)А=А=А=А; я) А^А^А^А; к)А^(А^А)^А; л)А^(А^(А^А)). 32. Для формы А^В&С найдите равносильную, содержащую а) только связки —1, &; б) только связки —i, v, в) только связки —1, 33. Упростите, насколько это возможно: а) (А vB vC) &(А vB v-^C) ; б) (С vD vlE) &С&(А v-^D v-^); в) D v(E&D&C) ; T)(EVC VB) &(D V-^D) ; д ) B&(A vB) <&A; e) A v(A v-^) v(C v —iC) vD; ж) C&(^ vC vD) &E&(E v-nB) ; з) C&-nC vD vA vB; и) C&-n(C&B) ; к) C&D&-nD&(E v-nA vB); л) A&B&C vB&C&A vA^B v-^\ м) В v-^ \^&В=А&-пА. 34. Докажите, что связки v недостаточно для выражения любой истинностной функции. 35. Докажите, что каждая из пар связок (^, v), (&, =) не является достаточной для выражения любой истинностной функции. 36. Покажите, что для выражения любой истинностной функции недостаточно: а) связки <&;, б) связки в) связки =, г) связок v; =, д) связок &, =^. 37. Докажите теоремы 1.3-1-1.6. 25