V. Решить задачу

1. Доказать, что если формула логики предикатов – тавтология, то – тавтология.

2. Пусть содержит только х и является тавтологией. Доказать, что – тавтология. Верно ли обратное утверждение?

3. Сколько имеется различных k -местных предикатов на n -элементном множестве?

4. Доказать, что из выполнимости формулы следует выполнимость формулы .

5. Показать, что выполнима тогда и только тогда, когда не тождественно истинная формула.

6. Показать, что если свободна для у, то .

7. Показать, что если свободна для у, то .

8. Доказать, что если формула логики предикатов – тавтология, то – тавтология.

9. Пусть не содержит свободно х, – формула, тогда если , то .

10. Пусть не содержит свободно х, – формула, тогда если , то .

11. Доказать, что если формула логики предикатов – тавтология, то – тавтология.

12. Доказать, что – тавтология тогда и только тогда, когда не выполнима.

13. Доказать, что если содержит свободно только х и является тавтологией, то – тавтология.

14. Доказать, что бескванторная формула является тавтологией тогда и только тогда, когда она получается подстановкой из тавтологии алгебры высказываний.

15. Сколько имеется различных n -местных предикатов на 2-элементном множестве?

16. Доказать, что если формула логики предикатов – тавтология, то – тавтология.

17. Доказать, что из выполнимости формулы следует выполнимость .

18. Доказать, что если , то .

19. Пусть содержит свободно только х, и . Доказать, что . Верно ли обратное?

20. Пусть и содержит свободно только х, тогда .

21. Доказать, что если , то .

22. Доказать, что если , то .

23. Доказать, что если свободна для у, то .

24. Доказать, что тогда и только тогда, когда тождественно ложна.

ДОПОЛНИТЕЛЬНЫЕ ВОПРОСЫ

1. Найти все эквивалентности и частичные порядки на множестве .

2. Образуют ли группу все отношения на множестве М, если в качестве операции берется композиция отношений?

3. Доказать, что пропозициональная формула от n переменных является тавтологией тогда и только тогда, когда ее совершенная дизъюнктивная нормальная форма содержит 2ⁿ дизъюнктивных членов.

4. Доказать, что если – пропозициональная формула, то .

5. Доказать или опровергнуть, что: а) ; б) .

6. Доказать, что для любых пропозициональных формул, если , то .

7. Доказать, что тогда и только тогда, когда .

8. Доказать, что для любых пропозициональных формул, если , то .

9. Построить выводы в теории L:
а) ;
б) ;
в) .

10. Доказать, что бескванторная формула тождественно истинна тогда и только тогда, когда она может быть получена подстановкой из некоторой тавтологии алгебры высказываний.

11. Для предиката найти равносильный, который не содержит кванторов.

12. Являются ли формулы

а) ;
б)

тавтологиями?

13. Пусть – два одноместных предиката, определенные на множестве М такие, что высказывание истинно. Доказать, что высказывание – ложно.

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

ЛИТЕРАТУРА

1. Столл Р. Множества. Логика. Аксиоматическая теория. – М.: Просвещение, 1968. – 231 с.

2. Мендельсон Э. Введение в математическую логику. – М.:Наука, 1971, – 320с.

3. Мощенский В.А. Лекции по математической логике. – Минск: Изд-во Беларус. ун-та, 1973. – 159. с.

4. Эдельман С.Л. Математическая логика. – М.: Высш. школа, 1975. – 172 с.

5. Ершов Ю.Л., Палютин Е.А. Математическая логика. – М.:Наука, 1979. – 320с.

6. Новиков П.С. Элементы математической логики. – М.: Изд-во физ. – мат. лит., 1959. – 288с.

7. Клини С.К. Математическая логика. – М.: Мир, 1973. – 480 с.

8. Калужин Л.А. Что такое математическая логика. – М.:Наука, 1964. – 151с.

9. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логики и теории алгоритмов. – М.:Наука, 1975. – 240с.

Дата добавления: 2015-11-14