Общезначимость и выполнимость формул логики предикатов
Определение. Формула А логики предикатов называется выполнимой в области М, если существуют значения -переменных, входящих в эту формулу и отнесенных к области М, при которых формула А принимает истинные значения.
Определение. Формула А называется выполнимой, если существует область, на которой эта формула выполнима.
Из определения 2 следует, что, если формула выполнима, то это еще не означает, что она выполнима в любой области.
Определение. Формула А называется тождественно истинной в области М, если она принимает истинные значения для всех значений переменных, входящих в эту формулу и отнесенных к этой области.
Определение. Формула А называется общезначимой, если она тождественно истинная на всякой области.
Определение. Формула А называется тождественно ложной в области М, если она принимает ложные значения для всех значений переменных, входящих в эту формулу и отнесенных к этой области.
Из приведенных определений следует:
1) если формула A общезначима, то она и выполнима на всякой области;
2) если формула A тождественно истинная в области M, то она и выполнима в этой области;
3) если формула A тождественно ложная в области M, то она не выполнима в этой области;
4) если формула A не выполнима, то она тождественно ложна во всякой области.
В связи с данными определениями естественно выделить два класса формул логики предикатов: выполнимых и не выполнимых формул.
Отметим, что общезначимую формулу называют логическим законом.
Приведем соответствующие примеры.
Пример 1. Формула «x$yР(х,у) выполнима. Действительно, если Р(х,у) – предикат «х Будет полезно почитать по теме:
Источник
Общезначимость и выполнимость формул логики предикатов
Определение. Формула А логики предикатов называется выполнимой в области М, если существуют значения -переменных, входящих в эту формулу и отнесенных к области М, при которых формула А принимает истинные значения.
Определение. Формула А называется выполнимой, если существует область, на которой эта формула выполнима.
Из определения 2 следует, что, если формула выполнима, то это еще не означает, что она выполнима в любой области.
Определение. Формула А называется тождественно истинной в области М, если она принимает истинные значения для всех значений переменных, входящих в эту формулу и отнесенных к этой области.
Определение. Формула А называется общезначимой, если она тождественно истинная на всякой области.
Определение. Формула А называется тождественно ложной в области М, если она принимает ложные значения для всех значений переменных, входящих в эту формулу и отнесенных к этой области.
Из приведенных определений следует:
1) если формула A общезначима, то она и выполнима на всякой области;
2) если формула A тождественно истинная в области M, то она и выполнима в этой области;
3) если формула A тождественно ложная в области M, то она не выполнима в этой области;
4) если формула A не выполнима, то она тождественно ложна во всякой области.
В связи с данными определениями естественно выделить два класса формул логики предикатов: выполнимых и не выполнимых формул.
Отметим, что общезначимую формулу называют логическим законом.
Приведем соответствующие примеры.
Пример 1. Формула «x$yР(х,у) выполнима. Действительно, если Р(х,у) – предикат «х
Пример 2. Формула 
тождественно истинная в любой области M. Значит, она является общезначимой, то есть является логическим законом (закон исключенного третьего).
Пример 3. Формула 
тождественно ложная в любой области M, и поэтому она не выполнима.
Легко установить связь между общезначимостью и выполнимостью формул логики предикатов.
Теорема. Для того, чтобы формула А была общезначима, необходимо и достаточно, чтобы ее отрицание было не выполнимо.
Доказательство
Необходимость. Пусть формула A общезначима. Тогда, очевидно, Ā – тождественно ложная формула в любой области, и поэтому формула A не выполнима.
Достаточность. Пусть формула Ā не выполнима в любой области. Тогда по определению невыполнимой формулы Ā – тождественно ложная в любой области. Значит, формула A – тождественно истинная формула в любой области, и, следовательно, она общезначима.
Теорема. Для того, чтобы формула А была выполнимой, необходимо и достаточно, чтобы формула Ā была не общезначима.
Доказательство
Необходимость. Пусть формула A выполнима. Это означает, что существует область M и набор значений переменных, входящих в формулу A, при которых формула A принимает истинное значение. Очевидно, что на этом наборе значений переменных формула Ā принимает ложное значение, и, следовательно, формула Ā необщезначима.
Достаточность. Пусть формула Ā не общезначима. Тогда существует область M и набор значений переменных, входящих в формулу, при которых формула Ā принимает ложное значение. На этом наборе значений переменных формула A принимает значение «истина», и поэтому формула A выполнима.
Рассмотрим проблему разрешимости для общезначимости и выполнимости и неразрешимости ее в общем случае.
Проблема разрешимости в логике предикатов ставится так же, как и в алгебре логики: существуют ли алгоритмы, позволяющие для любой формулы A логики предикатов установить, к какому классу она относится, то есть является ли она или общезначимой, или выполнимой, или тождественно ложной. Если бы такой алгоритм существовал, то, как и в алгебре высказываний, он сводился бы к критерию тождественной истинности любой формулы логики предикатов.
Отметим, что в отличие от алгебры логики, в логике предикатов не применим метод перебора всех вариантов значений переменных, входящих в формулу, так как таких вариантов может быть бесконечное множество. В 1936 г. американский математик А. Черч доказал, что проблема разрешимости логики предикатов в общем виде алгоритмически не разрешима, то есть не существует алгоритма, который бы позволил установить, к какому классу формул относится любая формула логики предикатов.
Очевидно, что проблема разрешимости в случае конечных областей разрешима. Действительно, в этом случае кванторные операции можно заменить операциями конъюнкции и дизъюнкции и тем самым свести формулу логики предикатов к формуле алгебры логики, .для которой проблема разрешимости разрешима.
4.7. Применение языка логики предикатов для записи математических
предложений, определений, построения отрицания предложений
1. Запись математических предложений в виде формул логики предикатов.
Язык логики предикатов удобен для записи математических предложений. Он дает возможность выражать логические связи между понятиями, записывать определения, теоремы, доказательства. Приведем ряд примеров таких записей.
1.1. Определение предела числовой последовательности:
.
Здесь использован трехместный предикат
.
Словесная формулировка этой записи выглядит следующим образом: число а является пределом последовательности <a1,a2,…>, если для всякого e > 0 существует n0 такое, что для n ³ n0 |an – a| 0 найдется d>0 такое, что для любого х, удовлетворяющего условию |x – x0| 2 . Обозначая эти предикаты соответственно через Р(х) и Q(x), где хÎR 2 , теорему можем записать в виде формулы
В связи с этим, говоря о строении теоремы, можно выделить в ней три части: 1) условие теоремы: предикат P(х), заданный на множестве R 2 ; 2) заключение теоремы: предикат Q(х), заданный на множестве R 2 ; 3) разъяснительная часть: в ней описывается множество объектов,
о которых идет речь в теореме.
2. Прямая, обратная и противоположная теоремы.
Рассмотрим четыре теоремы:
(4)
(5)
Пара теорем, у которых условие одной является заключением второй, а условие второй является заключением первой, называются взаимно обратными друг другу.
Так, теоремы (2) и (3) , а также (4) и (5) – взаимно обратные теоремы. При этом, если одну из них называют прямой теоремой, то вторая называется обратной.
Пара теорем, у которых условие и заключение одной является отрицанием соответственно условия и заключения другой, называются взаимно противоположными.
Так, теоремы (2) и (4), а также теоремы (3) и (5) являются взаимно противоположными теоремами.
Например, для теоремы «Если в четырехугольнике диагонали равны, то четырехугольник является прямоугольником» (2) обратной является теорема «Если четырехугольник является прямоугольником, то его диагонали равны» (3). Для теоремы (2) противоположной является теорема «Если в четырехугольнике диагонали не равны, то четырехугольник не является прямоугольником» (4), а для теоремы (3) противоположной является теорема «Если четырехугольник не является прямоугольником, то его диагонали не равны» (5).
В рассмотренном примере теоремы (2) и (5) являются одновременно ложными, а теоремы (3) и (4) одновременно истинными. Контрпримером к теореме (2) является равнобочная трапеция.
Ясно, что прямая и обратная теоремы, вообще говоря, не равносильны, то есть одна из них может быть истинной, а другая ложной. Однако легко показать, что теоремы (2) и (5), а также теоремы (3) и (4) всегда равносильны.
3. Необходимые и достаточные условия.
Рассмотрим теорему (2)
.
Предикат P(х)®Q(х) является истинным для всех хÎЕ в том и только в том случае, когда множество истинности предиката P(х) содержится в множестве истинности предиката Q(x). При этом говорят, что предикат Q(x) логически следует из предиката P(x), и предикат Q(х) называют необходимым условием для предиката P(х), а предикат P(x) – достаточным условием для Q(х). Так, в теореме «Если х – число натуральное, то оно целое» предикат Q(х): «х – число целое» логически следует из предиката P(х): «x – число натуральное», а предикат «x – число натуральное» является достаточным условием для предиката «х – число целое».
Часто встречается ситуация, при которой истинны взаимно обратные теоремы (2) и (3)
Это, очевидно, возможно при условии, что IР = IQ.
В таком случае из теоремы (2) следует, что условие P(х) является достаточным для Q(x), а из теоремы (3) следует, что условие P(х) является необходимым для Q(х).
Таким образом, если истинны теоремы (2) и (3), то условие P(х) является и необходимым, и достаточным для Q(х). Аналогично в этой случае условие Q(х) является необходимым и достаточным для P(х).
Иногда вместо логической связки «необходимо и достаточно» употребляют логическую связку «тогда и только тогда».
Так как здесь истинны высказывания (2) и (3), то истинно высказывание
.
Пример 1. Теорема «Если число x делится на 12, то оно делится на 3» истинна. Поэтому здесь делимость числа x на 12 является достаточным условием для делимости числа x на 3, а делимость числа x на 3 является необходимым условием для делимости числа x на 12. В то же время обратная теорема «Если число x делится на 3, то оно делится на 12» не верна. Поэтому делимость числа x на 3 не является достаточным условием делимости числа x на 12, а делимость числа x на 12 не является необходимым условием делимости числа x на 3.
Пример 2.Теоремы «В описанном четырехугольнике суммы длин противоположных сторон равны между собой» и «Если в четырехугольнике суммы длин противоположных сторон равны между собой, то в этот четырехугольник можно вписать окружность» взаимно обратны.
Обе они истинны, и, следовательно, здесь можно употребить логическую связку «необходимо и достаточно»:
«Для того чтобы в четырехугольник можно было вписать окружность, необходимо и доста-точно, чтобы суммы длин его противоположных сторон были равны между собой».
Источник
Формулы логики предикатов
В алгебре высказываний мы подробно изучили одно из важнейших ее понятий и инструментов — понятие формулы алгебры высказываний. Теперь наша задача состоит в том, чтобы определить и изучить соответствующее понятие в логике предикатов, а затем на его основе продемонстрировать, насколько тоньше и точнее язык и логика предикатов отражают процессы человеческого мышления, нежели это делают язык и логика высказываний.
Понятие формулы логики предикатов
Это понятие вводится аналогично понятию формулы алгебры высказываний. Сначала задается алфавит символов, из которых будут составляться формулы:
Теперь дадим определение формулы логики предикатов, которое также носит индуктивный характер.
Определение 21.1 (формулы логики предикатов).
1) Каждая нульместная предикатная переменная есть формула;
2) если — n-местная предикатная переменная, то есть формула, в которой все предметные переменные свободны;
3) если — формула, то — также формула. Свободные (связанные) предметные переменные в формуле те и только те, которые являются свободными (связанными) в ;
4) если — формулы и если предметные переменные, входящие одновременно в обе эти формулы, свободны в каждой из них, то выражения
также являются формулами. При этом предметные переменные, свободные (связанные) хотя бы в одной из формул , называются свободными (связанными) и в новых формулах;
5) если — формула и — предметная переменная, входящая в свободно, то выражения и также являются формулами, в которых переменная связанная, а все остальные предметные переменные, входящие в формулу свободно или связанно, остаются и в новых формулах соответственно такими же;
6) никаких других формул логики предикатов, кроме получающихся согласно пп. 1–5, нет.
Формулы, определенные в пунктах 1 и 2, называются элементарными (или атомарными). Формулы, не являющиеся элементарными, называются составными.
Например, — элементарные формулы, а
являются составными формулами. При этом в первой составной формуле предметная переменная связана, а переменные — свободные. Во второй составной формуле свободна лишь переменная , остальные — связаны. В третьей составной формуле первое вхождение переменной связано, а второе — свободно. Переменная у связана. Последнюю формулу более целесообразно было бы записать в следующем виде (заменив связанную переменную х какой-нибудь буквой, не входящей в данную формулу):
Как и в алгебре высказываний, договоримся внешние скобки у формулы не писать, если только она не является частью более сложной формулы. Отметим кстати, что на основании пунктов 1, 3 и 4 сформулированного определения всякая формула алгебры высказываний будет также и формулой логики предикатов.
В формулах вида и формула называется областью действия квантора или , соответственно. Тогда ясно, что вхождение предметной переменной в формулу будет связанным, если эта переменная находится в области действия квантора по этой переменной.
Формулы, в которых нет свободных предметных переменных, называются замкнутыми, а формулы, содержащие свободные предметные переменные, — открытыми. Так, все приведенные выше формулы логики предикатов, кроме формулы , являются открытыми.
Примеры замкнутых формул:
Классификация формул логики предикатов
Если в формулу логики предикатов вместо каждой предикатной переменной подставить конкретный предикат, определенный на некотором выбранном множестве , то формула превратится в конкретный предикат, заданный над множеством . При этом, если исходная формула была замкнутой, то полученный конкретный предикат окажется нульместным, т.е. будет высказыванием. Если же исходная формула была открытой, т. е. содержала свободные вхождения предметных переменных, то в результате подстановки получим предикат, зависящий от некоторых предметных переменных. Если теперь подставить вместо этих предметных переменных конкретные предметы из множества , то полученный предикат, а следовательно, и исходная формула превратятся в конкретное высказывание.
Превращение формулы логики предикатов в высказывание описанным выше способом (а также само получаемое высказывание) называется интерпретацией этой формулы на множестве . Итак, если формула логики предикатов замкнутая, т.е. не содержит свободных предметных переменных, то ее интерпретация состоит из одного этапа и сводится к подстановке вместо всех предикатных переменных конкретных предикатов, в результате чего формула превращается в конкретное высказывание (нульместный предикат). Если же формула логики предикатов открытая, т. е. содержит ряд свободных предметных переменных, то ее интерпретация состоит из двух этапов. Во-первых, вместо всех предикатных переменных необходимо подставить конкретные предикаты, в результате чего формула превратится в конкретный предикат, зависящий от такого количества предметных переменных, сколько было свободных предметных переменных в исходной формуле. Во-вторых, нужно придать значение каждой предметной переменной, от которой зависит получившийся предикат, в результате чего этот предикат (и, значит, вся исходная формула) превратится в конкретное высказывание (истинное или ложное).
Пример 21.2. Дадим интерпретацию формуле . В качестве множества возьмем множество всех мужчин, а вместо предикатной переменной подставим конкретный предикат, определенный на » есть отец «. Тогда исходная формула превратится в следующее (очевидно, ложное) высказывание ( есть отец ) — «у каждого мужчины есть сын». Этой же формуле можно дать и другую интерпретацию. Возьмем в качестве множество всех натуральных чисел, а вместо предикатной переменной подставим предикат » «, определенный на . Тогда исходная формула превратится в (очевидно, истинное) высказывание — «Для каждого натурального числа существует большее по сравнению с ним натуральное число».
Пример 21.3. В предыдущем примере была рассмотрена интерпретация замкнутой формулы. Дадим интерпретацию открытой формуле . В качестве множества возьмем множество всех натуральных чисел. Вместо предикатных переменных и подставим трехместные предикаты » » и » » соответственно, а вместо нульместного предиката подставим (ложное) высказывание » «. Тогда данная формула превратится в двухместный предикат (от предметных переменных ):
Посмотрим, в какие высказывания может превращаться данный предикат при подстановке вместо его переменных и конкретных предметов (чисел) из . Нетрудно понять, что двухместный предикат превращается в истинное высказывание при любой подстановке вместо его предметных переменных и натуральных чисел. В самом деле, для натуральных тип получаем высказывание
Одноместный предикат (зависит от ) , стоящий под знаком квантора , выполним, потому что всегда можно найти такое натуральное число , что и , т. е. высказывания и будут ложны, а значит, высказывание — истинно. А раз так, то высказывание истинно. Поэтому высказывание
в которое превращается данный предикат, ложно. Итак, исходная открытая формула логики предикатов превращена в тождественно ложный предикат. Нетрудно понять, что если вместо предикатных переменных и подставить только что рассмотренные предикаты, а вместо нульместной предикатной переменной — любое истинное высказывание, то исходная формула превратится в тождественно истинный предикат.
Сформулируем классификационные определения для формул логики предикатов.
Определение 21.4. Формула логики предикатов называется выполнимой (опровержимой) на множестве , если при некоторой подстановке вместо предикатных переменных конкретных предикатов, заданных на этом множестве, она превращается в выполнимый (опровержимый) предикат.
Другими словами, формула выполнима (опровержима) на , если существует истинная (ложная) ее интерпретация на . Формула из примера 21.2 является как выполнимой, так и опровержимой.
Определение 21.6. Формула логики предикатов называется общезначимой, или тавтологией (тождественно ложной или противоречием), если при всякой подстановке вместо предикатных переменных любых конкретных предикатов, заданных на каких угодно множествах, она превращается в тождественно истинный (тождественно ложный) предикат. (Тот факт, что формула является тавтологией, обозначается, как и в алгебре высказываний, .) Так, формула из примера 21.3 не является тавтологией, потому что хотя при одной подстановке она и превратилась в тождественно истинный предикат, при другой она оказалась превращенной в предикат тождественно ложный. Поэтому данная формула не является и противоречием.
Пример 21.7. Покажем, что формула является противоречием, т.е. тождественно ложной. В самом деле, допустим противное: на некотором множестве имеется конкретный предикат , такой, что данная формула превращается в выполнимый предикат (от ) . Последнее означает: найдется предмет , такой, что высказывание истинно. Истинность конъюнкции дает истинность высказываний и . Из истинности первого следует, что высказывание ложно, а из истинности второго — что предикат тождественно истинный и, значит, для любого предмета из , в том числе и для , высказывание истинно. Получаем противоречие, исключающее предположение о непротиворечивости исходной формулы. Следовательно, она тождественно ложна.
Источник
