Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Операции квантификации.

Построение контрпримера | Равносильные формулы | Некоторые логические законы | Нормальные формы | Логическое следствие | Применение к переключательным схемам | Теория L. Аксиомы и правила вывода | Общезначимость теорем. Непротиворечивость L | Полнота теории L | Понятие предиката. |


Читайте также:
  1. Аддитивная и мультипликативная операции коммутативны
  2. Активные операции коммерческого банка
  3. Атомарные операции
  4. Банковские операции.
  5. В дальнейшем изложении мы будем предполагать применение операции переименования во всех конфликтных случаях.
  6. Вложенные операторы If. Логические операции и выражения
  7. Вложенные операторы if. Сложное условие в операторе if. Логические операции

 

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

Если A(x) – одноместный предикат, определенный на множестве М, то с помощью кванторов можно построить высказывания xA(x) (читается «для всех xA(x)») и xA(x) (читается «существует х, такое что A(x)»). Первое из них называют универсальным, а второе – экзистенциональным.

Универсальное высказывание истинно тогда и только тогда, когда A(x) - тождественно истинный предикат, а экзистенциональное высказывание истинно только тогда, когда A(x) - выполнимый предикат.

Примеры. Высказывание x(x2≥0) – истинно, а x(x2-3x+2=0)- ложно, так как предикат x2>0–тождественно истинный, а предикат x2-3x+2=0 таковым не является. Высказывание x(x2-3x+2=0)истинно, а x(x2=-1) – ложно.

Следует обратить внимание на то, что если предикат A(x) определен на конечном множестве {a1,a2,...,an}, то универсальное высказывание xA(x) равносильно высказыванию A(a1) A(an), а экзистенциональное высказывание x A(x) равносильно высказыванию A(a1) A(an).

При квантификации n–местного предиката A(x,…,xn), определенного на множествах M1,…,Mn, квантором общности по переменной xi, 1≤x≤n, получаем (n-1)-местный предикат xi A(xi,…,xn), зависящий от переменных

x1,..,xi-1,xi+1,…,xn. Значение предиката xi A(xi,…,xn) от набора значений переменных < α1,.., α i-1, α i+1,…, α n > совпадает со значением универсального высказывания xi A(α1,.., α i-1, xi, α i+1,…, α n)

Пример. Пусть A(x,y)=(xy=0). Квантификация данного предиката по переменной x дает одноместный предикат B(y)= xA(x,y). B(3)= xA(x,3)= x (x×3=0)=0, B(0)= x(x×0=0)=1. Таким образом, квантификация двуместного предиката xy=0 квантором общности по переменной x дала одноместный выполнимый предикат, зависящий от у.

Если A(x,y,z)=(x2+y2+z2=1), то y(x2+y2+z2=1)=C(x,z) – двуместный предикат, зависящий от x,z. нетрудно увидеть, что C(x,z) - тождественно ложный предикат. В самом деле, для любых фиксированных значений x=α, z=β предикат α2+y22=1 одноместный не тождественно истинный. Квантификация его по переменной у квантором общности дает ложное высказывание.

Аналогично квантификация n–местного предиката квантором существования дает (n-1)–местный предикат, вычисление которого от данного набора значений переменных сводится к квантификации одноместного предиката квантором существования.

x(x+y+z=4) = D(y,z) -двуместный тождественно истинный предикат. Здесь, например, D(2,-1)= x(x+2-1=4)=1

y(x2+y2<-1)=F(x) - тождественно ложный предикат.

Очень важно усвоить, что кванторы связывают переменные. Предикаты xiA(x1,…,xn), xiA(x1,…,xn) уже не зависят от переменной xi. Аналогичную ситуацию мы встречали и в других разделах математики. Так, переменная х в выражении связана операцией интегрирования.

Конечно, предикат xi A(x1,…,xn) можно повторно квантифицировать по переменной xj. Если i≠j, то получаем (n-2)–местный предикат xj xiA(x1,…,xn) и т.д. после квантификации n–местного предиката по всем переменным каким-либо квантором получаем высказывание.

Примеры.1. высказывание y z(xy=0) истинно, так как одноместный предикат x(xy=0)выполним и квантификация его квантором существования дает 1.

2. Высказывание x y(x>y) истинно, а y x(x>y) – ложно. Можно рассуждать здесь чисто формально, отмечая, что y (x>y) - тождественно истинный, а x(x>y) - тождественно ложный предикат. Но и здравые соображения человека, знакомого с математикой в рамках средней школы, дают тот же результат. Ведь первое высказывание равносильно утверждению, что не существует наименьшего действительного числа (известная истина),а второе высказывание утверждает как раз противное.

Пример 2 убеждает нас в том, что кванторы общности и существования не перестановочны.

Обратим внимание еще на одну деталь. Высказывания принято считать 0–местными предикатами (это позволяет включить алгебру высказываний в алгебру предикатов). Кроме того, квантификация предиката по переменной, от которой он не зависит, дает предикат, равносильный исходному. Так, например, x(y+z=0) равносильно y+z=0, (2×2=4) равносильно 2×2=4.

Последнее замечание в данном пункте будет касаться очередности выполнения логических операций в алгебре предикатов. Договоренность относительно очередности выполнения операций ù, остается в силе. Кроме того, операции квантификации считаются более «привязанными» к предикатам, чем другие связки, т.е. в выражении xA(x) B(x) нужно сначала квантифицировать предикат A(x), а затем выполнять дизъюнкцию 0-метсного предиката xA(x) и одноместного предиката B(x).

 

Контрольные вопросы и упражнения

1. Обобщением каких простейших логических операций являются операции квантификации?

2. Построить на множестве целых чисел предикаты:

а) , что ; в) , что ;

б) , что ; г) , что .

3. Пусть «х – целое число», «х – рациональное число». Что означает запись: ?

4. Какой местности и какого типа следующие предикаты, определенные на целых числах:

а) ; г) ;

б) ; д) ;

в) ; е) .

5. Найти значение следующих высказываний, образованных квантификацией предикатов, в которых переменные определены на целых числах:

а) ; г) ;

б) ; д) ;

в) ; е) .

6. Записать на языке предикатов следующие высказывания, введя для простых предикатов соответствующие обозначения:

а) каждое число, кратное 10, кратно 5 и 2;

б) каждая функция , дифференцируемся в точке , непрерывна в точке ;

в) каждая непрерывная на функция – интегрируема на ;

г) диагонали произвольного прямоугольника равны между собой;

д) все числа, кратные 46, кратны 8 и 6, но не всякое число, кратное 8 и 6, кратно 48;

е) все трансцендентные числа – иррациональны, но не все иррациональные числа – трансцендентны;

ж) каждый квадрат является ромбом, но не всякий ромб – квадрат.

7. Даны два предиката и , где переменные определены на множестве . Для следующих предикатов найти равносильные, не содержащие кванторов:

а) ; г) ;

б) ; д) ;

в) ; е) .

 

 


Дата добавления: 2015-11-14; просмотров: 180 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Простейшие логические операции над предикатами.| Предикатные формулы.

mybiblioteka.su - 2015-2024 год. (0.014 сек.)