Лекция №8

Вид материала

Лекция

Содержание Рассмотрим 3-местный предикат

Подобный материал:

• «Социальная стратификация и социальная мобильность», 46.19kb.
• Первая лекция. Введение 6 Вторая лекция, 30.95kb.
• Лекция Сионизм в оценке Торы Лекция Государство Израиль испытание на прочность, 2876.59kb.
• Текст лекций н. О. Воскресенская Оглавление Лекция 1: Введение в дисциплину. Предмет, 1185.25kb.
• Собрание 8-511 13. 20 Лекция 2ч режимы работы эл оборудования Пушков ап 8-511 (ррэо), 73.36kb.
• Концепция тренажера уровня установки. Требования к тренажеру (лекция 3, стр. 2-5), 34.9kb.
• Лекция по физической культуре (15. 02.; 22. 02; 01. 03), Лекция по современным технологиям, 31.38kb.
• Тема Лекция, 34.13kb.
• Лекция посвящена определению термина «транскриптом», 219.05kb.
• А. И. Мицкевич Догматика Оглавление Введение Лекция, 2083.65kb.

^

Рассмотрим 3-местный предикат

P(x, y, z) =  и, если z = x + y,

 л, если z  x + y,


на множестве N. Заменив х на 2 получим новый 2-местный предикат P(2,y,z)


P(2, y, z) =  и, если z = 2 + y,

л, если z  2 + y,


который можно записать, например, в виде «Число z на две единицы больше числа y».

2. Пусть Р(x₁, …, x_n) - произвольный предикат на множестве М и n  2. Заменим х₁ на х₂ (или, как говорят, отождествим переменные х₁, х₂). В результате получим (n-1)-местный предикат

Р(x₁, х₂, х₃, …, x_n).

Аналогично можно получить из предиката Р(x₁, …, x_n) новые предикаты, отождествляя какие-либо другие переменные.

Пример 8.2.8.

Отождествляя переменные х и у в предикате из примера 8.2.7, получим 2-местный предикат


P(у, y, z) =  и, если z = 2y,

л, если z  2y,


на множестве N. Этот новый предикат можно записать, например, в виде предложения «Число z в два раза больше числа у».

3. Учитывая связь понятия предиката с понятием высказывания, можно определить логические операции для предикатов. Если Р – n-местный предикат, а q – m-местный предикат, и переменные, входящие в Р, не входят в q, то через Pq обозначим (m+n)-местный предикат, значение которого при конкретных значениях переменных равно дизъюнкции соответствующих значений предикатов P и q.

Аналогично определяются конъюнкция и импликация предикатов, а также отрицания предиката.

4. Кроме операций , , ->, для предикатов на множестве можно определить еще логические операции навешивания кванторов всеобщности и существования.

Рассмотрим n-местный предикат Р(x₁, …, x_n) на множестве М. Добавив к нему фразу «Для всех х₁» или «Для всякого х₁», получим новое предложение, которое обозначим в виде

 x₁ Р(x₁, …, x_n). (8.2.9)


Из построения этого предложения видно, что при замене в нем переменных х₂,…,х_n соответственно элементами а₂, …, а_n получится высказывание

 x₁ Р(x₁,а₂, …, а_n),


которое истинно в том и только том случае, когда высказывание Р(а, а₂, …, а_n) истинно при любом а  М. Таким образом, (8.2.9) является (n-1)-местным предикатом. При этом говорят, что предикат (8.2.9) получен из предиката Р навешиванием квантора всеобщности по переменной х₁. Отметим, что квантор всеобщности  можно навешивать и по другим переменным.

Добавляя перед предикатом Р(x₁, …, x_n) фразу «Существует х₁, такое что», получим новое предложение, которое обозначается в виде

 x₁ Р(x₁, …, x_n) (8.2.10)

Подставив в него элементы а₂, …, а_n вместо x₂, …, x_n, получим высказывание

 x₁ Р(x₁,а₂, …, а_n),

которое истинно в том и только том случае, когда высказывание Р(а, а₂, …, а_n) истинно хотя бы при одном а из М. Следовательно, предложение (8.2.10) есть (n-1)-местный предикат на М.

Символ  называется квантором существования, а о предложении (8.2.10) говорят, что оно получено из предиката Р(x₁, …, x_n) навешиванием квантора существования по переменной х₁. Квантор существования  можно навешивать и по другим переменным.


Пример 8.2.11.

Пусть Р(х, у) есть предикат на N


P(x, y) =  и, если x делит y,

л, если x не делит y,


тогда предложение

у Р(х, у)

зависит только от переменной х.

При х = 1 оно принимает значение «и», т.к. 1 делит любое натуральное число. При любом другом значении х из N оно принимает значение «л», т.е.


у P(x, y)   и, если x = 1,

л, если x  1,

Предложение

х P(x, y)

зависит только от переменной у и принимает значение «л» при любом значении у, поскольку в N не существует чисел, делящихся на все натуральные числа , т.е.

х P(x, y) = л

Пример 8.2.12.

Р(х, у) – то же самое, что и в примере 8.2.11, тогда

х P(x, y)  и

зависит от у и принимает значение «и» для всех значений у.

Аналогично

у P(x, y)  и

Для всех значений х.


Лекция №9. Исчисление предикатов.

§9.1 Общее понятие о логическом исчислении.


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

• всякое ли утверждение, сформулированное в терминах данной теории, можно доказать или опровергнуть (вопрос о полноте);
  
• нельзя ли в этой теории доказать какое-либо утверждение и его отрицание (вопрос о непротиворечивости) и др.
  

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

Каждое логическое исчисление характеризуется:

1. набором используемых в нем символов, или алфавитом;
   
2. правилами построения из алфавита осмысленных утверждений, или формул;
   
3. некоторым фиксированным наборам формул, называемым системой аксиом;
   
4. наборами правил.
   

Алфавит, правила образования формул и само множество формул образуют язык исчисления, а правила преобразования формул образуют синтаксис исчисления.

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

Аксиомы и правила вывода логического исчисления позволяют выделить из множества всех формул так называемые доказуемые формулы, или теоремы. К ним относятся все аксиомы, а также формулы, которые могут быть получены из аксиом с помощью правил вывода. Если исчисление создается для обслуживание какой-либо математической теории то естественно требовать, чтобы все доказуемые в нем формулы были формализацией истинных утверждений теории. Этот фактор должен накладывать определенные ограничения на выбор аксиом и правил вывода исчисления. В тоже время набор аксиом и правил вывода должен достаточно богатым, чтобы с его помощью можно было доказать возможно большее число истинных утверждений теории.

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


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


Формулы будут определяться как строчки некоторых символов, или, как говорят, слова в некотором алфавите.

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

Если А = {а₁, а₂, …, а_n} – алфавит, то любая последовательность

а_i1a_i2 …a_im


его букв называется словом в алфавите А. При этом число m называется длинной слова. Длинна слова Р обозначается в виде ℓ(Р). Для удобства в рассуждениях вводится еще символ Λ для обозначения пустого слова, т.е. слова, не содержащего ни одной буквы. По определению ℓ(Λ) = 0.

Так как слово есть конечная последовательность букв, то можно все буквы в слове естественным образом занумеровать и говорить о 1-й, 2-й, и т.д. буквах слова. Обычно слова записывают в строки, а буквы в них нумеруют слева направо. Два слова называют равными, или графически равными, если они имеют одинаковую длину и соответствующие их буквы равны. Равенство будем обозначать знаком =. Множество всех слов и всех слов длины m в алфавите А обозначим соответственно через W(A) и W_m(A).

На множестве W(A) можно ввести операцию умножения (или приписывания) слов, взяв в качестве произведения слов P, Q слово PQ, полученное приписыванием слова Q справа к слову P.

Говорят, что слово P является подсловом Q, если существуют такие слова L, R (возможно пустые), что


Q = LPR.


В этом случае говорят также, что слово Р входит, или имеет вхождение, в слово Q. Может оказаться, что указанная выше пара слов L, R находится по словам P и Q неоднозначно. Выпишем все такие различные пары слов (L_i, R_i) и упорядочим их по возрастанию длины слова L_i. Получим:

Q = L₁PR₁ = L₂PR₂ = … L_sPR_s

В этом случае говорят, что имеется s вхождений слова P в слово Q, и все эти вхождения упорядочивают по возрастанию длины слова L_i. В соответствии с этим говорят о 1-м, 2-м, и т.д. вхождениях слова P в слово Q. Например, слово «арарат» содержит два вхождения слова «ара». В следующей записи 1-е и 2-е вхождения слова «ара» подчеркнуты соответственно одной и двумя черточками снизу:


«арарат»

——


Перейдем к определению формул алгебры предикатов на алгебраической системе М(σ). Сигнатуру σ представим в виде объединения σ = σ₁Uσ₂, где σ₁ – множество символов операций, а σ₂ непустое множество символов предикатов на М. В частности, множество σ₁ может быть и пустым. Обозначим через σ₀ подмножество из σ₁ обозначений всех нуль-арных операций, т. е. выделенных элементов множества М. Оно может быть любым подмножеством из М. При определении формулы в качестве обозначений будут использоваться различные буквы (возможно, с индексами): a, d, c для элементов из σ₀; f, φ, ψ для элементов из σ₁; p, q для элементов из σ₂. Кроме того, будут использоваться: множество Х символов предметных переменных со значениями из М, обозначаемых буквами x, y, z, u, v (возможно, с индексами); множество О логических операций , v, ->, ┐, ,  и служебных символов – скобок и запятых. Таким образом, алфавитом при построении формул будет служить множество


Ҩ = σ U X U O


В конкретных примерах для операций и предикатов будут использоваться также общепринятые обозначения +, , *, =, ≤ и т. д.

Определим предварительно понятие терма на системе М(σ).

Определение 9.2.1.

1. Каждый символ переменного из Х или константы из σ₀ есть терм.
   
2. Если f – символ n-арной операции из σ и t₁, …, t_n – термы, то слово f(t₁, …, t_n) есть терм.
   
3. Других термов нет.
   

Таким образом, множество термов для М(σ) есть минимальное подмножество слов в алфавите Ҩ, содержащее множество σ U X и замкнутое относительно образования слов по правилу 2. Если вместо переменных из Х в терм t подставить элементы из М и произвести все указанные в t операции, то мы получим элемент из М, называемый значением терма t. Следовательно, терм t определяет функцию на M, зависящую от тех переменных, которые входят в t. Так, если M=N и σ = {0, 1, +, .}, то термами могут быть представлены все многочлены над N.

Теперь определим понятие формулы. В формулах нам необходимо будет различать свободные и связанные вхождения переменных. Эти понятия удобнее определить параллельно с определением формулы.

Определение 9.2.2.

1. Любой символ нуль-местного предиката σ есть формула.
   
2. Если р – символ n-местного предиката из σ, а t₁, …, t_n – термы, то слово p(t₁, …, t_n) есть формула.
   

Формулы, определенные в пунктах 1-2, называются элементарными. Все вхождения переменных в элементарные формулы называются свободными.

3. Если А и В – формулы, то слова
   

(A)(B),(A)v(B),(A)->(B),┐(А)*¹

также являются формулами. В них каждое вхождение переменной является вхождением в формулу А или В и считается таким же (свободным или связанным), каким оно было соответственно в А или В.

4. Если А - формула, в которой в которой есть свободное вхождение переменной x_i, то слова
   

 x_i (A) и  x_i (A)


являются формулами, в которых все вхождения переменных, отличных от x_i, называются так же, как и в А, а все вхождения переменной x_i называются связанными. При этом формула А называется областью действия записанного перед ней квантора  или  по переменной x_i.

5. Других формул нет.

Замечание. В приведенном определении формулы на алгебраической системе М(σ) от М, по существу, использовалось лишь множество выделенных элементов σ₀. Поэтому формулу М(σ) можно рассматривать также и как формулу на любой другой алгебраической системе сигнатуры σ₀. В связи с этим формулы на алгебраической системе М(σ) называют просто формулами алгебры предикатов сигнатуры σ.

Число всех логических операций, участвующих в записи формулы А, назовем рангом формулы А и обозначим через r(A). В частности, r(A) = 0 в том и только том случае, когда А – элементарная формула.

Рассмотрим пример. Пусть р₁, р₂ – символы двухместных предикатов. Тогда выражение

______

x₁((x₁(p₁(x₂, x₁)))v(x₂((p₂(x₁, x₂))))) (1)

есть формула, поскольку p₁(x₂, x₁), p₂(x₁, x₂) являются


формулами по пункту 2, это элементарные формулы. Тогда

________

(p₂(x₁, x₂)) есть формула по пункту 3, x₁(p₁(x₂, x₁)) и

____________

x₂((p₂(x₁, x₂))) есть формулы по пункту 4, далее

______

(x₁(p₁(x₂, x₁)))v(x₂((p₂(x₁, x₂))))


есть формула по пункту 3. В ней последнее вхождение х₁ свободно, а потому (1) есть формула по пункту 4.

Заметим, что в формуле (1) все вхождения переменной х₁ связанные, первое вхождение переменной х₂ свободно, остальные – связанные.

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

1. не заключать в скобки элементарные формулы;
   
2. не заключать в скобки формулу, над которой находится знак отрицания;
   
3. считать, что операция  сильнее , обе эти операции сильнее ->, а операции навешивания кванторов сильнее всех других операций;
   
4. не заключать в скобки большие латинские буквы, являющиеся обозначениями формул;
   
5. опускать скобки в формулах вида
   

(…((A₁A₂)A₃)…)A_k, (…((A₁vA₂)vA₃)…)vA_k ;

6. записывать формулу δ₁x₁(δ₂x₂(…(δ_kx_kA)…)) с кванторами δ₁,…,δ_k в виде δ₁x₁δ₂x₂…δ_kx_kA и в виде δ₁x₁, x₂, …, x_kA при совпадении кванторов δ₁,…,δ_k.
   

При указанных соглашениях формулу (1) можно записать в виде

_____

x₁(x₁p₁(x₂, x₁)vx₂p₂(x₁, x₂)).


В дальнейшем для сокращения иногда будем опускать знак , т. е. вместо АВ писать АВ.

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

Определение 9.2.3.

1. Подформулой элементарной формулы А лишь сама формула А.

2. Подформулами любой формулы вида


AB, AvB, A->B

называется сама эта формула и все подформулы формул А и В.

3. Подформулами любой формулы вида


A, xA, xA


называется сама эта формула и все подформулы формулы А.

Пользуясь определением 9.2.3, нетрудно выписать все подформулы любой заданной формулы. Так, подформулами формулы (1) будут сама она и формулы:

_______ ______ ______

x₁p₁(x₂, x₁)vx₂p₂(x₁, x₂), p₂(x₁, x₂), x₂p₂(x₁, x₂), p₁(x₂, x₁), p₂(x₁, x₂), x₁p₁(x₂, x₁),


Из рассмотренных в § 2 правил получения предикатов на множестве М из заданных предикатов видно, что любая формула А алгебры предикатов сигнатуры σ является предикатом на алгебраической системе М(σ), зависящим лишь от тех предметных переменных, которые имеют свободное вхождение в А. Если такими переменными являются x₁, …, x_n, то формулу А иногда записывают в виде A(x₁, …, x_n). Заменив свободные вхождения переменных в формуле А элементами из М (одинаковыми для всех вхождений одной переменной), мы получим высказывание, значение которого можно вычислить, исходя из значений элементарных высказываний и используя определение логических операций. Значения этих высказываний называются значениями формулы А на М(σ) при соответствующих значениях переменных.

Определение 9.2.4. Формула А алгебры предикатов сигнатуры σ называется выполнимой на алгебраической системе М(σ), если она принимает значение «и» хотя бы при одном наборе из М для переменных, имеющих свободное вхождение в А. В противном случае формула А называется ложной на М(σ). Формула А называется истинной на М(σ), если она принимает значение «и» при любых наборах значений из М для переменных, имеющих свободные вхождения в А.

Определение 9.2.5. Формула алгебры предикатов сигнатуры σ называется выполнимой, тождественно истинной или тождественно ложной, если она соответственно выполнима хотя бы на одной алгебраической системе, истинна на всех системах или ложна на всех системах сигнатуры σ.

Тождественную истинность (ложность) формулы А обозначают в виде Аи (Ал).

Примеры 9.2.6.


1.А->(В->А)  и для любых формул А,В.

____

2.АВ->А  л для любых формул А,В.


3.Формула

_____

x₁x₁=x₁ x₂,x₃((x₁=x₂x₃)->(x₁=x₂)v(x₁=x₃) (2)

выполнима, но не истинна на алгебраической системе N(. ; =). Легко видеть, что она зависит лишь от х₁ и принимает истинное значение в том и только в том случае, когда значением переменной х₁ является простое число.

4.Формула


x₁, x₂ (x₁x₂=x₂x₁) (3)


выполнима, так как она выполнима, например, на системе N(. ; =). Однако она не тождественно истинна, поскольку существуют некоммутативные системы с операцией умножения.

Пример 3 показывает, что формулами алгебры предикатов можно записывать те или иные свойства элементов алгебраических систем, или характеризовать те или иные подмножества ее основного множества или множества наборов ее элементов.

Так формула (2) характеризует множество всех простых чисел. Формула

x₂(x₁x₂=x₃)


характеризует множество пар натуральных чисел, из которых первое делит второе, т. е. отношение делимости на N.

Пример 4 показывает, что формулы алгебры предикатов сигнатуры σ могут быть использованы для характеризации алгебраических систем сигнатуры σ. Формула (3) выделяет класс алгебраических систем с коммутативной операцией умножения, если под равенством = понимать отношение (предикат) совпадения элементов множества.