Задачи и упражнения по математической логике и теории множеств. Часть математическая логика (стр. 1 из 5)

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО

ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

РОСТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Я.М.ЕРУСАЛИМСКИЙ, М.Р.УХОВСКИЙ, А.В.КОЗАК

ЗАДАЧИ И УПРАЖНЕНИЯ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ

И ТЕОРИИ МНОЖЕСТВ. ЧАСТЬ 1. МАТЕМАТИЧЕСКАЯ ЛОГИКА.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ ДЛЯ СТУДЕНТОВ 1-ГО КУРСА

МЕХАНИКО-МАТЕМАТИЧЕСКОГО ФАКУЛЬТЕТА ПО КУРСАМ

“МАТЕМАТИЧЕСКАЯ ЛОГИКА”, ”МАТЕМАТИЧЕСКАЯ ЛОГИКА,И ДИСКРЕТНАЯ МАТЕМАТИКА.”

РОСТОВ-НА-ДОНУ

1980

Печатается по решению учебно-методической комиссии механико-математического факультета РГУ от 11 января 1980 г.

I. АЛГЕБРА ВЫСКАЗЫВАНИЙ.

§ 1. ЛОГИЧЕСКИЕ ОПЕРАЦИИ. ТАБЛИЦЫ ИСТИННОСТИ.

Цель этого параграфа - познакомиться с определениями основных логических операций: отрицанием ( ,  ), дизъюнкцией ( ,  ), конъюнкцией ( ,  ), импликацией ( , ), эквиваленцией ( , «,  ), их свойствами, построением таблиц истинности формул алгебры высказываний, а также равносильными преобразованиями формул.

Под высказыванием мы понимаем связное (осмысленное) повествовательное предложение, о котором можно сказать истинно оно или ложно. Если A - символ высказывания, то через

будем обозначать его значение истинности. 1 (И) – истина, 0 (Л) – ложь. В высказываниях нас будет интересовать только значение истинности, поэтому логические операции можно определить с помощью таблиц истинности.

Отрицание			Бинарные операции
0	1		0	0	0	0	1	1
1	0		0	1	1	0	1	0
			1	0	1	0	0	0
			1	1	1	1	1	1

Составить таблицу истинности для следующих формул:

1)

2)

3)

4)

5)

6)

7)

8)

9)

10) (x~y)~z

11)

12)

13)

14)

15)

16)

Пусть x_i (i=1,2,3…) – символы булевских переменных (т.е. принимающих два значения: 0,1). Построить таблицы истинности.

17) (x₁=x₂)Ú(x₂=x₃) 18) (x₁>x₂)®(x₂=x₃)

19) (x₁¹x₂)Ù(x₂¹x₃) 20) ((x₁>x₂)Ù(x₂=x₃))®(x₂=x₃)

Применяя таблицы истинности, доказать тождественную истинность формул:

21) x ~ x 22) x Ú

23)

24)

25) x ®(y ®x) 26)

® (x ® y)

27) ((x ® y) Ù x) ®y 28) ((x ® y) Ù

) ®

29) ((x Ú y) Ù

) ® 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 º y Ù x

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)

Законы де Моргана.

Законы идемпотентности.

46) x Ú 0 º x 47) x Ù 1 º x

48)

49) x ~ y º y ~ x

50) x ~ (y ~ z) º (x ~ y) ~ z 51) x ® y º

Ú y

52) x ~ y º (x ® y) Ù (y ®x)

При записи формул принимают следующие соглашения об упрощении записи формул:

1). Операции располагаются по старшинству (от «сильных» к «слабым») а ù Ù Ú

2). Знак конъюнкции опускается.

Учитывая соглашения о порядке выполнения операций, опустить «лишние» скобки и знак «Ù» в формулах:

53) x Ù (y Ù(x Ú

))

54) (x Ù y) Ú ((y Ù z) Ú ((

Ù y) Ú (x Ù

)))

55) ((x Ú y) Ú z) ® ((x Ù

) Ú z)

56) ((x Ú y) Ù (x Ú (y Ù z))) ® ((

Ù`y ) ®

57) ((x Ú y) Ú (x Ú ((y Ù (x Ú z)) Ù (y ® z))) ~ z)

58) ((x Ú y) ® (x Ù y)) Ú((

Ù y) Ù( x Ú ))