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

32. Для пропозициональной формы А=>В&,С найти равносиль­ ную. содержащую; а) только связки 1, б) только связки 1 , v; в) только связки 1, =>, 33. Упростить, насколько это возможно: а) (AVBVC)&IAVBV^C ); б) (CvDv1 Е )&С&(^v1 J D V 1 Е ); в) D\iE&D&C ); г) {EvCvB)&(Dv^ D); д) B&(AvB)&A-, е) v^v(y^v"U)v(CvlC)vD; ж) C&Cl4vCvD)&E&(Evl В); з) C&1CvZ3v^v5; и) С &1 (С&В); к) C&D &.1 D&(EV1AVB); л) A&B&CvB&C&AvA=>Bvl В; м) Bv^ BvC&B=ASIM. 34. Доказать, что связки v недостаточно для выражения любой истинностной функции. 35. Доказать, что казвдая из пар связок {=>, v), (&, =) не является достаточной для выражения любой истинностной функции. 36. Показать, что для выражения любой истинностной функции недостаточно: а) связки (&•, б) связки в) связки =; г) связок v, =; д) связок &, 37. Следующие пpioпoзициoнaльныe формы привести к д.н.ф. и к.н.ф.: а) У 4=>((^=> В )=> В ); б) ((А=>В)&(С=^В))ЩА&С)^(\ C&D)); в) (А=>В)=>((АГ&С)=>(А&С)); г) (^:^(Я&С))&((Л=>В)&(^=>С)); д ) ((A=>B)v(A=i>C))=>(A=>(AvC)). 38. Для заданных пропозициональных форм: 1) найдите д.н.ф., к.н.ф.; 2) выясните, является ли заданная фор­ ма выполнимой; 3) найдите с.д.н.ф и с.к.н.ф.: а) AsBvC; б) (^=>1 В)&,С-, в) (А^А^АЩ&С; г) (А=>А=>А=^В)УС; д ) AsA=BvC; е)