5 10 11 12

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, а ее можно из конъюнкции исключить.
После рассмотренных процедур мы получим СКНФ А.