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

2). В приведенных далее сокращенных записях пропозицио­ нальных форм восстановить опущенные скобки; а) б) 1 B^B=>C=C&D\ в) B8LA\ г) ^=t>S=>'U&SvC; д ) А=В:=^>С\ЛА8Л BWA\ е) ASc] Bc&C=>A^\ivA=B. 18. Найти простейшие (содержащие минимально возможное число вхождений пропозициональных букв) равносильные про­ позициональные формы для заданных пропозициональных форм: a) A&,(AvBJ vA&B; 6)Av~l4&,B; B)1AVA&B; Г) A&(~l4vB); д) ~l4&(AvB); e) AvAvA&A&B&C; ж) A&A&BvB^A&BvBvA&A&C- з) (^v(5&lC))v("U&(l 5vC)); и) iA&B)vC&Dv(]Av'] B)i к) A&Bv(C^C); л) vlC &5 =>Cv1C; m ) A zz> A = A zz> A => A . 19. Законы де Моргана для п переменных можно записать в виде 1 ( ^ д ) равносильно v О л ) ' /=1 /=1 1( V ) равносильно & (1Д) . (=1 /=1 Для п=2 эти равносильности доказаны (например, с помощью таблицы истинности). Доказать их для любого п индукцией по числу переменных. 20. Доказать, что AvB&C&D равносильно iAvB)&iAvC)&(AvD). 21. Доказать, чтоA v ( & В,-) равносильно & ( AVB /). /=1 /=1 43