Тема 3. Дії над предикатами, їх

ВЛАСТИВОСТІ

План:

1. Означення предиката. Область визначення і область істин_

ності предиката.

2. Дії над предикатами:

а) заперечення предиката;

б) кон’юнкція двох предикатів;

в) диз’юнкція двох предикатів;

г) імплікація двох предикатів;

д) еквіваленція двох предикатів.

3. Властивості дій над предикатами.

Означення предиката. Область визначення і область

Істинності предиката.

Як вказувалось вище (стор. 28), серед речень, крім вислов_

лень, зустрічаються речення, що вміщують змінні, і відносно яких

не можна встановити істинні вони чи хибні. Але при підстановці

значень змінних ці речення перетворюються у висловлення, при_

чому при одних значеннях змінних отримуються істинні вислов_

лення, а при інших _ хибні. Такі речення називаються вислов)

лювальними формами або предикатами. Кожен предикат в

результаті підстановки замість змінних певних значень пород_

жує множину висловлень однакової форми. Наприклад, преди_

кат А(х): “натуральне число х кратне 3” при х=5 перетворюється

у висловлення А(5): “натуральне число 5 кратне 3”, яке хибне, а

при х=6 _ у висловлення А(6): “натуральне число 6 кратне 3”, яке

істинне. Очевидно, речень такої форми (висловлень) можна

одержати нескінченну множину, оскільки множина натуральних

чисел, з якої вибирається значення змінної х, нескінченна.

Залежно від кількості змінних предикати бувають одномісні,

двомісні, тримісні, і т.д. і символічно позначаються А(х), А(х,у) і т.д.

З кожним предикатом зв’язана множина, з якої вибираєть_

ся значення змінних. Цю множину називають областю визна_

чення предиката.

Введемо означення.

Означення 1. Одномісним предикатом називається

Речення А(х) із змінною х, яке задане на певній мно)

Жині Х і при підстановці значень змінної перетво)

Рюється у висловлення (істинне або хибне).

Означення 2. Областю визначення предиката А(х)

Називається множина тих значень змінної х, при яких

Цей предикат перетворюється у висловлення (істин)

Не або хибне).

Область визначення прийнято позначати буквою Х.

Означення 3. Областю істинності предиката А(х) на)

Зивається множина тих значень змінної, при яких цей

Предикат перетворюється в істинне висловлення.

Область істинності предиката А(х) прийнято позначати симво_

лом ТА(х).

ТА(X)={x/x є Х ∧ А(х) }

Область істинності предиката є підмножиною області його

визначення, тобто TA(х)⊂ X, що можна зобразити діаграмою

Ейлера_Венна так:

Двомісний предикат означається ана_

логічно. Слід лише мати на увазі, що оск_

ільки двомісний предикат А(х,у) перетво_

рюється у висловлення при підстановці

пар значень змінних х і у, кожна з яких ви_

бирається з деякої множини Х, то його областю визначення є

множина Х2 всіх можливих пар, утворених з елементів множини

Х, а областю істинності є множина ТА(х,у) тих пар (х,у) з множини

Х2 ((х,у) є Х2), при яких цей предикат перетворюється в істинне

висловлення.

ТA(х,у)={(x,y)/(x,y) є Х2 ∧ А(x,у)} — символічний запис області істин_

ності двомісного предиката. Відношення між множинами Х2 і ТА(х,у)

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

TA(х,y)⊂ X2.

ТА(х) Х

Зауваження. Нагадаємо, що Х2, як відомо з теорії множин, є де_

картовим квадратом множини Х, або ж декартовим добутком X×X.

Розглянемо приклад. Нехай дано двомісний предикат:

А(х,у): “х+у=7” на множині одноцифрових натуральних чисел.

Знайдемо область його істинності.

Очевидно, що множина Х={1,2,3,4,5,6,7,8,9}. Всіх можли_

вих пар з цієї множини можна утворити 81. (Це відомо з теорії

множин:

n(Х2)=n(

X×X

)=n(Х)•n(Х)= 9•9=81).

Не будемо виписувати цих пар, але можемо стверджувати,

що кількість висловлень форми х+у=7, які можна утворити,

підставляючи замість змінних їх значення, буде дорівнювати 81.

Серед цих висловлень будуть істинні і хибні. Легко визначити,

при яких значеннях х і у отримаємо істинні висловлення.

Якщо х=1, то х+у=7 при у=6. Отже, пара (х,у) може бути (1,6),

яка перетворює предикат в істинне висловлення.

Якщо х=2, то х+у=7 при у=5. Отже, пара (2,5) також перетво_

рює предикат в істинне висловлення.

Якщо х=3, то х+у=7 при у=4. Пара (3,4).

Аналогічно отримаємо пари (4,3), (5,2), (6,1).

Нарешті можемо записати область істинності даного пре_

диката. Із загальної формули

TA(x,y)= { (x,y) /(x,y) є Х2 ∧ А(х,у) } маємо:

TA(x,y)= { (x,y) /(x,y) є Х2 ∧ x+y=7 }

TA(x,y)= { (1;6), (2;5), (3;4), (4;3), (5;2), (6;1) }

У випадку тримісного предиката кожен раз будемо мати

справу з трійками елементів, тобто областю визначення такого

предиката є множина Х3.

Ми будемо розглядати найчастіше одномісні предикати.

Дії над предикатами

Над предикатами можна виконувати такі самі дії, як і над вис_

ловленнями, лише потрібно, щоб ці предикати були задані на

одній і тій самій області визначення.

а) Заперечення предиката.

Операція заперечення є унарною (стор. 30), а тому її викону_

ють над одним предикатом.

Означення. Запереченням предиката А(х), заданого

На множині Х, називається такий новий предикат

А (х)

(читається “не А від х” або “заперечення пре)

Диката А(х)”), який перетворюється в істинне вис)

Ловлення при тих значеннях змінної х з області виз)

Начення Х, при яких даний предикат А(х) перетво)

Рюється в хибне висловлення.

Згідно означення маємо, що множина Х є областю визна_

чення обох предикатів А(х) і А (х).

Областю істинності предиката А(х) є множина, яку

позначимо ТА(х) = {x/x є Х ∧ А(х)}.

(Читаємо: Область істинності предиката А(х) — це множина

тих значень змінної х з області визначення Х, при яких предикат

А(х) перетворюється в істинне висловлення). Відомо, що

Т А ( х ) ⊂ Х.

Зобразимо на діаграмі Ейлера_Венна область визначення Х

як універсальну множину, а область істинності ТА(х), як її підмно_

жину. Позначимо область істинності предиката А (х) симво_

лом Т А (х), тобто

Т А (х) = {x/x є Х ∧ А (х) } і виразимо її через ТА(х).

Згідно означення заперечення,

предикат А (х) перетворюється в

істинне висловлення при тих значеннях

змінної х, при яких предикат А(х) пере_

творюється в хибне висловлення. З

діаграми очевидно, що предикат А(х) перетворюється в хибне

висловлення на множині, яка є доповненням до області його

істинності. А це означає, що на цій множині предикат А (х) пе_

ретворюються в істинне висловлення.

Символічно можемо записати таке співвідношення:

Т А (х) = Т А (х)

Отже, область істинності заперечення предиката,

Заданого на певній множині, дорівнює доповненню

До області істинності даного предиката.

Приклад. На множині М= { x/x є N ∧ 5 ≤ x ≤ 15 } задано

предикат А(х): “х кратне 3”. Сформулюйте предикат А (х)і виз_

начте його область істинності.

Х

ТА(х)

Розв ’ язання. Областю визначення предиката А (х), згідно

означення, є множина М, яку задамо переліком:

М={5,6,7,8,9,10,11,12,13,14,15}.

А (х): “число х не є кратне 3” — є запереченням даного пре_

диката А(х). Область істинності предиката А(х) _ це множина, яка

складається з тих елементів множини М, при яких даний преди_

кат перетворюється в істинне висловлення, тобто множина, яка

складається з чисел, кратних 3.

ТА(х)= {x/x є М ∧ А(х)}, ТА(х)= {x/x є М ∧ хM 3}.

ТА(х)= {6; 9; 12; 15}.

Запишемо тепер множину Т А (х), яка є областю істинності

заперечення даного предиката. За вище поданою формулою

маємо:

Т А (х) = Т А (х) ={5,7,8,10,11,13,14}.

Ця множина складається з тих елементів області визначення

М, які не кратні 3.

б)Кон’юнкція двох предикатів.

Означення. Кон’юнкцією двох предикатів А(х) і В(х),

Заданих на множині Х, називається такий новий пре)

дикат А(х) ∧ В(х), який перетворюється в істинне вис)

Ловлення лише при тих значеннях змінної х з області

визначення Х (х є Х), при яких обидва предикати од)

Ночасно перетворюються в істинні висловлення.

Виразимо область істинності складеного предиката, який є

кон’юнкцією даних предикатів, через їх області істинності.

Згідно означення, областю визначення даних предикатів і

їх кон’юнкції є множина Х. Запишемо символічно їх області

істинності.

ТА(х)={x/x є Х ∧ А(х) }, ТА(х) ⊂ Х;

ТВ(х)={x/x є Х ∧ В(х) }, ТВ(х) ⊂ Х;

За означенням предикат А(х)∧В(х) перетворюється в істинне

висловлення лише тоді, коли обидва предикати одночасно пере_

творюються в істинні висловлення. Це означає, що до області істин_

ності предиката_кон’юнкції належатимуть тільки ті елементи, які

одночасно належать до областей істинності обох предикатів і пе_

ретворюють кожен з них одночасно в істинне висловлення.

З діаграми Ейлера_Венна очевид_

но, що ТА(х)∧В(х) _ область заштрихова_

на на діаграмі.

ТА(х) ∧ В(х) = {x/x є Х, А(х) ∧ В(х)}=

={x/x є Х, А(х)} ∩ {x/x є Х, В(х) } =ТА(х) ∩ ТВ(х).

Отже, Т А(х)∧ В(х) = ТА(х) ∩ ТВ(х).

Останню формулу читають так:

Область істинності кон ’ юнкції предикатів дорівнює пе)