Читайте также:
|
Студент, внимательно изучивший тему «Алгебра высказываний» не мог не заметить, что построенная теория обладает весьма ограниченными возможностями в плане обоснования выводов, умозаключений. Она оперирует с предложениями, как с неразделимыми блоками, не расчленяя их на составляющие и не имея возможности использовать эти составляющие для анализа умозаключения.
Например, логичность рассуждения «Всякое натуральное число есть целое число. 5 – натуральное число. Следовательно, 5- целое число» не может быть установленной в рамках алгебры высказываний.
Более широкими возможностями в этом плане обладает алгебра предикатов.
Изучая математику, мы привыкли оперировать с переменными x,y,…, которые принимают, как правило, значения числовых множеств. При введении понятия предиката мы будем иметь дело с переменными x, x1, x2, …, xi,y1,y2,…. которые принимают значения из произвольных множеств (будем говорить, что переменная xi определена на множестве Mi).
Рассмотрим предложение “x - делитель 12”, где x принимает значения из множества натуральных чисел N. При любом фиксированном значении x получаем некоторые высказывания: «3 – делитель 12», «5 - делитель 12» и т. д. (первое высказывание истинно, второе – ложно).
Предложение A(x), содержащее переменную x и превращающееся в высказывание при замене x элементом из области ее определения М, называется одноместным предикатом.
Приведем несколько примеров одноместных предикатов:
x2+3x+2=0, где x определена на R,
x>1, где x определена на Q,
«х – спортсмен», где переменная х определена на множестве студентов ДонНУ, и т.д.
В общем случае, предложение A(x1,…,xn) содержащее переменные x1,…,xn и превращающееся в высказывание при замене каждой из переменных xi элементом αi из области определения Mi, i=1, …, n, называется – n-местным предикатом.
Примеры. Выражение x>y, x,y 
R является двуместным предикатом; x2+y2+z2=1, x,y,z R - трехместный предикат; “x брат y”- двуместный предикат (x,y определены на множестве людей); линейное уравнение x1+x2+..+xn=0, где неизвестные определены на множестве действительных чисел, является n-местным предикатом.
Подчеркнем еще раз, что местность предиката определяется количеством переменных, входящих в предикат. При фиксировании в n-местном предикате A(x1,…,xn) одной переменной, например, xi=αi, получим (n-1) –местный предикат A(α1,x2,…,xn). Так, из предиката x>y, x,y R, при x=1, получаем одноместный предикат 1>y.
Если высказывание отождествлять с его значением (0 ли 1), то n-местный предикат A(x1,…,xn), по существу, является функцией от n переменных xi, определенных на множествах Mi, i=1,..,n, принимающей значения 0,1.
Например, если A(x,y)=(x>y), x,y R, A(1,2)=0, A(3,-4)=1, A(1,1)=0 и т.д.
Замечание. В дальнейшем, если в примерах или задачах переменные принимают значeния из R, то для сокращения записи мы не будем отмечать это в условии задачи. Однако подчеркиваем, что предикат не определен полностью, если не указывать области определения переменных.
Пусть A(x1,…,xn) – n-местный предикат, определенный на множествах M1,…,Mn (т.е. xi принимает значение из множества Мi). Если для последовательности <α1, …, αn> A(α1, …, αn)=1, то говорят, что последовательность <α1, …, αn> удовлетворяет предикату. В противном случае, последовательность не удовлетворяет предикату A(x1,…,xn).
Пример. Упорядоченная тройка <0,1,-1> удовлетворяет предикату x+y+z=0, а тройка <1,1,1>– не удовлетворяет этому предикату.
Множество всех упорядоченных последовательностей <α1,…αn>, удовлетворяющих предикату A(x1,…xn) составляет его множество истинности.
Обратите внимание, что мы при изучении первой темы уже оперировали предикатами. Предикаты задавали характеристические свойства множеств. Именно, запись {x|A(x)} – задавала множество истинности предиката A(x). Мы и в дальнейшем через {<x1,…,xn>|A(x1,…,xn)} будем обозначать множество истинности предиката A(x1,…,xn). Если предикат A(x1,…,xn) определен на множествах M1,…,M2, то {<x1,…,xn>|A(x1,…,xn)}ÍM1×M2×¼× Mn, т.е. множество истинности n-местного предиката является некоторым n-арным отношением.
Примеры. {x|x>2}=(2;∞); {x|x2-3x+2=0} = {1;2}; Множество {<x,y>|xy=0} составляет всевозможные упорядоченные пары действующих чисел, где, по крайней мере, одна компонента равна 0.
Заметим, что в учебном пособии [3] рассматривается «однородный» случай, когда все переменные, входящие в предикат определены на одном и том же множестве М. это несколько сужает возможные применения алгебры предикатов.
5.2.Типы предикатов.
Обратите внимание на то, что определение дает классификацию предикатов по их местности. Большой интерес представляет проведение классификации предикатов по их множествам истинности.
Если A(x1,…,xn) определен на M1,...,Mn, и {x1,..,xn|A(x1,…,xn)}=M1×…×Mn, то предикат A(x1,…,xn) называется тождественно истинным; если {<x1,..,xn|A(x1,…,xn)}=Ø, то A(x1,…,xn) – тождественно ложный предикат; наконец, если {<x1,..,xn|A(x1,…,xn)}≠Ø, то предикат A(x1,…,xn) называется выполнимым.
Следует иметь в виду и «функциональную» характеристику приведенных типов предикатов. Тождественно истинный предикат принимает значение только 1; тождественно ложный - только 0; выполнимый предикат принимает значение 1 хотя бы для одной последовательности значений переменных.
Примеры. Предикат x2+y2≥0– тождественно истинный, x>y - выполнимый, x2+x+1=0 - тождественно ложный на множестве действительных чисел. Ясно, что первому предикату удовлетворяет любая упорядоченная пара действительных чисел, второму предикату удовлетворяет, например, пара (1,0), а третий предикат – квадратное уравнение без действительных корней, ему не удовлетворяет ни одно число из R.
Два n–местных предиката A(x1,…,xn) и B(x1,…,xn), определенные на одних и тех же множествах M1,...,Mn, называются равносильными, если их значения для любого набора значений переменных совпадают. Обозначают
A(x1,…,xn)=B(x1,…,xn).
Для неравенств и уравнений введенное понятие равносильности предикатов совпадает с понятием равносильности или эквивалентности, хорошо известным из школьного курса математики. Заметим также, что отношение равносильности на множестве предикатов рефлексивно, симметрично и транзитивно, т.е. является эквивалентностью. Предикаты, относящиеся к одному и тому же классу, задают одну и ту же функцию.
Примеры. (x2=y2)≡(x2-y2=0)=((x-y)(x+y)=0),(x>3)≡(x ]3;∞[≡(x-3>0),(x2-3x+2=0)≡(x=2 или x=1).
Предикат A(x1,…,xn) называется следствием предиката B(x1,…,xn), если всякая последовательность значений переменных, удовлетворяющая второму предикату, удовлетворяет и первому.
Очевидно, {<x1,…,xn>| A(x1,…,xn) } 
{<x1,…,xn>| B(x1,…,xn) }
Теорема. Два предиката, определенные на одних и тех же множествах, равносильны тогда и только тогда, когда каждый предикат является следствием другого.
Примеры. Предикат x>1 является следствием предиката x>2.
Предикат (x+1)(x-3)=0 является следствием x+1=0.
Дата добавления: 2015-11-14; просмотров: 104 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Полнота теории L | | | Простейшие логические операции над предикатами. |