В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 15
Текст из файла (страница 15)
Из теоремы 1.13 следует, что исчис- ление высказываний есть полная акснонатическая теория. Формальную аксиоматическую теорию называют непротиво- речивой, если нс существует формулы А такой, что олновремен. но выводимы формулы А и )Л. Теорема 1.16, Исчпслгииг высжимэпний непротиворечиво.
Действительно, согласно теореме 1.12 всякая выводимая формула тождественно-истинна. Отрицание этой формулы не является тождественно-истинной формулой. Следовательно, ня~ для наной формулы А невозможно, чтобы одновременно 1- А и) 1--! А. Наряду с полнотой аксиоматичсской теорнк в широком' смысло расснатривают сс полноту в узком смысле. Формаль- ную аксиоматическую теорию называют полкой а узком сммслг;, если добавление лкбой иеаыводнмой формулы в качестве схс-(' мы аксиом грвводит к противоречивой теории.
Теорема 1ЛО, Игчпслгииг эыскпзмлалий полно в узкои! смысле. Пусть Š— произвольная невыводимая формула (согласно) теореме 1.16 в качестве Е можно взять любую не тождественно( истинную формулу], Хь ..., Մ— список ее переменных, (зь ..., е ) — такаи опенка спиеиа переменных, на которо формула Е принимает ложное значение (т. е. 0).
Пусть такж А ш А. если з, 1; -! (А ш А), сели ы = О, в.= ( где Л вЂ” произвольная формула. Тогда формула Е(Вь ..,, В будет тождественно-ложной. Рассмотрим исчисление, в котором к схемам акгиом А) — А1 в качестве сще одной схемы аксиом добавлена формула Е Л4. Е(Ль..., Л ).
Выводимость в этом исчислении обозначим символом Поскольку Е(Вь, В ) получена но схеме А4, то 1- Е(Вь... г 70 В„). Пусть С вЂ” произвольная формула. Тогда Р(Вь..., В ] ш ш С вЂ” тождественно-истинная формула в силу свойств нмплнкаихи. Сзсааватезьпо, (-Г(Вь ..., В )шС, з значит, ! — Р(Вг, ..., В„) шС. Прнмегшв правила зг. р., получим, что (- С. Если виесга формулы С рассмогреш бюрмулу -! С, то также получим, что ! — -! С, т.
е. расширенвзи теория оказалась противо речивоб. Ео всякой формальной теорип возникает вопрос о независп. носта ее аксиом, т. е. вопрос о том, можно ли какую-нибудь эконому вывести пз осталькых, применяя правила вывода даннсб «петен». Оказываеюя, что система аксиом А! — ЛЗ исчисления высааэыванмй независима. Устшимнм независимость аксиом» ЛЗ от остальных. Булем считать, что переменные принимают зиа. чеиия пз множества (е, Ь). Операции ! и ш зададим табл.
1.)7 н !. )8 соответственно. Лшно проверить, что аксиомы Л! н А2 прн ганой интерпре. таш:и примут эпачеяие а. Из определения ш вытенает, что применение прввнла вьпюпа ш. р. к формулам, тожлесгвснно. рамкам м дает формулу, также тождественно.равную а. Следе.
вателыиь формулы, выводимые нз аксиом А! и А2 па правилу м. р., тождественно-равны о. С друшй стороны, аксиома АЗ ( -)В ш -! Л) ш ((-! В ш Л) ш В) ие равна тождественно а, так как, например, прн Л = а, В Ь принимает значение Ь. Можно установить независимость каждой из аксиом А! и А2 от остальных (ори этом удобно гюпольэовать трешначные ло. нгки). Следует заметить. что исчисление высказываний можно описать системами аксиом, отличными от А! — АЗ. Кроме того.
вкесш символов ! к ш можно использовать и другие наборы символов, лишь бы с нх помашью можно было вырааить все Остальные логичесние оперании. таозхка !!а тзалзц !.гт у Хюу 1.4. ЛОГИКА И ИСЧИСЛЕНИЕ ЛРЕДИКАТОВ Мы рассмотрели два разлпчцык способа описания логики вмсказы»аний — содержамшьное и ансиоматнческое.
Логика высказываний — очшгь у»как логнчесиая система. Есть такие типы логическнк рассуждений, которые не масут бмть осушеспимиы в рамкак логики аысказыааннй, например: !. Всякий друг И»аяа есть друг Петра. Снлор не есть лруг Петра. Снелааательно, Сидор не есть друг Ивана. 2, Простое число дл» вЂ” четное. Следовательно, сушштвукж простые четные числа. Корректность зтнх умозаключений ос!гон»на на внутренней структуре самих предложений н на смысле слов «зсяппйз и «существуют . 1.4.1. Вреанкаты, кшмторы. формулы логики преднкатов Рассмстром прелзожеиия, занисвцне от парзметрон, и»примерз «т — четное число, к Меныие р», «х+ у х», «к — отец рз, х и р — братья» и т. п. Если х, у, з в первмх трек преллшкениях заменить некошрыми чнстамн, то получим определенные аысказывания, которые потуг быть истиннымн нти лажными, Наарцмерг 3 — четное число», «2 меньше б», «3+ 2 ум Последние лза ггрсдтажени» выражают родственные отношении а~ежду члеиачи семьи п также превращаются» оореясленные' высказыаання, по«явные пзи зох иые, прп замене х и у имена" мп чхснан этой сеиьаг «План — отец Петра, «Иван н Олег ( братья .
Предложении такого югпв нааываются преднкатами. Точнее,з лредякатам Р(кь..., х„] иазыеаетс» фу»кипя, переменные и ) торой принимают значени» пз иекоторога множества М, а саи она пранимаег дна значенн»г И [»стиннес) н Л (ложное), т. Р(хь...,д ) гМ (И, Л). Прсднкат от и аргументов назынмот л-местным предикато Множестао М значений персменнык определяется обычно ча магическим иантексюм. Например, шноанос соопюшенпе ментарной геометрии на плоскости — тоюш л. у.
х лежат и одной примой — выражается предикатам Е(х, р, з). где в ка честне зааченнй к, д и я рвссматриваюшя пшгпретные точки. Предикаты обозначавгсп »слышима букааын латинском( влфа»ит» Иногда бывает удобно указывать число перемеггнмй у преднкатон. В таких случаях у символов предикатое пнш верхний ипденс, который и указывает число аргументов, напр~ мерг Р"'(хь ...', х ) — и-местный прсдакат.
Высиазыванпя счй таются нуль-местнымн предякатамв. Над предикатамн можно производить обмены» логнческнй операции. В результате получаются аовые предпиши. ш Пример 1.25. 1. Пусть Рог(х) означает предикат «к делатся на двз», е)ог[х) — преднкат «х делится на грим Тогла выражение учо(х) АЯщ(х) означает предикат «х делится на два н х де- дптся на три», т. е. определяет ирсдикат делимости на б. 2. Пусть 51»~[х, д) означает предикат «х=д».
Он прини- мает значение И тогда и только тогда, когда х=д. В этом случае выражение 1 зн~(х, х) ~ йнн(х, у) определяет предикат, принимающий значение И прн любых к я д. Кроме операций логики высиазмваннй будем применять еще операции «назывании кваптором. Кзпнтор обп[яости.
Пусть Р[х) — некоторый предикат, при- нимающий значение И нли Л длп каждого элемента х множе- «тва М. Тогда под выражением ()[х)Р(х) будем подразумевать эысказываиие истинное, котла Р(х) истинно для каждого эле- мента х нз множества М, н ложное — в противном случае. Чи- тается это выражение таи: «длн всех х Р(х) . Эщ высказыва- ние уже не зависит ат х.
Символ Ух называется квантором общности. Каалгар сущзсгаоаолнл. Пусть Р(х) — некоторый прсднкзт. Под выражением (Ях)Р(х) будем сонимать высказывание ис- тинное, когда существует элемент множества М. для которого Р(х) истинно, н ложное — в противном случае. Читается это выражение тзк: «существуст к такое, что Р(х)» илп «сущест- нует к.
для которого Р[х)». Снмваи Бх называется квантором .существования. Операцию связывания квантором можно применять п к пре- дниатам от большого числа переменных [подробнее об этом булет сказано позже]. Пример 1.27. Для преднкатав, приведенных в примере 1.26, имеем: (Ях] (Рщ(х) 6 Цо~(х)) — истинное высказывание; (Ух) (Рщ (х) й Ягч (х) ) — ложное высказывание.
На языке предикатов можно составить гораздо более слож- ные прслложевня, чем на языке лсзякн высказываний. Опрелелнм понятие формулы логики предикатов. Алфавит .логики предикатов содержит следующие символы: 1) символы предметных переменных: хь зм..., х,,..г 2) символы прсднкатов: Аи~ь Агоь ..., А'г'ь ..., где 1=0. 1. 2,...; 3) логические символы: -1, А, 1/, ю, Ф) символы нванторов: Е,ТО 5) скобки и запятую: ), (.
Во избежание нагромождения индексов часто символы прел- метнмк переменных будем обозначать через х, у, ю а символы нредикзтов — через Р, 5, О, Я и т.д Слово в алфавите логики преднкатов называется форлдлоб. сслв она удовлетворяет следующему ннлуктнвпому опрслелсвню тз (одновременно определяется понятие сноба!пой н связапиод' переменной формулы]г 1. ЕСЛН А!'гг — СИМВОЛ ПРЕДИКата, Кп.
Хб,.... «г — СЧЯВОлы предметных переменныд не обязательно рззлнчпып то , к ' ) — формула. Такая формула называется пго., марной. Все предметные псремеипме атомарных формул сво-' бодные, связанных переменных нет. 2. Пусть А — формула. Тогда ( !А) тоже формула. Сво. бедные и связанные переменные формулы (-1 А) — зта соответственна свободные п связанные переменные формулы А. 3. Пусть А н  — формулы, причем нет таких предметных переменных, поторые были бы связаны в одной формуле и свободны — а другой. Тогда (А(УВ>, (ААВ>, (А В>, (А-В] (1.4) есть.
формулы, в которых свободные переменные формул А и В осгаютсн свободными, а связанные переменные формул А и В' остаютс» свпвавпыми. 4. Пусть А — формула, содержащая свободную переменную к. Тогда (Ых)А, (Ях)А (1 5) тоже формулы. Переменная к в пнх связаяа. Остальные жс переменные, которые в формуле А свободны, остаются свободнымн и в формулах (!.5). Переменные, поторме в формуле А связаны, остаются сеязаниымн и а формулах (!.5).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
