Математическая логика и теория алгоритмов. Стенюшкина В.А. - 49 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

Составители: 

Рубрика: 

в) (А → В) ∧ (С → D); (В → D) ∧ (¬С → А); (Е → F) ∧ (F →¬ D); ¬ Е →
Е;
г) (А
→ В ∧ С) ∧ (D → В ∧ Е); (F → А) ∧ G → Н; (G → Н) → F ∧ D; ¬(С
→ Е);
Решите задачу двумя способами: путем приписывания значений простым
высказываниям (буквам) и с помощью логического вывода.
33 Запишите в символической форме и установите логичность следую-
щих рассуждений:
а) Если заменить лампу (А), телевизор будет работать (В) при условии,
что напряжение подключено (С). Лампа заменена, а напряжение не подключе-
но. Следовательно, телевизор не будет работать.
б) Если поднять давление (А) или увеличить температуру (В), то реакция
произойдет быстрее (С), но опасность повысится (Д). Если опасность повысит-
ся, то необходимо принять меры защиты (Е). Меры защиты не приняты. Следо-
вательно, давление поднимать нельзя.
в) Если упростить схему (А), стоимость снизится (В), и если применить
новые элементы (С), надежность увеличится (Д). Можно или упростить схему,
или применить новые элементы. Однако, если упростить схему, то надежность
не увеличится, а если применить новые элементы, то стоимость не снизится.
Итак, надежность увеличится тогда и только тогда, когда стоимость снизится.
34 Свободен ли терм f (х1,х2) для х1 в формулах А1 (х1,х2)
→ ∀х2 А2
(х2),
∀ х2А(х2,а1)) ∨ ∃ х2А(х1,х2)?
35 Указать свободные и связанные вхождения переменных в следующие
формулы:
1)
∀х3 (∀х1А (х1,х2) → А (х3,х1));
2)
∀х2А (х3,х2) → ∀х3А(х3,х2);
3)
(∀х2∃ х1А1 (х1,х2, f1 (х1,х2))) ∨ ∀х1А2 (х2, f2(х1)).
36 Даны формулы:
1)
А1^2 (f1^2 (x1,x2),a1);
2)
А1^2 (x1,x2) → А1^2 (x2,x1);
3)
∀х1 ∀х2 ∀х3 (А1^2 (x1,x2) → А1^2 (x2,x3) → А1^2 (x1,x3).
Для следующих интерпретаций и для каждой из записанных формул ука-
зать, при каких значениях свободных переменных эти формулы выполнены
(если они имеют свободные переменные), или выяснить, являются ли они лож-
ными или истинными высказываниями (если они не содержат свободных пере-
менных):
а) Область интерпретации – множество всех целых положительных чисел;
А
1
2
(y,z), f
1
2
(x,z), a
1
интерпретируется соответственно как y ≥ z, yz, 1.
б) Область интерпретации – множество всех множеств целых чисел, А
1
2
(y, z), f
1
2
(y, z), а
1
интерпретируются соответственно как y⊃z, z ∪ y, ∅ (пустое
множество).
37 Показать, что следующие формулы не являются общезначимыми:
а) ((
∀х
1
А
1
1
(х
1
) → ∀х
1
А
2
1
(х
1
)) → ((∀х
1
(А
1
1
(х
1
) → А
2
1
(х
1
)));
б) (
∀х
1
(А
1
1
(х1) ∨ А
21
(х
1
))) → ((∀х
1
А
1
1
(х
1
)) ∨ (∀х
1
А
2
1
(х
1
))). 
        в) (А → В) ∧ (С → D); (В → D) ∧ (¬С → А); (Е → F) ∧ (F →¬ D); ¬ Е →
Е;
        г) (А → В ∧ С) ∧ (D → В ∧ Е); (F → А) ∧ G → Н; (G → Н) → F ∧ D; ¬(С
→ Е);
       Решите задачу двумя способами: путем приписывания значений простым
высказываниям (буквам) и с помощью логического вывода.
       33 Запишите в символической форме и установите логичность следую-
щих рассуждений:
       а) Если заменить лампу (А), телевизор будет работать (В) при условии,
что напряжение подключено (С). Лампа заменена, а напряжение не подключе-
но. Следовательно, телевизор не будет работать.
       б) Если поднять давление (А) или увеличить температуру (В), то реакция
произойдет быстрее (С), но опасность повысится (Д). Если опасность повысит-
ся, то необходимо принять меры защиты (Е). Меры защиты не приняты. Следо-
вательно, давление поднимать нельзя.
       в) Если упростить схему (А), стоимость снизится (В), и если применить
новые элементы (С), надежность увеличится (Д). Можно или упростить схему,
или применить новые элементы. Однако, если упростить схему, то надежность
не увеличится, а если применить новые элементы, то стоимость не снизится.
Итак, надежность увеличится тогда и только тогда, когда стоимость снизится.
       34 Свободен ли терм f (х1,х2) для х1 в формулах А1 (х1,х2) → ∀х2 А2
(х2), ∀ х2А(х2,а1)) ∨ ∃ х2А(х1,х2)?
       35 Указать свободные и связанные вхождения переменных в следующие
формулы:
       1)      ∀х3 (∀х1А (х1,х2) → А (х3,х1));
       2)      ∀х2А (х3,х2) → ∀х3А(х3,х2);
       3)      (∀х2∃ х1А1 (х1,х2, f1 (х1,х2))) ∨  ∀х1А2 (х2, f2(х1)).
       36 Даны формулы:
       1)      А1^2 (f1^2 (x1,x2),a1);
       2)      А1^2 (x1,x2) → А1^2 (x2,x1);
       3)      ∀х1 ∀х2 ∀х3 (А1^2 (x1,x2) → А1^2 (x2,x3) → А1^2 (x1,x3).
       Для следующих интерпретаций и для каждой из записанных формул ука-
зать, при каких значениях свободных переменных эти формулы выполнены
(если они имеют свободные переменные), или выяснить, являются ли они лож-
ными или истинными высказываниями (если они не содержат свободных пере-
менных):
       а) Область интерпретации – множество всех целых положительных чисел;
А1 (y,z), f12(x,z), a1 интерпретируется соответственно как y ≥ z, yz, 1.
   2

       б) Область интерпретации – множество всех множеств целых чисел, А12
(y, z), f12(y, z), а1 интерпретируются соответственно как y⊃z, z ∪ y, ∅ (пустое
множество).
       37 Показать, что следующие формулы не являются общезначимыми:
        а) ((∀х1А11(х1) → ∀х 1А21(х1)) → ((∀х1(А11(х1) → А21(х1)));
        б) (∀х1(А11(х1) ∨ А21(х1))) → ((∀х1 А11(х1)) ∨ (∀х1 А21(х1))).

Страницы