Логические операции над высказываниями и предикатами. §4. Операции над предикатами. Логические операции над предикатами

1 . Операция отрицания.

Отрицанием предиката Р(х), заданного на множестве Х, называется предикат , заданный на том же множестве и истинный при тех и только тех значениях х Х, при которых предикат Р(х ) принимает значение лжи.

2 . Операция конъюнкции.

Конъюнкцией предикатов Р(х) и Q(x) , заданных на множестве Х , называется предикат Р(х) Q(x ), заданный на том же множестве и обращающийся в истинное высказывание при тех и только тех значениях х Х, при которых оба предиката принимают значения истины.

Если обозначить ТР Р(х) , Т Q - множество истинности предиката Q(х) , а множество истинности их конъюнкции TPÙQ, то, по всей видимости, TPÙQ = TP Ç TQ.

Докажем это равенство.

1. Пусть а Х и известно, что а Î TPÙQ . По определению множества истинности это означает, что предикат Р(х) Q(x ) обращается в истинное высказывание при х = а , т.е. высказывание Р(а) Q(а ) истинно. Так как данное высказывание конъюнкция, то по определению конъюнкции получаем, что каждое из высказываний Р(а) и Q(а) также истинно. Это означает, что а ТР и а ТQ . Таким образом, мы показали, что TPÙQ Ì ТР Ç ТQ .

2. Докажем обратное утверждение. Пусть а - произвольный элемент множества Х и известно, что а Î TP Ç TQ . По определению пересечения множеств это означает, что а ТР и а ТQ , откуда получаем, что Р(а) и Q(а) - истинные высказывания, поэтому конъюнкция высказываний Р(а) Q(а ) также будет истинна. А это означает, что элемент а принадлежит множеству истинности предиката Р(х) Q(x ), т.е. а Î TPÙQ .

Из 1 и 2 в силу определения равных множеств вытекает справедливость равенства TPÙQ = ТР Ç ТQ , что и требовалось доказать.

Наглядно это можно изобразить следующим образом.

3. Операция дизъюнкции.

Дизъюнкцией предикатов Р(х) и Q(x ) называется предикат Р(х) Q(x Х и обращающийся в истинное высказывание при тех и только тех значениях х Х, при которых принимает значение истины хотя бы один из предикатов Р(х ) или Q(x).

Аналогично доказывается, что TPÚQ = TP È TQ.

4 . Операция импликации.

Импликацией предикатов Р(х) и Q(x) , заданных на множестве Х , называется предикат Р(х) Q(x ), определенный на том же множестве Х и обращающийся в ложное высказывание при тех и только тех значениях х Х, при которых Р(х) принимает значение истины, а Q(x) - значение лжи.

5 .Операция эквиваленции.

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

TPÛQ = .

Пример . На множестве М={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20} заданы предикаты: А(х) - «число х не делится на 5 », В(х) - «х - число четное», С(х) - «х - число простое», D(x) - «число х кратно 3 ». Найти множество истинности следующих предикатов:

a) А(х) В(х); b) A(x) ; c) C(x)A(x); d) B(x)D(x) и изобразить их при помощи диаграмм Эйлера-Венна.

Решение: a) Найдем множество истинности предикатов.

А(х): T = {1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19};

В(х): Т = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}.

Множество истинности конъюнкции А(х) В(х) есть истинности T и Т .

Предикаты так же, как высказывания, могут принимать два значения: “истина” (1) и “ложь” (0), поэтому к ним применимы все операции логики высказываний, в результате чего из элементарных предикатов формируются сложные предикаты (как и в логике высказываний, где из элементарных высказываний формировались сложные, составные). Рассмотрим применение операций логики высказываний к предикатам на примерах одноместных предикатов. Эти операции в логике предикатов сохраняют тот же смысл, который был им присвоен в логике высказываний.

Пусть на некотором множестве M определены два предиката P(x) и Q(x).

Определение 1.

Конъюнкцией двух предикатов P(x) и Q(x) называется новый (сложный) предикат , который принимает значение “истина” при тех и только тех значениях , при которых каждый из предикатов принимает значение “истина”, и принимает значение “ложь” во всех остальных случаях.

Очевидно, что областью истинности предиката является общая часть области истинности предикатов P(x) и Q(x), т.е. пересечение .

Так, например, для предикатов P(x): “x – четное число” и Q(x): “x кратно 3” конъюнкцией является предикат “x – четное число и x кратно трем”, т.е. предикат “x делится на 6”.

Определение 2.

Дизъюнкцией двух предикатов P(x) и Q(x) называется новый предикат , который принимает значение “ложь” при тех и только тех значениях , при которых каждый из предикатов принимает значение “ложь”, и принимает значение “истина” во всех остальных случаях.

Ясно, что областью истинности предиката является объединение области истинности предикатов P(x) и Q(x), т.е. .

Определение 3.

Отрицанием предиката P(x) называется новый предикат или , который принимает значение “истина” при всех значениях , при которых предикат P(x) принимает значение “ложь”, и принимает значение “ложь” при тех значениях , при которых предикат P(x) принимает значение “истина”.

Очевидно, что , т.е. множество истинности предиката является дополнением к множеству I P .

Определение 4.

Импликацией предикатов P(x) и Q(x) называется новый предикат , который является ложным при тех и только тех значениях , при которых одновременно P(x) принимает значение “истина”, а Q(x) – значение “ложь”, и принимает значение “истина” во всех остальных случаях.

Поскольку при каждом фиксированном справедлива равносильность , то .

Определение 5.

Эквиваленцией предикатов P(x) и Q(x) называется новый предикат , который обращается в “истину” при всех тех и только тех , при которых P(x) и Q(x) обращаются оба в истинные или оба в ложные высказывания.

Для его множества истинности имеем:

Кванторные операции.

Рассмотрим операции, преобразующие предикаты в высказывания.

Пусть имеется предикат Р(х) определенный на множестве М. Если “а” – некоторый элемент из множества М, то подстановка его вместо х в предикат Р(х) превращает этот предикат в высказывание Р(а). Такое высказывание называют единичным . Например, r(x): “х – четное число” – предикат, а r (6)- истинное высказывание, r (3) – ложное высказывание.

Это же относится и к n – местным предикатам: если вместо всех предметных переменных х i , i= подставить их значения, то получим высказывание.

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

1.1 Квантор всеобщности.

Пусть Р(х) – предикат , определенный на множестве М. Под выражением понимают высказывание , истинное, когда Р(х) истинно для каждого элемента х из множества М, и ложное в противном случае. Это высказывание уже не зависит от х. Соответствующее ему словесное выражение звучит так: “Для всякого х Р(х) истинно ”.

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

1.2 Квантор существования.

Пусть P(x) -предикат определенный на множестве М. Под выражением понимают высказывание , которое является истинным, если существует элемент , для которого P(x) истинно, и ложным – в противном случае. Это высказывание уже не зависит от x. Соответствующее ему словесное выражение звучит так: “Существует x, при котором P(x) истинно.” Символ называют квантором существования. В высказывании переменная x связана этим квантором (на нее навешен квантор).

Кванторные операции применяются и к многоместным предикатам. Пусть, например, на множестве М задан двухместный предикат P(x,y). Применение кванторной операции к предикату P(x,y) по переменной x ставит в соответствие двухместному предикату P(x,y) одноместный предикат (или одноместный предикат ), зависящий от переменной y и не зависящий от переменной x. К ним можно применить кванторные операции по переменной y, которые приведут уже к высказываниям следующих видов:

Рассмотрим предикат P(x) определенный на множестве M={a 1 ,…,a n }, содержащем конечное число элементов. Если предикат P(x) является тождественно - истинным, то истинными будут высказывания P(a 1),P(a 2),…,P(a n). При этом истинными будут высказывания и конъюнкция .

Если же хотя бы для одного элемента P(a k)окажется ложным, то ложными будут высказывание и конъюнкция . Следовательно, справедлива равносильность .

Численные кванторы.

В математике часто встречаются выражения вида “по меньшей мере n” (“хотя бы n”), “не более чем n”, “n и только n” (“ровно n”), где n – натуральное число.

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

Пусть n=1. Предложение “По меньшей мере один объект обладает свойством P” имеет тот же смысл, что и предложение “Существует объект, обладающий свойством P”, т.е. (*)

Предложение “не более чем один объект обладает свойством P” равнозначно предложению “Если есть объекты, обладающие свойством P, то они совпадают”, т.е. (**) Предложение “один и только один объект обладает свойством P” равнозначно конъюнкции вышеуказанных предложений (*) и (**).

1.3 Отрицание предложений с кванторами.

Известно, что часто для отрицания некоторого предложения достаточно предпослать сказуемому этого предложения отрицательную частицу “не”. Например, отрицанием предложения “Река х впадает в Черное море.” является предложение “ Река х не впадает в Черное море ”. Годится ли этот прием для построения отрицаний предложений с кванторами? Рассмотрим пример.

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

Например, в рассуждении «Всякий ромб – параллелограмм; AВCD – ромб; следовательно, AВCD – параллелограмм» посылки и заключение являются элементарными высказываниями логики высказываний и с точки зрения этой логики рассматриваются как целые, неделимые, без учета их внутренней структуры. Следовательно, алгебра логики, будучи важной частью логики, оказывается недостаточной в анализе многих рассуждений.

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

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

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

Субъект – это то, о чем что-то утверждается в высказывании; предикат – это то, что утверждается о субъекте.

Например, в высказывании «7 – простое число», «7» – субъект, «простое число» – предикат. Это высказывание утверждает, что «7» обладает свойством «быть простым числом»

Если в рассмотренном примере заменить конкретное число 7 переменной х из множества натуральных чисел, то получим высказывательную форму «х – простое число». При одних значениях х (например. х = 13, х = 17) эта форма дает истинные высказывания, а при других значениях х (например, х = 10, х = 18) эта форма дает ложные высказывания.

Ясно, что эта высказывательная форма определяет функцию одной переменной х, определенной на множестве N, и принимающую значения из множества {1,0}. Здесь предикат становится функцией субъекта и выpaжает свойство субъекта.

Определение. Одноместным предикатом Р(х) нaзывается произвольная функция переменного х, определенная на множестве М и принимающая значения из множества {1,0}.

Множество М, на котором определен предикат Р(х), называется областью определения предиката.

Множество всех элементов, при которых предикат принимает значение «истина», называется множеством истинности предиката Р(х) , то есть множество истинности предиката Р(х) – это множество.

Так. предикат Р(х) – «х – простое число» определен на множестве N, а множество для нeгo есть множество всех простых чисел. Предикат Q(x) – «» определен на множествеR, а eгo множество истинности. Предикат F(x) «Диагoнали параллелогpамма х перпендикулярны» определен на множестве всех параллелограммов, а eгo множеством истинности является множество всех ромбов.

Приведенные при меры одноместных предикатов выражают свойства предметов.

Определение. Предикат Р(х), определенный на множестве М, называется тождественно истинным (тождественно ложным), если .

Естественным обобщением понятия одноместного предиката является понятие многоместного предиката, с помощью котopoгo выражаются отношения между предметами.

Примером бинарного отношения (отношения между двумя предметами) является отношение «меньше». Пусть это отношение введено на множестве Z целых чисел. Оно может быть охарактеризовано высказывательной формой «x<у », где, то есть является функцией двух переменных Р(х,у), определенной на множествес множеством значений {1,0}.

Определение. Двухместным предикатом Р(х, у) называется функция двух переменных х и y, определенная на множествеИ принимающая значения из множества {1,0}.

Аналогично определяется n-местный предикат.

Рассматриваемые вопросы
1.
Понятие предиката. Область определения предиката.
2.
Одноместный предикат. Многоместный предикат.
3.
Логические операции над предикатами.

Понятие предиката

Выразительные возможности языка логики высказываний очень
ограничены. С ее помощью невозможно проанализировать
внутреннюю структуру даже очень простых рассуждений.
Пример: есть два умозаключения.
Любой человек смертен, Сократ - человек, следовательно, Сократ
смертен.
Крокодилы не летают, Луна - головка швейцарского сыра,
следовательно, сборная России выиграет чемпионат мира по футболу.
X Y Z.
Расширение
логики
высказываний
называется логикой предикатов

Понятие предиката

Первое высказывание представляется строгим логическим выводом,
второе же не соответствует никакому здравому смыслу.
Эти примеры подтверждают тезис о том, что в логике высказываний не
рассматривается внутреннее содержание простейших высказываний
(атомарных формул).
Не имеется
высказывания.
возможности
«влезть»
внутрь
элементарного
Расширение логики высказываний называется логикой предикатов.

Понятие предиката

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

Понятие предиката

Логика предикатов, как и традиционная формальная логика,
расчленяет
элементарное
высказывание
на
субъект
(подлежащее, хотя оно может играть и роль дополнения) и
предикат (сказуемое, хотя оно может играть и роль
определения).
Субъект – это то, о чем что-то утверждается в высказывании
Предикат – это то, что утверждается о субъекте
Например, в высказывании “7 - простое число”, “7” – субъект,
“простое число” – предикат.
Это высказывание утверждает, что “7” обладает свойством
“быть простым числом”.

Понятие предиката

ПРИМЕР “7 - простое число”
Если в рассмотренном примере заменить конкретное число 7
переменной х из множества натуральных чисел, то получим
высказывательную форму:
“х – простое число”
При одних значения х (например, х=13, х=17) эта форма дает
истинные высказывания, а при других значениях х (например,
х=10, х=18) эта форма дает ложные высказывания.
Эта высказывательная форма определяет функцию одной
переменной х, определенной на множестве N, и принимающую
значения из множества {1;0}.
Здесь предикат становится функцией субъекта и выражает
свойство субъекта.

Понятие предиката

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

Понятие предиката

Таким образом, раздел математической логики, изучающий логические
законы, общие для любой области объектов исследования
(содержащей хоть один объект) с заданными на этих объектах
предикатами (т. е. свойствами и отношениями) называется ЛОГИКОЙ
ПРЕДИКАТОВ
Объект – некоторая часть окружающего нас мира, которая может быть
рассмотрена как единое целое
Субъект – (в логике) подлежащее суждения, то есть предмет, о
котором что-либо говорится или мыслится
Переменное высказывание, истинностное значение которого зависит
от параметра, и называется предикатом.
Предикат от лат. Praedicatum – сказанное. Таким образом, предикат
есть функция, определенная на некотором множестве параметров и
со значениями в {0, 1}.

Понятие предиката

Определение 1. Одноместным предикатом Р(х) называется такая функция
одной переменной, в которой аргумент х пробегает значения из некоторого
множества М, а функция при этом принимает одно из двух значений: истина
или ложь.
Само множество М называется предметным множеством, а аргументы
x1,...,xn M - предметными переменными.
Множество М, на котором задан предикат, называется областью определения
предиката.
Множество, на котором предикат принимает только истинные значения,
называется областью истинности предиката Р(х).
Определение 2. N-местным предикатом называется такая функция n
переменных Q(x1, x2, …,xn), определенная на множестве М=М1 М2 … Мn
и принимающая на этом множестве одно из двух значений: истина или ложь.
Можно считать, что высказывание это нульместный предикат, то есть
предикат, в котором нет переменных для замены.

10. Понятие предиката. Примеры

Пример 1
Пусть предметное множество М есть класс млекопитающих.
Рассмотрим одноместный предикат Р(х):
«У х четыре ноги».
Тогда Р(слон) = 1,
Р(кошка) = 1,
Р(человек) =0.
Пример 2
Пусть М - множество натуральных чисел.
Рассмотрим двухместный предикат G(x,y): х<у.
Тогда, например, G(l,3) = l,
G(8,5) = 0.

11. Классификация предикатов

Предикат называется:
А) Тождественно истинным, если значение его для любых
аргументов есть «истина»
Предикат “x+y=y+x” является тождественно истинным.
Б) Тождественно ложным, если значение его для любых
аргументов есть «ложь»
Предикат “x+1=x” – тождественно ложным.
В) Выполнимым, если существует, по крайней мере, одна nсистема его аргументов, для которой значение предиката есть
«истина».
Предикат “x+y=5” – выполнимым.

12. Равносильность предикатов

Два n-местных предиката Р(х1, х2, ..., хn) и Q(x1, x2, ..., хn),
заданных над одними и теми же множествами М1, М2, …, Мn,
называются равносильными, если набор предметов (элементов)
а1 М1, а2 М2, .., an Мn превращает первый предикат в
истинное высказывание Р(а1, а2, …, аn) в том и только в том
случае, когда этот набор предметов превращает второй предикат
в истинное высказывание Q(а1, а2, …, аn).
Предикаты Р(х1, х2, ..., хn) и Q(х1, х2, ..., хn) равносильны тогда
и только тогда, когда их множества истинности совпадают
Р+ = Q+.
Переход от одного равносильного предиката к другому
называется равносильным преобразованием первого

13. Пример

Пусть требуется решить
уравнение (найти множество
истинности предиката):
4х-2=-3х-9
Преобразуем его равносильным образом:
4х-2=-3х-9 4х+3х=-9 + 2 x = -1.
Ответ:{-1} - множество всех решений данного уравнения
(множество истинности данного предиката).

14. Следование предикатов

Предикат Q(х1, х2, ..., хn), заданный над множествами М1, М2,
…, Мn, называется следствием предиката Р(х1, х2, ..., хn),
заданного над теми же множествами, если он превращается в
истинное высказывание на всех тех наборах значений
предметных переменных из соответствующих множеств, на
которых в истинное высказывание превращается предикат Р(х1,
х2, ..., хn).
Предикат Q является следствием предиката Р тогда и только
тогда, когда Р + Q +.
Обозначается P Q

15. Пример

Одноместный предикат, определенный на
множестве
натуральных чисел, «n делится на 3» является следствием
одноместного предиката, определенного на том же множестве,
«n делится на 6».
Из двух предикатов первый будет следствием второго, если
считать, что оба предиката заданы на множестве Z целых чисел.

16. Упражнение 1.

Среди следующих предложений выделите предикаты:
1) Луна есть спутник Венеры
2) Планеты х и y принадлежат Солнечной системе
3) 5 5 70 6 10 150
2
4) x 3x 2 0
4
x
3x 8
5)
6) Любое простое число не имеет делителей, отличных от себя и 1
7) Натуральное число n не меньше 1
8) Треугольник АВС равен треугольнику А1В1С1
9) x 2 2 x 1 0
1
10) 1 tg 2 x
cos 2 x
11) ln x sin x
Ответ: 2); 4); 7)-11)

17.

Упражнение 2.
Среди следующих предложений выделить предикаты и для каждого из
них указать область истинности.
1) x+5=1
2) При х=2 выполняется равенство х2-1=0
3) х2-2x+1=0
4) Существует такое число х, что х2-2x+1=0
5) x+2<3x-4
6) Однозначное число x кратно 3
7) (x+2)-(3x-4)
1)
2)
3)
4)
5)
6)
7)
Одноместный предикат P(x), Ip=-4
Ложное высказывание. Не предикат
Одноместный предикат P(x), Ip=1
Истинное высказывание. Не предикат
Одноместный предикат P(x), Ip=(3;+)
Одноместный предикат P(x), Ip=(0;3;6;9)
Не предикат

18. Логические операции над предикатами

Отрицанием предиката P(x) называется новый предикат,
множество истинности которого является дополнением
множества истинности предиката Р(х), то есть:
I p CI p
Пример. Предикат P(x) - «x<3»
Отрицание предиката – «x>3»

19. Логические операции над предикатами

Конъюнкцией предикатов P(x) и Q(x) называется новый

значениях, при которых каждый из предикатов P(x) и Q(x)

Множество истинности есть пересечение множеств истинности
I P Q I p I q
Пример. Предикаты P(x) - «x>-3» и Q(x) – «x<3»
Конъюнкция предикатов – «(x>-3) Λ (x<3)»

20. Логические операции над предикатами

Дизъюнкцией предикатов P(x) и Q(x) называется новый
предикат, который принимает значение 1 при тех и только тех
значениях, при которых хотя бы один из предикатов P(x) и Q(x)
принимает значение 1 и принимает 0 во всех остальных случаях.

I P Q I p I q
Пример. Предикаты P(x) - «x≠0» и Q(x) – «y ≠0»
Дизъюнкция предикатов – «(x ≠0) v (y ≠0)»

21. Логические операции над предикатами

Импликацией предикатов P(x) и Q(x) называется предикат,
который имеет значение ложь на тех и только на тех наборах
аргументов х, на которых P(x) имеет значение 1, а Q(x) –
значение 0.
Множество истинности есть объединение множеств истинности
I P Q CI p I q
Пример. Предикаты P(x) - «Натуральное число х делится на 3».
Q(x) – «Натуральное число х делится на 4»
Импликация предикатов – «Если натуральное число х
делится на 3, то оно делится и на 4»

22. Логические операции над предикатами

Эквиваленцией P(x) и Q(x) называется предикат, который имеет
значение истина на тех и только на тех наборах аргументов х, на
которых значения истинности P(x) и Q(x) совпадают.
Множество истинности есть объединение множеств истинности
I P Q (CI p CI q) (I p I q)

23.

Упражнение 3.
Пусть даны предикаты P(x): «х – четное число» и Q(x): «х кратно 3»,
определенные на множестве N. Найти области истинности
предикатов:
1) P(x) Λ Q(x)
2) P(x) v Q(x)
3) ¬P(x)
4) P(x) -> Q(x)
Ip = {2,4,6,8,10,12,…2n,…}, Iq= { 3,6,9,12,...3n,…}
1)
2)
3)
4)
{6,12,…6n,…}
{2,3,4,6,…2n,3n,…}
{1,3,5,…2n-1,…}
{1,3,5,…2n-1,…} v {3,6,9,…3n,…}

24.

Упражнение 4.
Если значения x,y принадлежат отрезку , то в списке
выражений следующего вида:
1) х=2 или y=7
2) x-y=7
3) x+y<2
4) x 2 5 0
5) 3 6) x>12
Число истинных и ложных предикатов соответственно равно:
А) 2,4
Б) 1,4
В) 3,3
Г) 1,5
Д) 2,3
ОТВЕТ Г) 1,5

25.

Упражнение 5.
Запишите предикат (условие, которое может быть и сложным),
полностью описывающий область, нестрого заключенную между
окружностью с центром в начале координат и радиусом 2 и
квадратом, в который вписана эта окружность.
Уравнение окружности имеет вид: x 2 y 2 4
Уравнения квадрата: x 2
y 2
Искомая область образуется пересечением внешней области
окружности, и внутренней области квадрата
Таким образом, ответ: (x 2 y 2 4) & (x 2) & (y 2)

26.

Самостоятельно
Для более подробного изучения материала
самостоятельно читаем:
УЧЕБНИК: «Математическая логика и теория
алгоритмов»,
автор Игошин В.И.
Страницы 146-156

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

Отрицание предиката . Пусть предикат P(x 1 , x 2 , ..., x n) задан на множествах M 1 , M 2 , ..., M n . Предикат R(x 1 , x 2 ,..., x n) называется отрицанием предиката P(x 1 , x 2 , ..., x n) тогда и только тогда, если при одних и тех же кортежах (a 1 , a 2 , ... , a n), где а 1 M 1 , а 2 M 2 , ..., аn M n , высказывание P(a 1 , a 2 , ..., a n) истинно, когда R(a 1 , a 2 , ..., a n) - ложно и наоборот. Обозначение

R(x 1 , x 2 , ..., x n) ù P(x 1 , x 2 , ..., x n)

Например, предикат "n - четное число" есть отрицание предиката "n - нечетное число" на множестве целых чисел.

Конъюнкция предикатов . Пусть на множествах M 1 , M 2 , ..., M n заданы два n - местных предиката P(x 1 , x 2 , ..., x n) и R(x 1 , x 2 , ..., x n). Конъюнкцией этих предикатов называется предикат

Q(x 1 , x 2 , ..., x n) P(x 1 , x 2 , ..., x n) R(x 1 , x 2 , ..., x n),

который истинен для одних и тех же кортежей только тогда, когда оба предиката и P(x 1 , x 2 , ..., x n) и Q(x 1 , x 2 , ..., x n) истинны.

Например, конъюнкция предикатов "x 2 + y 2 1" и "x 0", где x, y - вещественные числа определяет предикат "точки правой половины единичного круга" (см. рис.2.2).

Дизъюнкция предикатов P(x 1 , x 2 , ..., x n) и R(x 1 , x 2 , ..., x n), есть новый предикат S(x 1 , x 2 , ..., x n) = P(x 1 , x 2 , ..., x n) R(x 1 , x 2 , ..., x n), который имеет значение "ложь" для тех и только тех кортежей из M 1 M 2 ... M n , для которых оба предиката и P(x 1 , x 2 , ..., x n) и R(x 1 , x 2 , ..., x n) имеют значение "ложь". На рис.2.3 иллюстрируется дизъюнкция предиката "x 2 + y 2 1" и "x 0" - (заштрихованная область).

Импликация предикатов P(x 1 , x 2 , ..., x n) и R(x 1 , x 2 , ..., x n), есть новый предикат T(x 1 , x 2 , ..., x n) = P(x 1 , x 2 , ..., x n) R(x 1 , x 2 , ..., x n), который имеет значение "ложь" для тех и только тех кортежей из M 1 M 2 ... M n , для которых предикат P(x 1 , x 2 , ..., x n) имеет значение "истина", а предикат R(x 1 , x 2 , ..., x n) имеет значение "ложь". Например, импликация "n делится на 4" " n делится на 2" есть предикат: "если n делится на 4, то n делится на 2".

Эквивалентность предикатов P(x 1 , x 2 , ..., x n) и R(x 1 , x 2 , ..., x n), есть новый предикат V(x 1 , x 2 , ..., x n) = P(x 1 , x 2 , ..., x n) R(x 1 , x 2 , ..., x n), который имеет значение "истина" для тех и только тех кортежей из M 1 M 2 ... M n , для которых предикат P(x 1 , x 2 , ..., x n) и предикат R(x 1 , x 2 , ..., x n) имеют одинаковые значение или оба "истина" или оба "ложь". Два предиката заданных на одних и тех же множествах называются равносильными , если при всех наборах входящих в них предметных переменных эти предикаты принимают одинаковые значения. Равносильность называют также логической эквивалентностью . Например, эквивалентность предикатов P(n) = "n делится на 6" и R(n) = "n делится на 2 и n делится на 3" есть предикат V(n) = P(n) R(n): "если n делится на 6, то n делится на 2 и на 3". Предикаты P(n) и R(n) логически эквивалентны.

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

Квантор всеобщности есть операция, которая предикат P(x) превращает в высказывание: "все x обладают свойством P(x)". Знак квантора всеобщности " ". Он заменяет фразы: "для всех", "каждый", "любой" и т.п. Обозначение x: P(x) читается так: "для всех x таких, что P от x". Например, “P(x) = x>0 , где x - вещественное число”, есть предикат "x - положительное число". Тогда x: P(x) есть высказывание "каждое число - положительно". Это ложное высказывание. Если же x - любое натуральное число (x N), то x: P(x) есть выражение: "каждое натуральное число - положительно" - истинное высказывание.

Квантор всеобщности можно рассматривать как обобщение серии конъюнкций единичных высказываний. Пусть M - множество очков, которое может выпасть при бросании игральной кости, т.е. M ={1,2,3,4,5,6} и P(x) - предикат: "при бросании игральной кости один раз выпадает x очков", где x M. Применение квантора всеобщности позволяет вместо сложного высказывания P(1) P(2) P(3) P(4) P(5) P(6) записать равносильное ему компактное высказывание x: P(x), x M: "при бросании игральной кости один раз может выпасть любое из шести первых натуральных чисел".

Квантор существования есть операция, которая предикат P(x) превращает в высказывание: "существует хотя бы один x из M, обладающий свойством P(x)". Знак квантора существования " ". Он заменяет фразы: "существует, хотя бы один", "найдется", "некоторый" и т.п. Обозначение x: P(x) читается так: "существует хотя бы один x такой, что P от x". Например, P(x) - предикат: "x - студент", где x - элемент множества жителей Москвы. Тогда выражение x: P(x) есть высказывание "хотя бы один житель Москвы является студентом".

Квантор существования можно рассматривать как обобщение серии дизъюнкций единичных высказываний. Если задано множество M={a 1 , a 2 , ..., a n } и на нем определен предикат P(x), то

P(а 1) P(а 2) ... P(а n) ( x M): P(x).

Кванторы обладают свойствами, являющимися аналогами законов де Моргана:

ù( x: P(х)) х:ù P(х),

ù( х: P(х)) х: ùP(х).

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

Переход от P(х) к х:P(х) или х:P(х) называется квантификацией или связыванием переменнойх . Связанная переменная фактически не является переменной, т.е. переход от х: P(х) к y:P(y) или от х:P(х) к y: P(y) не меняет истинности выражений. Навешивание переменной на многоместный предикат уменьшает в нем число свободных переменных и превращает его в предикат от меньшего числа переменных.

Рассмотрим пример. На множестве чисел задан двухместный предикат P(х,y)="число х делится на число y". Связывая одну переменную, можно получить следующие одноместные предикаты:

Х: P(х,y) = "каждое число делится на y" - ложь;

X: P(x,y) = "существует число, которое делится на y"- истина;

Y: P(х,y) = "число х делится на любое число" - ложь;

Y: P(х,y) = "существует число на которое делится х" - истина.

Связывая обе переменные данного предиката, получим высказывания:

Х, y:P(х,y)="каждое число делится на любое число" - ложное высказывание,

Х, y:P(х,y)="существует число, на которое делится любое число" - истина, т.к. такое число есть 1,

Х, y:P(х,y)="существует число, которое делится на любое число" - ложное высказывание,

Х, y: P(х,y)="существует число, которое делится на какое-нибудь число" - истинное высказывание.

Статьи по теме