Математическая логика. Шапорев С.Д (1019113), страница 21
Текст из файла (страница 21)
29 10. Формула А = х-+ (х-з у) задана на набарак а) (1,0) н б) (0,1). Вывести формулу А или ее отрицания из соответствующих множеств Г, =(х у~и ! з =~ У)з. 2.9.11. С помощью алгоритма Квайна проверить тождественную истинность следующих формул: а) (А-з В) — з(Вч А); б) (А ч В)-ь ((А л В)ч (В л А)); .>! ° Т! ): г) АчВ-+(Сяч А). 2.9.12. Используя алгоритм редукции, проверить тождественную истинность следующих формул: а) (А л  — ь С)-+ (А — ь (В -ь С)); б) 4 — ь (А, — > ..
— з (А„, — ь (А„— ь В ч В))..); в) (А-зВ)л(А-ьВ) — ь А. 2.9.13. С помощью алгоритма Квайна и алгоритма редукции доккмть тождественную истинность аксиом исчислении высказываний. 2.9.14. Метолом резолюций проверить следующие соотношения. а) (Ач С,Сь В, — ь А)-А-+ (В-ч С); Гв Ви «в 6) ' А ч С ь В, С вЂ” о А ч В ВС вЂ” э А ч В)5 —  — э С; в) )С,Ач В~(-( — + С)-ь А. 2,9А5.
Проверить нв противоречивость множества хорновских дизыоикптв: а) ))АчВчСчЗ,В,АчВчС,С,Вч х)1; б) ~4л В -+С,А„В,С); в) ~ Оч Е,ЕчЕ,С,)),А,Г) Глава 3 Логика предикатов 8.1. Определение предикатов И логические операции над ними В исчислении высказываний изучались логические отношения, составленные иэ простых высказываний и принимающие только двв зиа ~сиия 0 или 1 е помощью операций л.
щ, ->, г-э . Однако для т алания более сложных лащческих рассуждений исчисления высказываний недостаче ~но В шобой й\начной логике чгжгно определить н шичнс ~о~ о плп иного свойства ~ в ко печном множестве элсчентов, в случае же бесконечных множеств необхолиио введение функций, аргументы которых пробегазот бесконечное чисяо з~ ~ачений на множестве г>я.
Все вмсказывания, используемые до сих пор, рассматривались как нераздельные целые и только с ~очки зрения их истинности или лоэкности. Струкзура высказь|ваний и их содержание ипюрнровались. Однако, очевидно, что иа практике используются заклЮчсния, зависящие как от струкгуры, так и от :сдержанна используемых в них льюказываний Не всакие высказывания и ие иобы го~ич кис рассуягдения мщут быт вписаны иа языке исчисления высказываний В некоторых слу ~аях высказывания касаютс» свойств объектов шти отношений между объектаьги.
Кротге нио, необходимо иметь воэможносгь утверждать, что любые или какие-то абъекты обладают определенными слойствами или находятся в некоторых Шношениях. Поэтому следует расширять логик> высказываний и построить такую лог нчсжую систему, в рамках кошроц мо:кно было бы нсследоьать струю уру н содержание тех высказываний, которые в рамках алгебры еысказывяг~ий о ~иза- аись бы элементарными Улкой логической системой является толща лреоилагное, а алгебра «ысказыщиий — ее составной ~асс ыо.
Почимо зтсчеитарцых высказываний в логике Ча ьэ. Ыегеяа ичеся »логика предикатов рассматриваются высказывания, отнесенные к предмету, т. е, высказывания расчленяются на субъект и предикат. Субьекги — это то, о чем что-то утверждается, »реди»нег — это то, что утверждается о субъекте. Логи- «а предикатов — это расширение логики высказываний за счет использования предикатое в роли логических функций. Одноместным лредикатом Р(х) называется произвольнвя функци» пере ценного х, определенная на множестве М и принимающая значени» из множества (0,1).
Множество М, на котором определен предикат Р(х), назывзется предмело лой областью или облсстью определения предвкатс. Множество всех х б м, при ко горых Р(х) = 1, называшхя миожестаом иститнюти предиката Р(х): !р- — (д)хнМ,Р(х)=1). Предикат Р(х), определенный на множестве М, называетск тождестеелло «стиияым, если 1г = М, и тождественно ложным, если 1г =6. Булсаа функция однородна е том смысле, что для нее область значений функции и область изменений аргуиента по типу одна и та же в логическая(либо истина, либо ложь).
Для предикатоа же область значений функнии — логическая, а область изменения аргументов — предметная. Обобщение понятия одноме. стный предикат — понятие многоместного преднката, с помощью которого вырююгютс» отиошеии» мюкду предметаьзи. и-местным пред»лотом называется всякая функция л переменных (г(х„хз,...,х„), определеиншг на множестве М =М, хМ, х ..хМ. (декартово произведение) н принимающая на этом множестве одно из двух значений.' "истина" или "ложь", т. е. п-местный предикат (с(хы хз,..., х„) есть функци» Д: М вЂ” э В, где М вЂ” произвольное множество, а В = (О,1).
Высюшывани» можно считать иульместными цредикатами. Говориь, что предикат Р(х) является следствием средиката 1с(х) (Д(х)-э Р(х)),если! С 1г, и нредикапя Р(х) и Д(х) равносильны (Р(х)< э Я(х)) если 1о !г Так как предикаты принимают два значения 0 и 1, то к ним применимы исе операции логики высказываний кояьюяадией двух преднкатоа Р(х) и (г(х) называется новый преднкат Р(х)л(х(х), который принимает значение "истина" при тех и только тех Рлаю 3 лсглкв пр диявюв 143 значениях х н М, при которыя юяглый из прсдикатоь принимает значение "истина". и принимает значение "лохгь" во всех остаоьпых случаяч. Очевидно, что областью истинности прсдикатв Р(х)г 0(х ) является 1о гт 1„ . ))ючгогзхцгмй лвук прсдикатов Р(х) и )2(х) нюываегся новый предиют Р(х) и й(х), который принимает значение "ложь" при тех и июыю тех значениях хи М, при кОторых юокаый из предикагов принимает значение "ложь", и прпнимаегзоачение "истина" во всех остальных случаях.
Ясно, что )о ~ з 1р Отрицанием прсдиката Р(х) называется новый преликат Р(г), который приинмаег значение "истина" при всех значения х и М, при которых Р(х) принимает значение "ложь" и наоборот.Здесь очевидно, 1а = М ! 1 Имллцха!нсн Р(х) и й(т) называется новый прсдпкат Р(х) — г фх), который является ложным при тех и только тех значениях т и М, при которых одновременно Р(я) принимает значюпю "нсзнца", а фх) — значение "лозю,", и принимает истинное значение во всех остальных случаях. Пример !. а) Лупа есть спутник Вспергя — ло:кное высказывание, не являюнзесся преднкатам, т к.
в нем нет аргумента — переменного я: б) З.ь()70 0— ~зГ!О > !50 — тоже самое; в) х . Зз 42 =0 — прсликат Здесь хн М = Я, 1 =( — 2,— !) Пример 2. На мноззгестве М=(3,4,5,6,7,8) заданы два предикага Р(х): "х — простое число", й(х): "х — нечетное число". Составгпь го таблицы истинности (см.табл,3.!.!). Равносильны ли предикаты Р)х) и )3(х) намножествах Ь= (234.5678) К =(34567,89)1 Улгииця 3,1,1 Очевидно, что )г =(3,5,7) 10 =(3,5, 7) Таким образом, на множестве М Р(х)=й(х). На Е и К предикаты не равносильны, ибо на Ь, Чаем!.
Маг м шчеехаялогмм г44 например, 2 — простое число и четное, а иа К 9 — нечетное, на составное число. Пример 3. Исследовать, ивлаетсв ли один из двух данных предикатов Р(х, у) и ! з(х, у) следствием другого, если Р(ху)=РГх.,~» =15) Д(х,У)= (Ч!зу =15~, =(- у„ Рнс, 3.! Рис. 3.2 Найдем области определение обоих прсдикатов и изобразим их на рис. 3.1 и 3.2. рнао 3. Логика пнвднквтсв М ((х, У)н В'уУ /(х>б,у>0)м(х<0, у<0)~' Области определения обоих преднкатов на рисунках заштрихованы. следовательно, 1р с уо, т.е. Р(х,У)ем»(х,У) и пРедикат !»(х,У) ввляется следешием предиката Р(х,у). 2 Пример 4. Найти область истинности преликата х — у >0 н изобразить на плоскости. »!еравенство, составляющее исходный преднкат, отраничивает часть плоскости, заключенной между ветвями параболы х = у (р»»с. 3 32 з Р с.зл пример 5.
на мно»кестве М =(»,2,3,...,20) заланы предика» ы А(х) "з не делится на 5", В(х) "х — четное число", С(х): ".т — число простое", О(х): "х кратно трем". Найти мно»кества истинности предикатов А(х)л В(х)п О(х), А(х)н В(х), 23(х) » С(х). !. А(х)п В(х)п Р(х)=! х не делится на 5 и х — четное число и .» кратно трем!=! х не делится на 5 и х лел»псл па 6! Действщсльио, !р — — (б,! 2Л8), 2. А(х)н В(х)=! х не дел»пса на 5 или х - — четное число».
2„= М ! (5,! 5). 3. О(х) — » С(х)= О(х)и С(х)= (х не кратно трем нли х — непростое число!. Здесь рассуждения слоя»нее, однако, если перебрать все злеме»пы множеспм М, то ле» ко установить, 'по 1 „= М ! (3). ЧастЫ Ыагемвгич ся логика 3.2. Кеанторные операции Фуикционаяьная природа предиката влечет за собой введение еще одного паняти» вЂ” «аллюорп Кеанторные операции можно рассматривать «ак обобгцение операций конъюнкции и дизьюнкцин в случае бесконечных областей. Рассмотрим это подробнее. Пусть дан Р(х) — одноместный предикат. Если ли М, то Р(а) — высказывание.
Здесь как в обычной функции одного переменного при фиксации аргумента функции превращается в число. В логике предикатов существуют еще две особые операции, которые превращают одноместный предикат в высказывание, т. е, связывают аргумент предиката. П Кятгтор ясяобщиослш Чг.
пусть Р(х) — предикат, хц м . под выражением зУхР(х) понимают вьь сказывание, истинное, если Р(х) истинно для камлота элемента хц М, и ложное в противном случае. Символ Ч называется келюлорои есеобгчлосюи (ац — всякийф Соотвеютвующее ему словесное выражение звучит такг "ддя всякого х Р(х) истинно". Переменная х в предикатс Р(х) называется сеобадггой г х любое из МЕ в высказывании зУхР(х) переменную х называют сеюллиод переменной.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
