Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 26
Текст из файла (страница 26)
2.14). Коэффициент связности мографа (',~, определяющего сокращенную ДНФ функции у(х), хт, хз), равен 1,25: 2+2+2+2+1+3+2+5+1+4+3+3 2 12 — 1, 25. Аналогично вычисляем коэффициенты связности мографов, определяющих тупиковые ДНФ функции у(х), хз, хз). Мажорих)(с, 1) Рующая функция 7(х), хз, хз), определяемая первой тупиковой ДНФ, имеет вид Ут1(Х1, Х2, ХЗ) /т1ХЗ Ч )т1ХЗХЗ Ч )т)хт Ч Д) О Ъ 2 1 Ъ е 6 е Чу1 о 2Ч~~ 1 2Чу2 2 2 т1 1 3 т1 1 3 т1Х1 3' е е ее Коэффициент связности К„(бф) мографа Смд (рис.
2.15), определяющего функцию ут1(х1, хз, хз), равен 1, 18: ))~ 2+2+2+1+2+1+5+2+3+3+3 К-(~т1)— 2. 11 Ъ Мажорируюшая функция у(х1, Х2, хз), определяемая второй тупиковой ДНФ, имеет вид о етт(хь хз, хз) = этзхзЧутзхзхзЧ) ЗхтЧ е Ь е Ч ~~ х'х ~Ч ~~ х'х'Ч Д,х,'х,', т2 1 3 т2 1 3 т2 1 3 ~ е' е ее 143 142 Гл. 2. Мввгемвогическая логика 12 9 Исчисление предикаюов и соответствующий ей мограф 0~2 ~(рис.
2.16) имеет коэффициент связности, равный 1, 18: ы 2+2+2+1+2'+2+5+1+3+3+3 (~ 2)— 2. 11 — 1, 18. Полученные тупиковые ДНФ функции 7(хг, хг, хз) имеют равные сложности. 9 2.9. Исчисление преднкатов Исчисления высказываний недостаточна для задания более сложных логических рассуждений. По существу й-значная логика позволяет определить наличие того или иного свойства на конечном множестве элементов; в случае бесконечных множеств для установления определенного свойства у рассматриваемого абстрактного понятия необходимо введение функций, аргументы которых пробегают бесконечное число значений во множестве М. Функция Р, принимающая одно из значений, О или 1, аргументы которой пробегают значение из произвольного множества М, называетсн предикагпом Р в предметной области М.
Число аргументов предиката Р(хг, хг,..., х„) называется его порядком. Предикат Р(хы хг, ..., х„) определяет и-арное отношение В в М: если Р(хг, хг, ..., х„') = 1, то (хг, хг, ..., х„') находятся в отношении В, определяемом этим предикатом, и если Р(х"„х', ... ..., х„') = О, то эти элементы не находятся в отношении В, т.
е. (х1 х2 х ) г В Для упрощения структуры сложных логических рассуждений введем специальные обозначения для некоторых часто встречающихся выражений. Условимся обозначать выражение "для всякого элемента х б М свойство В выполнено" как (Чх Е М)(В(х) = = 1), а выражение "существует по крайней мере один элемент х Е М, обладающий свойством В" — как (Бх Е М)(В(х) = 1). В выражениях (Чх б М)(В(х) = 1) и (Зх б М)(В(х) = 1) обозначения Чх и 3х будем соответственно называть кванпгором всеобщноспги и кванпгором сущеспгвования. Определим индуктивно формулу исчисления предикатов аналогично определению формулы исчисления высказываний.
Будем использовать запятые, скобки, символы исчисления высказываний, предметные переменные хг, хг,... (переменные, принимающие значения из предметной области), предметные константы аг, аг, ..., предикатные буквы Рг, Рг, ... и функциональные буквы гы У2~ Определим понятие герма и элементарной формулы. Определение пгерма: 1) всякая предметная переменная или предметная константа — терм; 2) если У вЂ” функциональная буква и пг пг Π— термы то Лг1ы 212, ..., и„) — теРм; 3) любое выражение, полученное многократным повторением правил 1), 2), является термам.
Если Р— преднкатная буква, а пг, пг, ..., гг„— термы, то РЯм пг, ..., 21„) — элементарная формула. Определение формулы: 1) всякая элементарная формула является формулой; 2) если А и  — формулы и х — предметная переменная, то каждое из выражений А о В (о — связка исчисления высказываний) н (Чх б М)(А(х)) является формулой; 3) любое выражение, полученное многократным использованием правил 1), 2), является формулой.
В выражении (Чх е М)(А(х)) формула А(х) называется обласпгью дейсшвия квантора Чх. Предмепгная переменная, входящая в формулу, называется свободной, если она не следует непосредственно за квантором и не входит в область действия квантора по этой переменной; все другие переменные, входящие в формулу, называются связанными.
В пределе всякая формула без свободных переменных (замкнутая формула) является высказыванием, которое истинно или ложно, а всякая формула со свободными переменными задает некоторое отношение в предметной области, которую иногда называют обласпгью инпгерпретации. Это отношение может быть истинно или ложно в зависимости от значений свободных переменных.
В определении формулы в числе основных символов запись Зх можно заменить на Чх(А(х)). Квантор всеобщности можно рассматривать как обобщение конъюнкции. Если предметная область конечна и состоит из элементов гпм пгг,..., гп„, то формула (Чх)(Р(х)) равносильна коньюнкции Р(пгг) ЙР(пгг) Й...ЙР(гп„), а квантор существования можно рассматривать как обобщение дизъюнкции, при этом записи (Зх) (Р(х)) и Р(пгг) Ч Р(гпг) Ч... Ч Р(т„) равносильны. Для бесконечных предметных областей кванторы играют роль бесконечных дизъюнкций и конъюнкций. Каждая формула Р(Р1, Рг, ..., Р, хг, хг, ..., х„) в исчислении предикатов задает оператор, перерабатывающий систему предикатов Рг, Рг, ..., Р в предикат Р от аргументов хг, хг, ...
..., х„, где все эти переменные в формуле являются свободными. Две формулы, Р,(Рг Рг,, Р, хг, хг, ..., х„) и Рь(Ры Рг ..., Р, хм хг,..., х„), которые задают один и тот же оператор, перерабатывающий систему предикатов Рг, Рг, ..., Р в преднкат Р (хм хг, ..., х„), будем называть эквиваленпгными и обозначать Рь — Рь ° $2.10.
Теория тпрасс 145 Гп. 2. Математическая логика 144 Переход от формулы Г к ее эквивалентной форме будем назы- вать, как н в исчислении высказываний, пюждественным пре- образованием. Основываясь на введенных понятиях, можно доказать следую- щие четыре тождества: тождестпва двойственностпи (Зх)(Р(х)) = (Чх)(Р(х)), (Чх)(Р(х)) = (Зх)(Р(х)); пюждестпва длл к-операций (т. е. для конъюнкции и кван- тара всеобщности) (Чх)(Ря(х) Л Р,(х)) = (Чх)(Ря(х) Л (Ух)Р,(х)), (Чх)(Чу) (Р(х, у)) = (Чу)(Чх) (Р(х, у)); тождестпва для а-операций (т.
е. для дизъюнкцни н квантора существования) (ЗХ)(Р.(Х) Ч Ра(Х)) = (ЗХ)(Ря(Х) Ч (ЗХ)Г,(Х)), (Зх)(Зу) (Р(х, у)) = (Зу)(Зх) (Г(х, у)); тпождестпво вынесения константпы (Ех)(Ря о Гя(х)) = Р, о (Ех)(Гь(х)), где (Ех) = (Зх), (Чх); о = Л, Ч; Р— подформула, не содержащая связанную предметную переменную х, которая в дальнейшем будет называться констпантой отпносительно квантпора (Ех). При вынесении константы нз области определения квантора существования подкванторное выражение предварительно приво- дят к виду дизъюнкции конъюнкцией; при вынесении константы из области определения квантора всеобщности выражение приво- дят к виду конъюнкции.
Рассмотрим, например, вынесение константы С(у): (Чх) ((Р(х) ь С(у)) Ч (Н(х) о С(у))) = =)т*)(т)*)ла(ранчо) ~Га[рц) =~щ)т)*)лог)~ Ч (Н(х) Л С(у))) = (Чх) (С(у) Л Н(х) Ч Р(х)) = = (Чх) (С(у) Л (Н(х) -+ Г(х))) = (С(у)) Л (Чх) (Н(х) -+ Р(х)). В рассматриваемом исчислении кванторы применены только по предметным переменным. Формулы будут более выразитель- ными, если наряду с кванторамн по предметным переменным ис- пользовать и квантпоры по предикатпным переменным. Исчисление, в котором применяются только кванторы по пред- метным переменным, называется узким исчислением предика- тов; последнее можно преобразовать в раситиренное исчисление предикатов, добавив кванторы по предикатным переменным. Определение формулы в расширенном исчислении предикатов аналогично ее определению в узком исчислении; разница состоит в том, что в п.
2) определения формулы переменная х может быть как предметной, так и предикатной. Тождества двойственности и-, ст-оцераций и вынесение константы в расширенном исчислении предикатов тоже справедливы. Рассмотрим вопрос выводимости в исчислении предикатов. Расширим систему аксиом некоторого исчисления высказываний, включенного в узкое исчисление предикатов, следующими аксиомами: (Чх)(С(х) -+ С(у)); Н(у) — 1 (Зх)Н(х). Смысл этих аксиом следующий: если предикзт С(х) нстинен дпн любого х, то он истинен и для любого у, и если предикат Н(у) истинен для какого-нибудь у, то существует такой х, что Н(х) истинен. В узком исчислении предикатов два правила вывода (подстановки и заключения) исчисления высказываний дополняют еще тремя правилами.
Правило длл Ч: если 1от -+ утз выводима и в уг нет х в качестве свободной переменной, а в ~рз переменная х содержится в виде свободной переменной, то формула утг -+ Ч(х)утз также выводима. Лравило длл 3: если сот — т 1оз выводима и х содержится в качестве свободной переменной в ~рт и не содержится в качестве свободной пеРеменной стю то фоРмУла 3(х)1от -+ Ут также выводима. Правило переименования связанных переменных: если 1от— выводимая формула и в утт имеется квантер всеобщности нлн квантор существования, то одна связанная переменная в етг может быть заменена другой связанной переменной одновременно во ,всех областях действия квантора и в самом кванторе; полученная формула также выводима. $2.10.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
