Лекции, шпаргалки, информация по предметам, статьи, лабораторные, тех.задания


Кафедра ИС(АВТ)

Основы дискретной математики - Вопрос 21

Лекции(шпаргалка) по основам дискретной математики для кафедры Информационных систем (ИС), факультет Автоматики и вычислительной техники (АВТ).

Вопрос 21
Алгебра предикатов
Простейшими логическими операциями над предикатами, так же как и над высказываниями, являются отрицание, конъюнкция, дизъюнкция, импликация и эквивалентность. Они обычно обозначаются теми же символами, что и для высказываний, хотя иногда могут быть и отличия. При выполнении указанных операций от содержания предикатов отвлекаются: они рассматриваются только с точки зрения их значений. Другими словами, равносильные предикаты не различаются. Перечисленные операции определяют алгебру предикатов. Отрицанием п - местного предиката А(х1, х2,...,xп), определенного на множествах M1, М2,...,Мn, называется новый и - местный предикат, определенный на тех же множествах, обозначаемый |А(х1, х2,...,xп). Он читается "неверно, что A(х1, х2,...,xп) и имеет значение "истина" для тех и только тех его аргументов x01, х2,...,xп, для которых значение данного предиката А(х1, х2,...,xп) есть "ложь". Пример 3.26. Для одноместного предиката "х больше двух", определенного на множестве действительных чисел R, отрицанием будет одноместный предикат "х не больше двух", также определенный на множестве действительных чисел. Конъюнкцией п - местного предиката А(х1, х2,...,xп), определенного на множествах M1, М2,..., М3, и т-местного предиката B(y1,y2,...,ym), определенного на множествах N1, N2,..., Nm, называется новый (п + т) - местный предикат, определенный на множествах M1, М2,..., Мn, N1, N2,..., Nm, обозначаемый А(х1, х2,...,xп), /\ B(y1, у2,... уm) ( читается: "А(х1, х2,...,xп) и B(y1, у2,... уm). Он имеет значение "истина" для тех и только тех его аргументов х1, х2,...,xп, y1, у2,... уm для которых значения соответственно предикатов А(х1, х2,...,xп) и В(y1, у2,... уm) для аргументов какх01, х02,...,x0п, так и y01, у02,... у0m суть "истина".

Пример 3.27. Для одноместного предиката "х > 2", определенного на множестве действительных чисел, и двуместного предиката "у < z", также определенного на множестве действительных чисел, конъюнкцией будет предикат "x> 2 и у< z", все предметные переменные которого определены на множестве действительных чисел.

Дизъюнкцией п - местного предиката А(х1, х2,...,xп), определенного на множествах M1, М2,..., Мn, и m - местного предиката B(y1, у2,... уm), определенного на множествах N1, N2,..., Nm, называется новый (n + m) - местный предикат, определенный на множествах M1, М2,..., Мn, N1, N2,..., Nm, обозначаемый А(х1, х2,...,xп), v B(y1, у2,... уm). Он имеет значение "истина" для тех и только тех его аргументов х01, х02,...,x0п, y01, у02,... у0m для которых значение по крайней мере одного из предикатов А(х1, х2,...,xп) или В(y1, у2,... уm) для аргументов х01, х02,...,x0п, y1, у2,... уm cоответственно есть "истина".

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

Пример 3.28. Записать на языке логических формул предикат '"точка М(х, у) находится либо внутри левой половины единичного круга с центром в начале координат, либо на биссектрисе первого координационного угла".

Решение. Этот предикат можно представить как дизъюнкцию двух более. простых предикатов: "точка М(х. у) находится внутри левой половины единичного' круга с центром в начале координат " v "точка М(х, у) находится на биссектрисе первого координатного угла". Первый из используемых здесь предикатов можно представить как конъюнкцию предикатов: "точка находится внутри единичного круга с центром в начале координат "/\"точка находится в левой координатной полуплоскости", а второй - как конъюнкцию предикатов: "точка находится на прямой у=х "/\"точка находится в верхней координатной полуплоскости". Таким образом, нужный нам предикат на языке логических формул можно записать в ви-де:(x*х+y*y<1)/\(x<0)v(у=х)/\(у=>0).

Обсудить вопрос в студенческом форуме

 

Сайт содержит информацию о учебном заведении и студенческой общине и не является официальным