1. Алгебра высказываний Аксёнов Сергей Владимирович к.т.н., доцент каф.ОСУ ТПУ Национальный исследовательский Томский политехнический университет Логика и теория алгоритмов

Литература к курсу 1. Аляев Ю. А., Тюрин С. Ф. Дискретная математика и математическая логика – М.: Финансы и статистика, – 368 с. 2. Игошин В. И. Математическая логика и теория алгоритмов : учебное пособие для студ. высш. учеб. заведений – 2- е изд., стер. – М.: Академия, – 448 с. 3. Мендельсон Э. Введение в математическую логику. – М.: Наука, – 320 с. 4. Новиков П. С. Элементы математической логики – М.: Наука, – 400 с. 5. Соболева Т. С., Чечкин А. В. Дискретная математика : учебник для студ. ВУЗов ; под ред. Чечкина А. В. – М.: Академия, – 256 с. 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В.

Темы лекции 1. Высказывания и операции над ними 2. Формулы алгебры высказываний 3. Тавтологии алгебры высказываний 4. Логическая равносильность формул 5. Нормальные формы для формул алгебры высказываний 6. Логическое следование формул 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В.

Понятие высказывания Опр. Высказывание – предложение, о котором можно судить истинно оно или ложно. Высказывание не может быть одновременно истинным и ложным. Конкретные высказывания обозначаются заглавными буквами латинского алфавита, или тем же буквами с индексами внизу. 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В.

Примеры высказываний A 1 : Слоны умеют летать A 2 : Воздух – это смесь газов A 3 : 27>104 B 1 : Подосиновик – ядовитый гриб B 2 : Человек не может жить без сердца C 1 : Париж – столица Франции C 2 : Все дети любят шоколад 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В.

Функция истинности 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. λ– Функция истинности, Значение λ(P) – логическое значение, или значение истинности. Для истинных высказываний используются обозначения: 1, И, T Для ложных высказываний используются обозначения: 0, Л, F

Отрицание высказывания 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Опр. Отрицанием высказывания P называется новое высказывание, обозначаемое ¬P, которое истинно, если высказывание Р ложно, и ложно, если высказывание Р истинно. Таблица истинности операции отрицания P¬P¬P 01 10

Конъюнкция двух высказываний 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Опр. Конъюнкцией двух высказываний P и Q называется новое высказывание, обозначаемое P Q (или P&Q), которое истинно лишь в единственном случае, когда истинны оба исходных высказывания P и Q и ложно во всех остальных случаях. Таблица истинности операции конъюнкции PQ P Q

Дизъюнкция двух высказываний 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Опр. Дизъюнкцией двух высказываний P и Q называется новое высказывание, обозначаемое P Q, которое ложно лишь в единственном случае, когда ложны оба исходных высказывания P и Q и истинно во всех остальных случаях. Таблица истинности операции дизъюнкции PQ P Q

Импликация двух высказываний 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Опр. Импликация двух высказываний P и Q – есть новое высказывание, обозначаемое P Q, которое ложно в единственном случае, когда высказывание P – истинно, а высказывание Q – ложно, а во всех остальных случаях – истинно. Таблица истинности операции импликации PQP Q

Эквивалентность двух высказываний 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Опр. Эквивалентностью двух высказываний P и Q называется новое высказывание, обозначаемое PQ, которое истинно в том и только том случае, когда оба операнда P и Q имеют одинаковое логическое значение, а во всех остальных случаях – ложно. Таблица истинности операции эквивалентности PQP Q

Понятие формулы алгебры высказываний 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Опр. Пропозиционная переменная – это переменная, вместо которой можно подставлять высказывание. Опр. Формула алгебры высказываний 1. Каждая отдельная пропозициональная переменная есть формула алгебры высказываний. 2. Если F 1 и F 2 – есть формулы алгебры высказываний, то выражения ¬F 1, (F 1 F 2 ), (F 1 F 2 ), (F 1 F 2 ), (F 1 F 2 ) также являются формулами алгебры высказываний. 3. Никаких других формул алгебры высказываний, кроме получившихся согласно п.1 и 2. нет

Примеры 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Формулы алгебры высказываний 1.(X Y) 2.((X Y) (Y Z)) 3.((¬Y Z) ¬X) 4.((¬ X Y) ((¬ Z ¬Y) (XZ))) Не являются формулами алгебры высказываний 1.(XZ) 2.(Z Y ¬) 3.((¬Y ) X)

Логическое значение составного высказывания 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Если в формулу алгебры высказываний F(X 1, X 2, …, X n ) вместо пропозиционных переменных X 1, X 2, …, X n подставить конкретные высказывания A 1, A 2, …, A n соответственно, то получится некоторое новое составное высказывание F(A 1, A 2, …, A n ). Это высказывание называется конкретизацией формулы F(X 1, X 2, …, X n ) на наборе высказываний A 1, A 2, …, A n. Т. Логическое значение составного высказывания F(A 1, A 2, …, A n ) равно значению формулы F(X 1, X 2, …, X n ) на наборе λ(A 1 ), λ(A 2 ), …, λ(A n ) логических значений составляющих высказываний A 1, A 2, …, A n, т.е. λ(F(A 1, A 2, …, A n ) )=F(λ(A 1 ), λ( A 2 ), …, λ( A n ) )

Составление таблиц истинности для формул 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Пример Составить таблицу истинности для формулы (XZ) (Y ¬ Z) λ (X)λ (Y)λ (Z)λ (¬ Z) λ (Y ¬ Z) λ (X Z) λ ((X Z) (Y ¬ Z)

Классификация формул алгебры высказываний 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Опр. Формула алгебры высказываний F(X 1, X 2, …, X n ) называется выполнимой, если некоторая её конкретизация является истинным высказыванием. Опр. Формула алгебры высказываний F(X 1, X 2, …, X n ) называется опровержимой, если некоторая её конкретизация является ложным высказыванием. Опр. Формула алгебры высказываний F(X 1, X 2, …, X n ) называется тавтологией, или тождественно истинной, если все возможные её конкретизации являются истинными. Опр. Формула алгебры высказываний F(X 1, X 2, …, X n ) называется противоречием, или тождественно ложными, если все возможные её конкретизации являются ложными.

Основные тавтологии Ч.1 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. 1. Закон исключённого третьего: P ¬P 2. Закон отрицания противоречия: ¬(P ¬P) 3. Закон двойного отрицания: ¬ ¬P P 4. Закон тождества: P P 5. Закон контрапозиции: (P Q) (¬Q ¬P) 6. Закон силлогизма (правило цепного заключения): ((P Q) (Q R)) (P R) 7. Закон противоположности: (P Q) (¬P ¬Q) 8. Правило добавления антецедента («истина из чего угодно»): P (Q P) 9. Правило «из ложного что угодно»: ¬P (P Q)

Основные тавтологии Ч.2 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. 10. Правило «modus ponens»: (P (P Q)) Q 11. Привило «modus tollens»: ((P Q) ¬Q) ¬P 12. Правило перестановки посылок: (P (Q R)) (Q (P R)) 13. Правило объединения (и разъединения) посылок: (P (Q R)) ((P Q) R) 14. Правило разбора случаев: ((P R) (Q R)) ((P Q) R) 15. Правило приведения к абсурду: ((¬P Q) (¬P ¬Q)) P, (¬P (Q ¬Q)) P

Свойства конъюнкции и дизъюнкции 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Следующие формулы алгебры высказываний являются тавтологиями: 1. Законы идемпотентности: (P P) P, (P P) P 2. Законы упрощения: (P Q) P, P (P Q) 3. Законы коммутативности: (P Q) (Q P), (P Q) (Q P) 4. Законы ассоциативности: (P (Q R)) ((P Q) R), (P (Q R)) ((P Q) R) 5. Законы дистрибутивности: (P (Q R)) ((P Q) (P R)), (P (Q R)) ((P Q) (P R)) 6. Законы поглощения: (P (P Q)) P, P (P Q) P 7. Законы де Моргана: ¬(P Q) (¬P ¬Q), ¬(P Q) (¬P ¬Q)

Свойства импликации и эквивалентности Ч.1 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Следующие формулы алгебры высказываний являются тавтологиями: 1.(P (Q R)) ((P Q) (P R)) 2. P (Q (P Q)) 3.(P R) ((Q R) ((P Q) R)) 4.(P Q) ((P ¬Q ) ¬P) 5.(¬Q (P Q)) ¬P 6.(¬P (P Q)) Q 7.(P Q) ((P R) (Q R)) 8.(P Q) ((P R) (Q R)) 9.(P Q) ((Q R) (P R))

Свойства импликации и эквивалентности Ч.2 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Следующие формулы алгебры высказываний являются тавтологиями: 10.(P Q) (Q P) 11.(¬Q ¬P) ((¬Q P) Q) 12.((P Q) (R Q)) ((P R) Q) 13.((P Q) (P R)) (P (Q R)) 14. P P 15.(P Q) (Q P) 16.((P Q) (Q R)) (P R)

Выражение одних логических операций через другие 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Следующие формулы алгебры высказываний являются тавтологиями: 1.(P Q) ((P Q) (Q P)) 2.(P Q) (¬P Q) 3. (P Q) ¬(P ¬Q) 4.(P Q) ¬(¬P ¬Q) 5.(P Q) ¬(P ¬Q) 6.(P Q) ¬(¬P ¬Q) 7.(P Q) (¬P Q)

Основные правила получения тавтологий 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Т. (правило заключения) Если формулы F и F H являются тавтологиями, то формула H также тавтология. F, F H H Т. (правило подстановки) Если формула F, содержащая пропозиционную переменную X, является тавтологией, то подстановка в формулу F вместо переменной X любой формулы H снова приводит к тавтологии. F(X),F - формула, полученная из Fв результате подстановки в неё формулы H вместо пропозиционной переменной X.

Понятие равносильности формул 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Опр. Формулы F(X 1, X 2, …, X n ), H(X 1, X 2, …, X m ) алгебры высказываний называются равносильными (эквивалентными), если при любых значениях входящих в них пропозиционных переменных логические значения получающиеся из формул F и H высказываний совпадают. F H λ(F(A 1, A 2, …, A n )) = λ(H(A 1, A 2, …, A n )), где A i – любые конкретные высказывания. Примеры P ¬P Q ¬Q ¬Q (¬P Q) ¬ P ((P Q) (P R)) (P (Q R))

Признак равносильности формул 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Т. (признак равносильности формул) Две формулы F и H алгебры высказываний равносильны тогда и только тогда, когда формула F H является тавтологией F H Сл. Отношение равносильности между формулами алгебры высказываний: 1.Рефлексивно: F F 2.Симметрично: если F 1 F 2, то F 2 F 1 3.Транзитивно: если F 1 F 2 и F 2 F 3, то F 1 F 3

Равносильные преобразования формул 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Лемма (о замене) Если G(Y 1, Y 2, …, Y n ) H( Y 1, Y 2, …, Y m ), то для любой формулы алгебры высказываний F(X 1, X 2, …, Y, …, X n ) имеет место равносильность F(F(X 1, X 2, …, G(Y 1, Y 2, …, Y n ), …, X n ) F( X 1, X 2,…, H( Y 1, Y 2, …, Y m ), …, X m ). Опр. Переход от одной формулы к равносильной её формуле называется равносильным преобразованием формулы. Замечание Если некоторая формула алгебры высказываний является тавтологией, то всякая равносильная её формула также является тавтологией: F, F H H

Примеры равносильного преобразования 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Задача Упростить формулу ((P Q) (Q P)) (P Q). ((P Q) (Q P)) (P Q) ( (¬P Q) (¬Q P)) (P Q) (¬P Q) ((¬Q P) (P Q)) (¬P Q) (P (¬Q Q)) (¬P Q) P ( ¬P P ) (Q P ) Q P Задача С помощью равносильных преобразований докажите, что формула ((P Q) P) ¬P является тождественно ложной. ((P Q) P) ¬P ((¬P Q) P) ¬P (¬(¬P Q) P) ¬P ((P ¬Q) P) ¬P P ¬P 0 ((P Q) P) ¬P

Понятие нормальных форм 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Опр. Конъюнктивным одночленом от переменных X 1, X 2, …, X n называется конъюнкция этих переменных или их отрицаний. Пример X 1 ¬X 2 X 3, ¬X 1 ¬X 2, ¬X 1 X 2 X 3 ¬X 4 Опр. Дизъюнктивным одночленом одночленом от переменных X 1, X 2, …, X n называется дизъюнкция этих переменных или их отрицаний. Пример X 1 ¬X 2 X 3 ¬X 4, ¬X 1 ¬X 2, X 1 X 2 ¬X 3 Опр. Конъюнктивной нормальной формой (КНФ) называется конъюнкция дизъюнктивных одночленов. Пример (X 1 ¬X 2 ) (¬X 1 ¬X 3 ¬X 4 ) (¬X 1 X 3 ) Опр. Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция конъюнктивных одночленов. Пример(¬X 1 ¬X 2 ) (¬X 1 X 4 ) (X 1 ¬X 2 ¬X 3 )

Совершенные нормальные формы 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Опр. Одночлен (конъюнктивный или дизъюнктивный) от переменных X 1, X 2, …, X n называется совершенным, если от него от каждой пары X i, ¬X i входит только один представитель. Опр. Нормальная форма (конъюнктивный или дизъюнктивный) от переменных X 1, X 2, …, X n называется совершенной от этих переменных, если в неё входят лишь совершенные одночлены (дизъюнктивные или конъюнктивные соответственно) от X 1, X 2, …, X n. Пример СКНФ (¬X 1 ¬X 2 ¬X 3 ¬X 4 ) ( ¬X 1 X 2 X 3 X 4 ) ( ¬X 1 ¬X 2 X 3 ¬X 4 ) Пример СДНФ ( X 1 ¬X 2 ¬X 3 ) ( X 1 ¬X 2 X 3 ) ( X 1 X 2 ¬X 3 ) ( X 1 X 2 X 3 )

Представление формул алгебры высказываний СДНФ 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Т. (о представлении формул алгебры высказываний совершенными дизъюнктивными нормальными формулами) Каждая не тождественно ложная формула алгебры высказываний от n аргументов имеет единственную ( с точностью до перестановки конъюнктивных членов) СДНФ. Алгоритм нахождения СДНФ Необходимо выбрать все те наборы значений её переменных, на которых формула принимает значение 1; для каждого такого набора выписать совершенный конъюнктивный одночлен, принимающий значение 1 на этом наборе и только на нём; полученные совершенные конъюнктивные одночлены соединить знаками дизъюнкции.

Пример нахождения СДНФ 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Задача Для формулы (X ¬(Y Z)) (X Z) найти СДНФ Таблица истинности для данной формулы XYZ Y Z¬(Y Z)) X ¬(Y Z)X Z(X ¬(Y Z)) (X Z) Результат СДНФ: (X ¬Y ¬Z) (X ¬Y Z) (X Y ¬Z) (X Y Z)

Пример нахождения СДНФ 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Задача Для формулы (X ¬(Y Z)) (X Z) найти СДНФ (X ¬(Y Z)) (X Z) (X ¬(¬Y Z)) (X Z) (X (Y ¬Z)) (X Z) (X Y) (X ¬Z ) (X Z) (X X X ) (X X Z ) (X ¬Z X ) (X ¬Z Z ) (Y X X ) (Y X Z ) (Y ¬Z X ) (Y ¬Z Z ) X (X Z ) (X ¬Z ) (X Y) (X Y Z ) (X Y ¬Z ) (X 1 1) (X Z 1) (X ¬Z 1) (X Y 1) (X Y Z ) (X Y ¬Z ) (X Y Z) (X Y ¬ Z) (X ¬ Y Z) (X ¬ Y ¬ Z) (X Y Z ) (X ¬ Y Z ) (X ¬Z Y) (X ¬Z ¬ Y) (X Y Z) (X Y ¬ Z) (X Y Z ) (X Y ¬Z ) (X Y Z ) (X Y ¬Z ) (X ¬ Y Z) (X ¬ Y ¬ Z).

Представление формул алгебры высказываний СКНФ 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Т. (о представлении формул алгебры высказываний совершенными конъюнктивными нормальными формулами) Каждая формула алгебры высказываний от n аргументов, не являющаяся тавтологией, имеет единственную ( с точностью до перестановки конъюнктивных членов) СКНФ. Алгоритм нахождения СДНФ Необходимо выбрать все те наборы значений её переменных, на которых формула принимает значение 0; для каждого такого набора выписать совершенный дизъюнктивный одночлен, принимающий значение 0 на этом наборе и только на нём; полученные совершенные дизъюнктивные одночлены соединить знаками конъюнкции.

Пример нахождения СКНФ 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Задача Для формулы ((X Y) Z) ¬X найти СКНФ Таблица истинности для данной формулы XYZ X Y (X Y) Z ¬X ((X Y) Z) ¬X Результат СКНФ: (X ¬Y Z) (¬X Y ¬Z) (¬X ¬Y ¬Z)

Пример нахождения СКНФ 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Задача Для формулы ((X Y) Z) ¬X найти СДНФ ((X Y) Z) ¬X (¬(X Y) Z) ¬X ( (¬(X Y) Z) ¬X ) (¬X (¬(X Y) Z))) ( ¬(¬(X Y) Z) ¬X ) (X (¬(X Y) Z))) ((( X ¬Z) (Y ¬Z ) ¬X ) ( X Z (¬X ¬Y)) (X ¬Z X) (X ¬Z Z) (X ¬Z ¬X ¬Y) (Y ¬Z X) (Y ¬Z Z) (Y ¬Z ¬X ¬Y) (¬X X) (¬X Z) (¬X ¬X ¬Y) (X ¬Z) (Y ¬Z X) (¬X Z) (¬X ¬Y) (X ¬Z) (¬X Z) (¬X ¬Y) (X ¬X ¬X ) (X ¬X ¬Y) (X Z ¬X) (X Z ¬Y) ( ¬Z ¬X ¬X ) (¬Z ¬X ¬Y) (¬Z Z ¬X) (¬Z Z ¬Y) (X Z ¬Y) ( ¬Z ¬X 0 ) (¬Z ¬X ¬Y) (X Z ¬Y) ( ¬Z ¬X Y ) ( ¬Z ¬X ¬Y ) (¬Z ¬X ¬Y) (X ¬Y Z) ( ¬X Y ¬Z ) (¬X ¬Y ¬Z).

Понятие логического следствия 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Опр. Формула H(X 1, X 2, …, X n ) называется логическим следствием формул F 1 (X 1, X 2, …, X n ), …, F m (X 1, X 2, …, X n ) если формула H(X 1, X 2, …, X n ) превращается в истинное высказывание при всякой такой подстановке вместо всех её пропозиционных переменных X 1, X 2, …, X n конкретных высказываний, при которых в истинное высказывание превращаются все формулы F 1 (X 1, X 2, …, X n ), …, F m (X 1, X 2, …, X n ). F 1, …, F m H Формулы F 1 (X 1, X 2, …, X n ), …, F m (X 1, X 2, …, X n ) называются посылками.

Пример логического следствия 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Задача Определить справедливо ли следующее логическое следование: 1) P R, ¬R ¬Q R. Таблица истинности PQR P Q ¬R ¬Q¬R ¬Q Вывод Логическое следование P R, ¬R ¬Q R справедливо

Признаки и свойства логического следствия 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Т. (признак логического следствия) Формула H будет логическим следствием формулы F тогда и только тогда, когда формула FH является тавтологией: F H F H. Т. Для любых формул F 1, F 2, …, F m, H (m 2 ) следующие утверждения равносильны: 1. F 1, F 2, …, F m H ; 2. F 1 F 2 … F m H; 3. ( F 1 F 2 … F m ) H T. Отношение логического следования между формулами алгебры высказываний обладает следующими свойствами: 1) F 1, F 2, …, F m F i i =1,2,…,m; 2) Если F 1, F 2, …, F m G j для j =1,2,…,p и G 1, G 2, …, G p H, то F 1, F 2, …, F m H.

Следование и равносильность формул 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. T. Две формулы алгебры высказываний равносильны тогда и только тогда, когда каждая из них является логическим следствием другой: F H F H, H F Замечание Если некоторая формула является тавтологией, то и всякое её логическое следствие также является тавтологией: F, F H H

Правила логических умозаключений Ч.1 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Правило modus ponens Правило modus tollens Правило введения конъюнкции Правило удаления конъюнкции Правило введения дизъюнкции Контрапозиции

Правила логических умозаключений Ч.2 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Правило цепного заключения Правило перестановки посылок Правило объединения и разъединения посылок Правило расширенной контрапозиции

Нахождение следствий из данных посылок 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Т. Формула H(X 1, X 2, …, X n ), не являющаяся тавтологией, тогда и только тогда будет логическим следствием формул F 1 (X 1, X 2, …, X n ), …, F m (X 1, X 2, …, X n ), не все из которых являются тавтологиями, когда все совершенные дизъюнктивные одночлены из разложения формулы H в СКНФ входят в СКНФ формулы F 1 (X 1, X 2, …, X n ) … F m (X 1, X 2, …, X n ). Алгоритм для нахождения всех (неравносильных)формул, являющимися следствиями из посылок F 1, …, F m. 1. Составить конъюнкцию F 1 … F m. 2. Найти СКНФ формулы F 1 … F m. 3. Выписать все совершенные дизъюнктивные одночлены найденной СКНФ, а также всевозможные конъюнкции этих одночленов. Полученное множество формул – искомое.

Пример: Нахождение следствий из данных посылок 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Задача Найти все неравносильные формулы, являющиеся следствиями из посылок (P Q)R, ¬R. Решение СКНФ для формулы ((PQ)R) (¬R) имеет вид (P Q R) (P ¬Q R) (P ¬Q ¬R) (¬P ¬Q R). Набор всех неравносильных формул, являющихся следствиями: (P Q R), (P ¬Q R), (P ¬Q ¬R), (¬P ¬Q R), (P Q R) (P ¬Q R), (P Q R) (P ¬Q ¬R), (P Q R) (¬P ¬Q R), (P ¬Q R) (P ¬Q ¬R), (P ¬Q R) (¬P ¬Q R), (P ¬Q ¬R) (¬P ¬Q R), (P Q R) (P ¬Q R) (P ¬Q ¬R), (P Q R) (P ¬Q ¬R) (¬P ¬Q R), (P ¬Q R) (P ¬Q ¬R) (¬P ¬Q R).

Нахождение посылок для данного следствия 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Т. Чтобы найти все формулы, логическим следствием каждой из которых будет данная формула G(X 1, X 2, …, X n ) необходимо действовать согласно следующему алгоритму. Найти СКНФ для формулы G(X 1, X 2, …, X n ); выявить все совершенные дизъюнктивные одночлены, которые в ней отсутствуют; составить всевозможные конъюнкции формулы G(X 1, X 2, …, X n ) с недостающими дизъюнктивными одночленами. Получившаяся совокупность формул (вместе с формулой G) будет искомой (с точностью до равносильности формул).

Пример: Нахождение посылок для данного следствия 1. Алгебра высказываний. Логика и теория алгоритмов, Аксёнов С.В. Задача Найти все не равносильные между собой и не тождественно ложные формулы алгебры высказываний, зависящие от переменных Х и Y, для которых формула X Y является логическим следствием. Решение Для формулы X Y СКНФ имеет вид (¬X Y) (¬Y X). Недостающие одночлены (X Y) и (¬Y ¬X). Поэтому искомыми посылками являются следующие формулы (X Y) (X Y), (X Y) (¬Y ¬X), (X Y) (X Y) (¬Y ¬X). После упрощения (X Y) (X Y) X Y, (X Y) (¬Y ¬X) ¬X ¬Y, (X Y) (X Y) (¬Y ¬X) 0. Результат: X Y, X Y, ¬X ¬Y.