Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Реферат: Формули Рiвносильнiсть формул Тотожно iстиннi формули

Название: Формули Рiвносильнiсть формул Тотожно iстиннi формули
Раздел: Рефераты по астрономии
Тип: реферат Добавлен 03:51:27 21 января 2011 Похожие работы
Просмотров: 9 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

Реферат на тему:

Формули. Р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 ,yB (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 (xP (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 1P (a 2 )Ù ... ÙP (an ),

$xP (x ) = P (a 1P (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 (xB (x )) = "xA (x )Ù"xB (x ).

Нехай лiва частина цього співвiдношення є iстинною для деяких предикатiв A i B . Тодi для будь-якого a ÎM iстинною буде кон’юнкцiя A (aB (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 (xB (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 (xB (x )),

$x (A (xB (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 )) = "xP (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 )) = $xP (x )).

Наведемо без доведень ще декiлька важливих рiвносильних спiввiдношень. Нехай B предикатна формула, що не мiстить вiльних входжень змiнної x , тодi справедливi такi рiвносильностi:

"x (A (xB ) = "xA (xB , B ®"xA (x ) = "x (B ®A (x )),

$x (A (xB ) = $xA (xB , B ®$xA (x ) = $x (B ®A (x )),

"x (A (xB ) = "xA (xB , "xA (xB = $x (A (xB ),

$x (A (xB ) = $xA (xB , $x A (xB = "x (A (xB ).

Ц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 .

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений08:49:45 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
12:05:59 29 ноября 2015

Работы, похожие на Реферат: Формули Рiвносильнiсть формул Тотожно iстиннi формули

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(150451)
Комментарии (1831)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru