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

истинным только в том случае, если истинны одновременно все высказывания /Да,), Р{а2), ..., Р(а„), т.е. если истинна их конъ­ юнкция: Р(а^) л Р(а2) л ... л Р(а„). Аналогично высказывание Зх/*(х) означает, что оно истинно, когда истинно хотя бы одно из высказываний Р(а{), Р(а2), ..., Р(ап). Тогда должна быть ис­ тинной дизъюнкция высказываний Р(а{) v Р(а2) v ... v Р(ап). По­ этому для конечной области определения выполняются равно­ сильности: (Ух е D)P(x) » P ia^ л Р(а2) л ... л Р(а„) и (Зх € е D)P(x) <=> Р(ах) v Р(а2) v ... v Р(ап). Таким образом, кванторы общности и существования являют­ ся дополнениями и аналогами соответственно логических опера­ ций конъюнкции и дизъюнкции. Поскольку конъюнкцию можно выразить через отрицание и дизъюнкцию, то, вообще говоря, символ 3 можно было не вклю­ чать в число основных символов, так как квантор существова­ ния ЗхЛ(х) по сути является сокращенной записью формулы УхЛ(х), выражающей так называемую двойственность. Например, запишем с помощью формул логики предикатов следующее утверждение: «Для лечения любого известного компью­ терного вируса имеются программы. Существуют новые (неизвест­ ные) компьютерные вирусы, для лечения которых программы еще не разработаны». Введем обозначения элементарных формул: А(х) — известен компьютерный вирус х; В(х) — для лечения вируса х существует программа. Тогда с помощью логических связок и кванторов получим фор­ мулы: В(х) — против вируса х нет программы; Ух(Л(х)) — любой вирус известен; Зх(Л(х)) — существуют новые (неизвестные) вирусы; Ух(Л(х) -» В(х)) — если вирус давно известен, то имеется про- граммадля его лечения; Эх(А(х) л В(х)) — существуют (появились) новые вирусы, для лечения которых программы еще не разработаны. Тогда формализованное исходное утверждение примет вид (Ух(Л(х) -» В(х))) л (Зх(Д(х) л В(х))). В эту формулу входит лишь связанная переменная х, а, напри­ мер, в формуле А(х\, х2) —» У х ^ х Д первое включение перемен­ ной Х[ свободное, а второе — связанное. Отношения следования и равносильности между высказыва- тельными формами связаны с тождественно-истинными импли­ кацией и эквиваленцией, следовательно, их можно записать с по­ мощью квантора общности: Q\(x) => Qi(x) тождественно Ух(0 ,(х) -» Q2(x)); 0 i (х) <=> Q2(x) тождественно Ух(0,(х) = Q2(x)). 232