Известно несколько методов упрощения формул алгебры логики. Однако эти методы весьма трудоемка, когда число переменных велико. При минимизации дизъюнктивных нормальных форм обычно используют операцию поглощения , где под функцией f понимается произвольная элементарная дизъюнкция или конъюнкция. Это свойство является очевидным следствием свойства дистрибутивности дизъюнкции. При преобразованиях коньюнктивных нормальных форм используется аналогичное свойство , вытекающее из свойств дистрибутивности, например из отношений
На практике часто применяют также операции склеивания и ,
получающиеся из формулы
Упрощение формул с помощью операций алгебры логики, как уже говорилось, весьма трудоемко. Если число переменных в функции не более пяти, удобным оказывается метод неопределенных коэффициентов, который применим как при аналитическом задании функции с помощью формулы, так и при задании ее с помощью таблицы значений. Пусть, например, значения функции заданы в виде таблицы. Напишем общее разложение этой функции:
При имеем
При
При
При
Подставляя значения функции из таблицы, получим все неизвестные коэффициенты. Поскольку число коэффициентов больше числа уравнений, то часть коэффициентов можно положить равными нулю. Обычно нулю полагают наиболее сложные коэффициенты. Рассмотрим процедуру нахождения аналитического минимального вида функции на примере.
Пример. Пусть f(0,0)=0, f(0,l) = 0, f(l,0)=0, f(1,1)=1. Подставляя эти значения в уравнения для определения коэффициентов, получаем .
Отсюда следует: . Таким образом,
функция алгебры логики имеет вид
Если функция зависит от трех и более переменных, то задавать таблицу ее значений в том виде, как мы это делай раньше, представляется слишком громоздким. В этом случае переменные разделяют на две группы и задают такую функцию в форме табл. 6 для случая, когда число аргументов равно трем.
Таблица 6
Переменные | ||||
I | I | |||
I | I |
Иногда значения функции бывают заданы не для всех наборов переменных . Это означает, что подобная функция не всюду определена. Однако формула алгебры логики всегда задает функцию, определенную всюду. Поэтому подобную функцию следует доопределить. Доопределение значений функции может проводиться произвольно, но лучше доопределять ее так, чтобы задающая ее аналитическая формула оказалась как южно более простой.
ПРЕДИКАТЫИ КВАНТОНЫ
Изложенные выше операции алгебры логики можно применять и к двоичным переменным, зависящим от переменных, принимающих значения из некоторого (не обязательно конечного) множества м. Такие функции называют предикатами в предметной области М. С помощью операций коньюнкции, дизъюнкции и отрицания можно записывать многие высказывания. К сожалению, этих операций недостаточно для выражения более сложных высказываний. Например, невозможно на изложенном математическом языке выразить фразу: "для любого >0 найдется > 0, такое, что как только ". Легко видеть, что для записи этой фразы в виде формулы необходимо еще формализовать на математическом языке (языке алгебры логики) понятая "существования" и "общности". Операции существования и общности, вводимые в математической логике (в логике предикатов), изображаются кванторами существования и общности. С их помощью рассматривавшийся выше язык исчисления высказываний расширяется до так называемого языка исчисления предикатов.
В математической логике запись f (х) = I означает, что суждение х обладает свойством f истинно. Предикат f(x), зависящий от одной переменной, называется одноместным предикатом, а если независимых переменных несколько, то - многоместным предикатом. Квантор существования обозначают обычно посредством , а квантор общности . Запись () f(x) означает, что существует такое х, для которого выполняется свойство f, Если, например, /(х)- предикат, означающий, что "x четно", то суждение ()f(x) будет истинным, если под х понимается, например, множество натуральных чисел, а суждение ( x)f(x) будет ложным, так как не все натуральные числа четны.
Квантор общности можно считать обобщением конъюнкция. В самом доле, если, например, , то запись
эквивалентна конъюнкция ,
а запись f(x) эквивалентна дизъюнкции .
В формулах предметная переменная, относящаяся к квантору, называется связанной переменной; например, в записи переменная является связанной, а переменная свободна. По аналогии, например, с переменной интегрирования связанную переменную можно обозначать любой буквой, переименовывая её в формулах произвольным образом.
Формула может включать несколько предикатов и несколько свободных переменных, например , где А, В,С,... - предикаты, а - свободные переменные. Если предикаты в этой формуле рассматривать в качестве переменных, то формула будет определять некоторый оператор T, отображающий пространство переменных предиката А,В,С... d n-мерный переменный предикат .
В логике исчисления предикатов не всякую формулу можно считать за формулу исчисления предикатов, а только такую, которая определяет осмысленную выражение. Кроме того, даже а осмысленных выражениях не допускается использование одной и той же переменной в качестве связанной и свободной. Формулы исчисления предикатов должны удовлетворить следующим условиям,
1. Всякий предикатный символ А(), рассматриваемый как функция от некоторых предметных переменных, считается формулой, а все предметные переменные этого предиката являются свободными переменными; формулами считаются также I (истина) и 0 (ложь).
2. Если Ф(,А,В,С,...)- формула исчисления высказываний, где А,В, С,.,, - двоичные переменные, то она останется формулой при замене A,B,C,.,, на любые формулы если любая свободная переменная в любой из формул не будет входить
в качестве связанной переменной ни в одну из других формул; каковы были переменные (предметные) в формулах , т.е. свободными или связанными, такими они должны остаться и в сложной формуле Ф().
3. Если А(... ...)- формула, в которой - свободная переменная, то выражения и также являются формулами, в которых переменная оказывается связанной, а остальные переменные остаются такими же, какими они были в исходной формуле А.
Все формулы в логике предикатов должны удовлетворять перечисленным требованиям. Если в п. 3 формула А(.... ...) содержит какие-либо кванторы, то они считаются подчинёнными квантору() или , примененному к формуле А,
В общем случае квантор имеет единичный ранг, если ему не подчинены никакие другие кванторы, Квантор имеет ранг K+1, если в формуле, на которую он действует, есть хотя бы один квантор ранга К и нет кванторов большего ранга. Внешний квантор формулы всегда имеет наивысший ранг. Наивысший ранг формулы называется кванторной глубиной формулы.
Формулы исчисления предикатов, как включающие, так и не включающие кванторы, допускают многие из тех тождественных преобрааований, которые рассматривались выше. Тождественные преобразования формул, включающих кванторы, должны проводиться с учетом специфики последних. Определенную помощь здесь оказывает тот факт, что между квантором общности и конъюнкцией, с одной стороны, и квантором существования и дизъюнкцией, о другой стороны, существует тесная связь, отмеченная выше.
Формулы алгебры логики и , определяющие эквивалентности, вытекающие из правила де Моргана, переносятся и на формулы исчисления предикатов, включающие кванторы; при этом отрицание квантора общности заменяется квантором существования, и наоборот, например: ()
;здесь квантор существует неявно предполагает выполнение операции дизъюнкции, а квантор общности -операция конъюнкции. Приведенные тождества называются эквивалентностями с отрицаниями.
Аналогами свойств дистрибутивности конъюнкции и дизъюнкции относительно друг
друга служат следующие эквивалентности для предикатов:
.
Однако полностью свойства дистрибутивности и перестановочности операций, имеющие место в алгебре логики, не сохранятся для предикатов. Аналогом вышеприведенной формулы эквивалентности для квантора существования, примененного к дизъюнкции, служит эквивалентность для квантора общности, примененного к коньюнкции
а аналогом перестановочности кванторов существования служит перестановочность кванторов общности
;
в то же время левые и правые части следующих отношений не являются эквивалентными друг другу:
Заметим, что если в этих высказываниях справедливы левые части, то нельзя утверждать, что и правые будут справедливы; однако если истинны правые части, то истинными будут и левые. Например, в отношении всех вещественных чисел можно сказать: , и это высказывание, очевидно, истинно; в то же время высказывание явно ложно
Из сравнения приведенных отношений можно заключить, что если в формуле имеется несколько кванторов существования и отсутствуют кванторы общности, то кванторы существования могут рассматриваться в любой последовательности. Это справедливо и в отношении кванторов общности в отсутствие в той же формуле кванторов существования. Однако если в формуле стоят одновременно кванторы существования и общности, то перестановка этих кванторов меняет смысл формулы. Наконец, можно заключить, что квантор существования дистрибутивен относительно дизъюнкции (а следовательно, может выноситься за скобки), что является следствием того, что этот квантор является по существу аналогом операции дизъюнкции. Точно так же квантор общности, являющийся аналогом конъюнкции, дистрибутивен относительно конъюнкции, т.е. может выноситься за скобки, когда применяется к предикатам, связанным операцией конъюнкции.
Подобно тому, как в математическом анализе постоянный множитель может быть вынесен за знак интегрирования или дифференцирования, в логике предикатов можно выносить из-под знака квантора ту часть формулы, которая не зависит от предметной переменной (x), с которой связан квантор, например: . Легко записать и остальные три случая выноса постоянной из-под знака квантора:
Всюду в приведенных выше формулах своего рода "независимой переменной" кванторов у нас служили предметные переменные х, у,.... Однако еще большая формализация языка достигается, если в качестве "независимых переменных" кванторов рассматривать не только предметные переменные, но и предикатные переменные, или же независимыми переменными считать только предикатные переменные. Например, если А(х)- одноместный предикат, а х -предметная переменная, то высказывание выражает тот факт, что утверждение справедливо для любого одноместного предиката при всех значениях переменной х, являющейся в данном случае свободной. Очевидно, приведенное высказывание ложно при любых х. Рассмотренные выше эквивалентности для предикатов распространяются и на случай, когда квантор действует не на предметную, а на предикатную переменную.
Для многих приложений в качестве предметных переменных X, у,... целесообразно рассматривать натуральный ряд чисел, который можно интерпретировать так же, как дискретные значения времени. Подобная интерпретация делает естественный введение понятия ограниченного кванторе, например ограниченного квантора существования и ограниченного квантора общности .
Скажем, выражение означает существование t из интервала (), для которого удовлетворяется требование X(t). Приведенное высказывание о использованием понятия ограниченного квантора можно выразить, однако, и с помощью обычного квантора (без ограничений): . Иными словами, понятие ограниченного квантора не вносит ничего нового в логику высказываний, а всего лишь упрощает обозначения.
Установленные выше эквивалентности для кванторов имеют место и для ограниченных кванторов, за исключением лишь свойства коммутативности кванторов, что означает недопустимость изменения порядка применения ограниченных кванторов. В самой деле, например,
поскольку в правой части этого неравенства переменная t оказывается одновременно и свободной, и связанной, что недопустимо по определению формул алгебры логики.
Все формулы, выводимые в исчислении предикатов, выражают тождественно истинные высказывания, и любая тождественно истинная формула выводила в исчислении предикатов. Отсюда следует, что в исчислении предикатов невыводимы какие-либо действительно содержательные высказывания, например математические теоремы. Но если к аксиомам исчисления предикатов добавить какие-либо невыводимые в этом исчислении формулы, то можно надеяться вывести и еще какие-то формулы и получить нетривиальные результаты. Подобный подход позволяет рассматривать с позиций математической логики такие дисциплины, как арифметика, геометрия, теория множеств. Однако при этом необходимо исследовать вопрос о внутренней непротиворечивости рассматриваемых аксиом.
Исчисление высказываний называют непротиворечивым, если в нем нельзя вывести никакую пару формул, отрицающих друг друга. Исчисление называется противоречивым, если в нем можно одновременно вывести пару формул А и . В противоречивой системе можно вывести все формулы, а значит, в такой системе неразличимы истина и ложь.
Следовательно, чтобы утверждать о непротиворечивости системы, достаточно показать, что в этой системе существует хотя бы одна формула, которую нельзя вывести. Для доказательства непротиворечивости какой-либо системы исчисления необходимо привлечь некие факты, не следующие из аксиом этой системы. Понятно, что эти факты должны браться из источника, в отношения непротиворечивости которого у нас не имеется сомнений. В настоящее время в качестве такого источника используют теории множеств, рассматривая ее как наиболее общий источник предпосылок для доказательства более частных систем исчисления. Однако и сама теория множеств нуждается в доказательстве непротиворечивости, что, правда, уже выходит за возможности современной математики.
Пользуясь тем, что для доказательства непротиворечивости системы исчисления достаточно показать существование какой-либо формулы, которую нельзя вывести из этой системы, можно доказать, например, непротиворечивость ограниченной арифметики, получающейся, если из исходных понятий аксиоматической арифметики устранить аксиому полной математической индукции. Для доказательства непротиворечивости ограниченной арифметики достаточно показать, что в ней невыводима формула " ".