Задачи и упражнения по математической логике и теории множеств. Часть математическая логика МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ РОСТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Я.М.ЕРУСАЛИМСКИЙ, М.Р.УХОВСКИЙ, А.В.КОЗАК ЗАДАЧИ И УПРАЖНЕНИЯ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ И ТЕОРИИ МНОЖЕСТВ. ЧАСТЬ 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) Пусть xi (i=1,2,3…) – символы булевских переменных (т.е. принимающих два значения: 0,1 ). Построить таблицы истинности. 17) ( x1 =x2 ) Ú (x2 =x3 ) 18) (x1 >x2 ) ® (x2 =x3 ) 19) (x1 ¹ x2 ) Ù (x2 ¹ x3 ) 20) ((x1 >x2 ) Ù (x2 =x3 )) ® (x2 =x3 ) Применяя таблицы истинности, доказать тождественную истинность формул: 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 Ú )) 59) ((x Ú y) Ù z) ® (((x Ù y) Ú z) ~ ( Ú )) 60) (x Ù (y Ú z)) Ù ((x ® (y ® z)) ~ (x Ù y)) Восстановить скобки и знак «Ù » в формулах: 61) x Ú y ® z 62) x Ú y ® x y 63) 64) x Ú y(x y Ú z) 65) x y Ú x ® Ú y z 66) (x ® x Ú y z) ~ (x Ú y ® z) 67) (x Ú y) ® (x y ~ Ú ) 68) x Ú y ® x Ú y (x ® z) Ú x (y ~ z) 69) x y z ® (x ~ y z) Ú x Ú y (x ® (y ~ z)) 70) x y ~ x(y ® z)(x ~ y) Ú x z Ú y z § 2. РАВНОСИЛЬНЫЕ ПРЕОБРАЗОВАНИЯ ФОРМУЛ. НОРМАЛЬНЫЕ ФОРМУЛЫ. ДВОЙСТВЕННОСТЬ В АЛГЕБРЕ ВЫСКАЗЫВАНИЙ. Две формулы F и G называются равносильными ( F º G) , если . При равносильных преобразованиях формул используются основные равносильности булевой алгебры высказываний (см. [1] стр.42). Применяя равносильные преобразования доказать следующие соотношения: 71) 72) 73) 74) x ® y º ® 75) x y Ú x º x 76) x Ú x y º x 77) x(x Ú y) º x 78) x Ú y º x Ú y 79) Ú x y º Ú y 80) (x ® y) ® y º x Ú y 81) (x Ú y)(x Ú ) º x 82) Ú º y ® 83) x ~ y º ~ 84) x y Ú y Ú º x ® y 85) x ® (y ® z) º (x Ú z)(y Ú z) 86) x ® (y ® z) º y ® (x ® z) 87) Ú x y Ú x z Ú y Ú z º x ® y z Применяя равносильные преобразования доказать тождественную истинность формул: 88) x ® x Ú y 89) x y ® x 90) ® (x ® y) 91) (x ® y) ® ( Ú y) 92) ( ® y) ® ( ® x) 93) ( ® ) ® (y ® x) 94) (x ® y) Ú (y ® x) 95) (x ® y) Ú (x ® ) 96) x ® (y ® x y) 97) (x ® y) x ® y 98) (x ® y) ® 99) (x Ú y) ® y 100) (x ÚÚ y)x ® ; « ÚÚ » - альтернативная дизъюнкция. 101) ( x ® y)(y ® z) ® (x ® z) 102) (x ® (y ® z)) ® (x y ® z) 103) (x ® z)(y ® z) ® (x Ú y ® z) 104) (x ® z) ® ((y ® z) ® (x Ú y ® z)) Применяя равносильные преобразования, «упростить»: 105) 106) 107) 108) (x Ú y)(x ~ y) 109) (x ® y)(y ® z) ® (z ® x) 110) x z Ú x Ú y z Ú y z 111) 112) x y (x ~ y) 113) (x ® ) (x ~ y) 114) Следующие формулы преобразовать так, чтобы они содержали только «Ù » и «ù » 115) x Ú y 116) x ® y 117) x ~ y 118) x Ú y Ú z 119) x ® (y ® z) 120) x Ú (x ~ y) 121) Ú ( ® ) 122) x ÚÚ y 123) x ® ( ® x) 124) x Ú y ® ( ® y) Следующие формулы преобразовать так, чтобы они содержали только «Ú » и «ù »: 125) x y 126) x y z 127) x ~ y 128) x ÚÚ y 129) x (x ~ y) 130) x ~ y ~ z 131) (x ~ y) (y ~ z) 132) x y ~ x z Следующие формулы преобразовать так, чтобы знак отрицания был отнесен только к переменным высказываниям: 133) 134) 135) 136) 137) 138) Преобразовать формулы так, чтобы они содержали только операции «Ú », «Ù » и «ù » : 139) x ~ y 140) (x ® y) ~ (y ® z) 141) (x ~ y) ® (y ® z) 142) (x ~ y) ® (y ~ z) 143) (x ~ y)(y ~ z) ® (x ~ z) 144) ((x ~ y) Ú (y ~ z)) ® (x ~y~ z) 145) x ~ y ~ z ~ v 146) (x ® y) ~ (z ® (x~ )) Найти двойственные формулы: 147) x( Ú z) 148) x y Ú x z 149) 150) (x y Ú y z Ú z v) 151) 152) 153) ((x Ú y) Ú x y) Ú ( Ú x) 154) x y( Ú x y z Ú )(x Ú y Ú z) Применить закон двойственности к следующим равносильностям: 155) x x º x 156) x Ú 0 º x 157) x y º y x 158) x Ú (y Ú z) º (x Ú y) Ú z 159) º Ú 160) x (x Ú y) º x 161) x Ú y º x Ú y 162) x Ú x y Ú y z Ú z º x Ú z Привести к дизъюнктивной нормальной форме (ДНФ ): 163) 164) 165) 166) 167) 168) 169) 170) 171) 172) Привести к конъюнктивной нормальной форме (КНФ ): 173) 174) 175) 176) 177) 178) 179) 180) 181) 182) . Приведением к нормальной форме выяснить, какие из формул являются тождественно истинными, тождественно ложными, выполнимы: 183) 184) 185) 186) 187) 188) 189) 190) 191) Для каждой из следующих формул найти дизъюнктивное и конъюктивное разложение: 192) 193) 194) 195) 196) 197) 198) 199) 200) Привести к совершенной ДНФ (СДНФ) следующие формулы: 201) 202) 203) 204) 205) 206) 207) 208) Привести к совершенной КНФ (СКНФ) следующие формулы: 209) 210) 211) 212) 213) 214) 215) 216) 217) 218) Приведением к совершенным нормальным формам доказать не равносильность следующих формул: 219) и 220) и 221 ) и 222) и 223) и 224) и 225) и 226) и 227) и 228) и Следующие формулы разложить по переменным x, y, z : 229) 230) 231) x 232) 233) Выяснить, является ли первая формула логическим следствием остальных: 234) y ; 235) x ; 236) ; 237) 238) y ; 239) ; 240) ; 241) 242) 243) ; 244) ; 245) z; 246) 247) 248) 249) 250) Найти все (с точностью до равносильности) логические следствия из посылок: 251) 252) 253) 254) 255) 256) 257) 258) 259) 260) Найти все (с точностью до равносильности) посылки, логическим следствием которых являются формулы: 261) 262) 263) 264) 265) 266) xyz 267) 268) 269) 270) Докажите правильность умозаключений: 271) 272) 273) 274) 275) 276) 277) 278) 279) 280) 281) 282) Выяснить, правильны ли следующие умозаключения: 283) 284) 285) 286) 287) 288) 289) 290) 291) 292) §3.АНАЛИЗ И СИНТЕЗ РЕЛЕЙНО-КОНТАКТНЫХ СХЕМ. Составить схемы, реализующие следующие функции: 293) 294) 295) 296) 297) 298)       X Y Z 0 0 0 0 0 1 0 0 1 1 1 1 0 1 0 1 0 0 0 1 1 0 1