Название: Формули Рiвносильнiсть формул Тотожно iстиннi формули
Вид работы: реферат
Рубрика: Астрономия
Размер файла: 19.29 Kb
Скачать файл: referat.me-1885.docx
Краткое описание работы: Реферат на тему: Формули. Рiвносильнiсть формул. Тотожно iстиннi формули Наведемо iндуктивне означення поняття формули логiки предикатiв (предикатної формули або просто формули ) на предметнiй областi M.
Формули Рiвносильнiсть формул Тотожно iстиннi формули
Реферат на тему:
Формули. Рiвносильнiсть формул. Тотожно iстиннi формули
Наведемо iндуктивне означення поняття формули логiки предикатiв (предикатної формули абопросто формули ) на предметнiй областi M .
1. Усi предикати P (x 1 ,x 2 ,...,xn ) на множинi M є формулами. Такi формули називають елементарними , або атомарними .
2. Якщо A i B - формули, то (ØA ), (ØB ), (A ÙB ), (A ÚB ), (A ®B ), (A ~B ) теж є формулами.
3. Якщо A - формула, а x - вiльна змiнна в A , то ("x (A )) i ($x (A )) теж формули.
4. Iнших формул, крiм утворених за правилами 1-3, немає.
Це означення дозволяє твердити, що усi формули алгебри висловлень є формулами логiки предикатiв, оскiльки висловлення - це нульмiснi предикати.
За допомогою наведеного означення неважко також переконатись, що вирази ("x ($y (A (x ,y ))®(B (x )Ú($z (C (x ,z ))))) i ("x ("y (A (x ,y )ÙB (x ))®($y (C (x ,y )))) є формулами логiки предикатiв, а вираз ("x (A (y )®($x (B (x ))))) не є формулою, оскiльки у виразi (A (y )®($x (B (x )))), який є правильною формулою, змiнна x є зв'язаною, тобто не є вiльною змiнною i квантор "x до неї застосувати не можна.
Для зручностi можна запровадити такi умови скорочення кiлькостi дужок у формулах. По-перше, залишимо всi умови скорочення числа дужок, якi було прийнято в алгебрi висловлень, виходячи з прiоритету логiчних операцiй. По-друге, опускатимемо всi зовнiшнi дужки. Вважатимемо, що квантори мають бiльший прiоритет, нiж логiчнi операцiї. Опускатимемо також дужки, що позначають область дiї квантора, якщо остання є елементарною формулою. Нарештi, не писатимемо дужки мiж кванторами, що слiдують один за одним. При цьому виконання таких кванторних операцiй вiдбувається в порядку, зворотньому до їх написання (справа налiво).
Нехай F (x 1 ,x 2 ,...,xn ) - деяка формула логiки предикатiв на множинi M . При логiчнiй (iстинностнiй) iнтерпретацiї формули F можливi такi три основнi ситуації.
1. Iснує набiр значень змiнних, для якого формула F перетворюється на iстинне висловлення. У цьому разi формула F називається виконуваною в областi M .
Якщо для F iснує область M , в якiй F є виконуваною, то формула F називається просто виконуваною .
2. Якщо формула F приймає значення 1 (тобто є виконуваною) для всiх наборiв значень з M , то вона називається тотожно iстинною в M . Формула, тотожно iстинна у будь-яких M , називається тотожно iстинною або логiчно загальнозначущою (скорочено - лзз ).
3. Якщо формула F є невиконуваною в M , то вона називається тотожно хибною в M . Формула, невиконувана в усiх M , називається тотожно хибною , або суперечнiстю .
Приклад 5 .7. Формула $xA (x ,y )®"xA (x ,y ) є виконуваною i вона ж є тотожно iстинною в усiх одноелементних областях M . Формула F (x 1 ,x 2 ,...,xn )ÚØF (x 1 ,x 2 ,...,xn ) тотожно iстинна, а формула F (x 1 ,x 2 ,...,xn )ÙØF (x 1 ,x 2 ,...,xn ) тотожно хибна. Тотожно iстинними будуть формули "xP (x )®P (y ) i P (y )®$xP (x ).
Формули F 1 i F 2 називаються рiвносильними (еквiвалентними ), якщо при всiх можливих пiдстановках значень замiсть їх змiнних вони набувають однакових значень; позначається F 1 = F 2 .
Наприклад, усi тотожно iстиннi (усi тотожно хибнi) формули рiвносильнi мiж собою. Очевидно також, що коли F 1 i F 2 рiвносильнi, то формула F 1 ~F 2 є тотожно iстинною, і навпаки.
Множина тотожно iстинних формул логiки предикатiв є складовою частиною усiх формальних математичних теорiй, тому її дослiдження i опис є важливою задачею математичної логiки. Значення цiєї множини пiдтверджує той факт, що їй, як було зазначено вище, належать усi рiвносильнi спiввiдношення (тотожностi) логiки предикатiв.
Як i в логiцi висловлень постають двi проблеми. Перша - опис або побудова множини всiх тотожно iстинних формул, друга - перевiрка тотожної iстинностi заданої формули логiки предикатiв.
Якщо iснує процедура розв’язання другої з цих проблем, то на її основi можна сформулювати такий тривiальний алгоритм, що породжує шукану множину T тотожно iстинних формул. Послiдовно будуємо всi формули, кожну з них за вiдомою процедурою перевiряємо на тотожну iстиннiсть i вносимо до множини T тi, для яких результат перевiрки є позитивним.
Однак на вiдмiну вiд логiки висловлень, де така процедура iснує i зводиться до обчислення значень даної формули на скiнченнiй множинi значень її параметрiв, у логiцi предикатiв областi визначення предметних i предикатних змiнних формул є, взагалi кажучи, нескiнченними (злiченними або навiть незлiченними).
Метод обчислення значення формули шляхом пiдстановки значень замiсть змiнних i послiдовного виконання вказаних дiй є зручним для встановлення виконуваності заданої формули або доведення нерiвносильностi певних формул. Для цього достатньо пiдiбрати одну вiдповiдну пiдстановку. Застосовувати цей метод можна також, коли предметна область M є скiнченною. Пов’язано це з тим, що для скiнченної множини M = {a 1 ,a 2 ,...,an } кванторнi формули можна перетворити у рiвносильнi їм звичайнi формули логiки висловлень:
"xP (x ) = P (a 1 )ÙP (a 2 )Ù ... ÙP (an ),
$xP (x ) = P (a 1 )ÚP (a 2 )Ú ... ÚP (an ).
Замiнивши усi квантори за допомогою наведених спiввiдношень, будь-яку формулу логiки предикатiв можна перетворити у рiвносильну пропозицiйну форму або формулу логiки висловлень. Iстиннiсть останньої на скiнченнiй множинi M перевiряється за скiнченну кiлькiсть пiдстановок i обчислень.
Для доведення ж рiвносильностi предикатних формул, що заданi на нескiнченних предметних областях, прямий перебiр виключається i доводиться використовувати рiзнi опосередкованi методи.
Наприклад, вище шляхом простих мiркувань було доведено рiвносильнiсть формул, що описує переставнiсть однойменних кванторiв у двомiсних предикатах, тобто доведено iстиннiсть формул
"x "yA (x ,y )~"y "xA (x ,y ) i $x $yA (x ,y )~$y $xA (x ,y ).
Аналогiчними мiркуваннями доведемо рiвносильнiсть, що описує дистрибутивнiсть квантора "x вiдносно кон’юнêцiї:
"x (A (x )ÙB (x )) = "xA (x )Ù"xB (x ).
Нехай лiва частина цього співвiдношення є iстинною для деяких предикатiв A i B . Тодi для будь-якого a ÎM iстинною буде кон’юнкцiя A (a )ÙB (a ), тому A (a ) i B (a ) одночасно iстиннi для довiльних a , отже, формула "xA (x )Ù"xB (x ) є iстинною. Якщо ж лiва частина хибна, то це означає, що для деякого a ÎM хибним є або A (a ), або B (a ). Тому хибним буде або "xA (x ), або "xB (x ), а отже, хибною буде i права частина.
Подiбним методом можна довести дистрибутивнiсть квантора $x вiдносно диз’юнкцiї:
$x (A (x )ÚB (x )) = $xA (x )Ú$xB (x ).
У той же час аналогiчнi простi мiркування дозволяють переконатись, що квантори "x i $x є, взагалi кажучи, недистрибутивними вiдносно диз’юнкцiї i кон’юнкцiї вiдповiдно. Насправдi, iстинними є лише такi iмплiкацiї:
"xA (x )Ú"xB (x )®"x (A (x )ÚB (x )),
$x (A (x )ÙB (x ))®$xA (x )Ù$xB (x ).
Якщо один з предикатiв A (x ) чи B (x ) є тотожно iстинним, то лiва i права частини першої iмплiкацiї одночасно будуть iстинними. Якщо ж iснуватимуть такi значення a ,b ÎM , що A (a ) i B (b ) є хибними, то лiва частина буде хибною, а права - може бути хибною або iстинною. Для її iстинностi достатньо, щоб для кожного a ÎM iстинним був принаймнi один з предикатiв. Це означає, що знак iмплiкацiї ® не можна замiнити на знак еквiвалентностi ~, отже, лiва i права частини першої iмплiкацiї не є рiвносильними.
Пропонуємо самостiйно проаналiзувати другу iмплiкацiю i довести її iстиннiсть.
Доведемо ще одне корисне i популярне в логiцi i математицi рiвносильне спiввiдношення: Ø($xP (x )) = "x (ØP (x )).
Нехай для деякого предиката P i предметної областi M лiва частина iстинна. Тодi не iснує a ÎM , для якого P (a ) iстинно. Отже, для всiх a ÎM P (a ) хибне, тобто ØP (a ) iстинно. Таким чином, права частина є iстинною. Якщо ж лiва частина хибна, то iснує b ÎM , для якого P (b ) iстинно, тобто ØP (b ) - хибне. Отже, права частина буде також хибною.
Аналогiчно доводиться рiвносильнiсть
Ø("xP (x )) = $x (ØP (x )).
Наведемо без доведень ще декiлька важливих рiвносильних спiввiдношень. Нехай B предикатна формула, що не мiстить вiльних входжень змiнної x , тодi справедливi такi рiвносильностi:
"x (A (x )ÚB ) = "xA (x )ÚB , B ®"xA (x ) = "x (B ®A (x )),
$x (A (x )ÚB ) = $xA (x )ÚB , B ®$xA (x ) = $x (B ®A (x )),
"x (A (x )ÙB ) = "xA (x )ÙB , "xA (x )®B = $x (A (x )®B ),
$x (A (x )ÙB ) = $xA (x )ÙB , $x A (x )®B = "x (A (x )®B ).
Цi спiввiдношення означають, що формулу, яка не мiстить вiльних входжень x , можна виносити за межi областi дiї квантора, що зв’язує x . З iншого боку цi ж рiвносильностi дозволяють включати або вносити вiдповiдну формулу B до областi дiї квантора за змiнною x , вiд якої B не залежить.
Можливiсть проведення зазначених рiвносильних перетворень для предикатних формул дозволяє означити в логiцi предикатiв поняття певної канонiчної або нормальної форми.
Формула, що має вигляд Q 1 x 1 Q 2 x 2 ...Qn xn F , де Q 1 ,Q 2 ,...,Qn - квантори, а F формула, яка не мiстить кванторiв i є областю дiї всiх n кванторiв, називається випередженою (пренексною ) нормальною формулою , або формулою у випередженiй формi .
Формула, яка знаходиться в пренекснiй формi i рiвносильна формулi P , називається випередженою (пренексною ) формою P .
Використовуючи останнi вісім рiвносильних спiввiдношеннь та деякi iншi, iндукцiєю за числом логiчних операцiй можна довести, що для кожної формули P логiки предикатiв iснує випереджена нормальна форма P .
Похожие работы
-
Бульові функції
Реферат на тему: 1. Алгебри бульових виразів і бульових функцій 7.1.1. Основні поняття Множину {0, 1} позначимо літерою B. Множину всіх можливих послідовностей з 0 і 1 – Bn. Такі послідовності за традицією будемо називати наборами або векторами довжини n. Очевидно, Bn містить 2n елементів. Значення 0 і 1 називаються протилежними одне до одного.
-
Степеневі ряди Теорема Абеля Область збіжності степеневого ряду
Міністерство освіти і науки України Київський державний торговельно-економічний університет Коломийський економіко-правовий коледж Реферат З дисципліни „Вища математика”
-
Принципи побудови формальних теорій
Реферат на тему: Принципи побудови формальних теорій Математична логіка як самостійний розділ сучасної математики сформувався відносно нещодавно - на рубежі дев’ятнадцятого і двадцятого століть. Виникнення і швидкий розвиток математичної логіки були пов’язані з так званою кризою основ (засад) математики, одним з проявів якої є відомі парадокси або антиномії канторівської теорії множин.
-
Редактор формул буквиця колонки границя і заливка Опис редактора формул використання буквиці
Лабораторна робота №10 Тема: Робота у редакторі формул. Колонки. Границя і заливка. Буквиця. Мета: Навчитися створювати математичні формули, використовувати підпункти: колонка, границя і заливка, буквиця для форматування документу та закріпити знання по пункті головного меню “Формат”.
-
Інтегрування з допомогою заміни змінної Інтегрування частинами
Пошукова робота на тему: Інтегрування з допомогою заміни змінної. Інтегрування частинами. План Інтегрування частинами Інтегрування часток Заміна змінної
-
Редагування формул у WORD
Редагування формул WORD Математичні об’єкти редагуються як безпосередньо в тексті, так і в спеціальному діалоговому вікні. Перед редагуванням формули в тексті її виділяють, клацнувши на ній лівою клавішею миші. Потім за командою Правка — Об’єкт Equation — Изменить або подвійним клацанням лівою клавішею миші на формулі активізується панель “Формула” і здійснюється редагування.
-
Похідна суми добутку та частки з наведеними прикладами
Реферат на тему: “ Похідна суми, добутку та частки з наведеними прикладами”. Теорема: Якщо функції u(x) і n(x) мають похідні у всіх точках інтервалу ]a; b[, то
-
Числення висловлень і алгебра висловлень Основні проблеми числення висловлень
Реферат на тему: Числення висловлень і алгебра висловлень. Основні проблеми числення висловлень. Довільну формулу F числення висловлень можна змістовно інтерпретувати як складене висловлення, істинність або хибність якого залежить від істинності елементарних висловлень, що до нього входять.
-
Команди меню Microsoft Word
Реферат на тему: Команди меню «Файл» Команди меню «Файл» дозволяють розмістити та поновити формули в документі, а також завершити роботу з редактором формул.
-
Способи визначення дальності стрільби і застосування формули тисячної
Реферат на тему: СПОСОБИ ВИЗНАЧЕННЯ ДАЛЬНОСТІ СТРІЛЬБИ І ЗАСТОСУВАННЯ ФОРМУЛИ ТИСЯЧНОЇ У стрілецькій практиці для вимірювання кутів користуються не градусами, а поділками кутоміра — тисячними. Тисячною називається центральний кут, що спирається на дугу, яка дорівнює 1/6000 довжини кола.