Спирина, М.С. Дискретная математика

введем константу а. Поэтому 3xF(x) —» F(a). Это так называемое правило 3-удаления, или es-правило (правило выбора). Правило V- удаления снимает квантор общности, осуществляя переход от V x / \x ) к произвольным формулам F(a), F(y) и др. с учетом того, что эти переменные свободны от х в Fx. Например, из высказывания «Каждый студент колледжа владеет компьюте­ ром» будет следовать, что конкретный студент Максимов тоже владеет компьютером, и произвольно выбранный некоторый сту­ дент у владеет компьютером, и всякий студент z тоже владеет компьютером. При этом необходимо помнить, что предметные переменные у и г не должны быть связанными. Правило V -удале­ ния называют правшюм универсальной конкретизации, или us-npa- вилом. Рассмотрим примеры. «Все металлы (М) — плавятся (П). Цинк (Ц ) — металл. Зна­ чит, цинк плавится». Формализация в логике предикатов примет вид: Vx(M(x) —> П(х)) л V jc (Ц(л:> -» М(х)) }— Ух(Ц(х) -> П(х)). Снятие квантора общности: (М(х) —> П(х)) л (Ц(х) —» П(х)); тогда на основании транзитивности импликации имеем (Ц(х) —» -» М(х)), (М(х) -> П(х)) (= Ц(х) -> П(х). Поэтому вывод Vx(U(x) —> -> П(х)) — обобщение по Я2 — верен. «Все студенты (С) проходят практику (П). Некоторые студен­ ты работают в фирме (Ф), значит, некоторые работающие в фир­ ме — проходят практику». Формализация примет вид: Vx(C(x) —> -» П(х)) л Зх(С(х) л Ф(х)) |— Зх(Ф(х) л П(х)). Уберем кванторы по правилам us и es. Имеем (С (а) -» П(а)) а (С (а) л Ф(а)) <=> <=> (С (а) -> П(а)) л С (а) л Ф(а) <=>П(а) л Ф(а). Вывод: Зх(П(х) л л Ф(х)), т.е. существуют студенты, которые проходят практику в фирме. Свойства отношения классификации. Рассмотрим непустое мно­ жество U. Пусть дана одноместная высказывательная форма Ф с переменной, которая принимает значения из U, проявляя свой­ ство некоторых объектов из него и соответствуя некоторому пре­ дикату Q. Множество истинности Т( Q) таких объектов является подмножеством U как универсального множества. Пусть дано Ux = = {5, 6, 7, 8, 9, 10, 11, 12, 13, 14 ...}. Высказывательной форме «5 < х < 12» соответствует подмножество TX{Q) = {5, 6, 7, 8, 9, 10, 11} (7Х(?|) с Ux). Из множества U2 = {1, 3, 5, 7, 9, 11, 13, 15} та же высказывательная форма выделяет множество истинности T2(Q) - = {5, 7, 9, 11}, из U, - {5, 6, 7, 8, 9, 10, 11} - T3(Q) = U3, из UA= = {12, 13, 14, 15} рассматриваемая высказывательная форма выде­ ляет пустое подмножество истинности T4(Q) = 0 . Эта высказывательная форма выражает на множестве U един­ ственное свойство, характерное для рассматриваемого предиката на заданном множестве U, т.е. одноместный предикат Q (в дан­ ном случае «5 < х< 12») задает свойство данного множества. Тогда 237