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

UptoLike

ВУЗ: 

МГТУ ГА | Москва

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

Рубрика: 

§1. áÌÇÅÂÒÁ ×ÙÓËÁÚÙ×ÁÎÉÊ 209
óÏÓÔÁ×ÉÔØ ÔÁÂÌÉÃÙ ÉÓÔÉÎÎÏÓÔÉ ÄÌÑ ÓÌÅÄÕÀÝÉÈ ÆÏÒÍÕÌ:
1. x ∨ y; 2. x ∧ y; 3. x → (y ∨ x); 4. x → (x ∧ y);
5. (x∨y) → (x∨y); 6. x → ((x∨ y)∨z); 7. x → (y → z); 8. (x → y) → z;
9. x ∼ (y ∼ z); 10. (x ∼ y) ∼ z; 11. (x ∨ (y ∨ z)) → (x ∧ (y ∧ z));
12. (x → (y ∧ z)) → (x → (y ∧ z)); 13.
x ∼ (y ∨ z)
∼ (x ∼ (y ∨ z));
14. (x ∨ y) → ((y ∧ z) → (x ∨ (y ∼ z))); 15. ((x ∼ y) ∼ ((z → (x ∨ y)) →
→ z)) ∼ (x ∨ y); 16. (x ∼ y) → (((y ∼ z) → (z ∼ x)) → (x ∼ z)).
ðÕÓÔØ x
i
(i = 1, 2, 3) ¡ ÓÉÍ×ÏÌÙ ÂÕÌÅ×ÙÈ ÐÅÒÅÍÅÎÎÙÈ (ÔÏ ÅÓÔØ ÐÒÉÎÉÍÁ-
ÀÝÉÈ Ä×Á ÚÎÁÞÅÎÉÑ: 0, 1). ðÏÓÔÒÏÉÔØ ÔÁÂÌÉÃÙ ÉÓÔÉÎÎÏÓÔÉ:
17. (x
1
= x
2
)∨(x
2
= x
3
); 18. (x
1
> x
2
) → (x
2
= x
3
); 19. (x
1
6= x
2
)∨(x
2
6= x
3
);
20. ((x
1
> x
2
) ∧ (x
2
= x
3
)) → (x
1
> x
3
).
ðÒÉÍÅÎÑÑ ÔÁÂÌÉÃÙ ÉÓÔÉÎÎÏÓÔÉ, ÄÏËÁÚÁÔØ ÔÏÖÄÅÓÔ×ÅÎÎÕÀ ÉÓÔÉÎÎÏÓÔØ
ÆÏÒÍÕÌ:
21. x ∼ x; 22. x ∨ x; 23. (x ∧ x); 24. x ∼ x;
25. x → (y → x); 26. x → (x → y); 27. ((x → y) ∧ x) → y;
28. ((x → y) ∧ y) → x; 29. ((x ∨ y) ∧ x) → y; 30. ((x ∼ y) ∧ x) → y;
31. (x → y) ∼ (y → x); 32. ((x → y) ∧ (y → z)) → (x → z);
33. (x → (y → z)) → ((x ∧y) → z); 34. ((x → z)∧ (y → z)) → ((x ∨y) → z);
35. (x → (y → z)) → ((x → y) → (x → z)).
ðÒÉÍÅÎÑÑ ÔÁÂÌÉÃÙ ÉÓÔÉÎÎÏÓÔÉ, ÄÏËÁÚÁÔØ ÒÁ×ÎÏÓÉÌØÎÏÓÔØ ÆÏÒÍÕÌ:
36. x ∨ y ≡ y ∨ x; 37. x ∨ (y ∨ z) ≡ (x ∨ y) ∨ z; 38. x ∧ (y ∨ z) ≡ (x ∧ y) ∧ z;
39. x ∧ (y ∧ z) ≡ (x ∧ y) ∧ z; 40. x ∨ (y ∧ z) ≡ (x ∨ y) ∧ (x ∨ z);
41. x ∧ (y ∨ z) ≡ (x ∧ y) ∨ (x ∧ z);
42. (x ∨ y) ≡ x ∧ y
43. (x ∧ y) ≡ x ∨ y
)
¡ ÚÁËÏÎÙ ÄÅ íÏÒÇÁÎÁ;
44. x ∨ x ≡ x
45. x ∧ x ≡ x
¡ ÚÁËÏÎÙ ÉÄÅÍÐÏÔÅÎÔÎÏÓÔÉ;
46. x ∨ 0 ≡ x; 47. x ∧ 1 ≡ x; 48. x ≡ x; 49. x ∼ y ≡ y ∼ x;
50. x ∼ (y ∼ z) ≡ (x ∼ y) ∼ z; 51. x → y ≡ x ∨ y; 52. x ∼ y ≡ (x →
→ y) ∧ (y → x).
1.2. ðÏÒÑÄÏË ÄÅÊÓÔ×ÉÊ É ÕÐÒÏݾÎÎÁÑ ÚÁÐÉÓØ ÆÏÒÍÕÌ
õÞÉÔÙ×ÁÑ ÓÏÇÌÁÛÅÎÉÑ Ï ÐÏÒÑÄËÅ ×ÙÐÏÌÎÅÎÉÑ ÏÐÅÒÁÃÉÊ, ÏÐÕÓÔÉÔØ ¤ÌÉÛ-
ÎÉÅ¥ ÓËÏÂËÉ É ÚÎÁË ¤∧¥ × ÆÏÒÍÕÌÁÈ:
53. x ∧ (y ∧ (x ∨ y)); 54. (x ∧ y) ∨ ((y ∧ z) ∨ ((x ∧ y) ∨ (x ∧ z)));
55. ((x ∨ y) ∨ z) → ((x ∧ y) ∨ z); 56. ((x ∨ y) ∧ (x ∨ (y ∧ z))) → ((x ∧ y) → z);
§1. áÌÇÅÂÒÁ ×ÙÓËÁÚÙ×ÁÎÉÊ                                                          209

    óÏÓÔÁ×ÉÔØ ÔÁÂÌÉÃÙ ÉÓÔÉÎÎÏÓÔÉ ÄÌÑ ÓÌÅÄÕÀÝÉÈ ÆÏÒÍÕÌ:
1. x ∨ y;          2. x ∧ y;         3. x → (y ∨ x);           4. x → (x ∧ y);
5. (x ∨ y) → (x∨ y); 6. x → ((x ∨ y) ∨ z); 7. x → (y → z); 8. (x → y) → z;
9. x ∼ (y ∼ z);        10. (x ∼ y) ∼ z;     11. (x ∨ (y ∨ z))
                                                             → (x ∧ (y ∧ z));
12. (x → (y ∧ z)) → (x → (y ∧ z));             13. x ∼ (y ∨ z) ∼ (x ∼ (y ∨ z));
14. (x ∨ y) → ((y ∧ z) → (x ∨ (y ∼ z)));          15. ((x ∼ y) ∼ ((z → (x ∨ y)) →
→ z)) ∼ (x ∨ y);       16. (x ∼ y) → (((y ∼ z) → (z ∼ x)) → (x ∼ z)).
   ðÕÓÔØ xi (i = 1, 2, 3) ¡ ÓÉÍ×ÏÌÙ ÂÕÌÅ×ÙÈ ÐÅÒÅÍÅÎÎÙÈ (ÔÏ ÅÓÔØ ÐÒÉÎÉÍÁ-
ÀÝÉÈ Ä×Á ÚÎÁÞÅÎÉÑ: 0, 1). ðÏÓÔÒÏÉÔØ ÔÁÂÌÉÃÙ ÉÓÔÉÎÎÏÓÔÉ:
17. (x1 = x2 )∨(x2 = x3); 18. (x1 > x2) → (x2 = x3 ); 19. (x1 6= x2)∨(x2 6= x3);
20. ((x1 > x2 ) ∧ (x2 = x3)) → (x1 > x3).
   ðÒÉÍÅÎÑÑ ÔÁÂÌÉÃÙ ÉÓÔÉÎÎÏÓÔÉ, ÄÏËÁÚÁÔØ ÔÏÖÄÅÓÔ×ÅÎÎÕÀ ÉÓÔÉÎÎÏÓÔØ
ÆÏÒÍÕÌ:
21. x ∼ x;              22. x ∨ x;              23. (x ∧ x);             24. x ∼ x;
25. x → (y → x);             26. x → (x → y);              27. ((x → y) ∧ x) → y;
28. ((x → y) ∧ y) → x;         29. ((x ∨ y) ∧ x) → y;        30. ((x ∼ y) ∧ x) → y;
31. (x → y) ∼ (y → x);                   32. ((x → y) ∧ (y → z)) → (x → z);
33. (x → (y → z)) → ((x ∧ y) → z); 34. ((x → z) ∧ (y → z)) → ((x ∨ y) → z);
35. (x → (y → z)) → ((x → y) → (x → z)).
   ðÒÉÍÅÎÑÑ ÔÁÂÌÉÃÙ ÉÓÔÉÎÎÏÓÔÉ, ÄÏËÁÚÁÔØ ÒÁ×ÎÏÓÉÌØÎÏÓÔØ ÆÏÒÍÕÌ:
36. x ∨ y ≡ y ∨ x;    37. x ∨ (y ∨ z) ≡ (x ∨ y) ∨ z;    38. x ∧ (y ∨ z) ≡ (x ∧ y) ∧ z;
39. x ∧ (y ∧ z) ≡ (x ∧ y) ∧ z;               40. x ∨ (y ∧ z) ≡ (x ∨ y) ∧ (x ∨ z);
41. x ∧ (y ∨ z) ≡ (x)∧ y) ∨ (x ∧ z);
42. (x ∨ y) ≡ x ∧ y
                     ¡ ÚÁËÏÎÙ ÄÅ íÏÒÇÁÎÁ;
43. (x ∧ y) ≡ x ∨ y
              
44. x ∨ x ≡ x
                ¡ ÚÁËÏÎÙ ÉÄÅÍÐÏÔÅÎÔÎÏÓÔÉ;
45. x ∧ x ≡ x
46. x ∨ 0 ≡ x;      47. x ∧ 1 ≡ x;       48. x ≡ x;             49. x ∼ y ≡ y ∼ x;
50. x ∼ (y ∼ z) ≡ (x ∼ y) ∼ z;     51. x → y ≡ x ∨ y;            52. x ∼ y ≡ (x →
→ y) ∧ (y → x).

1.2. ðÏÒÑÄÏË ÄÅÊÓÔ×ÉÊ É ÕÐÒÏݾÎÎÁÑ ÚÁÐÉÓØ ÆÏÒÍÕÌ

   õÞÉÔÙ×ÁÑ ÓÏÇÌÁÛÅÎÉÑ Ï ÐÏÒÑÄËÅ ×ÙÐÏÌÎÅÎÉÑ ÏÐÅÒÁÃÉÊ, ÏÐÕÓÔÉÔØ ¤ÌÉÛ-
ÎÉÅ¥ ÓËÏÂËÉ É ÚÎÁË ¤∧¥ × ÆÏÒÍÕÌÁÈ:
53. x ∧ (y ∧ (x ∨ y));             54. (x ∧ y) ∨ ((y ∧ z) ∨ ((x ∧ y) ∨ (x ∧ z)));
55. ((x ∨ y) ∨ z) → ((x ∧ y) ∨ z);   56. ((x ∨ y) ∧ (x ∨ (y ∧ z))) → ((x ∧ y) → z);

Страницы