предикаты. Основные понятия алгебры предикатов
 Скачать 2.83 Mb.
|
Основные понятия алгебры предикатовЛогика высказываний оперирует простейшими высказываниями, которые могут быть или истинными, или ложными.
В логике такие предложения, истинность которых зависит от параметров, обозначают с помощью предикатов. «Предикат» с английского переводится, как сказуемое. Определение предикатаФормально предикат-функция, аргументами которого могут быть произвольные объекты из некоторого множества, а значения функции «истина» или «ложь». Предикат можно рассматривать как расширение понятия высказывание. Одноместным предикатом P(x)-произвольная функция переменного х, определенного на множестве М и принимающая значения из множества 1;0 . Двухместный предикат Р(х ; у)- функция двух переменных х и у, определенная на множестве М=М1хМ2 и принимающая значения из множества 1;0 . n-местный предикат – это функция определенная на наборах длинны n элементов некоторого множества М, принимающая значения в области True, False. Множество М называется предметной областью предиката, А х1, х2, х3 … , хn- предметными переменными. Предикат называется тождественно истинным (тождественно ложным), если на всех наборах своих переменных принимает значение 1 (0), выполнимым, если на некотором наборе своих переменных принимает 1 Логические операции над предикатамиЗамечание!Предикаты при подстановке переменных становятся высказываниями, поэтому с предикатами можно производить все логические операции Для предикатов справедливы логические операции и две новые операции, специфические. - операциями навешивания кванторов или операциями квантификации. Эти операции соответствуют фразам «для всех»-квантор общности и «некоторые»-квантор существования. Выражение «существует точно одно Х такое, что…»- квантор существования и единственности.Присоединение квантора с переменной к предикатной формуле называется навешивание квантора на переменную х. Переменная при этом называется связной и вместо нее подставлять константы уже нельзя. Если квантор навешивается на формулу с несколькими переменными, то он уменьшает число несвязных переменных в этой формуле. Переменную х в предикате Р(х) называют свободной ( ей можно придавать различные значения из М), В высказывании же х называют связанной квантором всеобщности. Переменная, на которую навешивается квантор называется связанной. Выражение, на которое навешиваете квантор, называется областью действия квантора. Кванторы общности и существования называют двойственными относительно друг друга. Равносильные формулы логики предикатовДве формулы логики предикатов А и В называются равносильными на области М, если они принимают одинаковые логические значения при всех значениях входящих в них переменных, отнесенные к области М. Нормальные формы формул логики предикатовВ логике предикатов формулы могут иметь нормальную формулу. При этом, используя равносильности логики предикатов, каждую формулу логики предикатов можно привести к нормальной форме. В логике предикатов различают два вида нормальных форм: приведенную и предваренную. Среди нормальных форм формул логики предикатов выделяют так называемую предваренную (префиксную) нормальную форму ПНФ. В ней кванторные операции, либо полностью отсутствуют , либо они используются после всех операций алгебры. |