Лекции, шпаргалки, информация по предметам, статьи, лабораторные, тех.задания


Кафедра ИС(АВТ)

Основы дискретной математики - Вопрос 20

Лекции(шпаргалка) по основам дискретной математики для кафедры Информационных систем (ИС), факультет Автоматики и вычислительной техники (АВТ).

Вопрос 20
Исчисление предикатов. Основные понятия.
Решение многих задач обработки информации требует ее логического анализа. Для автоматизации логического рассуждения необходим некоторый формальный язык, на котором можно формулировать посылки и делать логические выводы. Такой язык имеется. Он носит название языка логики предикатов.

В математике, информатике, кибернетике и других науках наряду с высказываниями встречаются выражения, грамматически имеющие форму высказываний, но содержащие предметные переменные некоторых множеств, а не конкретные объекты этих множеств. Здесь под предметными переменными понимаются произвольные, неконкретизированные объекты указанных множеств. Такие выражения можно получить из любых высказываний, заменив в них обозначения предметов предметными переменными множеств, к которым принадлежат эти предметы. Если в последних выражениях все предметные переменные снова заменить какими-либо элементами данных множеств (необязательно исходными), то опять получим высказывания.

Например, предложение "2 - простое число" есть" истинное высказывание. Заменим в нем конкретное число "2" предметной переменной п множества натуральных чисел. Получим выражение "n - простое число". Грамматически оно имеет ту же форму, что и исходное высказывание, но не является таковым. При замене предметной переменной п любым натуральным числом 1, 2, 3, 4, ... построенное выражение будет снова обращаться в высказывание, либо истинное, либо ложное. Все подобные выражения называются предикатами или функциями-высказываниями. Применяя к ним понятия исчисления высказываний, можно выразить довольно сложные конкретные факты.

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

Введем точное определение предиката. Для этого примем некоторые обозначения. Рассмотрим n множеств M1, Мз,..., Мn. Предметные переменные множества M1 обычно обозначают как х1, х1', х1'',... При этом элементы (конкретные значения) предметной переменной x1 записывают как как x01, x11, x21..., элементы предметной переменной х1' - как х01', х11', х21',... и т.д. Аналогично, предметные переменные множества М2 обозначают х2 (с элементами х02, x12, х22 ...), х2' ( с элементами x02', x12', x22',...) и т.д.

n - местным предикатом, определенным на множествах Mi, Мз,.... Мn, называется выражение, содержащее предметные переменные данного множества и обращающееся в высказывание при замене последних любыми элементами множеств M1, М2, ..., Мn соответственно. Множества M1,M2,...,Мn называются базисными множествами предиката, а их элементы - аргументами предиката: 1-м, 2-м,..., и т.д. n - местный предикат (n=>2), все базисные множества которого совпадают, называется однородным. В нем M1i= М2=... = М.

Будем обозначать n - местные предикаты, определенные на одномерных множествах M1, М2,..., Мn, содержащих предметные переменные х1, х2,...xn, через A(x1,x2,...xn), В(x1,x2,...xn), C(x1,x2,...xn)...

Высказывание, в которое обращается предикат А(x1,x2,...xn) при замене предметных переменных x1,x2,...xn аргументами x01,x02,...x0n соответственно, обозначается А(x01,x02,...x0n).

Пример 3.19. Пуcть х - переменная, принимающая какое-либо значение на множестве действительных чисел R. Тогда выражение "х больше двух^ есть одноместный (унарный) предикат, определенный на множестве действительных чисел. Заменив х числом 3, получим истинное высказывание: 3 > 2, а заменив х числом 1, получим ложное высказызание 1 > 2. Рассмотрим п - местный предикат A(X1, x2,....хn), определенный на одномерных множествах M1, M2,..,Мn, где В(у1, у2,...уn)- некоторые элементы множеств M1, М2,...,Мn. Значением предиката А(x1,х2,...хn) для аргументов x01, x02,...X0N называется логическое значение высказывания A(x01, x02,...x0n), в которое обращается данный предикат при замене предметных переменных х1, х2,....xn соответственно аргументами x01,x02,...,x0n Если значение предиката А(х1, x2,...xn) для аргументов x01,х02...,x0n есть истина, то говорят, что аргументы x01,х02...,x0n удовлетворяют данному предикату; в противном случае говорят, что аргументы x01,х02...,x0n этому предикату не удовлетворяют.

Обсудить вопрос в студенческом форуме

 

Сайт содержит информацию о учебном заведении и студенческой общине и не является официальным