В.Н. Нефедов, В.А. Осипова - Курс дискретной математики, страница 7

1А,З. Тождестве»но.истинные формулы. Правильные рассуждения Пусть формула А эавяснт от списка переменных (Хй,. Х „>. Формула А называется таатолааией (плв жахдествен»о-жтинной формулой), еслн на любых оценках списка переменных <Хн,..., Хг„> она принимает значение И.

Формула А называется аылолнцаой если на некоторой оценке списка ларемсюгыи (Х;,..., Хц> она принимает з»аченне И. Формула А называетс» гаждестеенно-ланжой. если иа любых сцепках списка переменных <Кг,,...,Хц> она принимает значение Л. Формула А вазываетс» опровержимой, если на некоторой оценке слпск» переменных <Х;,,..., Хг„ > ола приминает з»а- чгпне Л. Как н в определенны равносильности, днесь не имеет значения, будут лв в списке фиктивные переменные. Примнем утвержденна, которые являются очевнднымн следствнямя данных определений; 1) А — тавтологня тогда п только тогда, когда А не «»ляется опровержимой; зз 2) А тождественно-ложна тогда я только тогда, когда А цс является выполнимой; 3) А — тавтология тогда и только тогда, когда -)Л тож- дественно-ложна; 4) А тюкдествснно-ложна тогда в только тогда, когда -)Л— таьтология; б) А  — тавтология тогда и только тогда, когда А п В равносильны.

С точки зрения логика тавтологии суп не что иное, как логические заковы, нбо при любой подстановке вместо пере- менных тавтологии коикретнык вмспазыванвй в результате получим истинные высказывания. Перечислим наиболее вэж- ныс тавтологнп (Л, В, С вЂ” произвольные формулы): 1) А'т(-1Л (заюж исключенного третъего нли Гегдит лол- йдлг)1 2) А»А1 3) А» (В»А); з) (А»В)»((В»С)»(А»С)) (цепное рассуждаю«)1 5) (А» (В»С))» ((А»В)» (А»С)); 6) (АЛВ)»А (АЬВ)»В; У) Л» (В» (АЛВ)); 3) А» (А~/В), В=з (ЛЧ В); й) (-)В -)Л) (( — 1В Л) ВП (б) ((А»В)»А)»А (зюиж Пирса). Каждую пз зтнх тавтологий можно обосмовать, например, составив таблицу и вычислив по ней значение формулы при пропзвольнык значсипях А, В, С.

Прн доказательстве утверждений различных математиче- ских теорий обычно используют рассуждения, которые ва язы- ке логике можно выразить формулами. Рассуждение называется правпльныл, есеп из конъюнкини посылок следует заключение, т. е. веяний раз, когда асе посыл- ки истинны, заключение тоже исп!нпо. Пусть Рь..., Є— посылки, Π— заключение. Тогда длв Р»..., Р определения правильности рассуждения по схеме " " " ", т. е. л УГЕЕРжДЕНИЯ О тОМ, ЧтО ПЗ ДаННЫХ ПССЫЛОК Рь...

Р„СЛЕВУЕт заключемне О, требуется установить тождественную истинность фоомулы (Р~й... йР,)»О Так как речь идсг лнн~ь о правильности рассуждения, нс- тпвиость заключения ис является пи необходимы», пп лоста- ~~~ным условием правильности рассуждения. * В сыне п«срэ, нрэмиз (л,а... аР 1» и эс уэо эспюг ег сев Фсзнг н. Оаэаю даме (см, узза ! 3 з) устл «з, з теюк Зевс«э, ул Пример 1А.

Рассмотрим лвв рассуждеимя: 1. Если число б простое, то оиа нечетное. Число б нечеткое. Следовательио, число б простое. Заключение истинно, ио рас. суждение иеправвльиов Зто рассуждение по схеме Я Легко проверять, что формула ((А юв) ЗВ) юА не является тщкдесгвеино-ястиииой. й Если Патр эапимаежл спортом, то Петр пикогда ве болмт. Петр занимается спортом. Следовательно, Петр никогда Яюп, Я ие болеет. Зто ра«суждение по схеме ' . Формула ((А ю я юВ) ЗА) юв тождесгвеиио-истинна, и, значит, рассуждение правильное. Распространенными схемами яравильных рассуждепяй яв, Яюл Я Яюи тл лаются следующие схемы: — ' и В тя Рассиотрим условное высказывание вида Аюв, где А— конъюнкция посылок.

 — заключение. Иногда удобнее вместо доказательства истинности эта о условиого высказывания устаиовить логическую истинность пекоторого другого высказывамия, равиосильиого исходному. Такие формы доказательства иазываютсв косаеннылл мсгодали доказательства. Одним пз иих явлиетс» способ доказательства от противно. го. Предположим, что утверждение А юВ ложно. Тогда, исхо дя вз этого предположеиия, вриходим к противоречию, т. е. доказываем, чю иекоторое утасрждевяе (соответствующее выскавываиию С) выполняется и яе внполияегсп (одновременно). Применимость этой формы косвсниого метода доказательства опраедываетея рэвиосильиостыо А В -,(А В> (Сй-)С> (Ай ПВ) (Ой-зв). Существуют и прутке схемы докаэательства от пропщиога АюВ ив (Ай-)В) ю -)А, А ю В в (А й -)В) ю В.

Еще одной формой юювеииого метода доказательства явля ется доказательство по закову коитрапозипии. осиовакиое из равносильности А В -,В -1А. когда вместо иствпвости А ю В мы доказываем истиипост( ;)В ю -1А 1.1.4. Диайствщщвста. Заков двэйствеввести Будем рассматривать формулы, содержащие только логичесюь симщщы й, )у, 1 зт Свмволы 3, 'т/ называются двойственныли друг другу. Фор. мула А' нззываетс» двойствеиной формуле А, если она получена из А ошговремснной заменой всех символов Уь 'т/ на двойственные. Например, формула Х~ й (Хт'тl -( Х,) двойственна формуле Х~ 1/ (Хзй-(Хз). Очевидно, что (А')' совпадает с А.

Пусть (Хг,... Хг ) — некоторый список переменных, а (зь..., яь> — его оценка. Назовем оценку <1ь..., 1г> двойственной оценке <яь..., а>, если <й,..., 1ь> получается из <яь..., яь) заменой всех И па Л н всех Л на И. Лемме 1.3. Пусть А ю формула, а <Хп, ..., Хг ) — снисоя переменных, от хоторого она зависит.

Тогда А принимает значение И на оценке <зь..., ш> в тон и только в гоы случае, если А* принимает значение Л на оценке <(ь..., 1ь>, двойственной оценке <яь..., яь>. Докажем лемму 1.3 для всех формул А, ззввсяшпх от спнс. ка переменных <Хг„..., Хгя), пндукцней по числу л логических снмволов А Еслн и О, то А совпадает с одной нз переменных Хг (1 м.: < 1 ~ й). В этом случае А' тоже совпэдгет с ХН . То, что Хг, принимает значение И на оценке (яь ..., яь), означает, что я~ есть И.

Но это равносильно тому, что й есть Л. а также тому, что Хг прмннмэег значение Л нэ оценке ((ь.... (ь>. Пусть утверждение леммы 1.3 спрзведлпво при чнсле логических снмволов, меньшем и. Докажем, что опо остается спра. ведливым н прп числе символов, равном п. Тогда формуле А должна нмиь ввд чВ, ВАС илн В ьl С. В соответсгвнк с этны утверждением различают тря случая: 1. Формула А есгь "1 В. Тогда, очевндно, А совпадает с -1 '(В ).

Пусть А нстнвна на оценке <вь...,яь>. Тогда В будет ложной нэ ней. В формуле В число логнческнх символов меньше и. Так как (В*)" есть В, то нз ложности (В ) на оценке (яь..., яь) следует испппюсгь В па оценке <1ь..., 1а> (нбо (зь ..., зь> к (1ь ..., 1х> взаимно двойствснны). Отсюда следует, что формула А (нлн -1,(В )) ложия не <(ь." ° 1а>. Аналогично нз ложностн А' на <1ь..., 1ь> выводится астннность А ка (ш...., ш>.

2. Формуля А есть ВАС. В этом случае А* есть В' т/С'. Пусть А принимает значепне И на оценке <яь..., яь>. Тседа и В, С бУдУт истинны нз (Яь ., зь). Тэк кзк в фоРмУлах В, С число лшнческих символов меньше н, то В, С* примут звзченне Л на <1ь..., 1а), а значит, н В'т/С' пРинимает значение Л нэ втой оценке. И наоборот, еслн В т,)С прпннмаеэ гнэченне Л на (1ь....

1ь>, то фоРмУлы В, С бУдУт ложны вэ <(ь..., 1ь>, к, далее, в силу индуктивного предаоложеняя С будут истинны ня <зь..., яь>, а значит, к ВЬС буден низинка на этой оценке я яб 3. Формула А ють ВтгС. В эюм случае А' сею В*ай". Пусть А «рнп«наю значение И на (зь .... зэ>. Тогда лнбо В, снбо С булет вотан«ой на (зь.-., щ>.

Если кю, напр«мер, булет В, то, поеною «у в В логвческнх символов меньше, чем л, 9' будет ложкой нз <а,..., д>. Но тогда н В'ЬС булет еожной на <(ь. "1 >. Лнвлогнчно рэссуждаек н в случае гетин«опт« С. Доказательство обрат«ого утверждения также гесложно. Теорема 1.1 (яро«чик дюйсгазнюстн). С ли А В, то 4'.

- Вь Пусть А В. Еслн <Хь,..., Хь > — список переменных, зт коюрого зависят формулы А, В (н, очевидно, А, В'), а (!ь.... й > — оценка этого списка, то А прннннасг звачеаю И на этой сценке в том н толью а том случае, сев« (А )' (т. е. А) прннамает зняченне Л на оценке <з,, зь>, двойственной опенке <1«..., 1з>. По последнее в снлу равнсснльнасти А к В иксег место тогда н только тогда, жкда В прннпмает значчн«с Л на оцсмкс <зь.... яэ>. С другой сюроны, В" ПРНННМаст ЗпаЧЕННЕ И На ОЦСНКЕ <1г,..., 1ь> тп«ЬКО тСГДа, «огла (В*)* (т. е.

В) приникает значение Л «а <з,..., зз>. Итзв, ВИДИМ, ЧтО Нет«ппсетъ А* На <1ь..., (ь> Ранпее«ДЬва истин«щек В' на (1,.... (а>. Поскольку оценка <Еь . ° .. 1ь> пронзвольна, получзезг, чтп А В . Прнншгп двойственности можно применить для няхсждсв«н новых рамкснльнссгей. Напрнмер, нспользуя следующнй частный случай листрнбутнвнсстн а стноснтезьна 'ту Х.а(Х111Хз) (ХгаХЛХг(Х,аХ,), получаем разнос«льне лъ Х,11 (Ххах„) ю (Х,т'Х,) Ь(хг((хз).

Другпе прнлаження прпнцкпа двойстюнност» будут приве ясны ннжс. 1 йб Нормальные формм формул Замстнм, что в салу зссоцватнвностн операций а и 'т) (см. тео рему 0.1), как бы мм не расставляли скоба« в аыражсннн Аал,й... ЬАь. А,т)йзт)... ЧА» (й>3), есегла бУдс арихоюпь к рав«сснльнмм формулам. Допуская не«отару волыюсп, «ажлсе нз этих выражен«й будем считать формуло к называть соответственно млогочлеяяой ксньюющней я днев юкклнсй формул Аь.... Аь Дл» инх формуд, нспользуя, вз прнмер, индукцию по гпах (й, 1), нетрудно получнть раяггОсиль( ноет«, выражающие обсбщенйую дпстрнбутпвассть: (Аг ЬАаа... ЬАь) )тг (Вг а Вэ а... а В ) (АгЪ/ В ) а зе й (А т/Вз) а...а (Аг'т/ В) гг (Аа т/В~) а (Лз'т/ Вт) йг... „а(Л1/В) а...