Теорема 4. Законы удаления квантора общности и введения квантора существования.
а).
б).
Теорема 5. Законы коммутативности для кванторов.
Определение 1. Две формулы F и H логики предикатов называются равносильными на множестве M, если при любой подстановке в эти формулы вместо предикатных переменных любых конкретных предикатов, определенных на М, формулы превращаются в равносильные предикаты.
Определение 2. Если две формулы равносильны на любых множествах, то их будем называть просто равносильными.
Равносильность обозначается .
Покажем, что
Вместо предикатных переменных P(x) и Q(x) подставим конкретные предикаты A(x) и B(x), определенные на N.
A(x) = “x – четное число”, B(x) = “x – нечетное число”
Левая часть формулы есть высказывание:
«Каждое число четно или нечетно» (которое истинно).
Правая часть – высказывание:
«Каждое натуральное число четно, либо каждое натуральное нечетно» (которое ложно).
Определение. Формулы F и H равносильны тогда и только тогда, когда формула является тавтологией:
Определение. Приведенной формой для формул логики предикатов называется такая равносильная ей формула, в которой имеются только операции , и знаки отрицания относятся лишь к предикатным переменным и к высказываниям.
Теорема. Для любой формулы логики предикатов существует приведенная форма.
Определение. Предваренной нормальной формой для формулы логики предикатов называется такая ее предваренная форма, в которой все кванторы стоят в ее начале, а область действия каждого из них распространяется до конца формулы, т.е. формула вида , где – один из кванторов или , , а формула F не содержит кванторов и является приведенной формулой.
Do'stlaringiz bilan baham: |
