рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Язык исчисления предикатов

Язык исчисления предикатов - раздел Математика, КОНСПЕКТ ЛЕКЦИЙ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ   С Помощью Предикатов Можно Формулировать Содержательные Утвер...

 

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

Здесь возникает одна проблема: поскольку предикаты в разных областях знания совершенно разные, то при построении исчисления предикатов нужно отвлечься от специфики конкретных предикатов, рассматривая запись P(x1 , … , xn ) как абстрактный символ предиката P от n переменных x1 , … , xn , вместо которого в каждой науке можно подставлять те или иные её специфические предикаты от n переменных. Например, предикатный символ P(x, y) географ может наполнить своим содержанием, рассматривая конкретный предикат P(x, y) = “река х впадает в море y”, а математик – своим, полагая P(x, y) = “x > y”.

Алфавит языка исчисления предикатовсодержит несколько групп символов:

I. Пропозициональные переменные: a, b, c99 , d345 , … для обозначения высказываний.

II. Объектные переменные: x, y, z99 , t345 , … для обозначения объектов предметной области той или иной науки.

III. Логические связки: – отрицание, Ù – конъюнкция, Ú – дизъюнкция, ® – импликация и « – эквивалентность.

IV. Предикатные символы: P(1)( _ ), Q(1)( _ ), R(1)( _ ), … , P(2)( _ , _ ), Q(2)( _ , _ ), R(2)( _ , _ ), … для обозначения предикатов от любого числа переменных (количество переменных, если это необходимо, указано в скобках в верхнем индексе).

V. Кванторы: " – квантор всеобщности и $ – квантор существования.

VI. Служебные символы: ( , ) – скобки и запятая , .

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

(Ф1): любая формула исчисления высказываний (от пропозициональных переменных) является формулой исчисления предикатов, в которой нет объектных переменных и кванторов.

(Ф2): если P(n)( _ , … , _ ) – предикатный символ от n переменных и x1 , … , xn – объектные переменные, то P(n)( x1 , … , xn ) – формула исчисления предикатов, в которой все вхождения объектных переменных x1 , … , xn свободны, а вхождений других объектных переменных нет.

(Ф3): если A и В – две формулы, то (A Ù B), (A Ú B), (A ® B), (A « B), , – тоже формулы, в которых свободны все вхождения объектных переменных, свободные в А или в В, и связаны все вхождения объектных переменных, связанные в А или в В.

(Ф4): если A(x) – формула хотя бы с одним свободным вхождением объектной переменнойx, то выражения (" x A(x)) и ($ x A(x)) – формулы, в которых связаны вхождения всех объектных переменных, связанных в А, а также все вхождения x, и свободны все вхождения объектных переменных, свободные в А, кроме переменной х. При этом формула A(x) называется областью действия квантора.

(Ф5): других формул нет.

Будем называть объектную переменную в формуле свободной (связанной), если свободны (связаны) все её вхождения в этой формуле.

Примеры: 1.Если a – пропозициональная переменная, то ($ x (P(x) « a)) – формула исчисления предикатов, образованная по правилу (Ф4) из формулы (P(x) « a) со свободным вхождением объектной переменной x. В полученной формуле ($ x (P(x) « a)) нет свободных вхождений объектных переменных.

2. " x P(x) ® ($ y Q(y)) – не формула, т.к. в ней не хватает скобок.

3. ($ y (P(x) Ú (" y (Q(x) ® R(y))))) – не формула: в ней квантор $ навешивается на переменную y, у которой нет свободных вхождений.

4. (" x ((" y Q(y)) « ($ x (Q(y) Ù R(x))))) – не формула (?!), но (" y ((" y Q(y)) « ($ x (Q(y) Ù R(x))))) – формула, в которой нет свободных вхождений объектных переменных. Такие формулы называются замкнутыми.

5.((" x P(x, y)) Ú Q(x, z)) – формула, в которой свободно вхождение объектной переменной y, вхождение переменной x в формулу (" x P(x, y)) связано, а вхождение переменной x в формулу Q(x, z) свободно, как и вхождение z.

6. (" x ((" y Q(y, v)) « ($ z (Q(z, u) Ù R(x, t))))) – формула со свободными переменными v, u, t.

7. ($ x (" y (Q(y, v)« (" z Q(z, x))))) – формула со свободной переменной v.

В формулах примеров 1и 4 нет свободных переменных, в формуле примера 5 свободна объектная переменная z, в формуле примера 6переменные v, u, t, а в формуле примера 6 переменная v.

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

– Конец работы –

Эта тема принадлежит разделу:

КОНСПЕКТ ЛЕКЦИЙ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ

Государственное образовательное учреждение... Тобольская государственная социально педагогическая академия... им Д И Менделеева...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Язык исчисления предикатов

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Тобольск – 2010
УДК 510.6Печатается по решению редакционно-издательского ББК 22.12 я 73 совета Тобольской государственной социально- В 15пе

С О Д Е Р Ж А Н И Е
ПРЕДИСЛОВИЕ . . . . . . . . . . . . . .       Глава I.

П Р Е Д И С Л О В И Е
Хотя настоящее учебно-методическое пособие предназначено, в первую очередь, для студентов физико-математических специальностей пединститутов, оно может быть использовано и при чтении курса математи

Понятие высказывания
  Математика, как это ни кажется странным, – наука устная: математики, рассуждая, оперируют высказываниями, именно общение является питательной средой математического творчества, в ко

Язык исчисления высказываний
В любом естественном языке есть возможность строить из простых высказываний более сложные. Примеры: 1. “Сейчас температура воздуха на улице от –25 до –30 гра

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

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

Нормальные формы
x1 … xn A(x1 , … , xn ) … … …

Булевы функции
  После того как каждой формуле A(x1 , … , xn) при любом наборе x1 = e1 , … … , xn = en (ei

Логическое следование
  Понятие логического следования является одним из важнейших в математической логике и имеет непосредственное отношение к жизни. Нам часто приходится обосновывать те или иные утвержде

Некоторые применения алгебры высказываний
I. Анализ логических рассуждений. Рассмотрим несколько примеров, которые используют понятие логического следования. Примеры: 1. Правильно ли следующее лог

Предикаты и кванторы
Каждая наука имеет дело со специфическими объектами, совокупность которых образует объектную (или предметную) областьданной науки. Об этих объектах можно формулировать высказывания, которые

Равносильные и тождественно истинные предикаты
  Два предиката P(x1 , … , xn ) и Q(x1 , … , xn ), определённые на множестве А (т.е. предикаты с условиями An

Теорема (об основных равносильностях с кванторами).
(0) " x Î A P(x, y) º " z Î A P(z, y), $ x Î A P(x, y) º $ z Î A P(z, y), где P(x,

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

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

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

Некоторые методы доказательства теорем
  Под теоремой обычно понимается математическое утверждение, которое можно доказать. Доказательством теоремыТ называется конечная последовательность теорем Т1

Формальные и неформальные аксиоматические теории
Нами изучены две математические теории, относящиеся к логике: алгебра высказываний и алгебра предикатов. В обоих случаях делалось следующее: · были объявлены первоначальные (неопределяемые

Непротиворечивость аксиоматических теорий
Система аксиом формальной теории, как и сама теория, называются непротиворечивой, если не существует такой формулы Ф этой формальной теории, что Ф и

Полнота аксиоматических теорий
Любая содержательная формальная теория строится для обоснования рассуждений в некоторых содержательных теориях. Возникает вопрос: насколько полно описывает формальная теория соответствующую содержа

Разрешимость аксиоматических теорий
Проблема разрешимости теории может быть сформулирована несколькими способами: (Проблема доказуемости):Существует ли алгоритм, позволяющий за конечное число шагов эф

Независимость системы аксиом теории
Создавая аксиоматическую теорию, естественно стремиться не выписывать лишних аксиом – тех, которые выводимы из остальных. Система аксиом формальной теории называется независимой, если ни одн

Формальное исчисление высказываний
Подробно рассмотрим формальную теорию исчисления высказываний (ИВ). Нашей целью будет обоснование адекватности этой теории, описанной формально в § 1 главы III, неформальной алгебре высказыв

B, A (A Ù B) дедукция
11 · Г, B, A (A Ù B) расширение посылок 12 · Г, А, В

A Ù B) ® ((A Ú C) Ù (B Ú C))) дедукция
13 · (С ® (A Ú C)) (Д2) 14 · С (A Ú C) де

A Ú C) (В ® ((A Ù B) Ú C)) дедукция
10 · (A Ú C) (С ® ((A Ù B) Ú C)) (почему ?!) 11 ·

Дедукция
4 · (A Ù B) B (почему ?!) 5 ·

A, , (A ® B) Bдедукция
3 · A, , (A ® B)

A ® B) (Ú ) силлогизм
19 · (Ú )

A ® B)) дедукция
8 · (B ® (A ® B)) (И1) 9 · ((® (A ® B)) ® ((B ® (A ® B)) ® ((

Правило опровержения
Упражнение:Докажите формально остальные основные равносильности. 6. Доказуемость и тождественная истинность формул. Теперь уже можно доказать основной рез

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

Аксиоматика Цермело-Френкеля теории множеств
  В § 1 приложения были даны основные понятия теории множеств. Однако развиваемая на этом основании Г. Кантором наивная теория множеств столкнулась в конце XIX в. с трудностями. Вот –

Кущи или адские дебри ?
Попытаемся неформально проанализировать общематематические достижения в задаче обоснования теории множеств. Сразу нужно отметить, что замкнутого изложения основ формальная теория множеств не даёт.

Л И Т Е Р А Т У Р А
А) ОСНОВНАЯ ЛИТЕРАТУРА: 1.Глухов М.М., Козлитин О.А., Шапошников В.А., Шишков А.Б. Задачи и упражнения по математической логике, дискретным функциям и тео

СПИСОК ОСНОВНЫХ ОБОЗНАЧЕНИЙ
N – множество всех натуральных чисел, Q – множество всех рациональных чисел, R – множество в

ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
А аксиома объёмности................................................. 150 аксиома (неупорядоченной) пары..............................

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги