пользователей: 21281
предметов: 10473
вопросов: 178149
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

Исчисление предикатов. Аксиомы исчисления предикатов. Применение логики предикатов. Кванторы. Формулы логики предикатов. Равносильные формулы логики предикатов. Приведенные и нормальные формы в логике предикатов. Алгоритм преобразования формул в нормальную форму.

Исчисление предикатов 

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

Теперь же вопрос следует поставить иначе. Принимает ли данная функция значение 1 при:

а) любых предметных переменных и любых предикатах,
б) на некотором множестве предметных переменных и любых предикатах,
в) при некоторых значениях предметных переменных и любых предикатах, 
г) является ли она тождественно ложной, т.е. невыполнимой?

Таким образом, в логике предикатов, в отличие от логики высказываний, нет эффективного способа для распознавания общезначимости функций.

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

Аксиоматическая теория и правила вывода и составляют исчисления предикатов.

Символами исчисления предикатов или алфавитом исчисления предикатов являются символы предметных переменных, символы предикатов, логические символы (отрицание и импликация), символы кванторов, а также скобки и запятая.

Сформулируем аксиомы исчисления предикатов и правила вывода исчисления предикатов

 

Применение предикатов в алгебре

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

Типичным примером является уравнениенапримерх2-Зх+2=0Свободная переменная может принимать здесь любое числовое значениеДля некоторых чисел х (а именно х = 1, х = 2утверждениесодержащееся в этом уравненииистиннов остальных оно ложноВ подобных случаяхкогда истинность или ложность предиката зависит только от значенияпринимаемого свободной переменной хмножество допустимых значений х можно рассматривать как множество логических возможностей Uа множество всех значений этой переменнойпри которых высказывание истинно — как его множество истинности.

В приведенном выше примере множество состоит из всех действительных чисела множеством истинности является множество {1,2}.

В результате введения понятия множества истинности для предикатов мы сможем сказатьчто решить уравнение — значит найти один элемент или все элементы его множества истинностиПри решении системы двух уравнений у нас имеется предикатпредставляющий конъюнкцию двух уравненийПоэтому мы ищем пересечение двух множеств истинностиЕсли это пересечение пустото система уравнений не имеет решенийТакие уравнения называются несовместнымипоскольку их множества истинности не имеют общих элементов х.

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

Если — множество действительных чиселто множество истинности неравенства х < 0 состоит из всех отрицательных действительных чиселМножество же истинности неравенства х > -3 состоит из всех действительных чиселбольшихчем -3Если мы потребуемчтобы эти неравенства выполнялись одновременно, то множеством истинности будет множествоявляющееся пересечением двух исходных множествт.евсе действительные числа между -3 и 0.

Понятие множества истинности предиката позволяет выяснитьчем разнятся между собой уравнения и тождестваКогда мы решаем уравнениемы тем самым ищем один из элементов множества истинности этого уравнения или все его элементыЕсли же мы доказываем тождеството тем самым утверждаемчто оно справедливо для всех хТаким образомтождество представляет собой уравнениемножеством истинности которого является универсальное множество Uтеявляется логически истинным или тождественно истинным

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

Наряду с определенными предикатами для которых истинность или ложность

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

W(х1, х2, ..., хn); U(х,у),....

Применяя к переменным предикатам операции ; ; ; ; Ї; ; , получим формулы логики предикатов,

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

Пример.

(( х) W(х, у) В) U(z) формула логики предикатов. Формула логики предикатов называется тавтологией, если при подстановке любых конкретных предикатов она всегда обращается в тождественно истинный предикат

Остальное додумайте сами
 

10.06.2014; 17:23
хиты: 1293
рейтинг:+1
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь