Алгебра предикатов

Логика, алгебра и исчисление предикатов

В логике высказываний элементарным объектом, обладающим зна-чением истинности, является высказывание, которое никаким образом нельзя разделить на компоненты. Логика предикатов разделяет атомарное высказывание на субъект (подлежащее) и предикат (сказуемое). Субъект - это то, о чём что-то утверждается в высказывании, предикат-это то, что ут-верждается о субъекте. Пример: “7-простое число”. “7”- субъект, “простое число”- предикат. Заменим 7 переменной Х из множества натуральных чисел, то получим высказывание “Х-простое число”. При одних значе-ниях Х (13,17) это истинное высказывание, при других (10,18)- ложное, т. е. получим функцию, значение которой зависит от значений Х -аргумента.

Определение. Одноместным предикатом P(x)называется произволь-ная функция переменного x, определённая на множестве M и принимаю-щая значения из множества {1,0}. Множество M, на котором определён предикат P(x), называется областью определения предиката. Множество всех элементов xÎM, при которых предикат P(x), принимает значение “истина” называется множеством истинности предиката и обозначается Ip. Предикат P(x) называется тождественно истинным (тождественно ложным) на множестве M, если Ip = M (Ip= Æ).

Пример:Предикат P(x) ”Диагонали параллелограмма x перпендикуляр-ны” определён на множестве всех параллелограммов, а его множеством истинности является множество всех ромбов.

Одноместные предикаты выражают свойства предметов. Обобщением по-нятия одноместного предиката является понятие многоместного предиката с помощью которого выражаются отношения между предметами.

Определение. Двухместным предикатом P(x,y), называется функция двух переменных x и y, определённая на множестве M = M1 X M2 и принимающая значения из множества {1,0}. Пример: Q(x,y) “x = y”- предикат равенства, определённый на множестве RІ = R ´ R, где R- множество действительных чисел. Аналогично определяется n- местный предикат.

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

Определение. Отрицанием предиката P(x) называется новый предикат ù P(x), который принимает значения “истина” при всех значениях xÎM, при которых предикат P(x) принимает значение “ложь”, и принимает значение “ложь” при тех значениях xÎM, при которых предикат P(x) принимает значение “истина”. Областью истинности предиката является: ùI p =-Ip.

Пример: Для одноместного предиката “X больше двух”, определённого на множестве действительных чисел, отрицанием будет одноместный предикат “X не больше двух”, также определённый на множестве действительных чисел.

Определение. Конъюнкцией двух одноместных предикатов P(x) и Q(y) называется новый двухместный предикат P(x)ÙQ(y), который принимает значение “истина” при тех и только тех значениях xÎM yÎN, при которых каждый из предикатов принимает значение “истина”, и принимает значение “ложь” во всех остальных случаях. Областью истинности предиката является: I pÙq = IPÇIQ. Пример: Для одноместного предиката “X-чётное число” и одноместного предиката “точка y лежит на прямой”, определённых на множестве натуральных чисел и множестве точек, конъюнкцией этих предикатов будет двухместный предикат “X-чётное число и точка y лежит на прямой”.

Определение. Дизъюнкцией двух одноместных предикатов P(x) и Q(y) называется новый двухместный предикат P(x)ÚQ(y), который принимает значение “ложь” при тех и только тех значениях xÎM и yÎN, при которых каждый из предикатов принимает значение “ложь” и принимает значение “истина” во всех остальных случаях. Областью истинности предиката является: IpÚq = IPÈIQ. Пример: Для одноместного предиката “x-простое число” и одноместного предиката “y-равносторонний треугольник” дизъюнкцией будет двухместный предикат “x - простое число или y - равносторонний треугольник”

Определение. Импликацией двух одноместных предикатов P(x) и Q(y) называется двухместный предикат P(x)®Q(y), который принимает значение “ложь” при тех и только тех значениях xÎM и yÎN,при которых P(x) принимает значение “истина” и Q(y) принимает значение “ложь”, во всех остальных случаях предикат P(x)®Q(y) принимает значение “истина”. Областью истинности предиката является: Ip®q=IùPÈIQ -это следует из A ® B = ù A Ú B. Пример: Для одноместных предикатов, определённых на одном и том же множестве целых чисел “x-делится на шесть” и “x-делится на три” импликацией будет одноместный предикат, определённый на том же множестве: “если x-делится на шесть, то x-делится на три”.

Определение. Эквивалентностью двух одноместных предикатов P(x) и Q(y) называется двухместный предикат P(x)«Q(y), который принимает значение “истина” при тех и только тех значениях xÎM и yÎN, при которых P(x) и Q(y) принимают одинаковые значения и “ложь” во всех остальных случаях. Областью истинности предиката является: I p«q =(IùPÈIQ)Ç(IùQÈIP) -это следует из A «B = (A ® B) Ù (B ® A) и A ® B = ù A Ú B. Пример: Для двух одноместных предикатов “x-делится на два” и “x-чётное число” эквивалентностью будет “x-делится на два тогда и только тогда, когда x-чётное число”. Операции конъюнкции, дизъюнкции, импликации и эквивалентности можно применять также к предикатам, у которых общие переменные (с одинаковой областью определения). В таком случае число переменных конъюнкции и дизъюнкции, а следовательно и местность этих предикатов будет равняться числу различных (с разной областью определения) переменных предикатов, составляющих эти дизъюнкцию, конъюнкцию, импликацию и эквивалентность (смотри два последних примера).

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

Определение. Пусть P(x)- предикат определённый на множестве M. Под выражением "x P(x) понимают высказывание, истинное, когда P(x) тождественно истинный на множестве M предикат и ложное в противном случае. Соответствующее ему словесное выражение будет: “Для всякого x P(x) истинно”. Символ " называют квантором всеобщности.

Определение. Пусть P(x)- предикат определённый на множестве M. Под выражением $xP(x) понимают высказывание, которое является истинным, если существует хотя бы один элемент xÎM для которого P(x) истинно, и ложным в противном случае. Соответствующее ему словесное выражение будет :”Существует x, при котором P(x) истинно”. Символ $ называют квантором существования. Пример: Пусть P(x) одноместный предикат “Число x кратно 5”, определённый на множестве натуральных чисел, тогда высказывание "xP(x)-”Все натуральные числа кратны 5”-ложно, а высказывание $xP(x)-”Существует натуральное число, кратное 5” истинно. Переменную x в предикате P(x) называют свободной (ей можно придавать различные значения из M), в высказывании "xP(x) или $xP(x) -переменную x называют связанной квантором " или $, т.к. от этой переменной истинность или ложность высказываний не зависит. Нетрудно видеть, что когда предикат P(x) определён на конечном множестве M={x1,x2,...xn}, то "xP(x)=P(x1)ÙP(x2)Ù¼ÙP(xn), а $xP(x)=P(x1)ÚP(x2)Ú¼ÚP(xn), то есть кванторные операции обобщают операции конъюнкции и дизъюнкции на случай конечных множеств. Кванторные операции применяются и к многоместным предикатам. Так, применение к двухместному предикату Q(x,y) квантора всеобщности по переменной x даёт одноместный предикат "xQ(x,y), зависящий от y. К этому предикату можно применить кванторную операцию по переменной y. В результате получим или высказывание "y"xQ(x,y), или высказывание $y"xQ(x,y). В общем случае, пусть P(x1,x2,¼xn),- n -местный предикат, определённый на множествах M1,M2,...Mn (n ³ 2). Предикатом, полученном из P(x1,x2,¼xn) применением квантора всеобщности (существования) по переменной x, называется (n-1) - местный предикат "x1P(x1,x2,¼xn) ($x1P(x1,x2,¼xn)),- определённый на множествах. К этим(n-1)-местным предикатам снова можно применить один из кванторов по любой свободной переменной, получая (n-2)-местные предикаты и т.д. После n -кратного применения кванторов к n -местному предикату все его свободные переменные будут связаны, и получится высказывание.

Можно показать, что перестановка любых кванторов местами для многоместных предикатов изменяет логическое значение высказывания. Пример: Пусть предикат Q(x,y) “y делитель x“ определён на множестве натуральных чисел. Тогда высказывание "y$xQ(x,y),-”Для всякого натурального числа y существует натуральное число x такое, что y является делителем x “ истинно, а высказывание $x"yQ(x,y), отличающееся от предыдущего перестановкой кванторов и означающее, что “Есть натуральное число x, которое делится на любое натуральное число y “ ложно.

В алгебре предикатов будем пользоваться следующей символикой:

- символы p,q,r,...- переменные высказывания, принимающие два значения: 1 -истина, 0 -ложь.

- предметные переменные x,y,z,..., которые пробегают значения из некоторого множества M; x°,y°,z°,...- предметные константы, т.е. значения предметных переменных.

- P(·),F(·)- одноместные предикатные переменные; Q(·,·,...,·),R(·,·,...,·) - n -местные предикатные переменные;

- P°(·),Q°(·,·,...,·)- символы постоянных предикатов.

- символы логических операций: Ù,Ú,®,ù.

- символы кванторных операций :"x,$y.

- вспомогательные символы: скобки, запятые.

Правилами описания формул алгебры предикатов являются следующие:

-каждое высказывание как переменное, так и постоянное, является формулой(элементарной).

-если F(·,·,...,·)- n -местная предикатная переменная или постоянный предикат, а x1,x2,¼xn предметные переменные или предметные постоянные (не обязательно все различные), то F(x1,x2,¼xn) есть формула. Такая формула называется элементарной, в ней предметные переменные являются свободными, не связанными кванторами.

-если A и B-формулы, причём такие, что одна и таже предметная переменная не является в одной из них связанной, а в другой - свободной, то слова A Ù B, A ® B, A Ú B есть формулы. В этих формулах те переменные, которые в исходных формулах были свободными, являются свободными, а те, которые были связанными, являются связанными.

- если A -формула, то ù A -формула, и характер предметных переменных при переходе от формулы A к формуле ù A не меняется.

-если P(x)- формула, в которую предметная переменная x входит свободно, то слова "xP(x) и $xP(x) являются формулами, причём предметная переменная входит в них связано.

- всякое слово, отличное от тех, которые выше названы формулами, формулами не являются.

Пример: Если P(x) и Q(x,y) - одноместный и двухместный предикаты, а q, r,- переменные высказывания, то формулами будут слова: q, P(x), P(x)ÙQ(x°,y), "xP(x)®$xQ(x,y), (ùQ(x,y)Ú q)®r. Не является формулой слово: "xQ(x,y)®P(x), т.к.

здесь в формулу "xQ(x,y) переменная x входит связано, а в формулу P(x), переменная x входит свободно. Логическое значение формулы алгебры предикатов зависит от значений трёх видов переменных:

· значений, входящих в формулу переменных высказываний;

· значений свободных предметных переменных из множества M;

· значений предикатных переменных.

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

Пример: Рассмотрим формулу: $y"z(P(x,y)®P(Y,Z)), в которой двухместный предикат P(x,y)- определён на множестве M´M, где M = {0,1,2,...,n,...}. В эту формулу входит переменный предикат P(x,y)- предметные переменные x, Y, Z, две из которых Y и Z -связанные квантором, а x -свободная. Возьмём за конкретное значение предиката P(x,y) фиксированный предикат P°(x,y): “x < y”, а свободной переменной x придадим значение x°=5 Î M. Тогда при значениях Y, меньших x°=5 предикат P°(x°,y)- принимает значение ложь, а импликация P(x,y)®P(Y,Z) при всех z Î M принимает значение истина, т.е. высказывание $y"z(P°(x,y)®P°(Y,Z)) имеет значение “истина”.

Определение. Две формулы алгебры предикатов A и B называются равносильными на области M, если они принимают одинаковые логические значения при всех значениях входящих в них переменных, отнесённых к области M

Определение. Две формулы алгебры предикатов A и B называются равносильными, если они равносильны на всякой области M.

Очевидно, что все равносильности алгебры высказываний будут верны, если в них вместо переменных высказываний подставить формулы алгебры предикатов. Но, кроме того, имеют место равносильности самой алгебры предикатов. Пусть A(x) и B(x)- переменные предикаты, а R -переменное высказывание.

Тогда:

1. ù " x A(x) º $ xù A(x),

2. ù $ x A(x) º " xù A(x),

3. " x A(x) ºù $ xù A(x),

4. $ x A(x) ºù " xù A(x),

5. " x A(x) Ù" x B(x) º " x [A(x) Ù B(x)],

6. R Ù" x B(x) º " x [R Ù B(x)],

7. R Ú " x B(x) º " x [R Ú B(x)],

8. R ® " x B(x) º " x [R ® B(x)],

9. " x [B(x)®R] º $ x B(x)®R,

10. $ x [A(x) Ú B(x)] º $ x A(x) Ú $ x B(x),

11. $ x [R Ú B(x)] º R Ú $ x B(x),

12. $ x [R Ù B(x)] º R Ù $ x B(x),

13. $ x A(x) Ù$ y B(y) º $ x $ y [A(x) Ù B(y)],

14. $ x [R ® B(x)] º R ® $ x B(x),

15. $ x [B(x)®R] º " x B(x)®R,

16. " x A(x) Ú " x B(x) º " x A(x) Ú " y B(y) º º" x [A(x) Ú " y B(y)] º " x " y [A(x) Ú B(y)],

17. $ x A(x) Ù $ x B(x) º $ x A(x) Ù $ y B(y) º º$ x [A(x) Ù $ y B(y)] º $ x $ y [A(x) Ù B(y)].

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

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

Например: Привести к нормальной форме следующую формулу: ($ x A(x) ®" y B(y)) ® R(z)

Используя последовательно равносильности II-2,II-4,I-9 из раздела 2.2.3. Логика, алгебра и исчисление высказываний и равносильность 1 из раздела 2.2.4. Логика, алгебра и исчисление предикатов, проведём следующие преобразования:

($ x A(x) ®" y B(y)) ® R(z) ºù (ù $ x A(x) Ú " y B(y)) Ú R(z) º

ºù ù $ x A(x) Ùù " y B(y) Ú R(z) º $ x A(x) Ù $ yù B(y) Ú R(z).

Рассмотрим классы формул, существующих в алгебре предикатов.

Определение. Формула A алгебры предикатов называется выполнимой в области M, если существуют значения переменных, входящих в эту формулу и отнесённых к области M, при которых формула A принимает истинные значения.

Определение. Формула A называется выполнимой, если существует область, на которой эта формула выполнима.

Определение. Формула A называется тождественно-истинной в области M, если она принимает истинные значения для всех значений переменных, входящих в зту формулу и отнесённых к этой области.

Определение. Формула A называется общезначимой, если она тождественно - истинна на всякой области.

Определение. Формула A называется тождественно-ложной в области M, если она принимает ложные значения для всех значений переменных, входящих в эту формулу и отнесённых к этой области.

Из приведённых определений следует:

1. Если формула A общезначима, то она и выполнима на всякой области.

2. Если формула A тождественно-истинна в области M, то она и выполнима в этой области.

3. Если формула A тождественно-ложна в области M, то она невыполнима в этой области.

4. Если формула A не выполнима, то она тождественно-ложна на всякой области.

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

Пример: Формула "x $ y R(x,y)- выполнима. Действительно, если R(x, y)- предикат “x < y”, определённый в области M = E ´ E, где E = { 0,1,2,¼,k,¼}, то формула " x $ y R(x,y)- тождественно-истинна в области M, и, следовательно выполнима в этой области. Однако, если предикат “x < y” рассматривается в конечной области M1 = E1 ´ E, где E1 = { 0,1,2,¼,k}, то формула " x $ y R(x,y)- будет тождественно-ложной в области M1 (при x=k, y=k или y<k), и, следовательно, не выполнима в области M1. При этом ясно, что формула " x $ y R(x,y) - не общезначима.

Пример: Формула $ x $ y [ R(x)Ùù R(y)] - выполнима. Действительно, если R(x)- предикат “число x-чётное”, определённый в области M = E ´ E, где E = { 0,1,2,¼,k,¼}, то эта формула тождественно-истинна в области M, и, следовательно, выполнима в области M. Однако, если предикат “число x-чётное” рассматривать в области M1 = E1 ´ E1, где E1 = { 2,4,6,¼,2k,¼,}- множество чётных чисел, то формула $ x $ y [ R(x)Ù ù R(y)]- будет тождественно-ложной в области M1, и, следовательно, не выполнимой.

Пример: Формула " x [ R(x)Ú ù R(х)]- тождественно-истинна в любой области M. Значит она является общезначимой то есть является логическим законом.

Пример: Формула " x [ R(x)Ù ù R(X)]- тождественно-ложная в любой области M, и поэтому она не выполнима

Дата добавления: 2015-06-27