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

§ 16. Упражнения 1. Доказать, что Л }= В&С тогда и только тогда, когда 2. Доказать, что; а) Ах,Аг,...уЛп\' В тогда и только тогда, когда |= {ап=>в)\ )Ai^42,,..fAn [= J5 тогда и только тогда, когда 1= (АI=>(/l2=>(... (А„=>В)...))); в) В тогда и только тогда, когда Ai&A2&,...&A „ \= В. 3. Доказать, что если Л [= С и J5 |= С, то AvB [= С (доказательст разбором случаев). 4. Доказать, что если А^ В, го для произвольной пропозицио­ нальной формы С имеет место А&С |= В. 5. Доказать, что а) А^=>В [= В (правило заключения); б) А,Б ^А&,В\ в) А,В [= AvB\ г) А ^AwB-, ji)A=>B, I B |="U (правило отрицания); е) А=>В, В=:>С ^А=>С (правило силлогизма); ж) А=:>В [=1в=>"и (правило контрапозиции); з) Л=>(В=>С) (=jB=>(^.'=t>C) (правило перестановки посылок); и) j=v4&jB=i>C (правило соединения посылок); к) А&В=>С ^А^(В=>С) (правило разъединения посылок); л)А&В\^В; м) Bi&B2&,...8iBk для каждого i (l<i<k). Известно, что если пропозициональная форма С представлена в к.н.ф. или с.к.н.ф., то каждый ее конъюнктивный член, а также конъюнкция любого числа конъюнктивных членов является логиче­ ским следствием из С. Это позволяет находить следствия из данных пропозициональных форм, Пусть даны пропозициональные формы А ' В упражнениях 1-14 рассматриваются формулы логики высказываний (про­ позициональные формы). 130