Студопедия

Главная страница Случайная страница

Разделы сайта

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






Логические операции над предикатами.






 

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

Отрицание предиката. Пусть предикат P(x1, x2,..., xn) задан на множествах M1, M2,..., Mn. Предикат R(x1, x2,..., xn) называется отрицанием предиката P(x1, x2,..., xn) тогда и только тогда, если при одних и тех же кортежах (a1, a2,..., an), где а1 M1, а2 M2,..., аn Mn, высказывание P(a1, a2,..., an) истинно, когда R(a1, a2,..., an) - ложно и наоборот. Обозначение

R(x1, x2,..., xn) ù P(x1, x2,..., xn)

Например, предикат " n - четное число" есть отрицание предиката " n - нечетное число" на множестве целых чисел.

Конъюнкция предикатов. Пусть на множествах M1, M2,..., Mn заданы два n - местных предиката P(x1, x2,..., xn) и R(x1, x2,..., xn). Конъюнкцией этих предикатов называется предикат

Q(x1, x2,..., xn) P(x1, x2,..., xn) R(x1, x2,..., xn),

который истинен для одних и тех же кортежей только тогда, когда оба предиката и P(x1, x2,..., xn) и Q(x1, x2,..., xn) истинны.

 

 

 

Например, конъюнкция предикатов " x2 + y2 1" и " x 0", где x, y - вещественные числа определяет предикат " точки правой половины единичного круга" (см. рис.2.2).

Дизъюнкция предикатов P(x1, x2,..., xn) и R(x1, x2,..., xn), есть новый предикат S(x1, x2,..., xn) = P(x1, x2,..., xn) R(x1, x2,..., xn), который имеет значение " ложь" для тех и только тех кортежей из M1 M2 ... Mn, для которых оба предиката и P(x1, x2,..., xn) и R(x1, x2,..., xn) имеют значение " ложь". На рис.2.3 иллюстрируется дизъюнкция предиката " x2 + y2 1" и " x 0" - (заштрихованная область).

Импликация предикатов P(x1, x2,..., xn) и R(x1, x2,..., xn), есть новый предикат T(x1, x2,..., xn) = P(x1, x2,..., xn) R(x1, x2,..., xn), который имеет значение " ложь" для тех и только тех кортежей из M1 M2 ... Mn, для которых предикат P(x1, x2,..., xn) имеет значение " истина", а предикат R(x1, x2,..., xn) имеет значение " ложь". Например, импликация " n делится на 4" " n делится на 2" есть предикат: " если n делится на 4, то n делится на 2".

Эквивалентность предикатов P(x1, x2,..., xn) и R(x1, x2,..., xn), есть новый предикат V(x1, x2,..., xn) = P(x1, x2,..., xn) R(x1, x2,..., xn), который имеет значение " истина" для тех и только тех кортежей из M1 M2 ... Mn, для которых предикат P(x1, x2,..., xn) и предикат R(x1, x2,..., xn) имеют одинаковые значение или оба " истина" или оба " ложь". Два предиката заданных на одних и тех же множествах называются равносильными, если при всех наборах входящих в них предметных переменных эти предикаты принимают одинаковые значения. Равносильность называют также логической эквивалентностью. Например, эквивалентность предикатов P(n) = " n делится на 6" и R(n) = " n делится на 2 и n делится на 3" есть предикат V(n) = P(n) R(n): " если n делится на 6, то n делится на 2 и на 3". Предикаты P(n) и R(n) логически эквивалентны.

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

Квантор всеобщности есть операция, которая предикат P(x) превращает в высказывание: " все x обладают свойством P(x)". Знак квантора всеобщности " ". Он заменяет фразы: " для всех", " каждый", " любой" и т.п. Обозначение x: P(x) читается так: " для всех x таких, что P от x". Например, “P(x) = x> 0, где x - вещественное число”, есть предикат " x - положительное число". Тогда x: P(x) есть высказывание " каждое число - положительно". Это ложное высказывание. Если же x - любое натуральное число (x N), то x: P(x) есть выражение: " каждое натуральное число - положительно" - истинное высказывание.

Квантор всеобщности можно рассматривать как обобщение серии конъюнкций единичных высказываний. Пусть M - множество очков, которое может выпасть при бросании игральной кости, т.е. M ={1, 2, 3, 4, 5, 6} и P(x) - предикат: " при бросании игральной кости один раз выпадает x очков", где x M. Применение квантора всеобщности позволяет вместо сложного высказывания P(1) P(2) P(3) P(4) P(5) P(6) записать равносильное ему компактное высказывание x: P(x), x M: " при бросании игральной кости один раз может выпасть любое из шести первых натуральных чисел".

Квантор существования есть операция, которая предикат P(x) превращает в высказывание: " существует хотя бы один x из M, обладающий свойством P(x)". Знак квантора существования " ". Он заменяет фразы: " существует, хотя бы один", " найдется", " некоторый" и т.п. Обозначение x: P(x) читается так: " существует хотя бы один x такой, что P от x". Например, P(x) - предикат: " x - студент", где x - элемент множества жителей Москвы. Тогда выражение x: P(x) есть высказывание " хотя бы один житель Москвы является студентом".

Квантор существования можно рассматривать как обобщение серии дизъюнкций единичных высказываний. Если задано множество M={a1, a2,..., an} и на нем определен предикат P(x), то

P(а1) P(а2) ... P(аn) ( x M): P(x).

Кванторы обладают свойствами, являющимися аналогами законов де Моргана:

ù ( x: P(х)) х: ù P(х),

ù ( х: P(х)) х: ù P(х).

С помощью кванторов можно выражать ряд часто используемых на практике отношений между множествами. Например, высказывание " все объекты х из данного множества, обладающие свойством P(х), обладают также и свойством R(х)" формально можно записать так; х: (P(х) R(х)).

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

Рассмотрим пример. На множестве чисел задан двухместный предикат P(х, y)=" число х делится на число y". Связывая одну переменную, можно получить следующие одноместные предикаты:

х: P(х, y) = " каждое число делится на y" - ложь;

x: P(x, y) = " существует число, которое делится на y" - истина;

y: P(х, y) = " число х делится на любое число" - ложь;

y: P(х, y) = " существует число на которое делится х" - истина.

Связывая обе переменные данного предиката, получим высказывания:

х, y: P(х, y)=" каждое число делится на любое число" - ложное высказывание,

х, y: P(х, y)=" существует число, на которое делится любое число" - истина, т.к. такое число есть 1,

х, y: P(х, y)=" существует число, которое делится на любое число" - ложное высказывание,

х, y: P(х, y)=" существует число, которое делится на какое-нибудь число" - истинное высказывание.

 






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.