18282

ЛОГІКА ПРЕДИКАТІВ

Лекция

Математика и математический анализ

Лекція 9 ЛОГІКА ПРЕДИКАТІВ Поняття про зміну в математиці. Предикат висловлювальна форма та його основні характеристики. Тотожно істинні тотожно хибні і рівносильні предикати. Операції логіки висловлень над предикатами. Області істинності результат

Украинкский

2013-07-07

172.5 KB

77 чел.

Лекція 9

ЛОГІКА ПРЕДИКАТІВ

  1.  Поняття про зміну в математиці.
  2.  Предикат (висловлювальна форма) та його основні характеристики.
  3.  Тотожно істинні, тотожно хибні і рівносильні предикати.
  4.  Операції логіки висловлень над предикатами. Області істинності результатів цих операцій.
  5.  Кванторні операції над предикатами.
  6.  Правила побудови заперечення тверджень, що містять квантори.
  7.  Відношення логічного слідування на множині предикатів. Необхідні і достатні умови.

Питання на самостійне опрацювання

Властивості операції над висловленнями і предикатами

  1.  Поняття про операції над висловленнями і предикатами.
  2.  Властивості операцій над висловленнями і предикатами.

  1.  Поняття про зміну в математиці

Можливості природної мови не завжди дають змогу точно і однозначно записувати твердження у різних науках. Тому кожна з наук виробляє ще й свою специфічну мову. Однією з відмінностей між математичною і природною мовами є вживання у математичній мові змінних. У природній мові деякі слова можуть вживатися як змінні. Наприклад, у реченні "тигр має красиву ходу" слово "тигр" є змінною; у реченні ж "цей тигр має красиву ходу" слово "тигр" уже не є змінною. Між такими словами і змінними у математиці є суттєва різниця: слово можна вживати як змінну для елементів тільки певної множини, а в математиці – для елементів будь-якої множини.

Під змінною у математиці розуміють знак (символ) у деякому запису, замість якого можна підставляти елементи певної множини, які називаються значеннями змінної, а саму множину – областю визначення змінної.

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

У математиці розглядають змінні різної природи. Наприклад, у символічному запису "Для довільних елементів x і y множини M має місце рівність x * y = y * x" змінними є M, x, y і *, значення яких:

1) для M – множини;

2) для x і y – елементи множини M;

3) для * – бінарна операція на множині M.

Зокрема, якщо M – числова множина, то x і y будуть числовими змінними, якщо M – множина висловлень, то x і y – пропозиційні змінні.

  1.  Предикат (висловлювальна форма) та його основні характеристики

Засоби логіки висловлень виявляються недостатніми для аналізу багатьох математичних міркувань. Наприклад, її засобами не можна встановити правильність такого міркування: "Кожне ціле число є раціональним; 25 – ціле число. Отже, 25 – раціональне число". Це пояснюється тим, що у логіці висловлень прості висловлення, з яких за допомогою її операцій будуються складені висловлення, розглядаються як неподільні, тобто у них не аналізується їх структура. Тому виникає необхідність у побудові логічної системи, засобами якої можна дослідити будову простих тверджень, зокрема висловлень. Такою логічною системою є логіка предикатів, яка містить своєю складовою частиною логіку висловлень.

Крім висловлень можна виділити твердження, що містять одну або кілька змінних і перетворюються у висловлення при заміні змінних їх значеннями. Такі твердження називаються предикатами (висловлювальними формами).

Розрізняють одномісні, двомісні і т. д., n-місні предикати у залежності від того, скільки змінних входить до їх складу. Прикладами предикатів у математиці є рівняння і нерівності із змінними.

Будь-які одномісні, двомісні і т. д., n–місні предикати позначаються відповідно P(x), Q(xy), R(xyz), … , P(x1, x2, …, xn).

Вважають, що у багатомісному предикаті змінні строго лінійно впорядковані, тобто вони утворюють кортеж або набір змінних. Кожний предикат завжди задається разом із своєю областю визначення або ж її легко встановити за контекстом.

Якщо ж предикат P(x1, x2, …, xn) n–місний, то його областю визначення називається множина M = M1 ´ M2 ´ … ´ Mn, де M1, M2, …, Mn є областями визначення змінних x1, x2, …, xn відповідно. У випадку, коли множини M1, M2, …, Mn рівні, тобто M1 = M2 = … = Mn = M, то часто говорять, що предикат визначений на множині M, хоч в дійсності він визначений на множині Mn. Взагалі, область визначення предиката задається тією задачею, в якій розглядається предикат. Якщо на предикат не накладаються ніякі умови, то під його областю визначення розуміють множину всіх тих наборів значень змінних, при яких він перетворюється у висловлення.

Із багатомісних предикатів можна одержувати предикати меншої місності за допомогою підстановки замість деяких із змінних їх конкретних значень. Зокрема, у результаті заміни всіх змінних предиката їх значеннями одержується висловлення. Отже, висловлення можна розглядати як предикат від нуль змінних, а тому іноді говорять, що висловлення є нуль–місним предикатом. Розглянемо приклад. Рівняння

x + 2y – z = 5, де x, y, z Î R,

є тримісним предикатом. Коли надати x значення 1, то одержиться двомісний предикат

1 + 2 y – z = 5 або, що те саме, 2 y – z = 4, де y, z Î R.

При наданні значень x = 1 і y = 2 одержиться одномісний предикат 1 + 2 × 2 – z = 5 або, що те саме, z = 0, де z Î R.

При наданні ж значень x = 1, y = 1 і z = 1 отримаємо висловлення 1 + 2 × 1 – 1 = 5, тобто, 2 = 5, яке буде хибним.

Часто змінні, які входять у предикат, називаються предметними змінними.

Іноді n–місний предикат P(x1, x2, …, xn), визначений на множині M, зручно розглядати як одномісний предикат P(t), де t = (x1, x2, …, xn) і t Î M.

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

З кожним предикатом P(x), визначеним на множині M, пов'язані:

1) область істинності I, тобто множина тих значень змінної з області визначення предиката, при яких він перетворюється в істинне висловлення;

2) область хибності X, тобто множина тих значень змінної з області визначення предиката, при яких він перетворюється у хибне висловлення.

Множини M, I і X пов'язані співвідношеннями

I È X = M    і    I Ç X = Æ.

Кожний предикат однозначно визначається своєю областю визначення і областю істинності. Якщо предикат P(x), визначений на множині M, то його області істинності і хибності часто позначаються відповідно IP і XP = M\Ip.

На мові теорії відношень предикат, визначений на множині M, можна означити як відображення множини M у множину {0; 1}.

Одномісні предикати задають властивість елементів його області визначення, а n-місні предикати – n–арне відношення.

  1.  
    Тотожно істинні, тотожно хибні і рівносильні предикати

Предикат називається:

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

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

Предикати P(x) і Q(x), визначені на множині M, називаються рівносильними на ній, якщо їх області істинності рівні. Рівносильність предикатів P(x) і Q(x) записується

P(xº Q(x), x Î M.

Властивості тотожної істинності, тотожної хибності і рівносильності предикатів істотно залежать від їх областей визначення. Наприклад, одномісні предикати

P(x) – "x – 2 = 0"  і  Q(x) – "x2 – 4 = 0"

рівносильні на множині натуральних чисел n і нерівносильні на множині цілих чисел Z, бо на множині N   IP = IQ = {2}, а на множині Z   IP = {2}, але IQ = {–2; 2}.

Аналогічно, як для формул логіки висловлень, одержуємо теорему.

Теорема 1. Відношення рівносильності для предикатів, визначених на одній і тій же множині, є відношенням еквівалентності.

Відношення рівносильності предикатів дає змогу заміняти предикати на рівносильні їм. Цією властивістю широко користуються при розв'язуванні рівнянь і нерівностей.

  1.  
    Операції логіки висловлень над предикатами. Області істинності результатів цих операцій

Предикати, як і висловлення, також набувають логічних значень"0" чи "1", тому над ними можна виконувати всі операції логіки висловлень. Означення цих операцій над предикатами дається на основі відповідних операцій над висловленнями, при цьому закони операцій логіки висловлень для предикатів також мають місце. Отже, немає потреби в формулюванні законів для операцій над предикатами.

Запереченням довільного одномісного предиката P(x), визначеного на множині M, називається предикат, визначений на множині M, який набуває логічного значення "1" при тих і тільки тих x із множини M, при яких предикат P(x) набуває логічного значення "0". Записується  і читається "неправильно, що P(x)" або "не P(x)".

Операція на множині одномісних предикатів, визначених на множині M, при якій кожному предикату ставиться у відповідність його заперечення, називається операцією заперечення предикатів. З означення заперечення одномісного предиката P(x), визначеного на множині M, випливає, що область істинності заперечення предиката дорівнює області хибності предиката, тобто

.

Кон'юнкцією двох довільних одномісних предикатів, заданих на спільній області визначення, називається предикат, визначений на цій же множині, який набуває логічного значення "1" при тих і тільки тих значеннях змінної, при яких обидва предикати мають логічне значення "1".

Кон'юнкція предикатів P(x) і Q(x) записується P(xÙ Q(x) і читається: "P(x) і Q(x)".

Операція на множині одномісних предикатів із спільною областю визначення, при якій кожній упорядкованій парі предикатів ставиться у відповідність їх кон'юнкція, називається операцією кон'юнкції предикатів.

З означення кон'юнкції предикатів P(x) і Q(x), визначених на множині M, випливає, що її область істинності є перерізом областей істинності цих предикатів, тобто

.

Поняття кон'юнкції двох одномісних предикатів із спільною областю визначення можна узагальнити для кількох одномісних предикатів.

Кон'юнкцією кількох одномісних предикатів, заданих на спільній області визначення, називається предикат, визначений на цій же множині, який набуває логічного значення "1" при тих і тільки тих значеннях змінної, при яких усі предикати приймають логічне значення "1".

Кон'юнкція предикатів P1(x), P2(x), …, Pn(x) записується

 або  

і читається: "P1(x) і P2(x) і … і Pn(x)".

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

У математиці часто кон'юнкцію кількох предикатів, особливо у випадку рівнянь або нерівностей із змінними, називають системою предикатів (відповідно системою рівнянь або нерівностей із змінними).

Диз'юнкцією двох довільних одномісних предикатів, заданих на спільній області визначення, називається предикат, визначений на цій же множині, який набуває логічного значення "0" при тих і тільки тих значеннях змінної, при яких обидва предикати мають логічне значення "0".

Диз'юнкція двох предикатів P(x) і Q(x) записується P(xÚ Q(x) і читається: "P(x) або Q(x)".

З означення диз'юнкції предикатів P(x) і Q(x), визначених на множині M, випливає, що її область істинності є об'єднанням областей істинності цих предикатів, тобто

.

Поняття диз'юнкції двох одномісних предикатів можна узагальнити для кількох одномісних предикатів.

Диз'юнкцією кількох довільних одномісних предикатів, заданих на спільній області визначення, називається предикат, визначений на цій же множині, який набуває логічного значення "0" при тих і тільки тих значеннях змінної, при яких кожен із предикатів має логічне значення "0".

Диз'юнкція предикатів P1(x), P2(x), …, Pn(x) записується

 або  

і читається: "P1(x) або P2(x) або … Pn(x)".

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

У математиці часто диз'юнкцію предикатів, особливо, коли предикатами є рівняння або нерівності із змінними, називають сукупністю предикатів (сукупністю рівнянь або нерівностей із змінними).

Імплікацією одномісних предикатів P(x) і Q(x), визначених на множині M, називається предикат, визначений на множині M, який набуває логічного значення "0", при тих і тільки тих x множини M, при яких предикат P(x) має логічне значення "1", а предикат Q(x) – "0".

Імплікація предикатів P(x) і Q(x) записується P(x® Q(x) і читається: "якщо P(x), то Q(x)". Як і для висловлень, в імплікації предикатів P(x® Q(x) предикат P(x) називається умовою імплікації, а предикат Q(x) – висновком.

Щоб знайти область істинності імплікації предикатів, скористаємося правилом виключення імплікації

.

Звідси на основі знаходження областей істинності заперечення і диз'юнкції предикатів отримуємо

.

Отже, .

Еквіваленцією двох довільних одномісних предикатів, визначених на спільній області визначення, називається предикат, визначений на цій же множині, який набуває логічного значення "1" при тих і тільки тих значеннях змінної, при яких обидва предикати мають рівні логічні значення.

Еквіваленція предикатів P(x) і Q(x) записується P(x« Q(x) і читається: "P(x) тоді і тільки тоді, коли Q(x)". Щоб знайти область істинності еквіваленції предикатів P(x) і Q(x), визначених на множині M, скористаємося одним із правил виключення еквіваленції, а саме:

.

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

.

Аналогічно тому, як було сформульовано означення операції кон'юнкції двох одномісних предикатів, заданих на спільній області визначення, дається означення операцій диз'юнкції, імплікації та еквіваленції двох предикатів.

Означення бінарних операцій логіки висловлень над одномісними предикатами від різних змінних та багатомісними предикатами складніше, але при означенні всіх їх використовуються означення відповідних операцій над висловленнями.

Наприклад, кон'юнкцією двох одномісних предикатів P(x), x Î A і Q(y), y Î B, є двомісний предикат P(x) Ù Q(y), який визначений на множині M = A ´ B і набирає логічне значення "1" на всіх наборах значень змінних (x, y), на яких P(x) і Q(y) мають логічне значення "1".

  1.  
    Кванторні операції над предикатами

Крім операцій логіки висловлень, над предикатами виконуються ще дві властиві тільки їм операції: навішування квантора загальності і квантора існування.

У пункті 2 було встановлено, що заміна в одномісному предикаті змінної її значенням перетворює його у висловлення. Засоби мови дають можливість цей процес здійснювати ще й по-іншому. Для цього використовують слова "всі" і "існують" або їх синоніми, які називаються кванторами.

Операція навішування квантора загальності полягає у тому, що довільному одномісному предикату P(x), визначеному на множині M, ставиться у відповідність висловлення: "для всіх x множини M має місце предикат P(x)", яке набуває логічного значення "1" тоді і тільки тоді, коли предикат P(x) тотожно істинний на множині M, тобто, якщо область істинності предиката P(x) дорівнює його області визначення.

Якщо на скінченній множині M = {x1, x2, …, xn} визначено предикат P(x), то висловлення "для всіх x множини M має місце предикат P(x)", рівносильне кон'юнкції висловлень

P(x1Ù P(x2Ù … Ù P(xn).

Операція навішування квантора існування полягає у тому, що довільному одномісному предикату P(x), визначеному на множині M, ставиться у відповідність висловлення: "існує x у множині M таке, що має місце предикат P(x)", яке набуває логічного значення "1" тоді і тільки тоді, коли область істинності предиката P(x) є непорожньою множиною.

Якщо знову на скінченній множині M = {x1, x2, …, xn} визначено одномісний предикат P(x), то висловлення "існує x у множині M таке, що має місце предикат P(x)" рівносильне диз'юнкції висловлень

P(x1Ú P(x2Ú … Ú P(xn).

Символічно висловлення "для всіх x множини M має місце предикат P(x)" записується

(1)

а висловлення "існує x у множині M таке, що має місце предикат P(x)" –

.

(2)

Символи " і $ називаються, відповідно, квантором загальності і квантором існування.

У записах (1) і (2) буква x означає змінну, але оскільки записи є висловленнями, то від значення змінної x фактично не залежать. Тому підставляти замість x її значення із множини M уже немає смислу. Прийнято говорити, що в записах (1) і (2) квантори " і $ зв'язують змінну x, а саму змінну називають зв'язаною. Вона більше не є змінною у власному її розумінні: її наявність у запису необхідна тільки для того, щоб вказати на те, з якого предиката утворилося висловлення.

Операції навішування кванторів можна виконувати і над багатомісними предикатами. Змінні предиката, до яких застосовано квантори, називаються зв'язаними, всі інші змінні – вільними. З'ясуємо суть операції навішування кванторів для багатомісних предикатів на прикладі. На множині натуральних чисел N розглянемо двомісний предикат P(xy) – "x < y". Навісимо на нього квантор існування по змінній x, одержимо твердження

в якому x є зв'язаною змінною, а y – вільною змінною. Підставимо у це твердження замість y 1, одержимо висловлення

Це висловлення набуває логічного значення "0". Якщо ж замість y підставити будь-яке натуральне число більше 1, то одержиться істинне висловлення, а тому твердження  буде предикатом від однієї змінної. Якщо тепер на цей предикат навісити один із кванторів по вільній змінній, то одержимо уже висловлення. Наприклад:

яке буде хибним.

Аналогічні міркування можна провести для довільного n–місного предиката, і одержимо, що при навішуванні одного із кванторів на n–місний предикат одержується  предикат від n – 1 змінної. А тому, щоб за допомогою операції навішування кванторів із n–місного предиката одержати висловлення, потрібно кожну змінну зв'язати квантором існування чи загальності.

Задача. Із двомісного предиката P(xy) – "x £ y", визначеного на множині натуральних чисел N, за допомогою кванторних операцій побудувати всі можливі висловлення і встановити їх логічні значення.

► Навішуючи квантори по кожній змінній, одержимо такі висловлення:

1. ,

2. ,

3. ,

4. ,

5. ,

6. ,

7. ,

8. .

Сформулюємо висловлення 1 – 8 словами і вкажемо їх логічне значення.

Висловлення 1 і 2 мають однаковий смисл і їх можна сформулювати так: "Кожне натуральне число не перевищує довільного натурального числа". Це хибне висловлення.

Також однаковий смисл мають висловлення 3 і 4, їх можна сформулювати так: "Існують натуральні числа, з яких одне не перевищує другого". Це висловлення істинне.

Висловлення 5 можна сформулювати так: "Для всіх натуральних чисел існує не менше за них натуральне число". Висловлення істинне.

Висловлення 6 можна сформулювати так: "Існує натуральне число, якого не перевищують всі натуральні числа". Висловлення хибне.

Висловлення 7 можна сформулювати так: "Для кожного натурального числа існує натуральне число, яке його не перевищує". Висловлення істинне.

Висловлення 8 можна сформулювати так: "Існує натуральне число, яке не перевищує довільного натурального числа, тобто існує найменше натуральне число". Висловлення істинне.  ◄

Розгляд висловлень 1 і 2 та 3 і 4 показує, що при зміні порядку слідування однойменних кванторів, які стоять поряд, зміст висловлень, а, отже, і їх логічні значення, не змінюються. Навпаки, аналіз висловлень 5 і 6 та 7 і 8 показує, що зміна порядку слідування різнойменних кванторів приводить до зміни змісту висловлень, а тому може змінитися і їх логічне значення. Це має місце і у загальному випадку. Одержується твердження: однойменні квантори, які стоять поряд, можна міняти місцями, а різнойменні квантори міняти місцями не можна.

За даним твердженням можна спростити запис навішування однойменних кванторів на багатомісний предикат, усі змінні якого мають одну і ту ж саму область визначення. Покажемо це на прикладі тримісного предиката P(xyz), де xyz Î M. Висловлення, які одержуються із висловлення

: P(xyz)

всіма можливими перестановками виразів " x Î M, " y Î M і " z Î M, будуть рівносильними, а тому довільне з них прийнято записувати

" xyz Î M: P(xyz).

  1.  Правила побудови заперечення тверджень, що містять квантори

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

" x Î M: P(x).

Заперечимо його, тобто розглянемо твердження

.

Словами воно сформулюється так: "Неправильно, що для всіх x множини M має місце предикат P(x)". Очевидно, що одержане твердження рівносильне такому: "Існує x у множині M таке, що має місце предикат не P(x)", яке символічно записується

.

А тому

.

Аналогічно одержуємо, що

.

Проведені міркування доводять твердження, яке називається правилом заперечення тверджень, що містять квантори.

Щоб заперечити твердження, яке починається:

1) з квантора загальності, потрібно квантор загальності замінити на квантор існування і заперечити ту частину, яка йде за квантором;

2) з квантора існування, потрібно квантор існування замінити на квантор загальності і заперечити ту частину, яка йде за квантором.

Заперечуване твердження може містити декілька кванторів, тоді потрібно декілька разів скористатися сформульованим правилом.

Задача. Користуючись логічною і математичною символікою записати висловлення: "Існує найбільше натуральне число". Виконати операцію заперечення та встановити логічні значення одержаного і даного висловлень.

► Розглянемо на множині натуральних чисел предикат x £ y. Тоді наше висловлення запишеться так

.

За правилом заперечення тверджень, що містять квантори, одержимо

Враховуючи, що  остаточно матимемо

.

Одержане висловлення словами можна сформулювати так: "Для кожного натурального числа існує більше від нього число". Це твердження істинне, а тому твердження, яке заперечувалося, хибне.  ◄

  1.  
    Відношення логічного слідування на множині предикатів. Необхідні і достатні умови.

Якщо предикати P1(x), P2(x), …, Pn(x), визначені на множині M, то предикат Q(x) називається логічним наслідком предикатів P1(x), P2(x), …, Pn(x), коли він набуває логічне значення "1" при всіх тих x множини M, при яких кожен із предикатів P1(x), P2(x), …, Pn(x) приймає логічне значення "1". Записується

P1(x), P2(x),…, Pn(x|Q(x), x Î M.

Як і в логіці висловлень, користуються також терміном "з предикатів P1(x), P2(x), …, Pn(x) логічно випливає предикат Q(x)".

Між поняттями тотожної істинності, логічного наслідку і рівносильності для одномісних предикатів, визначених на множині M, існує зв'язок, який встановлюється на основі теорем, доведення яких безпосередньо одержується з означень.

Теорема 2. З предикатів P1(x), P2(x), …, Pn(x) логічно випливає предикат Q(x) тоді і тільки тоді, коли предикат

P1(xÙ P2(xÙ … Ù Pn(x® Q(x),  x Î M

тотожно істинний.

Наслідок 1. З предикатів P1(x), P2(x), …, Pn(x) логічно випливає предикат Q(x) тоді і тільки тоді, коли з предиката P1(xÙ P2(xÙ … Ù Pn(x) логічно випливає предикат Q(x).

На основі наслідку 1 відношення логічного слідування завжди можна розглядати як бінарне відношення.

Теорема 3. З предиката P(x) логічно випливає предикат Q(x) тоді і тільки тоді, коли область істинності предиката P(x) є підмножиною області істинності предиката Q(x).

Теорема 4. З предиката P(x) логічно випливає предикат Q(x) тоді і тільки тоді, коли висловлення

" x Î M: P(x® Q(x)

істинне.

Теорема 5. Предикати P(x) і Q(x) рівносильні тоді і тільки тоді, коли кожний з них є логічним наслідком іншого.

Якщо предикати P(x) і Q(x), визначені на множині M, такі, що предикат Q(x) є логічним наслідком предиката P(x), то предикат Q(x) називається необхідною умовою для предиката P(x), а предикат P(x) – достатньою умовою для предиката Q(x). Необхідна умова може не бути достатньою, а достатня – необхідною.

Якщо з предиката P(x) логічно випливає предикат Q(x) і з предиката Q(x) логічно випливає предикат P(x), тобто вони рівносильні, то предикат Q(x) називається необхідною і достатньою умовою для предиката P(x), а предикат P(x) – необхідною і достатньою умовою для предиката Q(x).

Задача. Замість крапок поставте у реченні "для того, щоб натуральне число ділилося на 5, …, щоб воно ділилося на 10" один із трьох виразів "необхідно", "достатньо" або "необхідно і достатньо" так, щоб утворилося істинне висловлення. Відповідь обґрунтуйте.

► З даного речення можна вичленити такі два предикати: P(x) –"натуральне число x ділиться на 5" і Q(x) – "натуральне число x ділиться на 10". Областю визначення цих предикатів є множина натуральних чисел N. Область істинності предиката P(x) є множина натуральних чисел, які кратні 5, а область істинності предиката Q(x) є множина натуральних чисел, що кратні 10. Кожне число кратне 10, кратне і 5, але не кожне число кратне 5 буде кратне 10. Отже, область істинності предиката Q(x) буде власною підмножиною області істинності предиката P(x), а тому лише предикат Q(x® P(x) є тотожно істинним на множині натуральних чисел. Значить, подільність натурального числа на 10 є достатньою умовою його подільності на 5. Тому у даному реченні замість крапок потрібно поставити слово "достатньо", а саме речення запишеться так: "для того, щоб натуральне число ділилося на 5, достатньо, щоб воно ділилося на 10".  ◄


Питання на самостійне опрацювання

Властивості операції над висловленнями і предикатами

  1.  Поняття про операції над висловленнями і предикатами.

Операції логіки висловлень можна описати за допомогою таблиць істинності (логічних значень), де зазначається, яких логічних значень набуває складене висловлення при різних логічних значеннях простих висловлень, що входять до його складу.

Предикати, як і висловлення, також набувають логічних значень"0" чи "1", тому над ними можна виконувати всі операції логіки висловлень. Означення цих операцій над предикатами дається на основі відповідних операцій над висловленнями, при цьому закони операцій логіки висловлень для предикатів також мають місце. Отже, немає потреби в формулюванні законів для операцій над предикатами.

Основні логічні операції логіки висловлень: заперечення, кон’юнкція, диз’юнкція, еквіваленція, імплікація.

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

Основні властивості операцій , Ú, Ù. Інші рівносильності можна дістати з них методом алгебраїчних перетворень.

1°. = А закон подвійного (заперечення).

2°.  A Ú B = B Ú A, – перестановка (комутативна)

3°. A Ù B = B Ù A,  властивість.

4°. (A Ú B) Ú C = A Ú (B Ú C)     сполучна (асоціативна)

5°. (A Ù B) Ù C = A Ù (B Ù C)   властивість.

6°. A Ù (B Ú C) = (A Ù B) Ú (A Ù C) – перша розподільна (дистрибутивна) властивість.

7°. A Ú (B Ù C) = (A Ú B) Ù (A Ú C) – друга розподільна властивість.

8°.  = ,   – закон де Моргана

.  = ,   

10°.  = 1 – закон виключення третього

11°.  = A.

12°.  = A.

13°. .

14°..

15°..

16°..

Рівносильності і безпосередньо випливають з означення; справедливість рівносильностей 10°-14° можна довести усно; рівносильності 15° і 16° були вже розглянуті. Залишилося перевірити властивості -9°.

Таблиця для перевірки властивості має вигляд:

A

B

C

A Ú (B Ù C)

(A Ú B) Ù (A Ú C)

0

0

0

0

0

0

0

1

0

0

0

1

0

0

0

0

1

1

1

1

1

0

0

1

1

1

0

1

1

1

1

1

0

1

1

1

1

1

1

1

Сукупність усіх висловлень разом з визначеними на ній логічними операціями , Ú, Ù,  і основними властивостями цих операцій називають алгеброю висловлень.


 

А также другие работы, которые могут Вас заинтересовать

78382. Введение в курс МЧП 15.25 KB
  Введение в курс МЧП. Понятие МЧП. МЧП – отрасль российского права которая регулирует частно правовые отношения отношения основанные на юридическом равенстве сторон при наличии иностранного элемента. МЧП распространяется только на отношения в пределах гражданского оборота.
78383. Источники МЧП 16.58 KB
  Источники МЧП Правовые источники: Международные соглашения договоры Закон в шир. смысле слова Обычаи правила которые не закреплены в законе Иные неправовые источники: Договоры и последующие соглашения доп.соглашения Локальные акты корпорации устав ООО Прецедент админ судеб Существо отношений Доктрина Юридическое равенство сторон заключается в том что одинаковый объем правоспособности если иное не закреплено в законе свобода вступать в правоотношения свобода выбора контрагента свобода согласования условий....
78384. Электрические аппараты 50.95 KB
  Если проводить аналогию между тепловозом и живым организмом то электрические аппараты представляют собой своеобразную нервную систему благодаря которой обеспечивается согласованная работа различных систем тепловоза. системы управления были реализованы на реле и электрические аппараты использовались для дистанционного управления электрической передачей тепловоза. для этой же цели стали применять магнитные усилители и другие бесконтактные аппараты.
78385. Строение и действие контроллеров, реверсоров, выключателей 230.44 KB
  Контактный элемент мостикового типа с двойным разрывом контактов состоит из изолятора 17 и рычага 13 контактных болтов 14 мостиковых контактов 16 держателя и пружин 15 обеспечивающих начальное и конечное контактное нажатие. Контроллер КВ1552 имеет следующую техническую характеристику: Тип контактов Мостиковый Напряжение 75 В Ток продолжительного режима 10А Ширина 10 мм Раствор 6 8 Провал 25 35 мм Нажатие 34 35 Н Угол поворота: главной рукоятки главного барабана реверсивного барабана в обе стороны нулевого положения 115 230 от 300...
78386. Аппаратура дистанционного действия. Назначение, устройство и действие электропневматических и электромагнитных контакторов 144.33 KB
  Форма контактов такова что при замыкании первоначально сходятся их передние концы затем подвижной контакт перекатывается по неподвижному до прилегания задних частей. Во время размыкания происходит обратное перекатывание и последними размыкаются переднее концы контактов. Последовательность положений контактов при замыкании показала на рис. При такой работе контактов уменьшается их износ предотвращается приваривание и сохраняется рабочей часть.
78388. Предохранители установлены в цепях регулирования и управления тепловозом 151.47 KB
  Расцепитель состоит из реле коромысла рейки и механизма свободного расцепления. Реле расцепителя с гидравлическим замедлением представляет собой электромагнитную систему с двумя подвижными частями: якорем 9 и плунжером. Промежуточные и специальные реле применяют для дистанционного управления и защиты электрических цепей. На тепловозе 2ТЭ116 устанавливают различные типы реле и датчиковреле в зависимости от выполняемых функций напряжения втягивающей катушки и количества контактов.
78390. Понятие о электрической схеме, условные обозначения схемы 32.24 KB
  Электрические схемы по ГОСТ. Структурные схемы используются для общего ознакомления с электропередачей тепловоза. Функциональные схемы представляют для объяснения принципов работы электрических машин аппаратов отдельных систем.