«Математическая логика Учебное пособие Издание второе, исправленное и дополненное Рекомендовано Ученым советом университета в качестве учебного пособия по дисциплине Математическая логика и теория алгоритмов для ...»

Пономарев В.Ф.

Математическая логика

Учебное пособие

Издание второе, исправленное и дополненное

Рекомендовано Ученым советом университета

в качестве учебного пособия по дисциплине

«Математическая логика и теория алгоритмов» для студентов, обучающихся по направлению552800 – «Информатика и вычислительная техника» и по специальности 654600 –

«Информатика и вычислительная техника».

Калининград 2005 ББК 60 УДК 53:630.11 Пономарев В.Ф. Математическая логика. Учебное пособие. – 2-е изд., испр. т доп. – Калиниград: изд-во КГТУ, 2005г., 201с.

В разделе «Классическая логика» дано описание логики высказываний и предикатов. Исследованы возможности вывода дедуктивным методом и методом резолюции. Каждый пример сопровождается графом вывода. Для многих примеров составлены и отлажены программы на языке Prolog. В этом разделе приведены также основы реляционных алгебры и исчисления с переменными-кортежами.

Приведены основы языка SQL и его инструкции для исполнения алгебраических и логических операций.

В разделе «Неклассическая логика» изложены основы нечёткой и модальной логик. Показаны особенности исполнения нечётких алгебраических операций и нечёткого вывода в исчислении, приведены примеры экспертных систем. Рассмотрены возможности применения модальных операторов для формального описания того, что «должно быть», и того, что «может быть». Кратко дано описание темпоральной и алгоритмической логик, которые нашли широкое применение в информационных технологиях.

Оглавление Предисловие -------------------------------------------------------- Глава1. Логика классическая --------------------------------- 1.1. Логика высказываний ------------------------------------ 1.1.1. Алгебра высказываний------------------------------ 1.1.1.1. Логические операции--------------------------- 1.1.1.2. Правила записи сложных формул ----------- 1.1.1.3. Законы алгебры высказываний --------------- 1.1.1.4. Эквивалентные преобразования формул --- 1.1.1.5. Нормальные формы формул ------------------ 1.1.2. Исчисление высказываний ------------------------- 1.1.2.1. Интерпретация формул ------------------------ 1.1.2.2. Аксиомы исчисления высказываний ------- 1.1.2.3. Метод дедуктивного вывода ------------------ 1.1.2.4. Метод резолюции ------------------------------- Вопросы и задачи ---------------------------------------------- Расчетно-графическая работа ----------------------------- 1. 2. Логика предикатов -------------------------------------- 1.2.1. Алгебра предикатов --------------------------------- 1.2.1.1. Логические операции--------------------------- 1.2.1.2. Правила записи сложных формул ----------- 1.2.1.3. Законы алгебры предикатов------------------- 1.2.1.4. Эквивалентные преобразования формул --- 1.2.1.2. Предварённая нормальная форма------------ 1.2.1.3. Сколемовская стандартная форма ----------- 4 Математическая логика 1.2.2. Исчисление предикатов----------------------------- 1.2.2.1. Интерпретация формул ------------------------ 1.2.2.2. Аксиомы исчисления предикатов----------- 1.2.2.3. Правила унификации предикатов----------- 1.2.2.4. Метод дедуктивного вывода ----------------- 1.2.2.5. Метод резолюции ------------------------------ 1.2.3. Логическое программирование ------------------ 1.2.3.1. Основы логического программирования -- 1.2.3.2. Подготовка среды Visual Prolog для работы --------------------------------------------------------------- 1.2.3.3. Описание логических задач на языке Prolog --------------------------------------------------------------- Вопросы и задачи --------------------------------------------- Расчетно-графическая работа ---------------------------- 1.3. Логика реляционная ------------------------------------- 1.3.1. Реляционная алгебра ------------------------------- 1.3.1.1. Унарные операции ----------------------------- 1.3.1.2. Бинарные операции ---------------------------- 1.3.1.3. Правила реляционной алгебры -------------- 1.3.2. Реляционное исчисление -------------------------- 1.3.3. Языки реляционной логики ----------------------- Вопросы и задачи --------------------------------------------- Расчетно-графическая работа ---------------------------- Глава 2. Неклассическая логика--------------------------- 2.1. Нечёткая логика ----------------------------------------- 2.1.1. Нечёткие множества ------------------------------- 2.1.2. Нечёткая алгебра ------------------------------------ 2.1.2.1. Операции над нечёткими множествами --- 2.1.2.2. Законы нечёткой алгебры -------------------- 2.1.2.3. Свойства нечётких отношений -------------- 2.1.2. Нечёткое исчисление ------------------------------- 4.4.2. Экспертные системы ------------------------------- Вопросы и задачи --------------------------------------------- Расчетно-графическая работа ---------------------------- 2.2. Модальная логика ---------------------------------------- 2.2.1. Темпоральная (или времення) логика. -------- 2.2.2. Алгоритмическая логика -------------------------- 2.2.3. Алгоритмическая логика Хоара------------------ Ответы и решения ------------------------------------------- Литература---------------------------------------------------- Предметный указатель-------------------------------------- Логика как наука впервые упоминается в трудах греческого философа Аристотеля (384-322г. до н.э.). С тех времен эта наука учит, как надо правильно рассуждать, правильно делать умозаключения и получать верные суждения. Поэтому было признано, что логика должна содержать счетное и конечное множество правил рассуждения для вывода новых, но верных высказываний. Основное правило, установленное еще в трудах Аристотеля утверждает, что «из двух известных и правильных суждений можно получить новое и верное суждение» [15]. Это правило получило название силлогизм *.

Без серьезных изменений эта наука просуществовала более двадцати столетий. Традиционную логику стали подвергать критике лишь в конце XVII века, когда немецкий математик Г. Лейбниц (1646-1716) впервые ввел в логику математические символы и некоторые математические правила. Это позволило заменить некоторые выводы вычислениями. Дальнейшее развитие в логику внесли английский математик Д. Буль (1815-1864), американский математик Пост, немецкие математики Г. Фреге (1848и Д. Гильберт (1862-1943), итальянский математик Д. Пеано (1858-1932) и многие другие. Так возникла математическая логика как формальная система, носителем когр. syllogismos – умозаключение, состоящее из двух суждений (посылок), из которых следует третье суждение (вывод), торой явились символы и последовательности символов, а правила математики позволили дать точное и удобное определение математического суждения **.

Применение символов в логике позволило представить суждения философов в компактной и удобной форме, а применение правил математики - дать простые алгоритмы вывода суждений. Центральным понятием, введенным математикой, явилось доказательство – «из положенного с необходимостью вытекает нечто, отличное от положенного» [15].

Во второй половине XX века резко возрос интерес к математической логике. При решении любой задачи нужно, прежде всего, перевести ее смысл и содержание с естественного языка на язык математической логики, с языка математической логики на язык алгоритмов, с языка алгоритмов на язык программирования, а затем применить компьютер для вывода заключения. «Во множестве формальных языков программирования, математической лингвистики и искусственного интеллекта, сменяющихся каждые десять лет, он - язык математической логики - является своего рода скалой среди айсбергов» [15].

В математической логике принято выделять два основных направления: логику классическую и логику неклассическую. Классическая логика является истиннозначной, т.е. любое умозаключение должно иметь только одно значение: «истина» или «ложь» и быть описано через истинные или ложные значения высказываний и суждений. А неклассическая логика во многом снимает эти ограничения и допускает континуальное множество испо материалам [10], [15], [21].

тинностных значений высказываний или указывает отношение субъекта высказывания к окружающей действительности (например, к возможности или необходимости в прошлом или будущем появлению факта или события).

Математическая логика нашла широкое применение в информационных технологиях, программировании, математической лингвистике, а также в системах искусственного интеллекта, управления базами данных, в принятии решений и управлении организационно-экономическими системами.

Раздел «Классическая логика» включает главы «Логика высказываний», «Логику предикатов» и «Логика реляционная».

В главе «Логика высказываний» изложены основы алгебры и исчисления высказываний, показаны правила формирования сложных суждений из элементарных высказываний и их преобразования в алгебраические формулы. Исследованы правила исполнения алгебраических операций, поиска равносильных формул и их эквивалентного преобразования, В исчислении высказываний рассмотрены метод дедуктивного вывода и метод вывода по принципу резолюции. Для демонстрации каждого шага вывода использованы графы.

В главе «Логика предикатов» введены новые понятия: предикаты и кванторы, что позволило формировать частные и общие суждения, используя предметные переменные и предметные постоянные. Приведены основные законы алгебры кванторов, показаны способы преобразования алгебраических формул к виду предварённых нормальных и совершенных сколемовских формам. ИсследоПредисловие ваны особенности в логике предикатов операций подстановки и унификации. В исчислении предикатов рассмотрены дедуктивный метод вывода заключения и метод по принципу резолюции. Для демонстрации каждого шага вывода также использованы графы. В параграфе 1.2.3 «Логическое программирование», написанном Ю.Ю. Шелухиным под руководством автора, дано описание подготовки среды Visual Prolog для логического вывода и написаны программы для большинства примеров логики высказываний и предикатов. Для ссылки на соответствующие примеры этих глав они нумерованы.

В главе «Реляционная логика» даны основы реляционных алгебры и реляционного исчисления для возможного использования в работе с множеством таблицотношений. На конкретных примерах объяснены сложные алгебраические преобразования таблиц-отношений. Изложены основы реляционного исчисления с переменнымикортежами и приведены правила написания логических формул на языке логики предикатов для вывода таблицотношений. Приведены основы языка SQL и его инструкции для исполнения алгебраических и логических операций при выводе новых отношений.

Раздел «Неклассическая логика» включает главы «Нечёткая логика» и «Модальная логика».

В главе «Нечёткая логика» введено понятие континуального множества значений «истина» на интервале [0, 1], т.е. стало возможным нечётко описывать в высказывании свойства объектов и/или отношений между ними. Показаны особенности исполнения алгебраических операций над нечеткими высказываниями и правила формирования неПредисловие четких сложных суждений. Приведены особенности нечеткого исчисления. Это позволило даже при нечетких знаниях о предмете исследования делать достаточно близкие к истине заключения. Аппарат нечеткой логики нашел широкое применение в экспертных системах и системах искусственного интеллекта. В главе дано краткое описание двух экспертных систем.

В главе «Модальная логика» с помощью кванторов «необходимо» и «возможно» раскрыто отношение субъекта высказывания к ожидаемому или прошедшему факту или событию. Правила вывода модальной логики позволили отобразить структуру вывода заключения на временнй оси. Так был осуществлен переход к темпоральной или временнй логике для моделирования взаимодействия одного или нескольких линейных и/или ветвящихся процессов. В дальнейшем идеи модальной логики дали развитие алгоритмической логике, правила вывода которой на логическом уровне формализовали семантику языков программирования. Законы темпоральной и алгоритмической логик стали использовать в доказательстве правильности программ (верифицикации) до их тестирования. Поэтому эти логики нашли применение в информационных технологиях, в параллельных вычислениях, в использовании общих ресурсов вычислительными системами.

В классической математической логике можно выделить три основных подраздела: логику высказываний, логику предикатов и реляционную логику.

Предметом логики высказываний (prepositional logic) являются предложения (или фразы), взятые целиком без учета их длины, состава и структуры и утверждающие или отрицающие какой-либо факт, явление или событие.

Предметом логики предикатов (predicate logic) также являются предложения произвольной длины, но утверждающие или отрицающие какой-либо отдельный (частный) факт или всеобщее явление в зависимости от значений элементов, формирующих состав и структуру предложения.

И наконец, предметом реляционной логики (relation logic) являются множества однородных предложений, имеющих одинаковую длину, одинаковые имена элементов, формирующих одинаковый состав и структуру предложений (совместимых кортежей), объединяемых в таблицы (отношения), но каждое из них утверждает какой-то отдельный факт и соответствующие ему значения имен элементов.

Всякое повествовательное предложение естественного языка называют высказыванием. Высказыванию, которое описывает верное или неверное суждение о факте, явлении или событии в определенных условиях времени и места, присваивают значение «истина» или «ложь». Например, «З - простое число» = истина, а «3.14… - рациональное число» = ложь, «Колумб открыл Америку» = истина, а «Киев - столица Узбекистана» = ложь, «Число 6 делится на 2 и 3» = истина, а «сумма чисел 2 и 3 равна 6» = ложь и т.п. Такие высказывания называют простыми или элементарными.

При исследовании сложных текстов понятие «простые высказывания» замещают понятием «пропозициональные * переменные», которые обозначают прописными буквами латинского алфавита A, B, C, … Истинность или ложность пропозициональной переменной будем отмечать символами «и» – истина или «л» – ложь.

Пример 1.1.

• если A1::= «3 - простое число», то A1 = и, • если A2::= «3 - вещественное число», то A2 = и, • если A3::= «3 - целое число», то A3 = и, • если B1::= «3, 14…- рациональное число», то B1 = л, • если B2::= «3, 14…- не рациональное число», то B2 = • если C::= «Колумб открыл Америку», то C = и, • если D::= «Киев - столица Узбекистана», то D = л, • если E1::= «Число 6 делится на 1, 2 и 3», то E1 = и, лат. propositio – предложение и др., • если Е2::= «Число 6 есть сумма чисел 1, 2, 3», то Е2 = Примечание: символ «::=» означает, что пропозициональная переменная слева есть формальное описание высказывания, стоящего справа, а её значение принадлежит множеству {и, л}.

Высказывания, которые на естественном языке создают из элементарных высказываний с помощью грамматических связок «не», «и», «или», «если…, то…», «… тогда и только тогда, когда…» и т.п. называют сложными.

Для формального обозначения этих связок вводят символы, которые называют логическими связками. Например, «»::= «или», «&»::= «и», «»::= «не», «»::= «если…, то…», «»::= «…тогда и только тогда, когда …». На естественном языке символы математической логики называют так: «» - дизъюнкция *, «&» - конъюнкция **, «¬» отрицание, «» - импликация ***, «» - эквивалентность ****.

Для построения более сложных высказываний используют вспомогательные символы «(», «)» - скобки.

Пример 1.2. Пусть обозначения элементарных высказываний А1, А2, А3, В1, В2, Е1, Е2 взяты из предыдущего примера.

• если высказывание «3 – вещественное и целое число», то (A1&A2) = и, • если высказывание «3,14… - рациональное число», лат. disjnctivus – разделительный, лат. conjunctivus – соединительный, *** лат. implicatio – сплетение, переплетение, **** лат aequus – равный + valentis, – имеющий значение, цену то B1=л или B1 = и, • если высказывание «число 6 делится на 1, 2, 3 и представляет сумму делителей 1, 2, 3», то (E1&Е2)= и, • если высказывание «если 3 - целое число, то оно вещественное», то (A3 A2)=и, • если высказывание «если 3 – простое число, то оно целое», то (A1 A3)=и, • если высказывание «3 - простое число, тогда и только тогда, когда оно целое», то (А1А2)=и.

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

Правила вывода новых высказываний, основанные на известных высказываниях и отношениях между ними, представляют исчисление высказываний. В этом случае высказывания, из которых делают вывод новых высказываний, называют посылками, а получаемое новое высказывание – заключением.

Множество пропозициональных переменных ={A, B, C,…} и множество логических операторов и отношений ={¬, &,,,, } представляют алгебру высказываЛогика высказываний ний:

где и, л –значения «истина» или «ложь» для пропозициональных переменных и правильно построенных алгебраических выражений. Символы логических операций: «¬» отрицание, «&» - конъюнкция, «» - дизъюнкция, «» импликация, «» - эквивалентность служат для формального описания сложных высказываний, а символ «» равносильности формирует отношение сравнения двух правильно построенных выражений.

Любая пропозициональная переменная есть элементарная формула, т. е. Ai =Fi.

Высказывание, которое может быть получено из элементарных высказываний посредством логических операций, называют формулой алгебры логики, т.е. если F1 и F – формулы, то ¬F1, ¬F2, (F1&F2), (F1F2), (F1F2) и (F1F2), (F1F2) - также формулы.

Никаких других формул в логике высказываний нет.

Значение формулы полностью определяется значениями входящих в нее пропозициональных переменных.

Логические операции бывают унарными (или одноместными) и бинарными (или двухместными). Если значения операндов принадлежат множеству {и, л}, то и результаты логических операций также принадлежат множеству {и, л}. Исполнение логических операций удобно описывать таблицами истинности.

Отрицание (¬F) есть одноместная операция, посредМатематическая логика ством которой ее значение есть отрицание значения операнда.

В программировании для этого используют оператор NOT, т.е. (NOT F). Если F - высказывание, то F также высказывание. Если ¬F есть высказывание, то ¬(¬F) также есть высказывание.

F F Пример 1.3. Верно ли, что А:=«4 - прои л стое число» или А=и?

л и «Нет, неверно, что 4 – простое число», Конъюнкция (F1&F2) есть двухместная операция, посредством которой из двух формул F1 и F2 получают новую формулу F, описывающую сложное высказывание.

Формула F=(F1&F2) истинна тогда и только тогда, когда истинны значения двух операндов F1 и F2.

F1 F2 F1&F В программировании для этого используют оператор AND, т.е. (F1_AND_F2).

отрицания очевидно, что (F&¬F)=л.

Если даны F1, F2, …, Fn, то формула F=(F1&F2&…&Fn)=и тогда и только тогда, когда истинны все формулы F1, F2,…, Fn.

Пример 1.4. Даны высказывания A:=«компьютер содержит основной микропроцессор», B:=«компьютер содержит оперативную память», C:=«компьютер содержит контроллеры», D:=«компьютер содержит порты ввода – вывода».

Тогда формула F=(A&B&C&D) отражает высказывание «компьютер содержит основной микропроцессор, оперативную память, контроллеры и порты ввода-вывода»

[17].

Дизъюнкция (F1F2) есть двухместная операция, посредством которой из двух формул F1 и F2 получают новую формулу F, описывающую сложное высказывание.

Формула F=(F1F2) ложно тогда и только тогда, когда ложны значения двух операндов F1 или F2.

F F F1F В программировании для этого используют оператор OR, т.е. (F1_OR_F2).

Следует обратить внимание, что в повседневной речи союз «или» употребляется в двух смыслах: «исключающее или», когда истинность сложного высказывания определяется истинностью только одного высказываний (второе должно быть ложным), и «не исключающее или», когда истинность сложного высказывания определяется истинностью хотя бы одного из них. В математической логике используют только «не исключающее или».

Пример 1.5. Даны высказывания A:= «в компьютере применяют матричный принтер», B:= «в компьютере применяют струйный принтер», C:= «в компьютере применяют лазерный принтер», D:= «в компьютере применяют литерный принтер».

Тогда формула F=(ABCD) отражает высказывание «в компьютере применяют матричный, струйный, лазерный или литерный принтеры» [17].

Пример 1.6. Даны высказывания A:= «монитор есть машинная программа, которая наблюдает, регулирует, контролирует или проверяет операции в системе обработки данных», B:= «монитор в языках программирования это высокоуровневый механизм взаимодействия и синхронизации процессов, обеспечивающих доступ к неразделяемым ресурсам», C:= «монитор - это дисплей, используемый для контроля процессов и управления системой».

Тогда формула F=(ABC) отражает высказывание «монитор есть машинная программа, которая наблюдает, регулирует, контролирует или проверяет операции в системе обработки данных или в языках программирования – это высокоуровневый механизм взаимодействия и синхронизации процессов, обеспечивающих доступ к неразделяемым ресурсам или дисплей, используемый для контроля процессов и управления системой» [17].

Импликация (F1F2) есть двуместная операция, посредством которой из двух формул F1 и F2 получают формулу F, описывающую сложное высказывание. Формула F=(F1F2) ложно тогда и только тогда, когда истинно F1 и ложно F2. При этом F1 называют посылкой, а F2 – заключением.

В программировании используют оператор IMPLIES, т. е. (F1_IMPLIES_F2).

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

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

Пример 1.7. Даны высказывания A:= «по проводнику протекает электрический ток» и B:= «вокруг проводника есть магнитное поле». Тогда формула F=(AB) отражает высказывание «если по проводнику протекает электрический ток, то вокруг проводника возникает магнитное поле».

Пример 1.8. Пусть даны высказывания A:= «на упругое тело оказывают влияние внешние силы» и B:= «в упругом теле возникают внутренние силы, препятствующие изменению формы». Тогда формула F=(AB) отражает высказывание «если на упругое тело оказывают влияние внешней силы, то в нем возникают внутренние силы, препятствующие изменению формы».

Эквивалентность (F1F2) есть двухместная операция, посредством которой из двух формул F1 и F2 получают формулу F, описывающую сложное высказывание. Формула F=(F1F2) истинна тогда и только тогда, когда оба операнда F1 и F2 имеют одинаковые значения.

F F F1 В программировании для этого используют оператор IFF, т.е. (F1IFF_ F2). На Пример 1.9. Даны высказывания A:= «быть четным числом» и B:= «число делится на два». Тогда формула F=(AB) отображает высказывание «для того, чтобы число было четным необходимо и достаточно, чтобы оно делилось на два».

Пример. Даны высказывания A:= «выполнить загрузку в компьютер операционной системы» и B:= «установить в компьютер дискету с записанной операционной системой».

Тогда формула F=(AB) отображает высказывание «для того, чтобы выполнить загрузку операционной системы в компьютер, необходимо и достаточно установить в компьютер дискету с записанной операционной системой».

Пример 1.10. Даны высказывания A:= «урожай будет стабильным ежегодно» и B:= «выполнены все ирригационные работы».

Тогда формула F=(AB) отображает высказывание «урожай будет ежегодно стабильным тогда и только тогда, когда будут выполнены все ирригационные работы».

Пример 1.11. Даны высказывания S:= «полная система функций математической логики», A:= «система функций содержит хотя бы одну нелинейную функцию», B:= «система функций содержит хотя бы одну немонотонную функцию», C:= «система функций содержит хотя бы одну не самодвойственную функцию», D:= « система функций содержит хотя бы одну функцию, не сохраняющую «0»», E:= «система функций содержит хотя бы одну функцию, не сохраняющую «1»». Тогда формула F=(S(A&B&C&D&E)) есть образ сложного высказывания: «для того чтобы система функций математической логики была полной, необходимо и достаточно, чтобы она содержала хотя бы по одной нелинейную, немонотонную и не самодвойственную функции, а также функции, не сохраняющие «0» и «1».

1.1.1.2. Правила записи сложных формул Для определения истинности сложного суждения необходимо анализировать значение истинности каждого элементарного высказывания и вычислять значения истинности каждой подформулы, входящей в формулу этого суждения.

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

Пример 1.12. Суждение «если инвестиции на текущий год не изменятся, то возрастает расходная часть бюджета или возникнет безработица, а если возрастет расходная часть бюджета, то налоги не будут снижены и, наконец, если налоги не будут снижены и инвестиции не изменятся, то безработица не возникнет» [21].

В этом суждении есть четыре простых повествовательных предложения: A:= «инвестиции на текущий год не изменятся», B:= «возрастет расходная часть бюджета», C:= «возникнет безработица», D:= «налоги не снизятся». Тогда формула суждения имеет вид:

F =(A(BC))&(BD)&((D&A)C).

A B C D C 4& 23 17 24 65 8&9 11& Для удобства описания формулы таблицей истинности каждый столбец таблицы 1.1 пронумерован, а исполнение логических операций (подформул) выполняется с индексами столбцов.

В 12-ом столбце таблицы выделены полужирным шрифтом те строки, в которых формула F имеет значение «истины» для различных наборов значений пропозициональных переменных A, B, C и D.

Анализ таблицы показывает: чтобы не возникла безработица при неизменных инвестициях и налогах необходимо увеличить расходную часть бюджета. Это показано в таблице выделенной строкой.

Пример 1.13. Суждение «если цены высокие (A), то и заработная плата должна быть также высокой (B). Цены повышают или применяют регулирование цен (C). Если применяют регулирование цен, то нет инфляции (D). Инфляция есть. Следовательно, заработная плата должна быть высокой» [19].

Формулы первых четырех высказываний (АB), (AC), (С ¬D), D есть посылки, а формула пятого высказывания – заключение B. Посылки и заключение разделены между собой чертой:

Для анализа этого суждения построим таблицу истинности (см. табл. 1.2).

Анализ выделенной строки таблицы показывает, что заработная плата при высоких ценах и наличии инфляции должна быть высокой и не должно быть регулирования цен. Только в этом случае посылки (AB), (AC), (C¬D) и D и заключение B имеют значение истины.

Пример 1.14. Суждение: ”Контракт будет выполнен (A) тогда и только тогда, когда дом будет сдан в эксплуаЛогика высказываний тацию (B). Если дом будет сдан в декабре, то в январе можно переезжать в новые квартиры (C). Если в январе квартиросъемщики не переезжают, то они не оплачивают квартирную плату. Даже если контракт не выполнен, то квартиросъемщики должны внести квартирную плату.

Квартиросъемщики внесут квартирную плату”[19].

В этом суждении пять высказываний. Формулы первых четырех высказываний (AB), (BC), (¬C¬D) и (¬AD) есть посылки, а формула пятого высказывания – заключение D. Посылки и заключение также разделены между собой чертой.

Анализ выделенной строки таблицы 1.3 показывает, при каких условиях (посылках) заключение должно быть истинным D.

Л Л Л ЛИ И И Л

Л Л Л ИИ И Л И

Л Л И ЛИ И И Л

Л Л И ИИ И И И

Л И Л ЛЛ Л И Л

Л И Л ИЛ Л Л И

Л И И ЛЛ И И Л

Л И И ИЛ И И И

И Л Л ЛЛ И И И

И Л Л ИЛ И Л И

И Л И ЛЛ И И И

И Л И ИЛ И И И

И И Л ЛИ Л И И

И И Л ИИ Л Л И

И И И ЛИ И И И

ИИИИ И И И Л

Пример 1.15. Суждение «если курс ценных бумаг возрастет (A) или процентная ставка снизится (B), то курс акций упадет (C) или налоги не повысятся (D). Курс акций падает тогда и только тогда, когда растут курс ценных бумаг и налоги. Если процентная ставка снизится, то либо курс акций не понизится, либо курс ценных бумаг не возрастет.

Следовательно, если налоги повысить, то не вырастет курс ценных бумаг и вырастет курс акций» [19].

В этом суждении четыре сложных высказывания, три из которых являются посылками (AB)(CD), C(A&¬D) и B(¬C¬A), а одно – заключением ¬D(¬A&¬C). Посылки и заключение также разделены между собой чертой.

Для анализа этого суждения построим таблицу истинности (см. табл. 1.4).

В таблице приведенывсе возможные наборы пропозициональных переменныъ (элементарных высказываний) и всех промежуточных формул посылок и заключения. Выделенные строки таблицы показывают варианты, для каких истинны посылки и заключение.

Для выбора только одного варианта из шести возможных следует рассмотреть вариант, когда курс ценных бумаг растет (А=и). При этом курс ценных бумаг может расти либо падать Приведенные примеры позволяют сформулировать некоторые правила записи сложных суждений:

• каждое вхождение логической связки «¬» относится к пропозициональной переменной или формуле, следующей непосредственно за логической связкой справа, • каждое вхождение логической связки «&» после расстановки скобок связывает пропозициональные переменные или формулы, непосредственно окружающие логическую связку, • каждое вхождение логической связки «» после расстаМатематическая логика новки скобок связывает пропозициональные переменные или формулы, непосредственно окружающие эту связку и т.д., • в формулах нет двух рядом стоящих логических связок - они должны быть разъединены формулами, • в формулах нет двух рядом стоящих формул - они должны быть разъединены логической связкой, • логические связки по силе и значимости упорядочены так: ¬, &,,,, т.е. самой сильной связкой является отрицание, затем конъюнкция, дизъюнкция, импликация и, наконец, эквивалентность.

Знания силы логических связок позволяет опускать скобки, без которых очевиден порядок исполнения операций.

F=(((F1(¬F2))F3)F4).

Зная силу логических связок, упростить запись формулы.

• удалить внешние скобки формулы, так как они не определяют старшинство никакой операции:

F=((F1(¬F2))F3)F4, • удалить скобки, охватывающие формулу импликации, так как операция эквивалентности будет исполняться только после выполнения операции импликации:

F=(F1(¬F2))F3F4, • удалить скобки, охватывающие формулу дизъюнкции, так как операция импликации будет исполняться только после выполнения операции дизъюнкции:

F=F1(¬F2)F3F4, • удалить скобки, охватывающие формулу отрицания, так как операция дизъюнкции будет исполняться только F=F1¬F2F3F4, Последовательность исполнения операций определяется силой логических связок: сначала вычислить значение (¬F2), затем (F1(¬F2)), ((F1(¬F2))F3) и, наконец, F1(¬F2))F3)F4).

F=F1&F2&F3¬F1F3F1. Расставить вспомогательные символы - скобки.

• поставить скобки для операции отрицания:

F1&F2&F3(¬F1)F3F1;

• поставить скобки для операции конъюнкция:

F=((F1&F2)&F3)(¬F1)F3F1;

• поставить скобки для операции дизъюнкция:

F=(((F1&F2)&F3)(¬F1))F3F1;

• поставить скобки для операции импликация:

F=((((F1&F2)&F3)(¬F1))F3)F1;

• поставить скобки для операции эквивалентности:

F=(((((F1&F2)&F3)(¬F1))F3)F1).

Скобки позволяют организовать вычисление значения всей формулы, последовательно определяя значение каждой вложенной подформулы: сначала найти значение (¬F1), затем - (F1&F2), ((F1&F2)&F3), (((F1&F2)&F3)(¬F1)), ((((F1&F2)&F3)(¬F1))F3), и наконец, F1&F2)&F3)(¬F1))F3)F1).

1.1.1.3. Законы алгебры высказываний Ещё во времена Аристотеля в классической логике были признаны два основных закона: закон тождества – «используемые понятия не должны ни изменяться, ни подменяться в ходе одного и того же рассуждения» и закон непротиворечия – “невозможно, чтобы одно и то же в одно и то же время было и не было присуще одному и тому же в одном и том же отношении» [15]. С внедрением в логику высказываний алгебраических методов потребовались аксиомы, представляющие законы алгебры высказываний.

Две формулы Fi и Fj называют равносильными (F F2), если они имеют одинаковое значение «истина» или «ложь» при одинаковых наборах пропозициональных переменных. Если две формулы равносильны F1 F2, то они эквивалентны между собой, т.е. (FiFi). И наоборот, если формулы эквивалентны (FiFi), то они равносильны (F F2).

Коммутативности Ассоциативности Дистрибутивности Идемпотентности Исключенного Противоречия Де Моргана Поглощения Порецкого Обобщенного Дополнения Константы Справедливость некоторых законов следует проверить таблицами истинности.

Пример. 1.19. Даны две формы закона поглощения.

F1 F2 1&213 F1 F2 12 1&3 Сравните значения Пример 1.20. Даны две формы закона де Моргана.

¬(F1F2)¬F1& ¬(F1&F2) Сравните ¬F F1 F2 ¬(1 ¬1& Пример 1.21. Даны две формы закона дистрибутивности.

F F F 2& 1 1 1 6& F1 F2 F3 231&41&21& Сравните значения логических функций в пятом и восьмом таблицы.

Пример 1.22. Даны две формы закона Порецкого F1(¬F1&F2) F1&(¬F1F2) F F ¬ 2& 1 1 F1 F2¬1231&4 1&2 Сравните знал л и л л л л л и и л л чения логичел и и и и и л и и и л л ских функций Пример 1.23. Даны две формы обобщенного склеивания.

F1&F2¬F1&F2 F2. (F1F2)&(¬F1F2)& F2. Сравните F1 F2 ¬1 1&2 2&3 45 26 F1 F2 ¬1 12 23 4&5 2&6 значения Если формула F содержит подформулу Fi, которая, в свою очередь, имеет эквивалентную формулу Fj, т.е. (FiFj), то возможна подстановка в формулу F всюду вместо формулы Fi формулы Fj.

Этот факт описывают так:

где символ « F » означает подстановку формулы Fj вместо Пример 1.18. Даны формулы F=(A&CA) и А (CВ). Выполнить подстановку.

Любая замена переменной или подформулы в формуле определяется правилом подстановки, а любые эквивалентные преобразования формул законами алгебры высказываний, которые приведены в таблице 1.5.

1.1.1.4. Эквивалентные преобразования формул Знание законов алгебры высказываний позволяет выполнять эквивалентные преобразования любой правильно построенной формулы для замены одних логических операций на другие, сохраняя ее значение для всех наборов пропозициональных переменных.

Пример 1.24. Дано (F1F2) (¬F1F2) ¬(F1&¬F2).

Часто необходимо удалять символ «» для последующих преобразований формул.

F1 F2 ¬F1 ¬F2 12 32 1&4 ¬7 Равносильность или л л и и и и л и этих формул показал и и л и и л и на таблицей истинл и л ности. Сравните лоил л и л и и л л и и л и гические функции в Пример 1.25. Дано F1F2(F1F2)&(F2F1)(¬F1F2)& (¬F2F1) ¬(¬(¬F1F2)¬(¬F2F1)) F1&F2F1&F2.

Эквивалентность или равносильность формул показана в таблице истинности.

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

F=(F1F2)((F2F3)(F1F2F3)). Упростить выражеЛогика высказываний ние формулы.

• Удалить всюду логическую связку «»:

F= ¬(¬F1F2)(¬( ¬F2F3)(¬(F1F2) F3), • опустить отрицание до элементарных формул по закону де Моргана:

F=F1&¬F2F2&¬F3¬F1&¬F2F3, • выполнить преобразование по закону дистрибутивности:

F=( F1¬F1) &¬F2F2&¬F3 F3, • удалить член (F1¬F1), так как (F1¬F1)=и:

F=¬F2F2&¬F3 F3, • выполнить преобразование по закону Порецкого:

F=¬F2¬F3 F3, • так как (F3¬F3)=и, то F=¬F2и=и, F=¬(F1F2)&(¬F3¬F4)¬(F1F2)&¬(F3&F4). Упростить выражение формулы.

• Удалить логическую связку «»:

F=¬(¬F1F2)&(¬F3¬F4)¬(F1F2)&¬(F3&F4), • опустить отрицание на элементарные формулы по закону де Моргана:

F=F1&¬F2&(¬F3¬F4) ¬F1&¬F2&(¬F3¬F4), • выполнить преобразование по закону дистрибутивности:

F=( F1¬F1) &¬F2&(¬F3¬F4), • удалить член (F1¬F1)=и:

F=¬F2&(¬F3¬F4).

Итак, ¬F2&(¬F3¬F4).

Пример 1.28. Дано суждение «или верно, что Петр поступил в университет (А), и при этом неверно, что Петр не поступил и Андрей не поступил, или Петр поступил и Семен поступил (С), или даже Петр поступил и Семен поступил, и Андрей поступил (В)». Кто же один из друзей поступил в университет? [15].

Формула этого высказывания имеет вид:

F=А&¬(¬A&¬В)А&СА&В&С.

Для ответа на поставленный вопрос необходимо:

• преобразовать формулу, используя закон де Моргана:

F=А&(АВ)А&СА&В&С, • применить закон идемпотентности:

F=А&(АВ)A&А&СА&В&С, • применить закон дистрибутивности:

F=А&((АВ) А&СВ&С), F=А&((АВ) С&(АВ)), F=(АВ)&(АС), F=А(В&С).

Полученная формула равносильна исходной, но имеющая более простое выражение. Если в университет поступил только один из трех друзей (по условию задачи), то А=и, а (В&С)=л. Следовательно, в университет поступил Петр.

Пример 1.29. Шесть школьников - Андрей, Борис, Григорий, Дмитрий, Евгений и Семен - участвовали в олимпиаде. Двое из них решили все задачи. На вопрос, кто решил все задачи, последовали ответы:1) Андрей и Дмитрий, 2) Борис и Евгений, 3) Евгений и Андрей, 4)Борис и Григорий, 5) Семен и Андрей. В четырех из этих ответов одна часть неверна, другая верна. В одном - обе части неверны. Кто же решил все задачи? [15].

Введем обозначения: A:= Андрей решил все задачи, Б:= Борис решил все задачи, Г:=Григорий решил все задачи, Д:= Дмитрий решил все задачи, Е:= Евгений решил все задачи, С:= Семен решил все задачи.

Так как в одном из ответов обе части неверны, а в остальных - одна, то необходимо составить пять формул, отражающих пять различных вариантов высказываний:

¬A&¬Д&(¬Б&ЕБ&¬Е)&(¬Е&АЕ&¬А)&(¬Б&ГБ&¬ Г)&(¬С&АС&¬А), ¬Б&¬Е&(¬А&ДА&¬Д)&(¬Е&АЕ&¬А)&(¬Б&ГБ&¬ Г)&(¬С&АС&¬А), Е&¬А&(¬А&ДА&¬Д)&(¬Б&ЕБ&¬Е)&(¬Б&ГБ&¬Г) &(¬С&АС&¬А), Б&¬Г&(¬А&ДА&¬Д)&(¬Б&ЕБ&¬Е)&(¬Е&АЕ&¬А )&(¬С&АС&¬А), ¬С&¬А&(¬А&ДА&¬Д)&(¬Б&ЕБ&¬Е)&(¬Е&АЕ& ¬А)&(¬Б&ГБ&¬Г).

¬A&¬Д&(¬Б&ЕБ&¬Е)&Е&¬А&(¬Б&ГБ&¬Г)&С&¬ А, так как ¬Е&А=л.

Если допустить, что ¬Б=и и ¬Е=и, то вторая формула равна ¬Б&¬ Е&(¬А&ДА&¬Д)&¬Е&А&¬Б&Г&(¬С&АС&¬А), так как Е&¬А=л и Б&¬Г=л.

Если допустить, что ¬Е=и и ¬А=и, то третья формула равна ¬Е&¬А&¬А&Д&Б&¬Е&(¬Б&ГБ&¬Г)&С&¬А, так как А&¬Д=л, ¬Б&Е=л, и ¬С&А=л.

¬Б&¬Г&(¬А&ДА&¬Д)&¬Б&Е&(¬Е&АЕ&¬А)&(¬С &АС&¬А), так как Б&¬Е=л.

¬С&¬А&¬А&Д&(¬Б&ЕБ&¬Е)&Е&¬А&(¬Б&ГБ&¬Г ), так как А&Д=л.

То есть система формул имеет вид:

1) ¬A&¬Д&(¬Б&ЕБ&¬Е)&Е&¬А&(¬Б&ГБ&¬Г) 2) ¬Б&¬Е&(¬А&ДА&¬Д)&¬Е&А&¬Б&Г&(¬С&А 3) ¬Е&¬А&¬А&Д&Б&¬Е&(¬Б&ГБ&¬Г)&С&¬А, 4) ¬Б&¬Г&(¬А&ДА&¬Д)&¬Б&Е&(¬Е&АЕ&¬А) 5) ¬С&¬А&¬А&Д&(¬Б&ЕБ&¬Е)&Е&¬А&(¬Б&Г Применив законы дистрибутивности, идемпотентности и поглощения, эти формулы можно упростить так:

1) A&¬Д&¬Б&Е&Г&С, 2)¬Б &¬Е&¬Д&¬С&А&Г, 3)¬Е&¬А&¬Г&Д&С&Б, 4)¬Б&¬Г&¬А&Д&Е&С, 5)¬С&¬А&¬Б&Д&Е&Г.

По условиям задачи только два участника решили все задачи. Поэтому формулы, содержащие три пропозициональные переменные без отрицания ложны, а одна, содержащая только две пропозициональные переменные без отрицания, отвечает поставленным условиям. Это Б&¬Е&¬Д&¬С&А&Г. Следовательно, все задачи на олимпиаде решили Андрей (А) и Григорий (Г).

Примеры показывают, что всякую формулу алгебры логики можно заместить равносильной формулой, содержащей только две логических связки: дизъюнкцию и отрицание или конъюнкцию и отрицание или три логических связки: дизъюнкции, конъюнкции и отрицания. Этот факт показывает, что эти логические связки представляют функционально полные алгебраические системы.

1.1.1.5. Нормальные формы формул В алгебре высказываний используют две нормальные формы: дизъюнктивную (ДНФ) и конъюнктивную нормальные формы формул (КНФ).

ДНФ есть формула, равносильная формуле исходной логической функции и записанная в виде дизъюнкции элементарных конъюнкций, построенных на пропозициональных переменных, т.е. F = K1K2K3…, где каждая Ki = (A&B&C&…).

В элементарной конъюнкции нет двух одинаковых пропозициональных переменных, так как A&A A, а в ДНФ нет двух одинаковых элементарных конъюнкций, так как KK K. Если одна из элементарных конъюнкций содержит (A&A), то ее следует удалить из формулы ДНФ по закону противоречия.

Пример 1.30. Если F=F1&(F2¬F2)F2&(F1¬F1), то по закону F=F1&F2F1&¬F2F1&F2¬F1&F2= F1&F2F1&¬F2¬F1&F2. Так сформирована ДНФ.

КНФ есть формула, равносильная формуле исходной логической функции и записанная в виде конъюнкции элементарных дизъюнкций, построенных на пропозициональных переменных, т.е. F = D1&D2&D3&…, где каждая Di=(ABC…).

В элементарной дизъюнкции нет двух одинаковых пропозициональных переменных, так как AA A, а в КНФ нет двух одинаковых элементарных дизъюнкций, D&D D. Если одна из элементарных дизъюнкций содержит (FF), то ее следует удалить из КНФ по закону исключенного третьего.

Пример 1.31. Если F=F1&(F1F2)¬F2&(F1F2), то по закону дистрибутивности имеем F=(F1F2)&(F1¬F2). Так сформирована КНФ.

Наибольшее распространение в логике высказываний получили формулы КНФ, элементарные дизъюнкции которых Di принято называть дизъюнктами, а члены каждого дизъюнкта A, B, C –атомами.

Алгоритм приведения формулы к нормальной форме.

Шаг 1. Устранить «» и «» всюду по правилам:

(F1F2) (F1F2)&(F2F1) (¬F1F2)&(¬F2F1) (F1F2) (F1F2)¬(F1&¬F2).

Шаг 2. Продвинуть отрицание до пропозициональной переменной по правилам:

¬(¬F) F, ¬(F1F2)(¬F1&¬F2), ¬(F1&F2)(¬F1¬F2).

Шаг 3. Применить закон дистрибутивности:

а) для КНФ: F1F2&F3(F1F2)&(F1F3), b) для ДНФ: F1&(F2F3) F1&F2F1&F3.

Пример 1.32. F=((F1(F2¬F3))F4). Преобразовать формулу к виду КНФ.

• Удалить всюду символ «»:

F=¬(¬F1F2¬F3)F4), • выполнить логическую операцию отрицания формулы:

F=F1&¬F2&F3)F4), • применить закон дистрибутивности:

F=(F1F4)&(¬F2F4)&(F3F4). Это – КНФ формулы.

Пример 1.33. F=¬(F1&F2)&(F1F2). Преобразовать формулу к виду ДНФ.

• Выполнить операцию отрицания формулы:

F=(¬F1¬F2)&(F1F2), • применить закон дистрибутивности:

F=( F1&¬F1F1&¬F2F2&¬F1F2&¬F2, • применить закон противоречия:

F=F1&¬F2F2&¬F1. Это – ДНФ формулы.

Если каждая элементарная конъюнкция (или элеменМатематическая логика тарная дизъюнкция) формулы содержат символы всех пропозициональных переменных, то такая формула называется совершенной. Есть совершенные дизъюнктивные нормальные формы формулы (СДНФ) и совершенные конъюнктивные нормальные формы формулы (СКНФ).

Алгоритм преобразования ДНФ к виду СДНФ.

Шаг 1:.если в элементарную конъюнкцию F не входит подформула Fi или ¬Fi, то дополнить элементарную конъюнкцию формулой (Fi¬Fi)=и и выполнить преобразование формулы по закону дистрибутивности F&(Fi¬Fi) F&FiF&¬Fi, Шаг 2: если в элементарную конъюнкцию F не входит подформула Fj или ¬Fj, то повторить шаг 1, иначе – конец.

F=F1&¬F2F1&¬F3&F4F1&F2&F3&¬F4.

Преобразовать формулу к виду СДНФ:

• F=F1&¬F2&(F3¬F3)F1&¬F3&F4&(F2¬F2) F1&F2&F3&¬F4;

• F=F1&¬F2&F3F1&¬F2&¬F3F1&F2&¬F3&F4F1&¬F2& F1&F2&F3&¬F4;

• F=F1&¬F2&F3&(F4¬F4)F1&¬F2&¬F3&(F4¬F4)F1&F 2&¬F3&F F1&¬F2&¬F3&F4 F1&F2&F3&¬F4;

• F=(F1&¬F2&F3&F4)(F1&¬F2&F3&¬F4)(F1&¬F2&¬F (F1&¬F2&¬F3&F4) (F1&F2&F3&¬F4). Так получена формула СДНФ.

Алгоритм преобразования КНФ к виду СКНФ.

Шаг 1: если в элементарную дизъюнкцию F не входит подформула Fi или ¬Fi, то дополнить элементарную дизъюнкцию высказыванием (Fi&¬Fi)=л и выполнить преобразование формулы по закону дистрибутивности F(Fi &¬Fi) (F Fi)&(F¬Fi), Шаг 2: если в элементарную конъюнкцию F не входит подформула Fj или Fj, то повторить шаг 1, иначе – конец.

Пример 1.35. Дано F=(F1F2)&(¬F1¬F2F3F4).

Преобразовать формулу к виду СКНФ:

• F=(F1F2F3&¬F3) &(¬F1¬F2F3F4);

• F=(F1F2F3) &(F1F2¬F3) &(¬F1¬F2F3F4);

• F=(F1F2F3F4&¬F4)&(F1F2¬F3F4&¬F4)& &(¬F1¬F2F3F4);

F=(F1F2F3F4)&(F1F2F3¬F4)&(F1F2¬F3F4)&(F1F 2¬F3¬F4)& &(¬F1¬F2F3F4). Так преобразования заданная формула к виду СКНФ.

Совершенные нормальные формы удобно записывать по таблицам истинности, используя значения пропозициональных переменных для всех значений, описываемых формулой.

F=(A(BC))&(BD)&((D&A)C) по таблице истинности 1.1 можно найти равносильные СДНФ F=(¬A&¬B&¬C&¬D)(¬A&¬B&¬C&D)(¬A&¬B&C& ¬D)(¬A&¬B&C&D) (¬A&B&¬C&D)(¬A&B&C&D)(A&¬B&C&¬D)(A& B&¬C&D) и СКНФ F=(A¬BCD)&(A¬B¬CD)&(¬ABCD)&(¬AB C¬D)&(¬AB¬C ¬D)& (¬A¬BCD)&(¬A¬B¬CD)&(¬A¬B¬C¬D).

Элементарные конъюнкции формируются для значений формулы “и”. Число элементарных конъюнкций СДНФ равно числу истинных значений формулы. Пропозициональные переменные, элементарной конъюнкции записываются без изменений, если их значение равно “и” и с логической связкой “¬”, если их значение равно “л”.

Элементарные дизъюнкции СКНФ формируются для значения формулы, равной “л”. Число элементарных дизъюнкций равно числу ложных значений формулы.

Пропозициональные переменные элементарной дизъюнкции, записываются без изменений, если их значение равно “л” и с логической связкой “¬”, если их значение равно “и”.

1.1.2. Исчисление высказываний Исчисление высказываний – это формальная система, позволяющая формировать новые высказывания путем указания исходных высказываний, имеющих значение «истина», а также аксиом и правил вывода, каждое из которых описывает, как формировать новое высказывание из исходных и уже построенных высказываний. Поэтому изучение исчисления высказываний следует начинать с определения аксиом и правил вывода, обеспечивающих доказательство истинности заключения.

Аксиома – это высказывание, имеющее значение истины при любых значениях пропозициональных переменных, входящих в это высказывание.

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

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

Задание необходимого числа аксиом определяет полноту исчисления, а задание правил вывода – метод исчисления.

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

Наиболее простой способ определения истинности или ложности формулы является использование таблиц истинности. Основной недостаток таблиц истинности состоит в том, что при большом числе пропозициональных переменных число строк таблицы равно 2n, а число столбцов не меньше (n+m), где n – число пропозициональных переменных, а m – число логических операций.

axima (гр.) – отправное, исходное положение, лежащее в основе доказательств теорем.

interpretatio (лат.) – истолкование, разъяснение смысла чего-л.

Все множество формул можно разбить на три класса:

тождественно истинные, тождественно ложные и выводимые.

Тождественно истинные формулы – это особый класс формул, которые принимают значение «истина» при любом значении пропозициональных переменных, входящих в формулу. Эти формулы играют роль аксиом и законов логики высказываний.

Например. F = ((AB)&(AC)(A(B&C))=и.

Тождественно ложные формулы - это особый класс формул, которые принимают значение «ложь» при любых значениях пропозициональных переменных, входящих в формулу.

Например, F=A&(¬B¬C)&(AB)&(AC)=л.

ллл и лии л Выводимые формулы - это класс формул, которые принимают значения истина или ложь в зависимости от значений пропозициональных переменных.

Например, F=(¬АC&¬В)&(¬CB&¬A)&(A¬C).

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

Например, известна полная система аксиом, опирающаяся на две логические связки «¬» и «», которая содержит три аксиомы:

• (F1(F2F1)), • (F1(F2F3))((F1F2)(F1F3)), • (¬F1¬F2)((¬F1F2)F1).

Возможны и другие полные системы аксиом, опирающиеся на другие сочетания логических связок. Так система аксиом, опирающаяся на четыре логические связки ¬, &,,, содержит двенадцать аксиом:

• А2. (F1F2) ((F2 F3) (F1 F3)), • А3. (F1& F2)F1, • А4. (F1& F2)F2, • А5. F1(F2(F1&F2)), • А6. F1(F1F2), • А7. F2(F1F2), • А8. (F1F3)((F2F3)((F1F2)F3)), • А9. (F1F2)(( F1¬F2) ¬F1), • A10. (F1F2)((F1&F3)(F2&F3)), • A11. (F1 F2)((F1F3)(F2F3)), Приведенные полные системы аксиом равносильны между собой в том смысле, что порождают одно и то же множество формул. Их равносильность может быть доказана выводимостью аксиом первой системы из аксиом второй и наоборот.

Для проверки истинности аксиом достаточно рассмотреть аксиомы A2 и A8 (см. таблицы 1.9 и 1.10). В 9-м столбце каждой таблицы приведены значения этих формул.

Для понимания механизма вывода заключения следует рассмотреть алгебраические правила введения и удаления логических связок. Эти правила – аналог аксиомам исчисления высказываний - существенно облегчают преобразования сложных формул:

П1. Правило введения логической связки «&»: если формулы F1 и F2 истинны, то истинной является их конъюнкция, т. е.

П2. Правило удаления логической связки «&»: если формула (F1&F2) истинна, то истинными являются формулы F1 и F2, т. е. F & F и F & F Это - аксиомы А3 и А4.

П3. Правило введения логической связки «»: если хотя бы одна из формул F1 или F2 истинна, то истинной является их дизъюнкция, т. е. F или F Это - аксиомы 1 А6 и А7.

П4. Правило удаления логической связки «»: если формула (F1F2) истинна, то истинными могут быть форМатематическая логика П5. Правило введения логической связки «»: если формула F2 истинна, то истинной является формула А1 («истина из чего угодно»).

П6. Правило контрапозиции: если формула (F1F2) истинна, то истинной является формула ( F2 F), т. е.

F F Это - аксиома А9.

¬F2 ¬F1.

П7. Правило введения в формулу (F1F2) логической связки «»: если формула (F1F2) истинна, то истинной является формула ((F1F3)(F2F3) при любом значении F3, т. е.

П8. Правило введения в формулу (F1F2) логической связки «&»: если формула (F1F2) истинна, то истинной является формула ((F1&F3)(F2&F3)) при любом значении F3, т. е.

(F1 & F3 ) (F2 & F3 ).

П9. Правило силлогизма: если формулы (F1F2) и (F2F3) истины, то истинной является формула (F1F3), т.

(F F ), (F F ) Это - аксиома А2.

П10. Правило введения логической связки «»: если формулы (F1F2) и (F2F1) истинны, то истинной является формула (F1F2), т. е.

П11. Правило удаления логической связки «»: если формула (F1F2) истинна, то истинными являются формулы (F1F2) и (F2F1), т.е. (F F ) или (F F ) 1 2 1 П12. Правило объединения формул (F1F3) и Это - аксиома А8.

1.1.2.3. Метод дедуктивного вывода Выводом формулы В из множества формул F1, F2,…, Fn называется такая последовательность формул, что любая Fi есть либо аксиома, либо выводима из множества предшествующих ей формул F1, F2,…, Fn.

В этом случае формулу B называют заключением, а последовательность формул F1, F2,…, Fn, - схемой дедуктивного вывода.

Схему дедуктивного вывода записывают так:

где «|» означает «верно, что B выводима из F1, F2, …, Fn».

Известна другая форма записи этой схемы:

где над чертой записывают множество истинных посылок и аксиом F1, F2, …, Fn, а под чертой - заключение В.

На языке математики схема дедуктивного вывода * есть доказательство теоремы (теорема Эрбрана):

Истинность этой теоремы доказывается так: «если все Fi=и, то F1&F2&... &Fn=и, а если B=и, то по таблице истинности импликации F1&F2&... &FnB=и».

Используя правила эквивалентных преобразований теоремы, можно показать дедуктивный характер вывода заключения:

• |(F1&F2&...&FnB), • |(¬(F1&F2&...&Fn )B), • |(¬F1¬F2...¬FnB), • |(¬F1¬F2...¬Fn-1(FnB)),

• |(F1(F2...(Fn-1(FnB))...).

Таким образом, вывод заключения всегда логически следует из множества посылок и аксиом. Вывод заключения опирается на два основных правила:

а) если F1 и (F1F2 ) выводимые формулы, то F2 также выводимая формула, т.е. F, F F Это правило называют modus ponens (m. p.) или прямое доказательство.

b) если ¬F2 и (F1F2) выводимые формулы, то ¬F также выводимая формула, т.е. ¬F, (F F ) Это правило наF1.

зывают modus tollens (m. t.) или доказательство «от противного».

Эти правила являются основными при выводе заключения, так как устанавливают отношение следования межлат. deductio – выведение или логическое умозаключение.

ду двумя формулами.

Пример 1.36. «Всякое общественно опасное деяние (А) наказуемо (В). Преступление (С) есть общественно опасное деяние (А). Дача взятки (D) - преступление (C). Следовательно, дача взятки наказуема ?» [9].

Формальна запись этого суждения:

Дедуктивный вывод:

• F4=CB - заключение по формулам F1 и F2 и правилу П9, • F5=DB - заключение по формулам F3 и F4 и правилу П9, ч.т.д *.

Процесс дедуктивного вывода удобно демонстрировать с помощью графа (см. рис. 1.1), вершинами которого являются формулы, а дугами – отношения между формулами согласно аксиомам и правилам введения и удаления логических связок.

Пример 1.37. «Если Петров говорит неправду (A), то - что и требовалось доказать.

он заблуждается (В) или сознательно вводит в заблуждение других (С). Петров говорит неправду и явно не заблуждается. Следовательно, он сознательно вводит в заблуждение других» [9].

Формальна запись этого суждения:

Дедуктивный вывод:

• F2=A&¬B – посылка, • F3=A - заключение по формуле F2 и правилу П2, • F4=¬B - заключение по формуле F2 и правилу П2, • F5=(ВС)(¬BC) - заключение по F1, F3 и правилу m.

• F6=C - заключение по формулам F4, F5 и правилу m. p., На рис. 1.2 показан граф вывода этой задачи.

Пример 1.38. “Если Петров не трус (A), то он поступит в соответствие с собственными убеждениями (B). Если Петров честен (C), то он не трус (A). Если Петров не честен ¬(C), то он не признает своей ошибки (D). Но Петров признает свои ошибки (D). Следовательно, он поступит соЛогика высказываний гласно собственным убеждениям (B)?"[9] Формальна запись этого суждения:

Дедуктивный вывод:

• F3=¬CD – посылка, • F4=¬D – посылка, • F5=CB - заключение по формулам F1, F2 и правилу П9, • F6=¬B¬C - заключению по формуле F5 и правилу П6, • F7=¬BD - заключение по формулам F3 и F6 и правилу • F8=B - заключение по формулам F4, F7 и правилу m. t., ч.т.д.

На рис. 1.3 показан граф вывода этой задачи.

Пример 1.39. Доказать истинность заключения:

Дедуктивный вывод:

• F1=(AC) - посылка, • F2=(AB)(CB) - заключение по F1 и правилу П7, • F3=(BD) - посылка, • F4=(CB)(CD) - заключение по F3 и правилу П7, • F5=(AB)(CD) - заключение по F2 и F4 и правилу П9, • F6=(AВ) - посылка, • F7=(CD) - заключение по F5 и F6 и правилу m. p., ч.т.д.

На рис. 1.4 показан граф вывода этой задачи.

Пример 1.40. Доказать истинность заключения:

Дедуктивный вывод:

• F1=(D&BE) - посылка, • F2=¬E - посылка, • F3=¬(D&B) - заключение по F1 и F2 и правилу m. t., • F4=(АВ)&(СD) - посылка, • F5=(AВ) - заключение по F4 и правилу П2, • F6=(СD) - заключение по F4 и правилу П2, • F7=(¬B¬A) - заключение по F5 и правилу П6, • F8=(¬D¬B) - заключение по F3 и закону де Моргана, • F9=(D¬B) - заключение по F8, • F10=(D¬A) - заключение по F7 и F9 и правилу П9, • F11=(С¬A) - заключение по F6 и F10 и правилу П9, • F12=(¬С¬A) - заключение по FII, ч.т.д.

На рис. 1.5 показан граф вывода этой задачи.

Пример 1.41. Доказать истинность заключения:

Дедуктивный вывод:

• F1=(¬D&¬N) - посылка, • F2=¬N - заключение по F1 и правилу П2, • F3=(MN) - посылка, • F4=¬M - заключение по F2 и F3 и правилу m. t, • F5=¬D - заключение по F1 и правилу П2, • F6=(¬D&¬M) - заключение по F4 и F5 и правилу П1, • F7=¬(DМ) – заключение по F6 и закону де Моргана, • F8=(( AB)C) - посылка, • F9=(С (DМ)) - посылка, • F10=((AB)(DM)) - заключение по F8 и F9 и правилу • F11=¬(AB) - заключение по F7 и F10 и правилу m.t., • F12=(¬А&¬B) - заключение по F11 и закону де Моргана, • F13=¬A - заключение по F12 и правилу П2, ч.т.д.

На рис. 1.6 показан граф вывода этой задачи.

Пример 1.42. “Если команда А выигрывает в футболе то город А’ торжествует, а если выигрывает команда В, то торжествовать будет город В’. Выигрывают или А или В.

Однако, если выигрывают А, то город В’ не торжествует, а если выигрывают В, то не будет торжествовать город А’.

Следовательно, город В’ будет торжествовать тогда и только тогда, когда не будет торжествовать город А’”[3].

Формальна запись этого суждения:

Дедуктивный вывод:

• F1=(AA’)&(BB’) – посылка, • F2=(AA’) - заключение по формуле F1 и правилу П2, • F3=(BB’) - заключение по формуле F1 и правилу П2, • F4=(A¬B’)&(B¬A’) - посылка, • F5=(A¬B’) - заключение по формуле F4 и правилу П2, • F6=(B¬A’) - заключение по формуле F4 и правилу П2, • F7=(B’¬A) - заключение по формуле F5 и правилу П6, • F8=(A’¬B) - заключение по формуле F6 и правилу П6, • F9=(AB) – посылка, • F10=¬AB - заключение по формуле F9, • F11=¬A¬A’ - заключение по формулам F6, F10 и правилу П9, • F12= B’¬A’ - заключение по формулам F7, F11 и правилу П9, • F13= ¬A’¬A - заключение по формуле F2 и правилу • F14=¬A’B - заключение по формулам F10, F13 и правилу П9, • F15=¬A’B’ - заключение по формулам F3, F14 и правилу П9, • F16= (B’¬A’)&(¬A’B’) (B’¬A’) – заключение по формулам F12, F15 и правилу П1, ч.т.д.

На рис. 1.7 показан граф вывода этой задачи.

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

Существует эффективный алгоритм логического вывода - принцип (или метод) резолюции Дж. Робинсона.

Он показал, что выводимость формулы В из множества посылок и аксиом F1, F2, F3, …, Fn равносильна доказательству теоремы:

|(F1&F2&F3&...&FnB), |(¬(F1&F2&F3&...&Fn)B), |¬(F1&F2&F3&...&Fn&¬B).

Из последней формулы следует, что заключение В истинно тогда и только тогда, когда формула (F1&F2&F3&...&Fn&(B)) есть КНФ, то все Fi иB должны быть приведены также к виду КНФ. Так может быть сформировано множество элементарных дизъюнктов К={D1, D2, …, Dm}. Два дизъюнкта Di и Dj, содержащие одинаковые пропозициональные переменные, но с противоположными знаками, объединяют в третий дизъюнкт Dk=(DiDj)– резольвенту, из которой удаляются эти переменные. Пропозициональные переменные с противоположными знаками называют контрарными атомами. Если Di=А, Dj=¬A, то Dk=(DiDj)=(А¬A) есть пустая резольвента, которую обозначают символом. Многократно применяя процедуру объединения дизъюнктов множества K с контрарными атомами стремятся получить пустую реМатематическая логика зольвенту. Наличие пустой резольвенты есть решение |(F1&F2&F3&...&Fn&B).

Алгоритм вывода по методу резолюции:

Шаг 1: принять отрицание заключения, т.е. ¬В, Шаг 2: привести все формулы посылок и отрицания заключения в конъюнктивную нормальную форму, Шаг 3: выписать множество дизъюнктов всех посылок и отрицания заключения: K = {D1, D2, …, Dk }, Шаг 4: выполнить анализ пар множества K по правилу:

«если существуют дизъюнкты Di и Dj, один из которых (Di) содержит атом А, а другой (Dj) - атом ¬А, то соединить эту пару логической связкой дизъюнкции (DiDj) и сформировать новый дизъюнкт - резольвенту, исключив контрарные атомы А и ¬А, а резольвенту включить в множество К», Шаг 5: если в результате соединения дизъюнктов будет получена пустая резольвента (пустой дизъюнкт), то конец (доказательство подтвердило истинность заключения), иначе включить резольвенту в множество дизъюнктов K и перейти к шагу 4; по закону идемпотентности любой дизъюнкт и любую резольвенту можно использовать неоднократно, т.е. из множества К не следует удалять использованные в соединении дизъюнкты.

Пример 1.43. Доказать истинность заключения по методу резолюции: (A & B C), (C & D ¬M), (¬N D & M) Вывод по методу резолюции:

• A&BC¬(A&B)C(¬A¬BC) – посылка содерЛогика высказываний жит один дизъюнкт, • C&D¬M¬(C&D)¬M(¬C¬D¬M) – посылка содержит один дизъюнкт, • ¬ND&M¬¬ND&M(ND)&(NM) – посылка содержит два дизъюнкта, • ¬((A&B)N)A&B&¬N - отрицание заключения содержит три одно-литерных дизъюнкта, • множество дизъюнктов:

K={(¬A¬BC), (¬C¬D¬M), (ND), (NM), A, B, ¬N}, • (MN)¬N М - резольвента, • множество дизъюнктов:

K1={(¬A¬BC), (¬C¬D¬M), (ND), (NM), A, B, M, ¬N}, • (¬C¬D¬M)M (¬C¬D) - резольвента, • множество дизъюнктов:

K2={(¬A¬BC), (¬C¬D¬M), (ND), (NM),A, B, M, ¬N, (¬C¬D)}, • (¬A¬BC)(¬C¬D) (¬A¬B¬D) – резольвента, • множество дизъюнктов:

K3={(¬A¬BC), (¬C¬D¬M), (ND), (NM), A, B, M, ¬N, (¬C¬D), (¬A¬B¬D)}, • (¬A¬B¬D)A (¬B¬D) - резольвента, • множество дизъюнктов:

K4={(¬A¬BC), (¬C¬D¬M), (ND), (NM), A, B, M, ¬N, D, (¬C¬D), (¬A¬B¬D)}, (¬B¬D) }, • (¬B¬D)B ¬D - резольвента, • множество дизъюнктов:

K5={(¬A¬BC), (¬C¬D¬M), (ND), (NM), A, B, M, ¬N, D, (¬C¬D), (ABD)}, (BD), D}, • D(ND) N - резольвента, • множество дизъюнктов:

K6={(ABC), (CDM), (ND), (NM), A, B, M, N, D, (CD), (¬A¬B¬D)}, (¬B¬D), ¬D, N}, • N¬N - пустая резольвента, ч.т.д.

Для демонстрации удобно использовать граф типа дерево, корнем которого является один из дизъюнктов отрицания заключения, а листьями– дизъюнкты всех посылок и отрицания заключения. Тогда узлами графа являются резольвенты. На рис. 1.8 показан граф вывода этой задачи.

Пример 1.44. Доказать истинность заключения:

Вывод по методу резолюции:

• (AB)&(CD) (¬AB)&(¬CD) - посылка, • D&BM ¬(D&B)M (¬D¬BM) - посылка, • ¬M - посылка, • ¬(¬A¬C ) A &C - отрицание заключения, • множество дизъюнктов:

K ={A, C, ¬M, (¬AB), (¬CD), (¬D¬BM)}, • A(¬AB) B - резольвента, • множество дизъюнктов:

K ={A, C, ¬M, (¬AB), (¬CD), (¬D¬BM), B}, • B(¬D¬BM) (¬DM) - резольвента, • множество дизъюнктов:

K ={A, C, ¬M, (¬AB), (¬CD), (¬D¬BM), B, (¬DM)}, • (¬DM)(¬CD) (¬CM) - резольвента, • множество дизъюнктов:

K ={A, C, ¬M, (¬AB), (¬CD), (¬D¬BM), B, (¬DM), (¬CM)}, • (¬CM)¬M ¬C - резольвента, • ¬CC - пустая резольвента, ч.т.д.

На рис. 1.9 показан граф вывода этой задачи.

Пример 1.45. Доказать истинность заключения:

Вывод по методу резолюции:

• ((¬А¬B¬А &¬B)С)(АC)&(BC) - посылка, • (ABА&B)¬C)(¬А¬C)&(¬B¬C) -посылка, • ¬(C¬A)C&А – отрицание заключения, • множество дизъюнктов:

K={(АC), (BC), (¬А¬C), (¬B¬C), C, А }, • С(¬А¬C) = ¬А – резольвента, • множество дизъюнктов:

K1={(АC), (BC), (¬А¬C), (¬B¬C), C, А, ¬А }, • ¬А(АC) = C – резольвента, • множество дизъюнктов:

K2={(АC), (BC), (¬А¬C), (¬B¬C), C, А, ¬А }, • С(¬B¬C) = ¬B –резольвента, • множество дизъюнктов:

K3={(АC), (BC), (¬А¬C), (¬B¬C), C, А, ¬А, ¬B • ¬B(BC) = C – резольвента, • множество дизъюнктов:

K4={(АC), (BC), (¬А¬C), (¬B¬C), C, А, ¬А, ¬B • C¬A = (C¬A) – резольвента, • множество дизъюнктов:

K5={(АC), (BC), (¬А¬C), (¬B¬C), C, А, ¬А, ¬B, (CA)}, • (C¬A) (¬А¬C) = ¬А – резольвента, • множество дизъюнктов:

K5={(АC), (BC), (¬А¬C), (¬B¬C), C, А, ¬А, ¬B, (CA)}, • (C¬A) (¬А¬C) = ¬А – резольвента, • ¬АA = - пустая резольвента, ч.т.д.

На рис. 1.10 показан граф вывода этой задачи.

Обратите внимание, уже после формирования первой резольвенты (¬А) из дизъюнктов второй посылки и отрицания заключения среди множества дизъюнктов появились два контрарных дизъюнкта (А и ¬А), соединение которых формирует пустую резольвенту. Следовательно, первая посылка - излишняя в доказательстве истинности заключения. Это подтверждается истинностью дизъюнкта (¬А¬C), что равносильно истинности (С¬А). Однако, в настоящем выводе был продолжен поиск решения при наличии дизъюнктов первой посылки. Так как резольвенМатематическая логика ты включаются в множество дизъюнктов, то возможно их многократное использование в процессе вывода. Это оправдано законом идемпотентности, т. е. Di=Di&Di&...&Di..

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

1.1.1. Написать формулы суждений:

а) «подготовка специалистов высокой квалификации возможна лишь на базе всемерного развития вузовской науки, усиления связи вузовской, академической и отраслевой науки, обеспечения единства научной и учебной работы, широкого привлечения студентов к научным исследованиям», b) «хлеба уцелеют в различных климатических и погодных условиях тогда и только тогда, когда будут выполнены все мелиоративные работы, а если хлеба не уцелеют, то фермеры обанкротятся и оставят фермы» [21], c) «если я поеду автобусом и автобус опоздает, то я опоздаю на работу, а если я опоздаю на работу, то я не сделаю в срок важную работу, а если я не сделаю в срок важную работу, то я стану огорчаться; следовательно, если я не поеду автобусом, то я сделаю в срок важную работу и не стану огорчаться» [3], d) «обвиняемый может быть либо исполнителем, либо организатором совершенного преступления. Обвиняемый является организатором преступления. Следовательно, он не является исполнителем преступления»[9], e) «если бы Цезарь был суеверен, то он уступил бы просьбам Кальпурнии не идти в сенат. Если бы он был осторожен, он удалил бы Брута. Но Цезарь не уступил просьбам Кальпурии, не удалил Брута».

1.1.2. Доказать тождества:

а) (AB)&(A¬B)A, b) (AB)&(BC)&(CA)(A&B)(B&C)(C&A), c) (AB)&(AC)&(BD)&(CD)((A&D)(B&C)), d) (AB)&(BC)&(CA) ((A&B)(B&C)(C&A)), ((A&B)(A&D)(B&D) C), f) (A&B)((AB)&(¬A¬B) (AB).

1.1.3. Привести формулу к виду ДНФ и КНФ:

а) (((AB)(C¬A))(¬B¬C)), b) (((((AB)¬A)¬B)¬C)C), c) (A(BC))(A¬C)(A¬B).

d) (¬(A&(BC)((A&B)C)).

e) (СA)(¬(BC)A).

1.1.4. Выполнить подстановку:

1.1.5. Доказать истинность заключения по методу дедукции и принципу резолюции:

Расчетно-графическая работа • составить таблицу истинности, число строк которой равно 2n, где n – число пропозициональных переменных, а число столбцов равно сумме числа пропозициональных переменных, посылок и заключения, а также столбец для конъюнкции всех посылок и столбец для импликации заключения из конъюнкции всех посылок; выделить штриховкой строки, в которых истинны все посылки и заключение; дать объяснения, • доказать истинность заключения методом дедукции и нарисовать граф дедуктивного вывода, • доказать истинность заключения методом резолюции и нарисовать граф вывода пустой резольвенты.

ВариДоказать истинность заключения Расчетно-графическая работа (AB) (A(BC)) (A&D) | C (AB) (CD) (B¬D) (C&¬D) | (AB) (A(BC)) ¬(CD) | (AB) (BC) (CD) A&B | B&D (A(BC)) (AB) ¬(CD) | (A(BC)) (¬DA) B | (¬DC) (A(BC)) (AB) A&D | C&D (A(BC)) ((AC)D) ¬D | ¬B (BA) (B(¬AC)) (¬С¬D) | (BA) (B(AC)) ¬(CD) | (BA) (B(¬AC)) (B&D) | C&D 32 (BA) (CA) ((AC)(CD)) (BA) (AC) (DC) (BD) | (CD) (B(AC)) (BA) ¬C&¬D | (B(AC)), (BA), (CD), ¬D | ¬B 35.

(B(AC)) (BA) ¬C&¬D | (¬AB) (C¬B) (¬С&¬D) | ¬(AD) (¬A¬B) (CA) (B¬D) | (¬C¬D) 41 (¬A¬B) (CA) B&D|DC (AB) (A(BC)) (DB) | (¬CD) (AB) (¬BC)(¬CD) (AC) | (AB) (A(BC)) (DB) | (¬CD) (A&BC) (¬D¬C) D | ¬A¬B) (A&BA&BС) ¬C | (AB) Логика предикатов – это расширение возможностей логики высказываний, позволяющее строить высказывания с учетом свойств объектов высказывания или отношений между ними.

Если неизвестны объекты высказывания или отношения между объектами высказывания, то такое высказывание называют высказывательной функцией. Высказывательную функцию иначе называют предикатом * и обозначают символом Р(…). Аргументами предиката являются предметные переменные и предметные постоянные.

Предметные переменные и предметные постоянные обозначают строчными буквами латинского алфавита {х, у, z,...} и {а, в, с, …} соответственно. Предикаты бывают одноместные Р(.), когда его аргументом является одна предметная переменная, и многоместные P(.,., …,.), когда его аргументами могут быть несколько предметных переменных и/или предметных постоянных. Одноместные предикаты выражают свойства предметных переменных, а многоместные - отношения между объектами высказывательной функции. Высказывательная функция приобретает значение высказывания только при замене предметных переменных предметными постоянными.

Множество, на котором даны предметные переменные и предметные постоянные, называют областью опреpraedicatum - логическое сказуемое деления предиката или универсумом. Множество, на котором предикат принимает значение «истины» называют множеством истинности предиката Р(x) или P(x1, x2, …, xn).

Например, а) если на множестве натуральных чисел задать функции:

Р1(x):= «x - простое число», P2(6, y):= «y меньше ‘6’», P3(6, y, z):= «z есть частное от деления числа ‘6’ на y», где x, y, z есть предметные переменные, а ‘6’ – предметная постоянная, то высказываниями будут P1(‘3’) = и, P1(‘4’) = л, б) если на множестве имен индивидов, учебных заведений и специальностей задать следующие предикаты:

P4(x):= «х – студент», P5(‘Сидоров’, ‘КГТУ’) = л P6(‘Петров’, 'прикладная информатика’) = и, P6– (‘Сидоров’, 'прикладная информатика’) = л.

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

Так, суждение, в котором утверждается или отрицается наличие каких-либо свойств или отношений у части предметных переменных, называют частным суждением.

Для формального описания таких суждений используют логический оператор «x», который получил название квантор существования. Предикат или сложную высказывательную функцию записывают после квантора существования в круглых скобках x(Р(x1, x2, …, хi,…, xn) или x(F(x1, x2, …, хi,…, xn). На естественном языке эта запись означает «существуют такие предметные переменные хi, для которых Р(хi) истинно». Иначе это выражают словами «один», «несколько» или «часть хi» и т.п.

Пример 1.46. Если на множестве целых чисел N дана предметная переменная xN и дан предикат, определяющий свойство предметной переменной, P1(x):= «быть простым числом», то может быть записано частное суждение x(P1(x)):= «часть целых чисел являются простыми числами». Этот предикат на множестве N (область определения) выделяет подмножество простых чисел X= {2, 3, 5, 7, 11,..., }.

Пример 1.47. Если на множестве N даны предметные переменные xN и yN и дан предикат, устанавливающий отношение между ними, P2(x, y ):= «y меньше x», то при x=’6’ может быть записано частное суждение y(P2(‘6’, y)):=«есть целые числа, которые меньше ‘6’». Этот предикат на множестве N при заданной предметной постоянной выделяет подмножество Y= {1, 2, 3, 4, 5}.

Пример 1.48. Если на множестве N даны предметные переменные x, y, zN и предикат, устанавливающий отношение между ними: P3(x, y, z):=«существует такое z, которое является частным от деления x на y», то при x=’6’ и y=’2’ может быть записано частное суждение z(P3(‘6’, ‘2’, z)):=«существует такое z, которое является частным от деЛогика предикатов ления ‘6’ на ‘2’». Этот предикат на множестве N выделяет единственное число z=’3’, для которого P3(‘6’, ‘2’, ‘3’)= и.

Пример 1.49. Если даны на множестве индивидов М предметная переменная xМ, на множестве учебных заведений Y - предметная переменная yY, на множестве специальностей Z - предметная переменная zZ и предикаты P4(x):= «x – студент», P5(x, y):= «x обучается в университете y», P6(x, z):= «x обучается по специальности z» и P7(x):= «x имеет зачетную книжку», то x(P4(x):= «существуют х, которые являются студентами», y(P5(x, y):= «существуют x, которые обучаются в yниверситете», z(P6(x, z):= «существуют x, которые обучаются по специальности z», x(P4(x)&¬P7(x)):= «существуют студенты, которые не имеют зачетной книжки», xy(P4(x) P5(x, y)):= «если x – студент, то он обучается в каком-то университете y», xyz(P4(x) P5(x, y)& P6(x, z)):= «если x –студент, то он обучается в каком-то университете y по какой-то специальности»

Частное суждение по нескольким переменным требует указания кванторов существования для каждой переменной перед предикатом. Например, x y z...(Pn(x, y, z,...)).

Пример 1.50. Частное суждение xy(P4(x)&¬P5(x, y)&¬P7(x)):= «существуют студенты (x) некоторых университетов (y), которые не имеют зачетной книжки» и т.п.

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

Суждение, в котором утверждается или отрицается наличие каких-либо свойств для всех предметных переменных области определения или отношений между ними, называют общими суждениями. Как правило, эти суждения в естественном языке отмечают словами «все», «каждый», «любой» и т.п. Для формального описания таких суждений используют логический оператор – «x», который получил название квантор всеобщности. Предикат или сложную высказывательную функцию записывают после квантора всеобщности в круглых скобках x(Р(x1, x2, …, xn)) или x(F(x1, x2, …, xn )). На естественном языке эта формальная запись означает «для всех предметных переменных xi значение Р(хi) истинно» или «для каждой предметной переменной хi значение Рn(хi) истинно»..

Если общее суждение распространяется на несколько предметных переменных, то перед предикатом или сложной высказывательной функцией записывают кванторы всеобщности для каждой предметной переменной, т.е.

x y z... (P(x, y, z,..., )).

Например, x(P4(x)&P7(x)):= «все студенты имеют зачетные книжки», xy(P4(x)&P5(x,y)&P7(x)):= «все студенты всех университетов имеют зачетные книжки», x(P4(x)&P5(x, ‘КГТУ’)&P6(x, ‘прикладная информатика’)& &P7(x)):= «все студенты, обучающиеся в университете КГТУ по специальности «прикладная информатика», имеют зачетные книжки», xz(P4(x)&P5(x, ‘КГТУ’)&P6(x, z)&P7(x)):= «все студенты университета КГТУ, обучающиеся на всех специальностях, имеют зачетные книжки», xyz(P4(x)& P5(x, y)&P6(x, z)&P7(x)):= «все студенты всех университетов, обучающиеся на всех специальностях, имеют зачетные книжки».

Существуют предикаты, для которых область определения по различным предметным переменным ограничивают различными кванторами.

Например, xy(P2(x, y)):= «для любого целого числа x существует меньшее число y» или xyz(P3(x, y, z)):= «среди целых чисел существует число z, которое является частным от деления некоторого числа x на некоторое число y».

Интересно отметить влияние на высказывание смены или перестановки кванторов.

xy(P2(x, y)):= «существует целое число x, которое больше любого целого числа y». Это высказывание явно ложное.

xy(P2(x, y)):= «x больше y для любых целых чисел».

Это высказывание также ложное.

xy(P2(x, y)):= «существуют целые числа x, для которых существуют меньшие число y». Это высказывание истинное, но оно ограничивает область определения предиката.

xyz(P3(x, y, z)):= «любое целое число z может быть частным от деления некоторого числа x на некоторое число y». Это высказывание истинно для y=1 и любого z.

Из рассмотренных примеров следует, что изменение кванторов или порядка их следования существенно измеМатематическая логика няют смысл высказывания. Поэтому при исследовании текстов естественного языка следует очень аккуратно переходить к их формальному описанию.

Предметную переменную, если она находится под действием квантора, называют связанной переменной. И наоборот, если ее вхождение свободно от квантора, называют свободной переменной.

Например, y(P2(x, y)):= «для любого целого числа существуют меньшие числа». В этом примере x – свободная, а y –связанная переменная квантором существования.

xy(P6(x, y)&P7(x)):= «во всех университетах существуют (есть) студенты, которые не имеют зачетной книжки». В этом примере x и y –связанные переменные кванторами существования и всеобщности соответственно.

x y(Р1 (x, y)z(Р2(z)) все предметные переменные являются связанными.

z(Р1(z)&x(Р2(x, z))(Р2(z, y)(Р2(x, z)) предметные переменные x и z связанные, а y – свободная.

Cвободная переменная может быть востребована на следующем шаге алгоритма, а связанная переменная служит для вычисления на данном шаге алгоритма значения предиката «и» или «л».

Между элементами области определения предиката могут быть заданы функциональные отношения. На это указывает функциональный символ f(x1, x2,..., xn).

Например, дату можно рассматривать как функцию, заданную на предметных переменных число, месяц, год. В этом случае функциональным символом является ”дата”, а аргументами, и. Для предметных та””(“ ”,””,””)”. Для предметных постоянных она формирует высказывание. Например, «дата(1 января 2005 года)». Описание треугольника также можно рассматривать как некоторую структуру на предметных переменных, описывающих координаты вершин треугольника. Тогда функциональным символом является “треугольник”, а аргументами этой функции будут координаты вершин,,, Для предметных переменных структура этой функции есть ”треугольник””(“”,””,””)”. При подстановке предметных постоянных будет дано описание конкретного треугольника.

Алгебры предикатов есть Апред.=, где T= {T1, T2, T3, T4} - носитель алгебры, при этом Т1= {x, y, z,...} - множество предметных переменных, Т2= {a, b, c,...} – множество предметных постоянных, Т3={f1, f2, f3,...} – множество функциональных символов и Т4=(P1, P2, P3,...} – множество предикатных символов, F={F1, F2, F3} – сигнатура алгебры, при этом F1= {¬, &,,, } - множество логических связок, F2= {, } множество кванторов, F3= {} - символ равносильности формул.

Любую предметную переменную и предметную постоянную предиката называют термом и обозначают символом ti.

Если fi - функциональный символ и t1, t2,...,, tn - его термы, то f(t1, t2,…, tn) также есть терм, где n –число арi гументов функции, i –индекс функции.

Никаких иных термов нет.

Если Pi – предикатный символ и t1, t2,...,, tn - термы, F= P(t1, t2,...,, tn ) - элементарная формула.

Если F1 и F2 - формулы, то ¬F1, ¬F2, (F1&F2), (F1F2), (F1F2), (F1F2) - также формулы.

Если F - формула, a x - предметная переменная, входящая в формулу F, то x(F) и x(F) - также формулы.

Никаких иных формул нет.

Простейшими операциями в логике предикатов являются те же операции, что в алгебре высказываний.

Отрицание (¬F(t1, t2,…, tn)) есть одноместная операция, посредством которой из данной формулы F(t1, t2,…, tn) получают ее отрицание.

Пример 1.51. Если Р(х. ‘a’):= «х находится на a», где 'a’= 'стол', то выводимы формулы:

а) x(¬Р(х, ‘a’)):= «для всех х верно, что х не находится на столе».

b) ¬x(Р(х, ‘a’)):= «не для всех х верно, что х находится на столе», c) ¬x(Р (х, ‘a’)):= «нет таких х, для которых верно, что х находится на столе”.

Конъюнкция (F1(t11, t12,…, t1n)&F2(t21, t22,…, t2n)) есть двуместная операция, посредством которой из формул F1 и F2 получают новую формулу F (t11, t12,…, t1n, t21, t22,…, t2n ) с числом предметных переменных и постоянных, равным объединению их в исходных формулах. Значение формулы истинно тогда и только тогда, когда истинны обе формулы F1 и F2.

Пример 1.52. Если P1(х):= «выдающийся музыкант» и P2(х):= «талантливый писатель», то выводимы формулы:

а) x(P1(х))&x(P2(х)):= «существуют выдающиеся музыканты и существуют талантливые писатели», b) x(P1(х)&P2(х)):= «существуют лица, которые являются талантливыми писателями и выдающимися музыкантами».

с) ¬x(P1(х)&P2(х)):= «не все талантливые писатели являются выдающимися музыкантами».

Пример 1.53. Если х - предметная переменная (индивид), a - предметная постоянная (например ‘а’:= «Саша») и P1(х, ‘a’):= «х дружит с ‘a’», P2 (х, ‘a’):= «х встретил ’a’», то выводимы формулы :

а) x(P1 ‘a’)&P2 ‘a’)):= «Саша встретил друга», b) x(¬P1 ‘a’)&P2 ‘a’)):= «Саша встретил недрух,.(х, га», c) ¬x(P1 ‘a’)&P2 ‘a’)):= «не каждый встречный есть друг Саши», d) x(P1.(х, ‘a’)&(¬P2.(х, ‘a’))):= «есть друзья, с которыми Саша не встречается».

Обратите внимание, как меняется смысл каждого высказывания.

Дизъюнкция (F1(t11, t12,…, t1n)F2(t21, t22,…, t2n)) есть двуместная операция, посредством которой из формул F1 и F2 получают новую формулу F (t11, t12,… t1n, t21, t22,… t2n ) с числом предметных переменных и постоянных, равным объединению их в исходных формулах. Значение формулы ложно тогда и только тогда, когда ложны обе формулы F и F2.

Пример 1.54. Если предметные переменные х, у - города России и P1(х, y):= «транспортная связь х и у поездом», P2(х, y):= «транспортная связь х и у самолетом», P3(х, y):= «транспортная связь х и у автобусом», то выводимы формулы:

a) xy(P1 y)P2 y)P3 y)):= «для всех горох,.(х,.(х, дов России (x и y) возможна транспортная связь поездом, автобусом или самолетом», b) ¬xy(P1 (х, y)¬P2 (х, y)¬P3 (х, y)) - «не для всех городов x существуют города y, между которыми нет транспортной связи автобусом или самолетом, но есть поездом».

Импликация (F1(t11, t12,…, t1n)F2(t21, t22,…, t2n)) есть двухместная операция, посредством которой из формул F и F2 получают новую формулу F(t11, t12,…, t1n, t21, t22,…, t2n ) с числом предметных переменных и постоянных, равным объединению их в исходных формулах. Значение формулы ложно тогда и только тогда, когда F1 истинно, а F2 - ложно.

Пример 1.55. Если х - индивид, P1(x):= «быть судьей», P2(x):= «быть юристом», то выводимы формулы:

a) x(P1(x)P2(x)):= «все судьи – юристы», b) ¬x(P2(x)P1(x)):= «неверно, что все юристы – суЛогика предикатов дьи», Пример 1.56. Если х - предметная переменная для индивида, P1(x):= «x принадлежит к большинству», P2(x):= «x стремится к миру», то выводима формула:

a) x(P1(x)&(P1(x)P2(x)):= «большинство стремится к миру».

b) x(¬P1(x)&(P1(x)P2(x)):= «существуют люди, не принадлежащие к большинству, которые не стремятся к миру».

Эквивалентность (F1(t11, t12,…, t1n)F2(t21, t22,…, t2n)) есть двуместная операция, посредством которой из формул F1 и F2 получают новую формулу F (t11, t12,…, t1n, t21, t22,…, t2n ) c числом предметных переменных и постоянных, равным объединению их в исходных формулах. Значение формулы истинно тогда и только тогда, когда обе формулы F1 и F2 имеют одно и то же значение истины или лжи.

Пример 1.57. Если х - предметная переменная, Р(х) предикат, то выводимы формула:

a) x(P(x))¬x(¬P(x)):= «существует переменная х, для которой Р(х) истинно эквивалентна не для всех х Р(х) ложно».

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

1.2.1.2. Правила записи сложных формул Пример 1.58. Дано «некоторые действительные числа являются рациональными». В этом суждении есть два предиката P1(x):= «x - действительное число» и P2(x):= «x рациональное число».

Формула этого суждения есть F=x(P1(x)&P2(x)).

Ошибочными являются формулы F=x(P1(x)P2(x)):= «некоторые числа, если они действительные, то они рациональные», и F=x(¬P1(x)P2(x)):= «некоторые числа не являются действительными или являются рациональными».

Пример 1.59. «Некоторые социал-демократы уважают всех демократов. Ни один социал-демократ не уважает ни одного коммуниста. Следовательно, ни один демократ не является коммунистом». В этом суждении три одноместных предиката P1(x):= «быть социал-демократом», P2(x):= «быть демократом», P3(x):= «быть коммунистом» и один двухместный предикат P4(x, y):= «x уважает y».

Формула сложного суждения имеет вид:

x (P1 (x) & y (P2 (y) P4 (x, y))), ¬x (P1 (x) y (P3 (y) ¬P4 (x.y))) Пример 1.60. «Ни один торговец наркотиками не является наркоманом. Некоторые наркоманы привлекались к ответственности. Следовательно, некоторые люди, привлекавшиеся к ответственности, не являются торговцами наркотиков»[15].

В этом суждении три предиката P1(x):= «быть торговцем наркотиков», P2(x):= «быть наркоманом», P3(x):= «привлекаться к ответственности».

Формула этого суждения имеет вид:

Примеры позволяют сформулировать некоторые правила:

• каждое вхождение логической связки «¬» относится к формуле, следующей непосредственно за логической связкой справа, • каждое вхождение логических связок «&» или «» после расстановки скобок связывает формулы, непосредственно окружающие логическую связку, • логические связки по силе упорядочены так: ¬, &,, • за квантором общности чаще всего следует импликация, а за квантором существования - конъюнкции, • если формула содержит подформулу, то последняя не должна содержать кванторов, связывающих ту же переменную, что и квантор формулы, • значения всех предметных переменных и постоянных должны принадлежать одной области определения предиката или функции, • если в одной формуле есть кванторы всеобщности и существования, то при формализации суждений следует стремиться поставить квантор существования слева от всей формулы.

1.2.1.3. Законы алгебры предикатов Основные законы алгебры предикатов приведены в таблице 1.11.

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

Имя закона Коммутатив- xy(F(x, y)) yx(F(x, y))*, ности xy(F(x, y)) yx(F(x, y))*.

Дистрибутив- x(F1(x)F2(x))**, ности * - только для формул с кванторами x по одной переменной x.

** - только для формул с кванторами x по одной переменной x.

Идемпотентности x(F(x))&x(F(x)) x(F(x)) для Исключенно- x(F(x))¬x(F(x))= и для го третьего Противоречия x(F(x))&¬x(F(x))= л для Отрицание кванторов ¬x(F(x)), Две формулы Fi(t1, t2, …, tn) и Fj (t1, t2, …, tn) называются равносильными, если они при одинаковых наборах термов имеют одинаковое значение. Равносильность формул будем обозначать символом «», т.е. (F1 F2). Если две формулы равносильны F1(t1, t2, …, tn)F2(t1, t2, …, tn), то они эквивалентны. Эквивалентность формул будем обозначать символом «», т.е. (Fi(t1, t2, …, tn)Fi(t1, t2, …, tn)). И наоборот, если две формулы эквивалентны (FiFi), то они равносильны (F1 F2).

Если в составе формулы F есть формула Fi, т.е. F(t1, t2, …, Fi, …, tn), и для Fi существует эквивалентная формула Fj, т.е. (FiFj), то возможна подстановка формулы Fj в формулу F без нарушения истинности формулы, т.е.

Докажем равносильность некоторых законов.

• Дано x(F1(x))&x(F2(x))x(F1(x)&F2(x)).

Если предикаты F1(x)=и, F2(x)=и, F1(x)&F2(x)=и, то истинны x(F1(x))=и, x(F2(x))=и, x(F1(x))&x(F2(x))=и, x(F1(x)&F2(x))=и.

Если предикаты F1(x)=л, F2(x)=и, F1(x)&F2(x)=л, то ложны x(F1(x)&F2(x))=л.

Следовательно, x(F1(x))&x(F2(x))x(F1(x)&F2(x)).

• Дано x(F1(x))x(F2(x)) x(F1(x)F2(x)).

Если предикаты F1(x)=и, F2(x)=и, F1(x)F2(x)=и, то истинны x(F1(x))=и, x(F2(x))=и, x(F1(x))x(F2(x))=и, x(F1(x) F2(x))=и.

Если предикаты F1(x)=л, F2(x)=и, F1(x)F2(x)=л, то ложны x(F1(x))=л, x(F1(x))x(F2(x))=л, x(F1(x)F2(x))=л.

Следовательно, x(F1(x))x(F2(x))x(F1(x)F2(x)).

• Дано x(¬F(x))¬x(F(x)).

Если предикат ¬F(x)=и, а F(x)=л, то x(¬F(x))=и, x(F(x))=л, ¬x(F(x))=и.

Если предикат ¬F(x)=л, а F(x)=и, то x(¬F(x))=л, x(F(x))=и, ¬x(F(x))=л.

Следовательно, x(¬F(x)) ¬x(F(x)).

Если в формуле F, содержащей свободную переменную x, выполнить всюду подстановку вместо переменной x терма t, то получим формулу F(t).Этот факт записывают так: x Подстановка называется правильной, если в формуле всюду вместо свободной переменной x выполнена подстановка терма t.

Например, Это - правильная подстановка, так как вместо свободной переменной можно подставить другую переменную.

Это - правильная подстановка, так как вместо свободной переменной можно подставить функцию.

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

Это - неправильная подстановка, так как связанная x заменена свободной переменной.

Это - неправильная подстановка, так как предикат P2(.) попадает в область действия квантора x3.

1.2.1.4. Эквивалентные преобразования формул Пример. 1.61. F=¬x1x2(P1 (х1)x3 (P2 (х1, x3)P3(x2, x3))).

Упростить алгебраическое выражение.

• Выполнить операцию отрицания:

F=x1¬x2(P1 (х1)x3 (P2 (х1, x3)P3(x2, x3))), F=x1x2(¬(P1 (х1)x3 (P2 (х1, x3)P3(x2, x3)))).

• Удалить логическую связку «»:

F=x1x2¬(¬P1 (х1)x3 (P2 (х1, x3)P3(x2, x3))).

• Выполнить операцию отрицания:

F=x1x2(P1 (х1) &¬x3 (P2 (х1, x3)P3(x2, x3))), F=x1x2(P1 (х1) &x3(¬(P2 (х1, x3)P3(x2, x3)))), F=x1x2(P1 (х1) &x3 (¬P2 (х1, x3)&¬P3(x2, x3))).

• Перенести квантор x3 влево:

F=x1x2x3 (P1 (х1) &¬P2 (х1, x3)&¬P3(x2, x3)).

Пример 1.62. F=x(P1(х)¬P2(х))¬(x(P1(х)) &x(P2(х))).

Упростить алгебраическое выражение.

• Удалить логическую связку «»:

F=¬(x(¬P1(х)¬P2(х)))¬(x(P1(х)) &x(P2(х))).

• Выполнить операцию отрицания:

F=x(¬(¬P1(х)¬P2(х)))x(¬P1(х))x(¬P2(х)), F=x(P1(х)&P2(х))x(¬P1(х))x(¬P2(х))).

• Применить закон дистрибутивности по квантору x:

F=x(P1(х)&P2(х)¬P2(х))x(¬P1(х), F=x((P1(х)¬P2(х))&(P2(х)¬P2(х)))x(¬P1(х)).

• Применить закон исключенного третьего:

F=x((P1(х)¬P2(х)))x(¬P1(х)).

• Применить закон де Моргана:

F=x((P1(х)¬P2(х)))¬x(P1(х)).

• Применить закон дистрибутивности по квантору x:

F=x(P1(х))x(¬P2(х))¬x(P1(х)).

• Применить закон исключенного третьего:

F=x(¬P2(х))и=и.

Следовательно, x(P1(х)¬P2(х))¬(x(P1(х))& &x(P2(х))) - аксиома.

1.2.1.2. Предварённая нормальная форма Для удобства анализа сложных формул рекомендуется преобразовывать ее к нормальной форме. Если в алгебре высказываний приняты две нормальные формы ДНФ и КНФ, то в алгебре предикатов – кроме ДНФ и КНФ есть предварённая нормальная форма (ПНФ), суть которой сводится к разделению формулы на две части: префикс и матрицу. Для этого все кванторы выносят влево по правилам логики предикатов, формируя префикс, а логические связки соединяют предикаты формулы, формируя матрицу. В результате будет получена формула: x1 x …xn(M), где x1 x2 …xn - префикс формулы при {, }, а М – матрица формулы. Затем матрицу формулы преобразуют к виду КНФ для определения истинности заключения по правилам 1.1.1.5.

Алгоритм приведения формулы к виду ПНФ:

Шаг 1: исключить в формуле всюду логические связки (F1F2)=(F1F2)& (F2F1)=(¬F1F2)&(¬F2F1), (F1F2)=(¬F1F2), Шаг 2: продвинуть отрицание до элементарной формулы:

¬x(F)=x(¬F), ¬(F1F2)=(¬F1&¬F2), ¬x(F)=x(¬F), ¬(F1&F2)=(¬F1¬F2), Шаг 3: переименовать связанные переменные по правилу:

«найти самое левое вхождение предметной переменной – такое, что это вхождение связано некоторым квантором, но существует еще одно вхождение этой же переменной, затем сделать замену связанного вхождения на вхождение новой переменной. Операцию повторять пока возможна замена связанных переменных», Шаг 4: вынести кванторы новых связанных переменных влево, не нарушая их последовательности.

Шаг 5: преобразовать бескванторную матрицу к виду КНФ, т. е. М=D1&D2&D3&…, где Di=(FiFjFk…). Алгоритм приведения матрицы формулы к виду КНФ приведен в1.1.1.5.

Пример 1.63. Дано F=¬x1x2(P1(х1)x3 (P2(х1, x3)P3(x2, x3))). Привести формулу к виду ПНФ.

• Выполнить операцию отрицания:

F=x1(¬x2(P1(х1)x3(P2(х1, x3)P3(x2, x3)))), F=x1x2(¬(P1(х1)x3 (P2(х1, x3)P3(x2, x3)))).

• Удалить логическую связку «»:

F=x1x2(¬(¬P1(х1)x3(P2(х1, x3)P3(x2, x3)))).