Функциональная природа предиката влечет за собой введение ещё одного понятия – квантора . (quantum – от лат. «сколько») Кванторные операции можно рассматривать как обобщение операций конъюнкции и дизъюнкции в случае конечных и бесконечных областей.
Квантор общности (все, всякий, каждый, любой (all – «всякий»)). Соответствующие ему словесное выражение звучит так:
«Для всякого x Р(x) истинно». Вхождение переменной в формулу может быть связанным, если переменная расположена либо непосредственно после знака квантора, либо в области действия квантора, после которого стоит переменная. Все прочие вхождения – свободные, переход от P(x) к x(Px) или (Px) называется связыванием переменной x или навешиванием квантора на переменную x (или на предикат P) или квантификацией переменной х. Переменная, на которую навешивается квантор, называется связанной , несвязанная квантования переменная называется свободной .
Например, переменная x в предикате Р(x) называется свободной (x – любое из М), в высказывании Р(x) переменную x называют связанной переменной.
Справедлива равносильность P(x 1)P(x 2)…P(x n),
P(x) – предикат, определенный на множестве М={х 1 ,х 2 ...х 4 }
Квантор существования (exist – «существовать»). Словесное выражение, соответствующее ему, звучит так: “Существует x, при котором Р(x) истинно”. Высказывание xР(x) уже не зависит от x, переменная x связана квантором .
Справедлива равносильность:
xP(x) = P(x 1)P(x 2)…P(x n), где
P(x) - предикат, определенный на множестве М={x 1 ,x 2 …x n }.
Квантор общности и квантор существования называют двойственными, иногда используется обозначение квантора ! – «существует, и притом, только один».
Ясно, что высказывание xP(x) истинно только в том единственном случае, когда Р(x) - тождественно истинный предикат, а высказывание ложно только тогда, когда Р(x) - тождественно ложный предикат.
Кванторные операции применяются и к многоместным предикатам. Применение кванторной операции к предикату P(x,y) по переменной x ставит в соответствие двухместному предикату P(x,y) одноместный предикат xP(x,y) или xP(x,y), зависящий от у и не зависящий от х.
К двухместному предикату можно применить кванторные операции по обеим переменным. Тогда получим восемь высказываний:
1. P(x,y); 2. P(x,y);
3. P(x,y); 4. P(x,y);
5. P(x,y); 6. P(x,y);
7. P(x,y); 8. P(x,y)
Пример 3. Рассмотреть возможные варианты навешивания кванторов на предикат P(x,y) – “x делится на y ”, определенный на множестве натуральных чисел (без нуля) N . Дать словесные формулировки полученных высказываний и определить их истинность.
Операция навешивания кванторов приводит к следующим формулам:
Высказывания “для любых двух натуральных чисел имеет место делимость одного на другое” (или 1) все натуральные числа делятся на любое натуральное число; 2) любое натуральное число является делителем для любого натурального числа) ложные;
Высказывания “существуют такие два натуральных числа, что первое делится на второе” (1. «существует такое натуральное число x, которое делится на какое-то число y»; 2. «существует такое натуральное число y, которое является делителем какого-то натурального числа x») истинны;
Высказывание “существует натуральное число, которое делится на любое натуральное”, ложное;
Высказывание “для всякого натурального числа найдется такое натуральное, которое делится на первое” (или для всякого натурального числа найдется свое делимое), истинное;
Высказывание “для всякого натурального x существует такое натуральное число y, на которое оно делится” (или «для всякого натурального числа найдется свой делитель»), истинное;
Высказывание “существует натуральное число, которое является делителем всякого натурального числа”, истинное (таким делителем является единица).
В общем случае изменение порядка следования кванторов изменяет смысл высказывания и его логическое значение, т.е. например, высказывания P(x,y) и P(x,y) различны.
Пусть предикат P(x,y) означает, что x является матерью для y, тогда P(x,y) означает, что у каждого человека есть мать – истинное утверждение. P(x,y) означает, что существует мать всех людей. Истинность этого утверждения зависит от множества значений, которые могут принимать y: если это множество братьев и сестер, то оно истинно, в противном случае оно ложно. Таким образом, перестановка кванторов всеобщности и существования может изменить сам смысл и значение выражения.
а) заменить начальный знак (или ) на противоположный
б) поставить знак перед остальной частью предиката
Кроме известных нам логических операций для предикатов вводятся две новые: операция навешивания кванторов существования и общности.
«для всех х » (для любого х , для каждого х ) называется квантором общности и обозначается х.
Высказывание «существует х » (для некоторых х , хотя бы для одного х, найдется такое х ) называется квантором существования и обозначается х.
Высказывание «существует одно и только одно х » (для единственного значения х ) называется квантором единственности : ! х.
Например: «Все кустарники являются растениями». Это высказывание содержит квантор общности («все»). Высказывание «существуют числа, кратные 5 » содержит квантор существования («существуют»).
Для того чтобы получить высказывание из многоместного предиката, надо связать кванторами каждую переменную. Например, если Р(х; у) - двухместный предикат, то (хХ) (уY) Р(х; у) - высказывание.
Если не каждая переменная связывается квантором, то получается не высказывание, а предикат, зависящий от той переменой, которая не связана квантором. Так, если перед предикатом Р(х; у) поставить квантор у, то получим предикат (уY) Р(х; у) , зависящий от переменной х.
Выясним, какие из следующих предложений являются высказываниями, а какие предикатами: а) найдется такое х, что х+ у = 2;
b) для любых х и у имеет место равенство х + у = у + х.
Решение : Выявим логическую структуру данных предложений.
а) Предложение «Найдется такое х, что х + у = 2 » можно записать в виде (хR) х + у = 2. Так как квантором связана только переменная х, то рассматриваемое предложение с двумя переменными является предикатом.
b) Предложение «для любых х и у имеет место х + у = у + х » можно записать в виде: (хR) (уR) х + у = у + х, где обе переменные являются связанными. Следовательно, данное предложение является высказыванием.
Если какое-либо предметное переменное в формуле не связано квантором, то его называют свободным переменным.
Например: (х) ху=ух. Здесь переменное у не связано каким-либо квантором, поэтому оно свободно. От него не зависит истинность данного высказывания.
Кванторы (х) (х ) называются двойственными друг другу.
Одноименные кванторы можно менять местами, что не влияет на истинность высказывания.
Например: (у) (х) х + у = 5. Это утверждение имеет тот же смысл, что и (х) (у) х + у = 5.
Для разноименных кванторов изменение порядка может привести к изменению истинности высказывания.
Например: (х) (у) х<у , т.е. для всякого числа х существует большее число у - истинное высказывание.
Поменяем местами кванторы: (х) (у) x
В связи с введением кванторов необходимо учесть следующее:
1. Формула логики предикатов не может содержать одно и то же предметное переменное, которое было бы связано в одной части формулы и свободно в другой.
2. Одно и то же переменное не может находиться в области двойственных друг другу кванторов.
Нарушение этих условий называют коллизией переменных .
Как устанавливается значение истинности высказывания с квантором?
Для доказательства утверждения с квантором общности необходимо убедиться в том, что при подстановке каждого из значений х в предикат Р(х) последний обращается в истинное высказывание. Если множество Х конечно, то это можно сделать путем перебора всех случаев; если же множество Х бесконечно, то необходимо провести рассуждения в общем виде.
Высказывание (х) Р(х) ложно, если можно указать такое значение а Х , при котором Р(х) обращается в ложное высказывание Р(а). Поэтому, для опровержения высказывания с квантором общности достаточно привести пример.
Высказывание (х) Р(х) истинно, если можно указать такое значение а Х , при котором Р(х) обращается в истинное высказывание Р(а) . Поэтому, чтобы убедиться в истинности высказывания с квантором существования , достаточно привести пример и таким образом доказать.
Для того чтобы убедиться в ложности высказывания с квантором существования (х) Р(х), необходимо убедиться в ложности каждого Р(х ), Р(х ), …, Р(х ). Если множество Х конечно, то это можно сделать перебором. Если же множество Х бесконечно, то необходимо провести рассуждения в общем виде.
Примеры .
1. Найти значение истинности «средичисел1, 2, 3, 4 найдется простое число».
Решение: Высказывание содержит квантор существования и поэтому может быть представлено в виде дизъюнкции высказываний: «1 - простое число» или «2 - простое число» или «3 - простое число» или «4 - простое число». Для доказательства истинности дизъюнкции достаточно истинности хотя бы одного высказывания, например, «3 - простое число», которое истинно. Следовательно, истинно и исходное высказывание.
2. Докажем, что любой квадрат является прямоугольником.
Решение: Высказывание содержит квантор общности. Поэтому оно может быть представлено в виде конъюнкции: «квадрат - прямоугольник» и «квадрат - прямоугольник» и «квадрат - прямоугольник» и т.д. Так как все эти высказывания истинны, то истинна конъюнкция этих высказываний, следовательно, истинно и исходное предложение.
3. «Любой треугольник равнобедренный». Это ложное высказывание. Чтобы убедиться в этом, достаточно начертить треугольник, не являющийся равнобедренным.а
Для построения отрицания высказывания с кванторами надо:
1) квантор общности заменить квантором существования, а квантор существования - квантором общности;
2) предикат заменить его отрицанием.
Пример. Сформулируем отрицание для следующих высказываний:
а) все элементы множества Z четные; b) некоторые глаголы отвечают на вопрос «что делать?».
Решение: а) Заменим квантор общности квантором существования, а высказывание его отрицанием: некоторые элементы множества Z нечетные.
b) Заменим квантор существования квантором общности, а выражение его отрицанием: все глаголы не отвечают на вопрос «что делать?».
В логике предикатов рассматриваются две операции, которыё превращают одноместный предикат в высказывание, для этого используются специальные слова, которые ставят перед предикатами. В логике их называют кванторами.
Различают два вида кванторов:
1. Квантор общности;
2. Квантор существования.
1. Квантор общности.
Пусть имеется предикат Р(х) определенный на множестве М
Символ называют квантором всеобщности (общности). Это перевернутая первая буква английского слова All- все. Читают «все», «каждый», «любой», «всякий». Переменную х в предикате Р(х) называют свободной (ей можно придавать различные значения из М), в высказывании же х называют связанной квантором всеобщности.
Пример №1: Р(х) – «Простое число х нечетно»
Добавим квантор общности – «Всякое простое число х нечетно» - ложное высказывание.
Под выражением понимают высказывание истинное, когда Р(х) истинно для каждого элемента х из множества М и ложное в противном случае. Это высказывание уже не зависит от х.
2. Квантор существования.
Пусть P(x) -предикат определенный на множестве М. Под выражением понимают высказывание , которое является истинным, если существует элемент , для которого P(x) истинно, и ложным – в противном случае. Это высказывание уже не зависит от x. Соответствующее ему словесное выражение звучит так: “Существует x, при котором P(x) истинно.” Символ называют квантором существования. В высказывании переменная x связана этим квантором (на нее навешен квантор).
(Читают: «Существует такое х из М, при котором Р от х истинно»)
Под выражением понимают высказывание, которое является истинным, если существует элемент х€М (хотя бы один), для которого Р(х) истинно, и ложным в противном случае.
Пример №2: Р(х) «Число х кратно 5»
Любое натуральное число кратно 5»
Каждое натуральное число кратно 5» ложные высказывания
Все натуральные числа кратны 5»
Существует натуральное число кратно 5
Найдется натуральное число кратно 5 истинные высказывания
Хотя бы одно натуральное число кратно 5
Кванторные операции применяются и к многоместным предикатам. Пусть, например, на множестве М задан двухместный предикат P(x,y). Применение кванторной операции к предикату P(x,y) по переменной x ставит в соответствие двухместному предикату P(x,y) одноместный предикат (или одноместный предикат ), зависящий от переменной y и не зависящий от переменной x. К ним можно применить кванторные операции по переменной y, которые приведут уже к высказываниям следующих видов:
Для построения отрицаний с кванторами надо:
1) квантор общности заменить на квантор существования, а квантор существования – на квантор общности;
2) предикат заменить его отрицанием.
Таким образом, справедливы формулы:
Отрицание предложения записывать как , а отрицание предложения – как . Очевидно, что предложение имеет тот же смысл, а следовательно, то же значение истинности, что и предложение , а предложение – тот же смысл, что . Иначе говоря, равносильно ; равносильно .
П р и м е р №3. Построить отрицание высказывания «некоторые двузначные числа делятся на 12».
Р е ш е н и е. Заменим квантор существования (он выражен словом «некоторые») на квантор общности «все» и построим отрицание предложения, стоящего после слова «некоторые», поставив частицу «не» перед глаголом. Получим высказывание «Все двузначные числа не делятся на 12».
П р и м е р №4. Сформулировать отрицание высказывания «В каждом классе хотя бы один ученик не справился с контрольной работой».
Р е ш е н и е. Данное высказывание содержит квантор общности, выраженный при помощи слова «каждый», и квантор существования, выраженный при помощи слов «хотя бы один». По правилу построения отрицаний высказываний с кванторами надо квантор общности заменить на квантор существования, а квантор существования – на квантор общности и убрать у глагола частицу «не». Получим: «Найдется такой класс, в котором все ученики справились с контрольной работой».
Кроме рассмотренных выше операций, мы будем употреблять еще две новые операции, связанные с особенностями логики предикатов. Операции эти выражают собой утверждения общности и существования.
Квантор - некоторый способ приписать наличие каких-либо свойств целому множеству объектов: (квантор общности) или просто (), (квантор существования).
1. Квантор общности. Пусть R (x) - вполне определенный предикат, принимающий значение И или Л для каждого элемента х некоторого поля М. Тогда под выражением (x)R(x) мы будем подразумевать высказывание истинное, когда R(х) истинно для каждого элемента х поля М, и ложное в противном случае. Это высказывание уже не зависит от х. Соответствующее ему словесное выражение будет: «для всякого х R (х) истинно».
Пусть теперь И(х)-формула логики предикатов, принимающая определенное значение, если входящие в нее переменные предметы и переменные предикаты замещены вполне определенным образом. Формула И(х) может содержать и другие переменные, кроме х. Тогда выражение И(х) при замещении всех переменных как предметов, так и предикатов, кроме х, представляет собой конкретный предикат, зависящий только от х. А формула (х)И(х) становится вполне определенным высказыванием. Следовательно, эта формула вполне определяется заданием значений всех переменных, кроме х, и, значит, от х не зависит. Символ (х) называется квантором общности .
2. Квантор существования. Пусть R(х) - некоторый предикат. Мы свяжем с ним формулу (x)R(x), определив ее значение как истину, если существует элемент поля М, для которого R(х) истинно, и как ложь в противном случае. Тогда если И(х) - определенная формула логики предикатов, то формула (x)И(x) также определена и от значения х не зависит. Знак (x) называется квантором существования .
Кванторы (х) и (х) называются двойственными друг другу.
Мы будем говорить, что в формулах (х)И(х) и (x)И(x) кванторы (х) и (х) относятся к переменному х или что переменное х связано соответствующим квантором.
Предметное переменное, не связанное никаким квантором, мы будем называть свободным переменным . Таким образом, мы описали все формулы логики предикатов.
Если две формулы И и В, отнесенные к некоторому полю М, при всех замещениях переменных предикатов, переменных высказываний и свободных предметных переменных соответственно индивидуальными предикатами, определенными на М, индивидуальными высказываниями и индивидуальными предметами из М, принимают одинаковые значения И или Л, то мы будем говорить, что эти формулы равносильны на поле М. (При замещениях переменных предикатов, высказываний и предметов мы, конечно, те из них, которые в формулах И и В обозначены одинаковым образом, замещаем также одинаковым образом).
Если две формулы равносильны на любых полях М, то мы будем их называть просто равносильными. Равносильные формулы могут быть замещаемы одна другой.
Равносильность формул позволяет приводить их в разных случаях к более удобному виду.
В частности, имеет место: И→ В равносильно И В.
Пользуясь этим, мы можем для любой формулы найти равносильную, в которой из операций алгебры высказываний имеются только &, и -.
Пример: (x)(А(х)→(у)В(у)) равносильна (x)(А(х)(у)В(у)).
Кроме того, для логики предикатов имеются равносильности, связанные с кванторами.
Существует закон, связывающий кванторы со знаком отрицания. Рассмотрим выражение (х)И(х).
Высказывание «(х)И(х) ложно», равносильно высказыванию: «существует элемент у, для которого И(у) ложно» или, что то же, «существует элемент у, для которого И(у) истинно». Следовательно, выражение (х)И(х) равносильно выражению (у)И(у).
Рассмотрим таким же образом выражение (х)И(х).
Это есть высказывание «(х)И(х) ложно». Но такое высказывание равносильно высказыванию: «для всех у И(у) ложно» или «для всех у И(у) истинно». Итак, (х)И(х) равносильно выражению (у)И(у).
Мы получили, таким образом, следующее правило:
Знак отрицания можно ввести под знак квантора, заменив квантор на двойственный.
Мы уже видели, что для каждой формулы существует равносильная ей формула, которая из операций алгебры высказываний содержит только &, и -.
Пользуясь равносильностями для каждой формулы можно найти равносильную, в которой знаки отрицания относятся к элементарным высказываниям и элементарным предикатам.
Для аксиоматического описания логики предикатов предназначено исчисление предикатов.
Исчисление предикатов - некоторая аксиоматическая система, предназначенная для моделирования некоторой среды и проверки каких-либо гипотез относительно свойств этой среды при помощи разработанной модели. Гипотезы при этом утверждают наличие или отсутствие некоторых свойств у некоторых объектов и выражаются в виде логической формулы. Обоснование гипотезы сводится, таким образом, к оценке выводимости и выполнимости логической формулы.
Рассматриваемые вопросы1. Кванторы.
2. Квантор всеобщности.
3. Квантор существования.
4. Понятие формулы логики предикатов. Значение формулы
логики предикатов.
5. Равносильные формулы логики предикатов.
Понятие квантора
Квантор - (от лат. quantum - сколько), логическаяоперация, дающая количественную характеристику
области предметов, к которой относится выражение,
получаемое в результате её применения.
В обычном языке носителями таких характеристик
служат слова типа "все", "каждый", "некоторый",
"существует",
"имеется",
"любой",
"всякий",
"единственный", "несколько", "бесконечно много",
"конечное число", а также все количественные
числительные.
Операции для предиката
Для предикатов вводятся две новые посравнению с логикой высказываний операции:
квантор общности
квантор существования
Квантор общности
Пусть Р(x) – одноместный предикат, определенный напредметном множестве М.
Универсальным высказыванием, соответствующим
предикату Р(x), называется высказывание:
«каждый элемент множества М удовлетворяет
предикату Р(x)»
или
«для всякого х выполняется предикат»
Это высказывание обозначается - (x)P(x)
Высказывание (x)P(x) считается истинным, если
предикат P(x) тождественно истинный, а ложным –
в противном случае.
Квантор общности
Символ x называется кванторомпеременной х, его читают так:
«для всех х»
«для каждого х»
«для любого х»
общности по
Выражение (x)P(x) читается: «для всех х, Р(х)», или
«для каждого х, Р(х)».
Например, x(х=х) – это истинное универсальное
высказывание, а x(х>2) – ложное универсальное
высказывание.
конечном множестве {a1,a2,…am}, то:
P(x) P(a1) P(a2) ... P(am)
Квантор общности
Таким образом, квантор общностиможно понимать как оператор
конъюнкции по квантифицируемой
переменной.
Квантор существования
Экзистенциональнымвысказыванием,
соответствующим
предикату
Р(x),
называется
высказывание «существует элемент множества М,
удовлетворяющий
предикату
Р(x)»,
которое
обозначается x P(x) и считается истинным, если
предикат Р(х) выполнимый, а ложным – в противном
случае.
Символ x называют квантором существования, а
выражение x, в котором этот квантор предшествует
переменной х, читают так:
«существует х такой, что…»
«для некоторого х, …»
Квантор существования
НАПРИМЕРx(х>2) –истинное экзистенциональное высказывание
x(х=х+1) – ложное экзистенциональное высказывание.
Если Р(х)- одноместный предикат, определенный на
конечном множестве {a1,a2,…am}, то
P(x) P(a1) P(a2) ... P(am)
Квантор существования
Таким образом, кванторсуществования можно понимать как
оператор дизъюнкции по
квантифицируемой переменной.
10. Примеры
Примеры записей формул и их словесные выражения:x(x 2 1 (x 1)(x 1)) Для всех х выполняется предикат…
x(x 0)
неравенство...
x(x 0)
Для всех х, справедливо…..
y (5 y 5)
Существует y такой, что 5+y=5
y(y 2 y 1 0)
Для всех y выполняется предикат
y(y 2 y 1 0)
Существует y, что ….
x(x x)
Для некоторого х, справедливо
3
2
11. Формулы логики предикатов
В логике предикатов имеется следующая символика:Символы p, q, r, …- переменные высказывания, принимающие
два значения: 1- истина, 0 – ложь.
Предметные переменные – x, y, z, …, которые пробегают
значения из некоторого множества М;
x0, y0, z0 – предметные константы, т. е. значения предметных
переменных.
P(·), Q(·), F(·), … - одноместные предикатные переменные;
Q(·,·,…,·), R(·,·, …,·) – n-местные предикатные переменные.
P0(·), Q0(·,·, …,·) – символы постоянных предикатов.
Символы логических операций: , .
Символы кванторных операций: х, х.
Вспомогательные символы: скобки, запятые.
12. Формулы логики предикатов
Предметная переменная называется свободной, если онане следует непосредственно за квантором и не входит в
область действия квантора по этой переменной, все другие
переменные,
входящие
в
формулу,
называются
связанными.
y z (P(x,y) P(y,z))
Формулой логики предикатов являются:
Каждая предикатная буква и предикатная буква со
следующими за ней в скобках предметными переменными.
Выражения вида F G, F G, G, F G, F G, (y)F,
(y)G, где F и G – формулы логики предикатов, переменная
у М.
13. Формулы логики предикатов
Каждое высказывание как переменное, такпостоянное, является формулой (элементарной).
и
Если F(·,·, …,·) – n-местная предикатная переменная
или постоянный предикат, а x1, x2,…, xn– предметные
переменные или предметные постоянные (не
обязательно все различные), то F(x1, x2,…, xn) есть
формула. Такая формула называется элементарной, в
ней предметные переменные являются свободными, не
связанными кванторами.
14. Формулы логики предикатов
Если А и В – формулы, причем, такие, что одна и та жепредметная переменная не является в одной из них
связанной, а в другой – свободной, то слова A B,
A B, A B есть формулы. В этих формулах те
переменные, которые в исходных формулах были
свободны, являются свободными, а те, которые были
связанными, являются связанными.
Если А – формула, то A– формула, и характер
предметных переменных при переходе от формулы А к
формуле A не меняется.
15. Формулы логики предикатов
Если А(х) – формула, в которую предметнаяпеременная х входит свободно, то слова xA(x) и
xA(x) являются формулами, причем, предметная
переменная входит в них связанно.
Всякое слово, отличное от тех, которые названы
формулами в предыдущих пунктах, не является
формулой.
16. Формулы логики предикатов
Например, если Р(х) и Q(x,y) – одноместный идвухместный предикаты, а q, r – переменные
высказывания, то формулами будут, выражения:
q, P(x), P(x) Q(x , y), xP(x) xQ(x, y), (Q(x, y) q) r
0
Не является формулой, например, слово: xQ(x, y) P(x)
Здесь нарушено условие п.3, так как формулу
xQ(x,y) переменная х входит связанно, а в формулу
Р(х) переменная х входит свободно.
Из определения формулы логики предикатов ясно, что
всякая формула алгебры высказываний является
формулой логики предикатов.
17. Интерпретация формулы предикатов
Интерпретацией формулы исчисления предикатовназывается конкретизация множеств, из которых
принимают значения предметные переменные и
конкретизация
отношений
и
соответствующих
множеств истинности для каждой предикатной буквы.
18. Формулы исчисления предикатов
тождественноистинные при
любой
интерпретации,
т.е.
общезначимые
тождественно
ложные
при
любой
интерпретации,
т.е.
противоречивые
выполнимые
(формулы,
истинность
которых зависит
от
интерпретации)
19. Значение формулы логики предикатов
В качестве примера рассмотрим формулуy z (P(x, y) P(y, z))
В формуле двухместный предикат Р(x, y) определен на
множестве MхM, где M={0,1,2,…,n,…}, т.е. MхM=NхN.
В формулу входит переменный предикат P(x,y), предметные
переменные x,y,z, две из которых y и z – связанные кванторами,
а x – свободная.
Возьмем
за
конкретное
значение
предиката
P(x,y)
фиксированный предикат P0(x,y): «x
Тогда при значениях y, меньших x0=5, предикат P0(x0,y)
принимает значение “ложь”, а импликация P(x,y) P(y,z) при
всех z M принимает значение “истина”, т.е. высказывание
имеет значение “истина”.
20. Равносильные формулы логики предикатов
Определение 1.равносильными на области М, если они принимают
одинаковые логические значения при всех значениях входящих в
них переменных, отнесенных к области М.
Определение 2.
Две формулы логики предикатов А и В называются
равносильными, если они равносильны на всякой области.
21. Равносильные формулы логики предикатов
Пусть А(х) и В(х) – переменные предикаты, а С – переменноевысказывание (или формула, не содержащая х). Тогда имеют
место следующие равносильности:
22. Равносильные формулы логики предикатов
ПримерПредикат Мать(x,y) означает, что x является матерью для y.
Тогда y xМать(x,y) означает, что у каждого человека есть
мать, - истинное утверждение.
x yМать(x,y) означает, что существует мать всех людей, что
является другим утверждением, истинность которого зависит от
множества значений, которые могут принимать y: если это
множество братьев и сестер, то оно истинно, а в противном
случае оно ложно.
Таким образом, перестановка кванторов всеобщности и
существования может изменить смысл и значение выражения.
23. Законы логических операций (общезначимые формулы логики предикатов)
24. Упражнение
Найти отрицание следующих формул25. Упражнение
иУпражнение
Доказать равносильность
x(A(x) B(x)) xA(x) xB(x)
Пусть предикаты А(х) и В(х) тождественно ложны. Тогда будет
ложным и предикат A(x) B(x)
x(A(x) B(x))
При этом будут ложными высказывания
xA(x) xB(x)
Пусть хотя бы один из предикатов (например, А(х)) не
тождественно ложный. Тогда будет не тождественно ложным и
предикат A(x) B(x)
При этом будут истинными высказывания xA(x) x(A(x) B(x))
Значит, будут истинными и исходные формулы
Следовательно: x(A(x) B(x)) xA(x) xB(x)
26.
СамостоятельноДля более подробного изучения материала
самостоятельно читаем:
УЧЕБНИК: «Математическая логика и теория
алгоритмов»,
автор Игошин В.И.
Страницы 157-164
Страницы 165-178
Страницы 178-183
27.
Домашнее заданиеДоказать равносильность
C xA(x) x(C A(x))
Доказать что формула является общезначимой
A V (P(x) Q(x)) xP(x) xQ(x)
Доказать что формула является противоречивой
A x((F (x) F (x)) (F (x) F (x)))
Чудесное превращение воды в природе
Герберт УэллсВойна миров
Нам говорят неправду о блокаде ленинграда