Називається елементарною диз'юнкцією

Означення 3. Пф, рівносильна даній і яка має вид

- елементарна кон'юнкція, називається диз'юнктивною нормальною формою (коротко ДНФ) даної пф.

Помітимо, що елементарні кон'юнкції в деякій ДНФ можуть бути і рівними.

Із означення 3 і рівносильності (6) маємо, що ДДНФ пф ^{А( X} 1, ^X2,•••, ^Xn ⁾,

яка містить рівно п різних змінних ^X1,^X2… ^Xn, є її ДНФ, у якій:

1) всі елементарні кон'юнкції попарно різні; 2) кожна елементарна кон'юнкція містить рівно п членів; 3) у кожній елементарній кон'юнкції

зустрічаються всі п змінних ^X 1, ^X2,•••, ^Xn («у деяких степенях»).

Теорема 5. Для будь-якої пф існує ДНФ даної пф.

Доведення. Нехай ^{А( X} 1, ^X2,•••, ^Xn ⁾, - довільна пф. Якщо вона є

протиріччям, то в якості її ДНФ, відповідно до рівносильності (15°), візьмемо

Якщо пф ^{А( X} 1, ^X2,•••, ^Xn ⁾,не є протиріччям і містить хоча б одну змінну, то в якості ДНФ візьмемо її ДДНФ; в іншому випадку ця пф -

тавтологія і за ДНФ візьмемо пф Теорему доведено.

Намітимо ще одне доведення теореми 5. Дану пф за рівносильностями (25°) і (21°), застосовуючи їх необхідне число раз, можна перетворити в їй рівносильну, яка не містить символів ^ і якщо вони у ній були. Потім, застосовуючи необхідне число раз рівносильності (1°), (7°), (9°) - (12°), одержуємо ДНФ даної пф.

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

не містить змінної ^Хп, то наступні рівносильні перетворення:

дають дві елементарні кон’юнкції, кожна з яких містить «відсутню» змінну

^Хп. Отже, застосовуючи це перетворення необхідне число раз, із такої ДНФ можна одержати ДДНФ.

Очевидно, що для даної пф її ДНФ не єдина, а для пф, що не є протиріччям і яка містить змінні, її ДДНФ єдина з точністю до перестановки диз'юнктивних членів.

Означення 4. Пф, рівносильна даній і яка має вид

де - елементарна диз'юнкція, називається кон'юнктивною нормальною формою (коротко КНФ) даної пф.

Помітимо, що деяка КНФ може містити рівні елементарні диз'юнкції.

Із означення 4 і рівносильності (11°) маємо, що ДКНФ пф ^{А( X} 1, ^X2,•••, ^Xn ⁾,

яка містить рівно п різних змінних ^Хі,^Х2 … ^Хп, є її КНФ, у якій:

і) всі елементарні диз'юнкції попарно різні; 2) кожна елементарна диз'юнкція містить рівно п членів; з) у кожній елементарній диз'юнкції

зустрічаються всі п змінних ^Х1, ^Х2… ^Хп («у деяких степенях»).

Теорема 6. Для будь-якої пф існує КНФ даної пф.

Доведення. Нехай ^{А( X} 1, ^X2,•••, ^Xn ⁾, - довільна пф. Якщо вона є

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

візьмемо пф . Теорему доведено.

Намітимо ще одне доведення теореми 6. Дану пф за рівносильностями (21°) і (25°), застосовуючи їх необхідне число раз, перетворимо в їй рівносильну, яка не містить символів . Потім, застосовуючи необхідне число раз рівносильності (1°), (8°) - (12°), одержуємо її КНФ.

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

Але якщо, наприклад, елементарна диз'юнкція не містить змінної ^Хп, то наступні рівносильні перетворення

дають дві елементарні диз'юнкції, кожна з яких містить «відсутню» змінну

^Xn. Отже, застосовуючи це перетворення необхідне число раз, із такої КНФ можна одержати ДКНФ.

Для даної пф її КНФ не єдина, а для пф яка містить змінні і не є тавтологією, її ДКНФ єдина з точністю до перестановки кон'юнктивних членів.

Закон двоїстості

У даному розділі будемо розглядати пф у мові На множині таких пф введемо бінарне відношення двоїстості і покажемо, як за допомогою нього можна доводити рівносильність пф.

Означення. Пф А * називається двоїстою для пф А, якщо А* утворена із А заміною в ній всюди л на .

Помітимо, що Легко зрозуміти, що відношення двоїстості симетричне.

Доведемо кілька тверджень.

Твердження (1) безпосередньо слідує з рівносильностей (9°), (10°). Для

доведення твердження (2) помітимо, що тоді і тільки тоді,

коли . Звідси, використовуючи твердження (1), одержуємо твердження (2).

Закон двоїстості доведено.

За рівносильністю (8°) . Звідси за законом двоїстості . І взагалі, якщо А, В і С - пф розглянутого виду, то з рівносильності за законом двоїстості одержуємо

22. Логічне слідування в логіці предикатів. Метод резолюції

Означення. Формула β логічно слідує з формули а, якщо в будь-якій інтерпретації формула β набуває значення істинності 1 при кожному заміщенні всіх вільних входжень предметних змінних елементами множини В(елементами області інтерпретації), при якому формула а набуває значення 1. Символічно відношення логічного слідування записують, як і в логіці висловлень, α \=β (а називають посилкою або припущенням, β - логічним наслідком або висновком).

Якщо формули не містять вільних входжень предметних змінних, то визначення спрощуються: формула β логічно слідує з формули а тоді і тільки тоді, коли при кожній інтерпретації формула β набуває значення 1 кожного разу, коли формула а набуває це ж значення.

Очевидно, для логічного слідування мають місце такі властивості:

1) якщо Г - множина формул логіки предикатів і а є Г, то

Г \= а;

2) якщо Г - множина формул логіки предикатів, Г |= а і а |= то Г |= (транзитивність/

У логіці предикатів як і в логіці висловлень між відношенням логічного слідування і операцією імплікації існує співвідношення: логічне слідування а_1, а₂, а_т \= має місце тоді і тільки тоді, коли а1^а₂ ^...^ а_т —> - загальнозначуща формула. Останнє твердження дозволяє звести проблему логічного слідування до перевірки певної формули логіки предикатів на тотожну істинність і навпаки, доведення тотожної істинності до доведення логічного слідування.

Формула загальнозначуща тоді і тільки тоді, коли вона логічно слідує з порожньої множини.

Неважко переконатися в справедливості і таких тверджень:

1) дві формули логіки предикатів рівносильні тоді і тільки тоді, коли кожна з них є логічним наслідком іншої;

2) якщо формула є логічним наслідком множини формул Г, які істинні в даній інтерпретації, то в цій інтерпретації істинна і формула .

Логічне слідування - важливий компонент правильних міркувань. Міркування правильне тоді і тільки тоді, коли між посилками і висновком цього міркування має місце відношення логічного слідування.

Встановлення логічного слідування Г |= користуючись означенням, навіть у простіших випадках (якщо формули замкнені) вимагає виявлення всіх моделей для Г, що практично нездійсненне. На щастя, на практиці для встановлення відношення Г |= не вимагається досліджувати різні інтерпретації, оскільки існують значно простіші методи, які ґрунтуються на логічному виводі. Важливість логіки предикатів саме в тому, що вона надає засоби, які забезпечують автоматичне виконання цієї процедури.

Проблема формалізації семантичного поняття логічного слідування зводиться до питання про те, що якщо формула логічно слідує з множини формул Г, то в цьому численні можна побудувати вивід з посилок Г, і навпаки, якщо існує вивід з посилок Г, то з Г логічно слідує . Для логіки предикатів першого порядку це питання розв'язується позитивно. Тут лише коротко зупинимось на питаннях формалізації логічного слідування, оскільки в логіці висловлень ці питання вже розглядалися.