Калижанова, А.У. Системный анализ Учебное пособие

34 последовательности по правилу MP. Если существует формальный вывод формулы B из формул A 1 , ..., A n , то формула B называется формально выводимой из формул A 1 , ..., A n (или теоремой теории L), и это обозначается так: A 1 , ..., , или Г B, где Г={A 1 , ..., A n }. В частном случае, при пустом множестве посылок, формальный вывод называется доказательством. Функции алгебры логики. В каждой своей интерпретации формула принимает одно из двух истинностных значений — И или Л . Другими словами, формула задает функцию вида { И, Л } n { И, Л }. Определение 8. Функция вида { И, Л } n { И, Л } называется n-местной истинностной функцией или функцией алгебры логики. Определение 9. Формулы A и B называются равносильными, если во всех интерпретациях формул A и B, содержащих все атомы формул A и B, истинностные значения этих формул совпадают. Две равносильные формулы определяют одну и ту же истинностную функцию. Следовательно, истинностные функции можно рассматривать как характеристики классов равносильных формул. Число n-местных истинностных функций равно . Обозначим истинностную функцию как f(a 1 , ..., a n ), где а 1 , ..., а n — атомы. Определение 10. Дизъюнкция, составленная из элементарных конъюнкций, называется совершенной дизъюнктивной нормальной формой (СДНФ). Определение 11. Конъюнкция, составленная из элементарных дизъюнкций, называется совершенной конъюнктивной нормальной формой (СКНФ). Определение 12. Всякая истинностная функция, не равная тождественно Л, может быть представлена в СДНФ. Всякая истинностная функция, не равная тождественно И, может быть представлена в СКНФ. Из определения 12 следует, что истинность или ложность функции алгебры логики можно выводить с помощью СКНФ и СДНФ. Известно, что класс общезначимых (тождественно истинных) формул алгебры логики совпадает с классом доказуемых формул теории L. Поэтому можно доказательства в теории L проводить средствами алгебры логики и наоборот. Вероятностная логика. Определение 13. Множество М, на котором определены две двуместные операции ( ) и ( ) и одна одноместная операция и выделены два элемента 0 и , причем для этих операций и элементов выполняются аксиомы (а1)—(а15), называется регулярной булевой алгеброй. Аксиомы: