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

9. Являются ли следующие выражения пропозициональными формами: а) &А; б) (А&(vB)); в) ((vC) vB); г) ((hC)^B)^B); д) (А^Ы) ) ; е)h h H ^ ) ) ) ) . 10. а) пусть значение формы (А=В) есть И. Что можно сказать о значениях форм (А^-В)) и ((^)=В)1 б) пусть значение формы (А=В) есть Л. Что можно сказать о значениях (А^^В)) и (Ы)^В)1 11. Найти значения А, В, С, если: а) НА&В)) =Л; б) НА^(^))) =Щ в) (НА v(A=B)))^) =Л; г) (А у(А&В))=Л; д) ((А&В)vC)) =И; е) А=В&С vA=Л; ж) ((^(А&В))К:)=И, з) Ш&B)VC)^A)=Л, (^уЫ))=Л-, (\У(^С))=Л; и) (А^В)=Л, к) q(A&B)vC)=A)=H, (\^С)=Л; (^у(^))=Л; л) (Л^(—В))=Л, м) (Л^>С)=Л, (ц&в)к:)=и. (\&в)=и. 12. Составьте таблицы истинности для следующих форм: а) (А^(В^А)); б) ((А^(В^>С))^((А^В)^(А^>С)))', в) ( ( ( ^ ) ^ ( ^ ) ) ^ ( ( ( ^ ) ^ ^ ) ^В ) ) ; г) ((А^В)^)-, д) (А^ (В^ ) ) - е) ((А^В)^(^В)^Ы))) ; ж) ((А^В) v((-^C)&B)); 3) ((А^ВМЫ)^(^))). 13. Укажите, какие из форм упражнения 12 являются тавтологиями и какие противоречиями. 14. Доказать, что если А - тавтология, то тавтологиями являются (AvB) и (В^А), где В - произвольная пропозициональная форма. 15. Для данных пропозициональных форм составить таблицы истинности. Определить, для которых из них истинностные значения всей формы можно записать без промежуточных выкладок (используйте результаты упражнения 14): а) ((А^А) vB); б) (С^(А^А)); -^)) ; ^) ((^ ^ 4 * ^4* ; д) (А^(А^А)); е) (((А&В) V(^C))^(A^A)); ж) (((C&D)v(A&B))^(Bv(^))); з) ((АУ(ВУЫ)))&(СУ(АУ(^С)))); и) ((В=В)&(С^)&(А у(^))); к) (((А&В)&(А&А)) у(^(А&В))). 16. Составить таблицу истинности для истинностной функции, зависящей от трех переменных, если известно, что функция истинна тогда и только тогда, когда: а) все переменные принимают одинаковые значения; б) истинны значения большинства переменных этой функции; в) истинно значение одного и только одного из ее переменных; 23