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

г) каждая переменная принимает значение, отличное от значения соседней переменной. 17. 1) Записать в сокращенном виде, т. е. по возможности опустив скобки: а) ((Ы)^(ВУ(^С))М(В&Л)У(^В))); б) (((А v(^B)) vC)^((-^)&B)); в) ((А=>В) С-пС))); г) (((Ы)^В)&(ВУ(^С)))^А); д) ((((А^Ы)) v(^)) vC)&(A^B)); е) (A^(B^(C^D))). 2) В приведенных ниже сокращенных записях пропозициональных форм восстановить опущенные скобки: a) A=Bv^C&A^ -А; б) -^B^B^K:&D; b)A=B=^V^B&A; T)A^B^^&BVC; Д)А=В^у^&^УА; Q)A&-^B&C^A^^VA=B. 18. Найти простейшие (содержащие минимально возможное число вхождений пропозициональных букв) равносильные формы для заданных форм: a) А&(А vB) vA&В; б) А v —A& В; B) — A V A&B; T )A&(—A V B); д) -А&(А vB); е) А vA vA&A&B&C; ж) А &В vB^A &В vB vA &С; з) (А v(B&-nC)) v(-^ &(^ vC)); и) (А&В) vC&D v(-iA v-^); к) А&В v(C^); ji) Av —iC&B^>Cv—iC', м) A^A=A^A^A. 19. Законы Де Моргана для п переменных можно записать в виде: п ^ \ ^ —'Г &А) равносильно VМ/); -^( V Aj) равносильно & ( —Aj). i=l i=l i=l i=\ Для n = 2 эти равносильности доказаны (например, с помощью таблицы истинности). Доказать их для любого п индукцией по числу переменных. 20. Сколькими способами можно расставить скобки в следующих выражениях, чтобы получались пропозициональные формы: а )^^—l S^C; 6) —A^BVC', B)A^—\B&DVC. П п 21. Доказать, что Av( 8с ВJ равносильно (А vBi). i=l i =l п п 22. Доказать, чтоА&( v В^) равносильно у (A&Bi). i =l г=1 23. ЗапишитеА ^ —^(В^>С) без связки Запишите ответ так, чтобы связка —1 не стояла перед скобками. 24. Запишите (В^>С)^ —А без связки Запишите результат в форме, не содержащей —i перед скобками. 24