Алгебра висловлювань. Логічні операції

План

Висловлювання із зовнішнім запереченням.

Кон'юнктивні висловлювання.

Диз'юнктивні висловлювання.

Суворо-диз'юнктивні висловлювання.

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

Імплікативні висловлювання.

Висловлювання із зовнішнім запереченням.

Висловлювання із зовнішнім запереченням - це висловлювання (судження), у якому стверджується відсутність певної ситуації. Воно найчастіше виражається пропозицією, що починається словосполученням "невірно, що..." або "неправильно, що...". Зовнішнє заперечення позначається символом “ù”, званим знаком заперечення. Цей знак визначається наступною таблицею істинності:

У висловлюваннях із зовнішнім запереченням заперечується ситуація у А. Наприклад, якщо А: “Волга впадає у Чорне море”, то ùА: “Невірно, що Волга впадає у Чорне море”.

Кон'юнктивні висловлювання.

Кон'юнктивними висловлюваннями є такі, у яких затверджується одночасна наявність двох ситуацій. Кон'юнктивні висловлювання утворюються із двох висловлювань з допомогою спілок “і”, “а”, “але”. Форма кон'юнктивного висловлювання: (А&В). Кожне з висловлювань А і В може набувати значення “істина”, так і значення “брехня”. Ці значення для стислості позначаються буквами і, л. Таблиця істинності для кон'юнктивних висловлювань має такий вигляд:

У кон'юнктивних висловлюваннях стверджується, що ситуація, описана в А і В мають місце одночасно. Приклади кон'юнктивних висловлювань: “Земля – планета, а Місяць – супутник”; "Петров добре освоїв логіку, але Сидоров освоїв логіку погано"; "На вулиці темно, і в аудиторії горить світло"; "Петров всунув чиновнику хабар грошима, а Сидоров - пляшкою".

Диз'юнктивні висловлювання.

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

Табличне визначення знака диз'юнкції має такий вигляд:

Приклад диз'юнктивного висловлювання: “Роман Сергійович Іванов є викладачем, чи Роман Сергійович Іванов є аспірантом”.

Суворо-диз'юнктивні висловлювання.

Строго-диз'юнктивними називаються висловлювання, в яких затверджується наявність рівно однієї з двох ситуацій, описаних в А і В. Такі висловлювання найчастіше здійснюються за допомогою пропозицій із союзом "або..., або..." ("або..., або ...”). Сувора диз'юнкція позначається символом V * (читається "або ..., або ...").

Табличне визначення знака суворої диз'юнкції має такий вигляд:

Приклад суворо-диз'юнктивного висловлювання: “Або надворі сонячно, чи йде дощ”.

Значення істинності

Ця стаття або розділ – грубий переклад статті іншою мовою (див. Перевірка перекладів). Він міг бути згенерований програмою-перекладачем або зроблений людиною зі слабкими знаннями у мові оригіналу. ¬( Шаблон:Mvar∧Шаблон:Mvar) ⇔ ¬Шаблон:Mvar ∨ ¬Шаблон:Mvar ¬( Шаблон:Mvar∨Шаблон:Mvar) ⇔ ¬Шаблон:Mvar ∧ ¬Шаблон:Mvar Багатозначна логіка Багатозначна логіка (наприклад, нечітка логіка дозволяє більше двох значень істинності, які, можливо, містять деякі внутрішні структури. Алгебраїчна семантика Не всі логічні системи істинно-ціннісні у цьому сенсі, що логічні зв'язки може бути інтерпретовані як істина функцій. Наприклад, в інтуїціоністській логіці відсутня повний набір значень істинності, тому що його семантика визначається в термінах доказовості умови, а не безпосередньо в термінах обов'язкової вірності формул. В інших теоріях Інтуїціоністська теорія типів використовує типи замість значень істинності. Топос теорії використовує значення істинності в особливому значенні: істина значення топос є глобальним елементом х подоб'єктом класифікатором. Маючи значення істинності у сенсі немає ціннісної логіки істини. Див. також Посилання Wikimedia Foundation. 2010 . Дивитись що таке "Значення істинності" в інших словниках: Зміст, позначений тим чи іншим мовним словом, пропозицією, знаком тощо. Питання про З. мовних виразів досліджується лінгвістикою, семіотикою та логічною семантикою. Розрізняють предметне, смислове та експресивне З. мовних … Філософська енциклопедія Значення істинності (у логіці), значення, яке набуває Висловлювання (пропозиція, судження), що розглядається стосовно змісту, що в ньому відображається. У звичайній (класичній) логіці використовуються два І. з. "істинно", "хибно"; в… … Велика Радянська Енциклопедія Таблиця істинності таблиця, що описує логічну функцію. Під «логічною функцією» в даному випадку розуміється функція, у якої значення змінних (параметрів функції) та значення самої функції виражають логічну істинність. Таблиця, за допомогою якої встановлюється істиннісне значення складного висловлювання при даних значеннях простих висловлювань, що входять до нього. У класичній математичній логіці передбачається, що кожне просте (що не містить логічних… Словник термінів логіки Денотат (від лат. denotatum позначене), термін лінгвістики та екстенсіональної логіки, що означає 1) екстенсіонал, 2) десігнат, 3) референт та 4) семантичне ядро ​​значення. Зміст 1 Денотат як екстенсіонал 2 Денотат як десігнат … Вікіпедія Однією з можливих характеристик висловлювання з погляду відповідності його описуваному фрагменту дійсності. Якщо допускається, що кожне висловлювання є або істинним, або хибним (тобто воно відповідає дійсності …). Словник термінів логіки Сукупність логічних систем, що спираються на принцип багатозначності. У класичній двозначній логіці висловлювання при інтерпретації набувають лише двох значень «істинно» і «хибно», в М.Л. розглядаються та ін значення, напр. «невизначено», … Філософська енциклопедія - (Від лат. factum зроблене, що відбулося) 1) синонім понять «істина», «подія», «результат»; щось реальне на противагу вигаданому; конкретне, одиничне на відміну абстрактного та загального; 2) у філософії науки особливого роду п... Філософська енциклопедія - (В л о г і к е) - істинність пропозиції (судження, висловлювання), обумовлена, на відміну від т.зв. логіч. істинності, змістом цієї пропозиції. Інакше кажучи, пропозиція є фактично істинною, коли її істинність залежить від значень. Філософська енциклопедія Стереометрична семантика- трактування логіки як науки отримання справжніх наслідків з справжніх посилок дедалі більше поступається місцем ширшої концепції, пов'язаної чи з узагальненням поняття слідування, заснованого на традиційної істиннісної оцінці і практичних… … Проектний філософський словник Книги Як щиро повірити в Бога, або Єдине, що має значення для розвитку віри, Враджев В.. Перш ніж зробити перші кроки в духовне життя, кожна людина завжди ставить питання: Чи існує Бог насправді? навколишній світ за допомогою…

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

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

Малюнок зверху - ілюстрація явища, відомого як "Парадокс брехуна". При цьому, на думку автора проекту, такі парадокси можливі лише в середовищах, невільних від політичних проблем, де на комусь можуть апріорі поставити тавро брехуна. У природному багатошаровому світі на предмет "істини" або "брехні" оцінюються лише окремо взяті висловлювання . І далі на цьому уроці вам представиться можливість самим оцінити цей предмет чимало висловлювань (А потім подивитися правильні відповіді). У тому числі складних висловлювань, у яких простіші пов'язані між собою знаками логічних операцій. Але насамперед розглянемо самі ці операції над висловлюваннями.

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

Так, може бути оголошена логічна змінна з ім'ям "КористувачЗареєстрований" (або його англомовний аналог), що має форму висловлювання, якій може бути присвоєно логічне значення "істина" при виконанні умов, що дані для реєстрації надіслані користувачем і ці програми визнані придатними. У подальших обчисленнях значення змінних можуть змінюватись в залежності від того, яке логічне значення ("істина" або "брехня") має змінна "КористувачЗареєстрований". В інших випадках змінної, наприклад, з ім'ям "ДоДняХЗалишилосяБільшеТрьохДнів", може бути присвоєно значення "Істина" до деякого блоку обчислень, а в ході подальшого виконання програми це значення може зберігатися або змінюватися на "брехню" і від значення цієї змінної залежить хід подальшого виконання програми.

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

Логічні операції над висловлюваннями

Для математичних висловлювань завжди можна зробити вибір між двома різними альтернативами "істина" і "брехня", а для висловлювань, зроблених "словесною" мовою, поняття "істинності" і "хибності" дещо більш розпливчасті. Однак, наприклад, такі словесні форми, як "Йди додому" та "Чи йде дощ?", не є висловлюваннями. Тому зрозуміло, що висловлюваннями є такі словесні форми, у яких щось стверджується . Не є висловлюваннями запитання чи оклику пропозиції, звернення, а також побажання чи вимоги. Їх неможливо оцінити значеннями "істина" та "брехня".

Висловлювання ж, навпаки, можна як величину, яка може набувати два значення: " істина " і " брехня " .

Наприклад, дані міркування: "собака - тварина", "Париж - столиця Італії", "3

Перше з цих висловлювань може бути оцінено символом "істина", друге - "брехня", третє - "істина" та четверте - "брехня". Таке трактування висловлювань становить предмет алгебри висловлювань. Позначатимемо висловлювання великими латинськими літерами A, B, ..., а їх значення, тобто істину та брехню, відповідно Іі Л. У звичайній мові використовуються зв'язки між висловлюваннями "і", "або" та інші.

Ці зв'язки дозволяють, поєднуючи між собою різні висловлювання, утворювати нові висловлювання. складні висловлювання . Наприклад, зв'язування "і". Нехай дано висловлювання: " π більше 3" та висловлювання " π менше 4". Можна організовувати нове - складне висловлювання" π більше 3 і π менше 4". Висловлювання "якщо π ірраціонально, то π ² теж ірраціонально" виходить зв'язуванням двох висловлювань зв'язкою "якщо - то". Нарешті, ми можемо отримати з будь-якого висловлювання нове - складне висловлювання - заперечуючи первісне висловлювання.

Розглядаючи висловлювання як величини, що приймають значення Іі Л, ми визначимо далі логічні операції над висловлюваннями , які дозволяють з цих висловлювань отримувати нові - складні висловлювання.

Нехай дано два довільні висловлювання Aі B.

1 . Перша логічна операція над цими висловлюваннями - кон'юнкція - є утворенням нового висловлювання, яке будемо позначати A ∧ Bі яке істинно тоді і тільки тоді, коли Aі Bістинні. У звичайній промові цієї операції відповідає з'єднання висловлювань зв'язкою "і".

Таблиця істинності для кон'юнкції:

A	B	A ∧ B
І	І	І
І	Л	Л
Л	І	Л
Л	Л	Л

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

Таблиця істинності для диз'юнкції:

A	B	A ∨ B
І	І	І
І	Л	І
Л	І	І
Л	Л	Л

3 . Третя логічна операція над висловлюваннями Aі B, що виражається у вигляді A → B; отримане таким чином висловлювання хибне тоді і лише тоді, коли Aістинно, а Bпомилково. Aназивається посилкою , B - наслідком , а висловлювання A → B - слідуванням , що називається також імплікацією. У звичайній промові ця операція відповідає зв'язці "якщо - то": "якщо A, то BАле у визначенні логіки висловлювань цей вислів завжди істинно незалежно від того, істинно чи хибно висловлювання B. Цю обставину можна коротко сформулювати так: "з хибного випливає все, що завгодно". У свою чергу, якщо Aістинно, а Bхибно, то все висловлювання A → Bпомилково. Воно буде істинним тоді і лише тоді, коли і A, і Bістинні. Коротко це можна сформулювати так: "із істинного не може слідувати хибне".

Таблиця істинності для слідування (імплікації):

A	B	A → B
І	І	І
І	Л	Л
Л	І	І
Л	Л	І

4 . Четверта логічна операція над висловлюваннями, точніше над одним висловлюванням, називається запереченням висловлювання Aі позначається ~ A(можна зустріти також вживання не символу ~, а символу ¬, а також верхнього надкреслення над A). ~ Aє висловлювання, яке хибно, коли Aістинно, і істинно, коли Aпомилково.

Таблиця істинності для заперечення:

A	~ A
Л	І
І	Л

5 . І, нарешті, п'ята логічна операція над висловлюваннями називається еквівалентністю та позначається A ↔ B. Отримане таким чином висловлювання A ↔ Bє вислів правдивий тоді і тільки тоді, коли Aі Bобидва істинні або обидва помилкові.

Таблиця істинності для еквівалентності:

A	B	A → B	B → A	A ↔ B
І	І	І	І	І
І	Л	Л	І	Л
Л	І	І	Л	Л
Л	Л	І	І	І

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

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

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

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

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

приклад 1.

1) (2 = 2) І (7 = 7);

2) Не (15;

3) ("Сосна" = "Дуб") АБО ("Вишня" = "Клен");

4) Не ("Сосна" = "Дуб");

5) (Не (15 20);

6) ("Очі дано, щоб бачити") І ("Під третім поверхом знаходиться другий поверх");

7) (6/2 = 3) АБО (7 * 5 = 20) .

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

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

3) Значення висловлювання у перших дужках - "брехня", значення висловлювання у других дужках - також "брехня". Висловлювання з'єднані логічною операцією "АБО" і жодне з висловлювань не має значення "істина". Тому логічне значення всього цього висловлювання - "брехня".

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

5) У перших дужках заперечується висловлювання у внутрішніх дужках. Цей вислів у внутрішніх дужках має значення "брехня", отже, його заперечення матиме логічне значення "істина". Висловлювання у других дужках має значення "брехня". Два цих висловлювання з'єднані логічною операцією "І", тобто виходить "істина І брехня". Отже, логічне значення всього цього висловлювання - "брехня".

6) Значення висловлювання у перших дужках - "істина", значення висловлювання у других дужках - також "істина". Два цих висловлювання з'єднані логічною операцією "І", тобто виходить "істина І істина". Отже, логічне значення всього цього висловлювання - "істина".

7) Значення висловлювання у перших дужках - "істина". Значення висловлювання у других дужках - "брехня". Два цих висловлювання з'єднані логічною операцією "АБО", тобто виходить "істина АБО брехня". Отже, логічне значення всього цього висловлювання - "істина".

приклад 2.Запишіть за допомогою логічних операцій такі складні висловлювання:

1) "Користувач не зареєстрований";

2) "Сьогодні неділя та деякі співробітники перебувають на роботі";

3) "Користувач зареєстрований тоді і лише тоді, коли надіслані користувачем дані визнані придатними".

1) p- одиночний вислів "Користувач зареєстрований", логічна операція: ;

2) p- одиночний вислів "Сегодня неділя", q- "Деякі співробітники перебувають у роботі", логічна операція: ;

3) p- одиночний вислів "Користувач зареєстрований", q- "Надіслані користувачем дані визнані придатними", логічна операція: .

Вирішити приклади на логіку висловлювань самостійно, а потім переглянути рішення

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

1) ("У хвилині 70 секунд") АБО ("Годинник годинника показує час");

2) (28> 7) І (300/5 = 60);

3) ("Телевізор - електричний прилад") І ("Скло - дерево");

4) Не((300 > 100) АБО ("Спрагу можна вгамувати водою"));

5) (75 < 81) → (88 = 88) .

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

1) "Якщо годинник неправильно показує час, то можна невчасно прийти на заняття";

2) "У дзеркалі можна побачити своє відображення і Париж – столиця США";

Приклад 5.Визначте логічне значення виразу

(p → q) ↔ (r → s) ,

p = "278 > 5" ,

q= "Яблуко = Апельсин",

p = "0 = 9" ,

s= "Шапка покриває голову".

Формули логіки висловлювань

Поняття логічної форми складного висловлювання уточнюється з допомогою поняття формули логіки висловлювань .

У прикладах 1 та 2 ми вчилися записувати за допомогою логічних операцій складні висловлювання. Взагалі вони називаються формулами логіки висловлювань.

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

p, q, r, ..., p 1 , q 1 , r 1 , ...

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

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

~, ∧, ∨, →, ↔,

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

Концепція формули логіки висловлювань визначимо так:

1) елементарні формули (атоми) є формулами логіки висловлювань;

2) якщо Aі B- формули логіки висловлювань, то ~ A , (A ∧ B) , (A ∨ B) , (A → B) , (A ↔ B) теж є формулами логіки висловлювань;

3) тільки ті вирази є формулами логіки висловлювань, для яких це випливає з 1) та 2).

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

Приклад 6.Нехай p- одиночний вислів (атом) "Всі раціональні числа є дійсними", q- "Деякі дійсні числа - раціональні числа", r- "деякі раціональні числа є дійсними". Перекладіть у форму словесних висловлювань наступні формули логіки висловлювань:

6) .

1) "немає дійсних чисел, які є раціональними";

2) "якщо не всі раціональні числа є дійсними, то немає раціональних чисел, які є дійсними";

3) "якщо всі раціональні числа є дійсними, то деякі дійсні числа - раціональні числа та деякі раціональні числа є дійсними";

4) "всі дійсні числа - раціональні числа та деякі дійсні числа - раціональні числа та деякі раціональні числа є дійсними числами";

5) "всі раціональні числа є дійсними тоді і лише тоді, коли немає місце бути, що не всі раціональні числа є дійсними";

6) "не має місця бути, що не має місце бути, що не всі раціональні числа є дійсними і немає дійсних чисел, які є раціональними чи ні раціональних чисел, які є дійсними".

Приклад 7.Складіть таблицю істинності для формули логіки висловлювань , яку в таблиці можна позначити f .

Рішення. Складання таблиці істинності починаємо із запису значень ("істина" або "брехня") для одиночних висловлювань (атомів) p , qі r. Усі можливі значення записуються у вісім рядків таблиці. Далі, визначаючи значення операції імплікації, і просуваючись праворуч по таблиці, пам'ятаємо, що значення дорівнює "брехні" тоді, коли з "істини" випливає "брехня".

p	q	r					f
І	І	І	І	І	І	І	І
І	І	Л	І	І	І	Л	І
І	Л	І	І	Л	Л	Л	Л
І	Л	Л	І	Л	Л	І	І
Л	І	І	Л	І	Л	І	І
Л	І	Л	Л	І	Л	І	Л
Л	Л	І	І	І	І	І	І
Л	Л	Л	І	І	І	Л	І

Зауважимо, що жодний атом не має вигляду ~ A , (A ∧ B) , (A ∨ B) , (A → B) , (A ↔ B). Такий вигляд мають складні формули.

Число дужок у формулах логіки висловлювань можна зменшити, якщо прийняти, що

1) у складній формулі опускатимемо зовнішню пару дужок;

2) упорядкуємо знаки логічних операцій "по старшинству":

↔, →, ∨, ∧, ~ .

У цьому списку знак ↔ має найбільшу область дії, а знак ~ - найменшу. Під областю дії знака операції розуміються частини формули логіки висловлювань, яких застосовується (що діє) аналізоване входження цього знака. Таким чином, можна опускати у будь-якій формулі ті пари дужок, які можна відновити з огляду на "порядок старшинства". А при відновленні дужок спочатку розставляються всі дужки, що відносяться до всіх входжень знака ~ (при цьому ми просуваємося зліва направо), потім до всіх входжень ∧ і так далі.

Приклад 8.Відновіть дужки у формулі логіки висловлювань B ↔ ~ C ∨ D ∧ A .

Рішення. Дужки відновлюються покроково наступним чином:

B ↔ (~ C) ∨ D ∧ A

B ↔ (~ C) ∨ (D ∧ A)

B ↔ ((~ C) ∨ (D ∧ A))

(B ↔ ((~ C) ∨ (D ∧ A)))

Не всяка формула логіки висловлювань може бути записана без дужок. Наприклад, у формулах А → (B → C) і ~ ( A → B) подальше виключення дужок неможливе.

Тавтології та протиріччя

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

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

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

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

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

Крім тавтологій і логічних протиріч існують такі формули логіки висловлювань, які є ні тавтологіями, ні протиріччями.

Приклад 9.Складіть таблицю істинності для формули логіки висловлювань і визначте, є вона тавтологією, протиріччям чи ні тим, ні іншим.

Рішення. Складаємо таблицю істинності:

І	І	І	І	І
І	Л	Л	Л	І
Л	І	Л	І	І
Л	Л	Л	Л	І

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

Тема програми: Висловлювання та операції з них.

Цілі уроку:

1) Узагальнити теоретичні знання на тему: «Висловлювання та операції з них».

2) Розглянути алгоритми розв'язання завдань темі «Висловлювання та операції з них», розв'язати задачи.

3) Формувати вміння прогнозувати власну діяльність, вміння організувати свою діяльність та аналізувати її.

Час виконання: 1:00.

Теоретичні основи

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

Приклади висловлювань.
1) Москва стоїть на Неві.
2) Лондон – столиця Англії.
3) Сокіл не риба.
4) Число 6 ділиться на 2 та на 3.
Висловлювання 2), 3), 4) істинні, а висловлювання 1) хибно.
Очевидно, пропозиція «Хай живе Росія!» не є висловлюванням.
Розрізняють два види висловлювань.
Висловлювання, що є одним твердженням, прийнято називати простим або елементарним. Прикладами елементарних висловлювань можуть бути висловлювання 1) і 2).
Висловлювання, що виходять з елементарних за допомогою граматичних зв'язок «не», «і», «або», «якщо.... то...», «тоді й тільки тоді», прийнято називати складними чи складовими.
Так, висловлювання 3) виходить із простого висловлювання «Сокіл - риба» за допомогою заперечення «не», висловлювання 4) утворено з елементарних висловлювань «Число 6 ділиться на 2», «Число 6 ділиться на З», з'єднаних союзом «і».
Аналогічно складні висловлювання можуть бути отримані із простих висловлювань за допомогою граматичних зв'язок «або», «тоді й тільки тоді».
У алгебрі логіки всі висловлювання розглядаються лише з погляду їхнього логічного значення, як від їхнього життєвого змісту відволікаються. Вважається, що кожен вислів або істинно, або хибно і жодне висловлювання не може бути одночасно істинним і хибним.
Елементарні висловлювання позначаються малими літерами латинського алфавіту: х, у, z, ..., а, b, с, ...;справжнє значення висловлювання цифрою 1, а хибне значення – буквою цифрою 0.
Якщо висловлювання аістинно, то писатимемо а = 1, а якщо ахибно, то а = 0.

Логічні операції над висловлюваннями

Заперечення.

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

Заперечення висловлювання хпозначається та читається «не х»або «невірно, що х».

Логічні значення висловлювання можна описати з допомогою таблиці.

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

Наприклад, для висловлювання Путін президент Росії запереченням буде вислів Путін не президент Росії, а подвійним запереченням буде вислів Невірно, що Путін не президент Росії.

Кон'юнкція.

Кон'юнкцією (логічним множенням) двох висловлювань х і уназивається новий вислів, який вважається істинним, якщо обидва висловлювання х і уістинні, і хибним, якщо хоча б одне з них хибне.
Кон'юнкція висловлювань х і упозначається символом х&у ( , ху)читається «х і у». Висловлювання х і уназиваються членами кон'юнкції.
Логічні значення кон'юнкції описуються наступною таблицею істинності:

Наприклад, для висловлювань "6 ділиться на 2", "6 ділиться на 3" їх кон'юнкцією буде висловлювання "6 ділиться на 2 і 6 ділиться на 3", яке, очевидно, істинно.

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

Диз'юнкція

Диз'юнкцією (логічним додаванням) двох висловлювань х і уназивається нове висловлювання, яке вважається істинним, якщо хоча б одне з висловлювань х, уістинно, і хибним, якщо вони обидва хибні. Диз'юнкція висловлювань х, упозначається символом "x V у"читається «х чи у». Висловлювання х, уназиваються членами диз'юнкції.
Логічні значення диз'юнкції описуються такою таблицею істинності:

У повсякденній промові союз «або» вживається у різному сенсі: що виключає і не виключає. У алгебрі логіки союз «чи» завжди вживається у сенсі.

Імплікація.

Імплікацією двох висловлювань х і уназивається нове висловлювання, яке вважається хибним, якщо х істинно, а у - хибно, і істинним у всіх інших випадках.
Імплікація висловлювань х, упозначається символом читається «якщо х, то у» або «з них випливає у».Висловлювання хназивають умовою або посилкою, висловлювання у- наслідком чи висновком, висловлювання слідуванням або імплікацією.

Логічні значення операції імплікації описуються такою таблицею істинності:

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

Еквівалентність.

Еквівалентністю двох висловлювань х і уназивається нове висловлювання, яке вважається істинним, коли обидва висловлювання х, уабо одночасно істинні, або одночасно помилкові, і помилковим у всіх інших випадках.

Еквівалентність висловлювань х, упозначається символом, читається «для того, щоб х, необхідно і достатньо, щоб у» або «х тоді і тільки тоді, коли у».Висловлювання х, уназиваються членами еквівалентності.
Логічні значення операції еквівалентності описуються такою таблицею істинності:

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

Практичні завдання

1. Встановити логічну структуру наступних пропозицій та записати їх мовою логіки висловлювань:

• Якщо метал нагрівається, то він плавиться.
• Неправда, що філософські суперечки є нерозв'язними.
• Гроші - продукт стихійного розвитку товарних відносин, а чи не результат домовленості чи будь-якого іншого свідомого акта.

2. Записати логічною формулою такі висловлювання:

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

б) якщо - прямокутний і сторони - рівні, то

3. Перевірити істинність висловлювання:

а якщо, .

б) , якщо, .

в), якщо, .

4. Перевірити істинність висловлювання:

а) Щоб завтра піти на заняття, я маю встати рано. Якщо я сьогодні піду в кіно, то ляжу спати пізно. Якщо ляжу спати пізно, то встану пізно. Отже, або я не піду в кіно або не піду на заняття.

б) Я піду або в кіно, або в басейн. Якщо я піду в кіно, то отримаю естетичну насолоду. Якщо я піду в басейн, то матиму фізичне задоволення. Отже, якщо отримаю фізичне задоволення, то не отримаю естетичного задоволення.

5 . На запитання: Хто з трьох студентів вивчав дискретну математику? отримана вірна відповідь: «Якщо вивчав перший, то вивчав і третій, але неправильно, що вивчав другий, то вивчав і третій». Хто вивчав дискретну математику?

6. Визначте, хто з чотирьох студентів склав іспит, якщо відомо:

якщо перший здав, те й другий здав;

якщо другий здав, то третій здав чи перший не здав;

якщо четвертий не здав, то перший здав, а третій не здав;

якщо четвертий здав, то перший здав.

Контрольні питання

1. Які елементи належать мові логіки?

2. Які засоби встановлення загальнозначущості формули логіки ви знаєте?

Список літератури

Практичні заняття №10-11

Тема програми: Формули алгебри висловлювань.

Властивості

Розглянемо кілька властивостей декартового твору:

1. Якщо A,B- кінцеві множини, то A× B- Кінцеве. І навпаки, якщо одна з множин-множників нескінченна, то і результат їх твору - нескінченна множина.

2. Кількість елементів у декартовому творі дорівнює добутку чисел елементів множин-співмножників (у разі їхньої кінцівки, зрозуміло): | A× B|=|A|⋅|B| .

3. A np ≠(A n) p- у першому випадку доцільно розглянути результат декартового твору як матрицю розмірів 1× np, у другому ж - як матрицю розмірів n× p .

4. Комутативний закон не виконується, т.к. пари елементів результату декартового твору впорядковано: A× B≠B× A .

5. Асоціативний закон не виконується: ( A× B)× C≠A×( B× C) .

6. Має місце дистрибутивність щодо основних операцій на множинах: ( A∗B)× C=(A× C)∗(B× C),∗∈{∩,∪,∖}

11. Поняття висловлювання. Елементарні та складові висловлювання.

Висловлювання- це твердження чи оповідне речення, про яку можна сказати, що воно істинно (І-1) або хибно (Л-0), але не те й інше одночасно.

Наприклад, "Сьогодні йде дощ", "Іванов виконав лабораторну роботу №2 з фізики".

Якщо ми маємо кілька вихідних висловлювань, то їх за допомогою логічних спілок або частинок ми можемо утворювати нові висловлювання, істиннісне значення яких залежить від істиннісних значень вихідних висловлювань і зажадав від конкретних спілок і часток, що у побудові нового висловлювання. Слова та висловлювання «і», «або», «ні», «якщо... , то», «тому», «тоді й тільки тоді» є прикладами таких спілок. Вихідні висловлювання називаються простими , а побудовані з них за допомогою тих чи інших логічних спілок нові висловлювання - складовими . Зрозуміло, слово «прості» ніяк не пов'язані з суттю чи структурою вихідних висловлювань, які можуть бути дуже складними. У цьому контексті слово «простий» є синонімом слова «вихідний». Важливо, що значення істинності простих висловлювань передбачаються відомими чи заданими; у будь-якому разі вони не обговорюються.

Хоча висловлювання типу «Сьогодні не четвер» не складено з двох різних простих висловлювань, для одноманітності конструкції воно також розглядається як складове, оскільки його істиннісне значення визначається істинним значенням іншого висловлювання «Сьогодні четвер»

приклад 2.Наступні висловлювання розглядаються як складові:

Я читаю «Московський комсомолець» і читаю «Комерсант».

Якщо він сказав це, значить, це правильно.

Сонце не є зіркою.

Якщо буде сонячно і температура перевищить 25 0, я приїду поїздом чи автомобілем

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

12. Операції над висловлюваннями.

1. Операція заперечення.

Запереченням висловлювання А (читається «не А», «Невірно, що А»), яке істинно, коли Ахибно і хибно, коли А- Істинно.

Висловлювання, що заперечують одне одного Аі називаються протилежними.

2. Операція кон'юнкції.

Кон'юнкцієювисловлювань Аі Уназивається висловлювання, що позначається А В(читається « Аі У»), справжні значення якого визначаються в тому і лише тому випадку, коли обидва висловлювання Аі Уістинні.

Кон'юнкцію висловлювань називають логічним твором та часто позначають АВ.

Нехай дано висловлювання А– «у березні температура повітря від 0 Сдо + 7 С» та висловлювання У- «У Вітебську йде дощ». Тоді А Вбуде наступною: «у березні температура повітря від 0 Сдо + 7 Сі у Вітебську йде дощ». Ця кон'юнкція буде істинною, якщо будуть висловлювання Аі Уістинними. Якщо ж виявиться, що температура була меншою 0 Сабо у Вітебську не було дощу, то А Вбуде хибною.

3 . Операція диз'юнкції.

диз'юнкцієювисловлювань Аі Уназивається висловлювання А В (Аабо У), яке істинно тоді і тільки тоді, коли хоча б одне з висловлювань істинне і хибне – коли обидва висловлювання хибні.

Диз'юнкцію висловлювань називають також логічною сумою А+В.

Висловлювання « 4<5 або 4=5 » є істинним. Бо висловлювання 4<5 » - Істинне, а вислів « 4=5 » - хибне, то А Вє справжнім висловлюванням « 4 5 ».

4 . Операція імплікації.

Імплікацієювисловлювань Аі Уназивається висловлювання А В(«якщо А, то У», «з Аслід У»), значення якого помилкове тоді і тільки тоді, коли Аістинно, а Упомилково.

В імплікації А Ввисловлювання Аназивають основою,або посилкою, а висловлювання У – наслідком,або висновок.

13. Таблиці істинності висловлювань.

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

Таблиці істинності застосовуються для:

Обчислення істинності складних висловлювань;

встановлення еквівалентності висловлювань;

Визначення тавтологій.

Встановлення істинності складних висловлювань.

приклад 1.Встановити істинність висловлювання · З

Рішення.До складу складного висловлювання входять 3 простих висловлювання: А, У, З. У таблиці заповнюються колонки значеннями (0, 1). Вказуються всі можливі ситуації. Прості висловлювання від складних відокремлюються подвійною вертикальною межею.
При складанні таблиці треба стежити, щоб не переплутати порядок дій; заповнюючи стовпці, слід рухатися “зсередини назовні”, тобто. від елементарних формул до більш складних; стовпець, що заповнюється останнім, містить значення вихідної формули.

А	У	З		А+		· З

З таблиці видно, що це висловлювання істинно лише у разі, коли А=0, В=1, С=1. У решті випадків воно хибне.

14. Рівносильні формули.

Дві формули Аі Уназиваються рівносильними, якщо вони набувають однакових логічних значень при будь-якому наборі значень вхідних у формулу елементарних висловлювань.

Рівносильність позначається знаком «». Для перетворення формул у рівносильні важливу роль відіграють основні рівносильності, що виражають одні логічні операції через інші, рівносильності, що виражають основні закони логіки алгебри.

Для будь-яких формул А, У, Зсправедливі рівносильності.

I. Основні рівносильності

закон ідемпотентності

1-істина

0-брехня

Закон протиріччя

Закон виключеного третього

закон поглинання

формули розщеплення

закон склеювання

ІІ. Рівносильності, що виражають одні логічні операції через інші.

закон де Моргана

ІІІ. Рівносильності, що виражають основні закони логіки алгебри.

комутативний закон

асоціативний закон

дистрибутивний закон

15. Формули логіки висловлювань.

Види формул класичної логіки висловлювань– у логіці висловлювань розрізняють такі види формул:

1. Закони(тотожно-справжні формули) – формули, які за будь-яких інтерпретацій пропозиційних змінних набувають значення «істинно»;

2. Протиріччя(тотожно-хибні формули) – формули, які за будь-яких інтерпретацій пропозиційних змінних набувають значення «хибно»;

3. Здійсненні формули– такі, що набувають значення «істинно»хоча б при одному наборі значень істинності входять до їх складу змінних змінних.

Основні закони класичної логіки висловлювань:

1. Закон тотожності: ;

2. Закон протиріччя: ;

3. Закон виключеного третього: ;

4. Закони комутативності та: , ;

5. Закони дистрибутивності щодо ,і навпаки: , ;

6. Закон видалення істинного члена кон'юнкції: ;

7. Закон видалення хибного члена диз'юнкції: ;

8. Закон контрапозиції: ;

9. Закони взаємовиразності пропозиційних зв'язок: , , , , , .

Процедура розв'язання– метод, що дозволяє кожної формули встановити є вона законом, протиріччям чи здійсненної формулою. Найпоширенішою процедурою розв'язання є метод істиннісних таблиць. Однак він не єдиний. Ефективним методом розв'язності є метод нормальних формдля формул логіки висловлювань. Нормальною формоюФормули логіки висловлювань є форма, яка не містить знака імплікації «». Розрізняють кон'юнктивну та диз'юнктивну нормальні форми. Кон'юнктивна форма містить лише знаки кон'юнкції «». Якщо у формулі, наведеній до кон'юнктивної нормальної форми, зустрічається підформула виду, то вся формула в цьому випадку є протиріччям. Диз'юнктивна форма містить лише знаки диз'юнкції « ». Якщо у формулі, наведеній до диз'юнктивної нормальної форми, зустрічається підформула виду, то вся формула в цьому випадку є законом. У всіх інших випадках формула є здійсненною формулою.

16. Предикати та операції з них. Квантори.

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

Залежно від кількості змінних, які входять у пропозицію, розрізняють одномісні, двомісні, тримісні тощо. предикати, що позначаються відповідно: А( х), В( х, у), С( х, у, z).

Якщо заданий певний предикат, то з ним пов'язані дві множини:

1. Безліч (область) визначення Х, Що складається з усіх значень змінних, при підстановці яких предикат останній звертається у висловлювання. При заданні предикату зазвичай вказують область визначення.

2. Безліч істинності Т,що складається з усіх значень змінних, при підстановці яких у предикат виходить справжнє висловлювання.

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

Над предикатами можна здійснювати самі операції, як і висловлюваннями.

1. Запереченнямпредикату А( х), заданого на множині Х, називається предикат , правдивий при тих значеннях , при яких предикат ( х) звертається у хибне висловлювання, і навпаки.

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

Безліч істинності предикату є доповненням до множини істинності предикату А( х). Позначимо через Т А безліч істинності предикату А( х), а через Т - безліч істинності предикату. Тоді.

2. Кон'юнкцієюпредикатів А( х) і В( хх) В( х хХ, за яких обидва предикати звертаються до справжніх висловлювань.

Безліч істинності кон'юнкції предикатів є перетин множин істинності предикату А( х) В( х). Якщо позначити безліч істинності предикату А(х) через Т А, а безліч істинності предикату В(х) через Т і безліч істинності предикату А(х) В(х) через , то

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

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

4.Імплікацієюпредикатів А( х) і В( х), заданих на множині Х, називається предикат А( х) В( х), який закладений за тих і тих значеннях змінної, у яких перший предикат звертається у справжнє висловлювання, а другий – у хибне.

Безліч істинності імплікації предикатів є об'єднання безлічі істинності предикату ( х) з доповненням до безлічі істинності предикату А ( х), тобто.

5. Еквіваленцієюпредикатів А( х) і В( х), заданих на безлічі Х, називається предикат , який звертається у справжнє висловлювання за всіх тих і лише тих значеннях змінної, у яких обидва предикату звертаються або у справжні висловлювання, чи хибні висловлювання.

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

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

Предикат можна перевести у висловлювання способом підстановки та способом «навішування квантора».

Про числа 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 можна сказати: а) всідані числа прості; б) деякіз цих чисел парні.

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

Якщо з пропозиції «а» прибрати слово «все», та якщо з пропозиції «б» - слово «деякі», отримаємо такі предикати: «дані числа прості», «дані числа непарні».

Слова «всі» та «деякі» називаються кванторами. Слово «квантор» латинського походження і означає «скільки», тобто квантор показує, про скількі (всі або деякі) об'єкти йдеться в тому чи іншому реченні.

Розрізняють два основні види кванторів: квантор спільності та квантор існування.

Терміни «кожний», «будь-який», «кожен» носять назву – квантор загальності.Позначається.

Нехай А ( х) – певний предикат, заданий на множині Х. Під виразом А( х) розумітимемо вислів істинний, коли А( х) істинно для кожного елемента з множини Х, і хибне в іншому випадку.

У прикладі 1 для R 1область визначення: , множина значень - . Для R 2Область визначення: , безліч значень: .

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

У першому випадку вибирають дві взаємно перпендикулярні лінії як горизонтальну і вертикальну осі. На горизонтальній осі відкладають елементи множини Aта через кожну точку проводять вертикальну лінію. На вертикальній осі відкладають елементи множини Bчерез кожну точку проводять горизонтальну лінію. Точки перетину горизонтальних та вертикальних ліній зображують елементи прямого твору

18. Способи завдання бінарних відносин.

Будь-яке підмножина декартового твору A×B називається бінарним ставленням, визначеним на парі множин A і B (латиною «біс» позначає «двічі»). У загальному випадку за аналогією з бінарними можна розглядати і n-арні відносини як упорядковані послідовності елементів, взятих по одному з n множин.

Для позначення бінарного відношення застосовують знак R. Оскільки R- це підмножина множини A×B, можна записати R⊆A×. Якщо ж потрібно зазначити, що (a, b) ∈ R, тобто між елементами a ∈ A та b ∈ B існує відношення R, то пишуть aRb.

Способи завдання бінарних відносин:

1. Це використання правила, згідно з яким вказуються всі елементи, що входять до цього відношення. Замість правила можна навести список елементів заданого відношення шляхом їх безпосереднього перерахування;

2. Табличний, як графів і з допомогою перерізів. Основу табличного способу складає прямокутна система координат, де по одній осі відкладаються елементи однієї множини, за другою - іншою. Перетин координат утворюють точки, що позначають елементи декартового твору.

На (рисунку 1.16) зображено координатну сітку для множин. Точкам перетину трьох вертикальних ліній із шістьма горизонтальними відповідають елементи множини A×B. Кружочками на сітці відзначені елементи відношення aRb, де a ∈ A та b ∈ B, R позначає відношення «ділить».

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

3. Спосіб завдання відносин за допомогою перерізів використовується рідше, тому розглядати його не будемо.

19. Рефлексивність бінарних відносин. приклад.

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

Властивість рефлексивності при заданих відносинах матрицею характеризується тим, що це діагональні елементи матриці дорівнюють 1; при заданих відносинах графом кожен елемент має петлю – дугу (х, х).

Якщо ця умова не виконана для жодного елемента множини, то відношення називається антирефлексивним.

Якщо антирефлексивне відношення задано матрицею, всі діагональні елементи є нульовими. За завдання такого відношення графом кожна вершина не має петлі - немає дуг виду (х, х).

Формально антирефлексивність відносини визначається як: .

Якщо умова рефлексивності виконано задля всіх елементів множини, кажуть, що ставлення нерефлексивно.

©2015-2019 сайт
Усі права належати їх авторам. Цей сайт не претендує на авторства, а надає безкоштовне використання.
Дата створення сторінки: 2016-04-12