вфцвфцввц. Математическая логика

• Название: Математическая логика
• Анкор: вфцвфцввц
• Дата: 05.12.2022
• Размер: 2.56 Mb.
• Имя файла: ML_i_TA_LEKTs.doc
• Тип: Задача; #828327
• страница: 3 из 7

Раздел II. АЛГЕБРА ПРЕДИКАТОВ
Алгебра предикатов является развитием алгебры высказываний. Кроме простых и составных высказываний она вводит в рассмотрение высказывания, отнесенные к переменным из некоторого множества M, которое в дальнейшем будем называть предметным множеством, а его элементы – предметными переменными.

1. Предикат. Операции над предикатами.

Неформально предикат можно определить как некоторое высказывание, значение которого зависит от значений предметных переменных из множества M, на котором определен предикат.

Примеры:

1. 
   P(x) : “xесть простое число”;
   

(Здесь и всюду в дальнейшем для задания предиката будем использовать краткую форму записи, которая подробно расписывается следующим образом: “xесть простое число”.)

2. 
   D(x,y) : “xнацело делится на y”;
   
3. 
   R(x,y) : “x > y”.
   

В качестве предметного множества для этих примеров можно рассматривать любые числовые множества, в частности, в примерах a), b) – M= , а в c) – M= .

Более строго предикат можно определить как отображение n-ной степени множества M, называемой местностью или арностью предиката в двухэлементное множество B= {1, 0}

.

При подстановке в предикат вместо предметных переменных набора значений получим логическое высказывание (так , а ). Таким образом, предикат представляет собой переменное высказывание (или систему высказываний), истинность которого определяется подстановкой различных значений предметных переменных.

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

Операция утверждение всеобщности ставит в соответствие высказывательной форме P(x) высказывание (читается как, P(x) истинно для всех x из множества M, на котором определен предикат). Высказывание истинно тогда и только тогда, когда высказывание P(a) истинно для любого элемента .

Операция утверждение существования ставит в соответствие высказывательной форме P(x) высказывание (читается как, существует такой x из множества M, для которого высказываниеP(x) истинно). Высказывание истинно тогда и только тогда, когда высказывание P(a) истинно хотя бы для одного элемента .

Знаки  и  называются кванторами всеобщности и существование (квантор в переводе с латинского – определение количества). Переход от высказывательной формы P(x) к высказываниям или называется навешиванием квантора или связыванием переменной x (иногда – квантификацией переменной x). Переменная, на которую навешен квантор, называется связанной, несвязанная переменная называется свободной. Смысл связанных и свободных переменных в предикатных выражениях различен. Свободная переменная – это обычная переменная, которая может принимать различные значения из M, а выражение P(x) – переменное высказывание, зависящее от значения x. Выражения и не зависят от переменной x и при фиксированных Pи Mимеют вполне определенное значение. Переменные, являющиеся по существу связанными, встречаются не только в математической логике. Например, в выражениях или переменная x связана, при фиксированной f первое выражение равно определенному числу, а второе является функцией от aиb.

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

В общем случае для n-арного предиката, если , операции утверждения всеобщности или существования можно выполнять k раз (порядок выбора переменных, по которым происходит навешивание квантора, может быть любым, исключая их повторение) и получить выражение

, (1)

где обозначает квантор всеобщности или существования. Переменные в высказывательной форме (1) являются связанными, а – свободными.

Высказывательная форма (1) при замене переменных элементами множества M обращается в истинное или ложное высказывание. При k= n высказывательная форма (1) становится высказыванием. Изменение порядка следования различных кванторов изменяет смысл высказывания, что может изменить его истинностное значение.

Например, для предиката делимости D(x,y):

высказывание читается, как “для любого xсуществует y, такое, что xделится на y”, и является истинным высказыванием, так как любое натуральное x делится на себя и на 1, т.е. y= x или y=1;

высказывание читается, как “существует y, на который делится любой x”, и также является истинным высказыванием, так как на значение y=1 делится любое натуральное x.

2. Модель. Формула алгебры предикатов сигнатуры .

Ряд важнейших понятий алгебры предикатов основывается на понятии модели.

Моделью  называется любое множество M с заданными на нем предикатами :

 = < M ; >.

Множество M называется основным множеством модели , предикаты – основными предикатами модели , и их набор  = < > называется сигнатурой модели . Натуральные числа k₁,  , k_n обозначают арности соответствующих предикатов, а их набор  = < k₁,  , k_n > называется типом модели.

Пример.

– множество натуральных чисел, E,S,P – определенные на множестве  предикаты равенства, сложения и умножения, т.е.

.

Модель  = < ;E,S,P> является арифметикой натуральных чисел. Ее синатура  = <E,S,P> и тип  = < 2, 3, 3 >.

Любое множество моделей с одной и той же сигнатурой  называется классом K_ моделей сигнатуры .

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

1. 
   Если и – предметные переменные, то выражение есть формула. Такая формула называется атомарной, в ней все вхождения предметных переменных называются свободными.
   
2. 
   Если U есть формула, в которой имеются свободные вхождения переменной x_i, то выражения x_i(U) и x_i(U) – формулы, в которых все вхождения x_i являются связанными, а все вхождения остальных предметных переменных такие же, какими они были в формуле U. При этом формула U называется областью действия соответствующего квантора всеобщности или существования.
   
3. 
   Если U есть формула, то  U – также формула, и все свободные и связанные вхождения предметных переменных в формулу U являются соответственно свободными и связанными вхождениями в формуле  U.
   
4. 
   Если Uи V есть формулы, то выражения (U)  (V), (U)  (V), (U)  (V), (U) (V) также являются формулами, причем все вхождения предметных переменных в этих формулах такие же, как и в формулах Uи V.
   
5. 
   Формулы могут быть образованы только с помощью правил 1 – 4.
   

Число скобок в формуле можно уменьшить, если условиться:

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

вместо записи , где – некоторые кванторы, допускать запись ;

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

не заключать в скобки подформулы, обозначенные буквами;

не указывать явно с помощью верхнего индекса местность предиката.

Если формула U не содержит свободных вхождений предметных переменных, то, используя определения операций, можно вычислить ее логическое значение. Если в формуле U есть свободные вхождения предметных переменных, то она является предикатом, называемым формульным, зависящим от значений этих переменных. Но при каждой замене в этой формуле всех свободных вхождений предметных переменных элементами множества M она становится высказыванием, значение которого вычисляется так же, как и в первом случае. Например, формула на модели арифметики натуральных чисел является формульным предикатом от переменных x иy, т.е.

(1)

и определяет отношение . Легко проверить, что , , .

Формула называется выполнимой на модели , если для некоторой системы элементов модели  сигнатуры  значение формулы сигнатуры , т.е. высказывание , является истинным.

Формула U сигнатуры  называется выполнимой, если существует модель сигнатуры , на которой выполнима формула U.

Если высказывание является истинным для любой системы значений , то формула U называется истинной на модели .

Если формула не выполнима на модели , то она называется ложной на модели .

Так формула (1) является выполнимой на модели , но она не будет ни истинной, ни ложной на ней. Формула

выражает однозначность операции сложения и является истинной на этой модели, а формула – ложной.

Если формула U истинна на любой модели класса K_ , то она называется истинной на классеK_ .

3. Формулы алгебры предикатов

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

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

Понятие формулы алгебры предикатов определяется также как и формулы алгебры предикатов сигнатуры . Число всех символов операций, входящих в запись формулы U, называется её рангом и обозначается . Формула называется атомарной, она может записываться , её ранг = 0.

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

Определение. Пусть U - формула алгебры предикатов и

(2)

набор предикатных переменных, входящих в U. Сигнатуру s, а также класс моделей K_s и модель M  K_s назовем допустимыми для формулы U, если s содержит хотя бы один предикат арности n_i для любого , т.е. существует отображение .

Такое отображение назовем сигнатурным. Формула, полученная заменой каждой предикатной переменной её образом ( ), является формулой сигнатуры s и обозначается sU.

Например, для формулы алгебры предикатов

модель арифметики натуральных чисел  = < N;E,S,P> является допустимой, так как можно построить сигнатурное отображение множества предикатных переменных формулы в сигнатуру модели  = <E⁽²⁾,S⁽³⁾,P⁽³⁾>. Вариантов такого отображения два:

1. 
   , ;
   
2. 
   , .
   

Обозначим через U формулу, полученную подстановкой в формулу U предикатов сигнатурного отображения .

Определение. Пусть для формулы алгебры предикатов U модель M является допустимой. Тогда:

1. 
   формула U называется выполнимой на модели M, если формула sU выполнима на модели M при некотором сигнатурном отображении ;
   
2. 
   формула U называется выполнимой, если существует допустимая модель, на которой она выполнима;
   
3. 
   формула U называется невыполнимой или ложной на модели M, если формула sU невыполнима на модели M при любом сигнатурном отображении ;
   
4. 
   формула U называется невыполнимой, если на любой допустимой модели она не выполнима;
   
5. 
   формула U называется тождественно истинной на модели M, если формула sU истинна на модели M при любом сигнатурном отображении ;
   
6. 
   формула U называется общезначимой, если она тождественно истинна на любой допустимой модели.
   

Примеры.

Формула алгебры предикатов на допустимой модели арифметики натуральных чисел N = < N;E,S,P> является ложной, так как для любых не существует такое натуральное x₂, что или .

Формула алгебры предикатов общезначима.

Основные общезначимости алгебры предикатов

1. 
   
   

2. 
   
   

3. 
   
   

4. 
   
   

5. 
   
   

Докажем формулу .

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

Пусть , тогда по определению операции утверждения существования для некоторого aиз M. Следовательно, , где M. Воспользовавшись снова определением операции утверждения существования, получим, что или , а, следовательно, истинна и их дизъюнкция .

Пусть теперь , тогда или . В первом случае получим, что M, , во втором – M, . Однако в обоих случаях существует такой элемент M, что , в первом случае , во втором – . А это означает, что .

На множестве формул алгебры предикатов можно ввести отношение эквиваленции.

Определение. Формула алгебры предикатов U называется эквивалентной формуле V (обозначается UV), если их эквиваленция общезначима.

Множество формул алгебры предикатов можно разбить на классы эквивалентности, включив в один класс эквивалентные между собой формулы. Каждой формуле U соответствует класс эквивалентности, который обозначается [U].

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

Теорема 3.1. Каждый класс эквивалентности [U] может быть представлен приведенной формулой, т.е. для любой формулы U существует эквивалентная ей приведенная формула V.

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

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

,

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

Будем говорить, что бескванторная формула U находится в ДНФ (КНФ), если U получается из формулы алгебры высказываний, находящейся в ДНФ (КНФ), подстановкой вместо пропозициональных переменных некоторых атомарных формул.

ПНФ называется пренексной нормальной формой (ПННФ), если её матрица имеет вид ДНФ, и предклазуальной (пкнф), если – КНФ.

Построим ПН-форму для формулы

.

Преобразуем формулу к приведенному виду



 

 .

Так как для квантора  и операции  нет соответствующей эквивалентности, то переименуем связанную переменную y второго операнда дизъюнкции и вынесем кванторы по переменным, от которых не зависит другой операнд вперёд



 

 .

В первом операнде конъюнкции последней формулы переменные xи y– связанные, а z – свободная, а во втором – наоборот. Переобозначив снова связанные переменные, получим



 

 .

Полученная предваренная нормальная форма является предклазуальной.

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

1. 
    ;
   
2. 
    .
   

Возможность удаления кванторов всеобщности непосредственно следует из определения операции, так как для произвольного x.

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

Так клазуальная нормальная форма для формулы предыдущего примера имеет вид

.