46. Нормальні форми: досконала кон’юнктивна нормальна форма (дкнф)

Досконалою кон’юнктивною нормальною формою (ДКНФ) булевої функції називається кон’юнкція тих конституент нуля, які перетворюються в нуль на тих самих наборах змінних, що й задана функція. Також по аналогії з ДДНФ, будь-яка булева функція має одну ДКНФ (кількість її членів дорівнює кількості нульових значень функції) і декілька КНФ.

Означення: добуток конституент нуля, які дорівнюють нулю на тих самих наборах, що і задана функція, називається досконалою кон’юктивною нормальною формою.

Будь-яка логічна функція має єдину досконалу кон’юктивну нормальну форму.

Можна навести такі властивості ДКНФ, що виділяють її з усіх КНФ:

в ній немає однакових співмножників;

жоден із співмножників не містить двох однакових доданків;

жоден із співмножників не містить якої-небудь змінної разом з її запереченням;

в кожному окремому співмножнику є як складова або змінна xi, або її заперечення для будь-якого i=1,2,…,n.

Якщо задано, що логічна функція дорівнює одиниці на більшості наборів аргументів, то подання функції в ДДНФ – громіздке. В таких випадках зручніше використовувати досконалу кон’юктивну нормальну форму.

В алгебрі логіки конституентою нуля називають логічну функцію n аргументів, яка набуває значення, що дорівнює нулю, лише на одному наборі.

Оскільки наборів аргументів 2n, то і конституент нуля - 2n.

Конституенти нуля можна виразити у вигляді диз’юнкцій всіх аргументів, частина з яких береться з запереченнями.

Заперечення ставляться так, щоб обернути в нуль диз’юнкцію в потрібному наборі.

47. Нормальні форми як визначаючий метод.

Нормальна форма - це така форма чого-небудь, що не допускає подальших спрощень. Не варто плутати з поняттям канонічна форма.

Говорят, что формула логики предикатов имеет нормальную форму, если она содержит только операции конъюнкции, дизъюнкции и кванторные операции, а операция отнесена к элементарным формулам.

Очевидно, что, используя равносильности алгебры высказываний и логики предикатов, каждую формулу логики предикатов можно привести к нормальной формуле.

48. Умовно - категоричні виводи.

Умовно-категоричний умовивід - це вивід, в якому один Ь засновків - умовне судження, а інший - категоричне судження. Наприклад:

Якщо фотоплівку засвітити (А), то вона вийде з ладу (В). Цю фотоплівку засвічено (А).

Ця фотоплівка вийшла з ладу (В). Структура цього виводу: Якщо А, то В.

А._

В.

Як бачимо, формула логіки висловлювань, що відображає дану структуру виводу, є завжди істинною або законом логіки. Цю структуру виводу називають стверджувальним модусом (modus ponens) умовно-категоричного умовиводу, оскільки в ній від ствердження підстави (А) переходять до ствердження наслідку (В). Можна будувати достовірні умовиводи від ствердження підстави до ствердження наслідку. При цьому засновки повинні бути істинними.

с) Заперечний модус. Побудуємо наше розмірковування таким чином:

Якщо фотоплівку засвітити (А), то вона вийде з ладу (В).

Ця фотоплівка не вийшла з ладу (~В).

Цю фотоплівку не було засвічено (^А).

Структура цього міркування є такою:

Якщо А, то В.

Не В._

Не А.

Йому відповідає формула логіки висловлювань: ((А —" В) Л~В) —> ~А. Ця формула є законом логіки або завжди істинною формулою. Цей різновид умовно-категоричного умовиводу називають заперечним модусом (modus tollem). Він встановлює, що можна будувати достовірні умовиводи від заперечення наслідку до заперечення підстави. Не слід забувати, що засновки при цьому повинні бути істинними.

Наше міркування, нарешті, можна побудувати і таким чином:

Якщо фотоплівку засвітити (А), то вона вийде з ладу (В).

Цю фотоплівку не засвічено (~А).

Ця фотоплівка не вийшла з ладу (~В).

Структура цього умовиводу є такою:

Якщо А, то В.

Не А._

Не В.

Цій структурі відповідає наступна формула логіки висловлювань: ((А —> В) Л-А) —" ~В. Виходячи із міркувань здорового глузду, якщо фотоплівка не засвічена, це не завжди означає її придатність для використання. Тобто ця структура не завжди дає необхідні виводи, бо вона є неправильною. А формула, яка їй відповідає, не є законом логіки. Не можна будувати достовірні умовиводи від заперечення підстави до заперечення наслідку. Цей модус умовно-категоричного умовиводу називають імовірним.