5. Равносильные преобразования формул. Использую равносильности всех трех групп, любую формулу можно заменить на равносильную ей. Такие преобразования и называются равносильными. Используются во многих случаях: упрощение, приведение к заданному виду, доказательство. Формула А проще равносильной ей формулы В, если она содержит меньше букв и меньше логических операций. Как правило, операции эквивалентности и импликации заменяются на конъюнкции и дизъюнкции, а отрицание рассматривается как элементарное высказывание (условно). Закон двойственности. Пусть формула А содержит только операции конъюнкции, дизъюнкции и отрицания. Будем называть конъюнкция двойственной операцией дизъюнкции и наоборот. Формула А и А* называются двойственными, если они получены путем замены каждой операции на двойственную. А=(x∨y)&z A*=(x&y)∨z Для двойственных формул справедливы следующие утверждения: Если для А (х1, х2, ..., xn) двойственной является А*, то справедлива равносильность: (A (x1, x2, ..., xn) ) ̅ = A* ((x_1 ) ̅, (x_2 ) ̅, ..., (x_n ) ̅) Закон двойственности: если равносильны формулы А и В, то равносильны и двойственные им формулы. Дизъюнктивная нормальная форма (ДНФ) и совершенная дизъюнктивная нормальная форма (СДНФ). Элементарная конъюнкция l переменных - конъюнкция этих переменных или их отрицание ДНФ А - равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций. Для любой формулы путем равносильных преобразований можно получить ее ДНФ, причем она не будет единственной. А≡x&(x→y)≡x&(x ̅∨y)≡x&x ̅∨x&y≡x&y Среди ДНФ А существует единственная ДНФ, которая обладает 4 свойствами совершенства, такая ДНФ называется СДНФ. Существует два способа получения СДНФ: с помощью таблицы истинности или равносильных преобразований. Рассмотрим последний метод. Сначала получается любая ДНФ А, а дальше реализуется следующий алгоритм: Если слагаемое В в ДНФ А не содержит переменную xi, то это слагаемое заменяется на В&(x_i∨(x_i ) ̅)≡B&x_i∨B&(x_i ) ̅) Если в ДНФ А встретились два одинаковых слагаемых (B∨B), то нужно одно слагаемое убрать. Если в некотором слагаемом В переменная xi встречается дважды, то одну их них надо убрать. Если В содержит xi&(x_i ) ̅, то &=0, слагаемое В=0, а 0 из дизъюнкции можно исключить. После рассмотренных преобразований будет получена СДНФ А. Конъюнктивная нормальная форма (КНФ) и совершенная конъюнктивная нормальная форма (СКНФ). Элементарной дизъюнкцией n переменных называется дизъюнкция этих переменных или их отрицание. КНФ А - равносильная формула, представляющая собой конъюнкция элементарных дизъюнкций. Для любой формулы алгебры логики можно получить КНФ, и она не будет единственной. КНФ называется СКНФ, если выполняются следующие условия: Все элементарные дизъюнкции, входящие в КНФ А, различны. Все элементарные дизъюнкции, входящие в КНФ А, содержат все переменные. Каждая элементарная дизъюнкция, входящая в КНФ А, не содержит двух одинаковых переменных. Каждая элементарная дизъюнкция, входящая в КНФ А, не содержит переменную и ее отрицание. Можно показать, что любая тождественно истинная формула имеет единственную СКНФ. Также существует два способа получения СКНФ: построение таблицы истинности для формулы А ̅. Для формулы находится СДНФ А. СКНФ А = (СДНФ А ̅ ) ̅. Равносильные преобразования. Сначала получается любая КНФ А, а дальше реализуется алгоритм, который позволяет получить СКНФ А. Если элементарная дизъюнкция, входящая в КНФ А, не содержит некоторую переменную xi, то она добавляется. B∨(x_i&x_i) Если в некоторой элементарной дизъюнкции переменная xi входит дважды, то ее можно исключить. Если КНФ содержит две одинаковые элементарные дизъюнкции, то одну можно исключить. Если в элементарной дизъюнкцию входит переменная и ее отрицание, то дизъюнкция равна 1, а ее можно из конъюнкции исключить. После рассмотренных процедур мы получим СКНФ А.
1/--страниц