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

4. Пусть А, В С - произвольные формулы логики высказываний. Дока­ зать, что если В,то для произвольной пропозициональной формы С имеет MQCTO А&С\'В. 5. Пусть А, В VI С - произвольные формулы логики высказываний. Дока­ зать, что: a) А,А =^В 1= В (правило заключения); б) А,В \^А&В; b)А,В\'А\^; Т)А\'А\^; д) А^В, —В 1= —А (правило отрицания); е)А^В, B^>cYa^>C(правило силлогизма); ж)А^В 1= —В^—А (правило контрапозиции); з)А^В^>С) \^В^А^>С) (правило перестановки посылок); А^В^>С) \'А&В^>С (правило соединения посылок); к) А&В^>С\'А^В^>С) (правило разъединения посылок); л)А&В 1=5; м) В1&В2& &Bk Вi для каждого i{\<i<k). 6. ПустьAj, А2,..., АпиВ - произвольные формулы логики высказываний. Доказать, что еслиЛ ; , Л 2 , . . . В и Ai тавтология / {\<i<k), то {Aj,A2,...,An}- {Ai} h »- 7. Пусть 5" = {^ vB, А^>С}. Докажите, что ^ |=5vC. 8. Докажите, что если А, -^В |= С& -iC, то ^ |=5. 9. Пусть S множество дизъюнктов и пусть литерал L содержится в некото­ ром (некоторых) дизъюнктах из S, но литерал —L не содержится ни в одном из дизъюнктов из S. Пусть 5"* получено из S удалением всех дизъюнктов содержа­ щих литерал L. Покажите, что S выполнимо тогда и только тогда, когда 5"* вы­ полнимо. 10. Пусть S множество дизъюнктов и пусть в некотором из дизъюнктов С содержатся как литерал L так и литерал —iL. Положим, что = S - {С}. Пока­ жите, что S выполнимо тогда и только тогда, когда 5"* выполнимо. 11. Пусть S множество дизъюнктов и пусть С дизъюнкт состоящий из единственной литеры L {C=L). Положим, что получено из Положим, что S удалением каждого дизъюнкта содержащего L и удалением литеры —L из всех оставшихся дизъюнктов. Покажите, что S выполнимо тогда и только тогда, ко­ гда 5"* выполнимо. 12. Пусть S множество дизъюнктов и пусть дизъюнкты Ci и С2 из 5" таковы, что Ci является поддизъюнктом дизъюнкта С2 (Ci является частью С2). Поло­ жим, что = S - {С2}, т.е. получено удалением из S большего дизъюнкта. По­ кажите, что S выполнимо тогда и только тогда, когда 5"* выполнимо. 13. Для каждого из множеств дизъюнктов S найдите более простое (с меньшим числом элементов и содержащих меньшее число литералов) множест­ 93