В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 13
Текст из файла (страница 13)
Функция прояоднмостн схсмы из иаследоэательиа соединенных «онтактов хг а хг есть Х," й бдг", а функция ироводнмасти схемы из параллельно соедпмен них панта ктоя — ХХ )г' Хг'г г Следовательно, каждой последоаательис параллельной контаптной схечс можно поставить в ссютвстстэие формулу логики высказываний, реализующую функпию проволнмостп этой схемы. Дяе схемы считаются эьэиаалентными, если онн одновременно проводят (илп не проводят) ток прн подаче напряжения на одноименные реле, т.
е, если они имеют одинаковую функцию проводичосгн. Применяя равносильности логики высиазмваний, можно упрощать кантакпцге схемы, заменив нк эквнвалентнымн, содержащими меньшее число контактов. Пример 121. Запипгем функцию проводимости и упредим злеитрическую схему: Функш~я прововлмосгн: (Уйу) Ч (Хй-! Уйу) Ч(-!ХЬ ,й-)Уйд) - (Уйд) )У ((-)УОХ) й (Х)У-)Х)) Хй(У)У 'х) У) 2. квнваиентиая схема: Завачи н упражнения 1.
Указать форыулы в СДНФ и СКНФ, вмражающвс слез! ющие функции: э) ((Хг. К». Хз), равную 1 тогда н только тогда, когда большинство перемеяпых равно 1; б) ДХг, Хз, Хь Х,), равную 1 тогда н только югда. котла Хг .1. Хз + Кз -1- Х<>4. 2. Выразить с помощью супсрпоэиции; а) ючерез1,+,.; б) й, т/ через ~, -9 в) -! через О, ю; г) -1, 'ьг, й через ) (здесь ) — функция Шеффера Х(у= -,«й'ПУ); д) -1, 'гг', й через е (здесь — функции Вебба К У - -) Х'тг'-)У) 3.
Представить маогочленом Жегалкина: а) Х щ У; б) Х У. 4. Доказать, ыо самодвпйствснная фувкпи» на противоположных наборах значений псременнмх принимает противоположные значения. б. Довэзатгь чю число самодвойственных функций от и пере. меиных равно 2З" ' 6. Дпказаты что число линейных функций от л переиенных равно 2"+Ц т. Доказать, что пересечение Лвух функционально замкнутых классов есть функционально замкнутый илвес. 9. Доказать. что совокупность функций, двойственных функциям из функционально замкнутого класса, образует функционально замкнутый класс. 9.
Доказаыь что следующие классы фунющй ие «вдаются фуию!нонально замннутыми: а) класс функций от двух переменных; б) класс функций, сокраняющих нуль, но не сохраняющик единицу. 1О. Доказать, что обьедниенне функционально замкнутых классов может не быть функционалыю замкнутым. 1!. Докавать, чю нельзя выразить с помощью суперпозиция: «).щ через -! и ; б) -! через щ. 12.
Проверить с помощью теоремы Поста полноту слелуюших систем булевык функций: а) (+, -); б) ( 3)г в) (О, ш)1 г) (, гг'. 0»; д) ()); е) (о). Будут лн эти системы функций кеэависимымиу 13. Доказать, что едиясгвеннымн полными системамн нз ганой двуместной булевой функция являются системы ()) и (о).
14. Доказать, что для класса К, всех булевых функций ба- . зисами ивляютсяг э) (1/, -1); б) (о); «) ()) 15». Доказать, что (й, ш) — базис для каэсса Ть 15. 3)столом минимизируюшнк карт найти минимальную ДНбг дла бУлевой фУнхдии )(Хь Хг, Хз), котоРаа Равна 1 толь ко на оценках <1, 1, 1>, <1, О, 1>, <О, О, 1>, <О, О, 0>. 17. Записать функцию проводимости и уггроспггь схему: к ъу 1.3. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ 1.3.1. Аксноматические теории Таблицы истинности позволяют ответить на многие воиросьг„ касающиеся формул логика высказывэняй, например на вопрос о тавтологичности (тождественной истинности) формулы нли на вопрос о равносильности двук формул.
Однако более сложные вопросы логики высказываний уже не могут быть решены с помощью таблиц истинности. Поэтому рассмотрим другой метод — метод формальных аксиоматических теорий. Фармальная аксиоматическэя теория Т считается оиреде. ленной, сели: 1) задано некоторое счетное множеспю символов — симво. лов теории Т; конечные последовательности символов теории Т называются выражениями теории Т; 2) имеется подмножеспю выражений теории Т, называемых.
формулами теории Т; аа 3) выделено некоторое множество формул, называемых аксиомами теории Т; 4) имеется конечное множество Яь..., )1 отношений между рмулами, называемых лрааилали эмаода. сли формула А и формулы Аь..., Аг находятся в некотором отношении ))» то А называется неаосредсгзеллмл следсгнпел из формул Аь..., Аь полученным по правилу Ег. ВмюнЪм в теории Т называется всякая последовательность Аь..., А„фоРмУл такаЯ, что дла любого» фоРмУла А, есть либо аксиома теории Т, либо непосредственное следствие каких-либо предыдущих формул. Формула А називаегся теоремой теории Т, если в ней существует вмвол, в котором последней формулой является А. Этот вывод называется выводом формулы А Иннин словами, теоремы аксиоматической теории — зю формулы, которме могут быть выведены по определенным правилам.
Формула А нюывастся следствием мломестап формул Г тогла и тельно тогда, когда существует такая пшледовательиость формул Аь ° ., А, что А есть А, и для любого !<)<я, Аг есп, либо аксиома, либо формула из Г, вибо непосрелствсниос следствие некоторых предыдущих формул. Эта последовательность называется выводом А из Г. Элементы Г называются посылками вывода или гл»ютеэалп.
Сокращенно можно записать Г 1-А (т. е. А есть следствие Г). Если множество Г состоит из формул Вь..., В», то пишут Вг,..., В») — А. Если à — пусггм множество, то Г)- А тогда и только тогда, когда А есть теорема. В этом случае принято писать 1 — А. Приведем несколько простых свойств понятия выводимоств нэ системы гипотез. Пусть à — произвольное множество формул, а А. В, С вЂ” произвольные формулы: 1. Г, А Г- А.
Действиттльно, вывод формулм А нз системы гипотез Г, А состоит иэ одной бюрмулм А. П. ЕслиГ,А,В1-С,тоГ.В,А) — С. ПЕ Если Г 1- А и  — произвольная формула, то Г, В 1 — А. Действителын» в качестве иывода формулы А нз системы гипотез Г, В можно взять нынод формулы А иэ системы гипотез Г. 1Н. Если Г ) — А. Г 1-В и А,В 1- С, то Г )- С. Пусть Аь..., А — выюд формулы А из Г; Вь . ° .,  — вывод формулы В иа Г; Сь..., С» — вывод формулы С из А, В. Тогда очевилно. что Аь..., А, Вь..., В Сь..., С» есть вывод формулы С иэ Г. У. Если Г, А 1- В и Г 1- А, то Г )- В (правило удаления выводимой шшшезы).
Пусть Вь..., „— вывод формулы В из Г, А. Если в етом выводе не встречаетсн формула А, то имеем мывод В иэ Г. Если в этом вывгще встречается формула А, то преть В»ы .. В»» — все вхождения формулы А в вывод. Пусть также Аь..., А — вывод А из Г. Тогда В»,..., В» г Аь..., еэ А, Вьы ..., В,, Ль..., А, Вг„ь..., Вц ы Аь ..., А, Вг„„,,  — выпод формулы В из П 1.3.2. Исчисление высказыванпйг определение, свойства. Теорема дедукции Рассмотрим один нз возможных способов формализации логи- «и высказываний — исчисление еыскааыааннй.
Оно яплясгся простым примером формальаой аксиоматцческой теории. ОпреЛелим эту формальную аксяоматическую теорнго следующим обрезомг 1. Символы псчпсаепн» высказываний: -1, щ, (, ) н буквы Х, с целыми положительны» числами в качестве пндексоа: Хг, Хг, Х ...
Снмвоты П и щ — логзчсскяе символы. символы Хь Хг, Х, ... †переменн. 2. Формулы исчисления еысказывавий: а) все персменнме Х. — формулы; б) если А и  — формулы, то (-!А) н (АщВ) тоже формулы. Пример 1.22. Последовательность симеонов -(Х, щ Хг~ щ Х, — выражение, во не формула. Пример 1.23. Пусть А, В, С вЂ” формулы. Тогда (С» (Л щВ)), ([(-1А] щВ) щ (-(С)) (1.2) тоже формулы.
Длн шжращеипя записи окустпм в формуле внешние скобки п те пары скобок, без которых можно восстановить формулу по следуюнгему правплу: каждое вхождение знака ! отнссится к наикратчайшей подформуле, следупхцей аа зткм знаком. Тогда форчулы <!.2) примут вид Сщ (А щВ), (-1А щВ) щ-!С. 3. Аксиомы осчпсления высказываний. Каковы бы ип были формулы А В н С, следующие формулы являются акспоыамис Л(, Ащ(вщЛ); А2. (А щ (ВщС)) щ ((А щВ) щ (АщС)); ДЗ. (-!Вщ-)Л) щ ((-! В щА) ~В).
Выражения А! — АЗ называются схемвмв аксиом, поскольку кажлое из вих порождает бесконечное множество формул, являющихся аксиОмами исчисления высказываний. Например, гРоРмУла Хгщ(ХгщХг) есть аксиома, полУченнаЯ па схеме А1, формула (Тдю-)А) щ (( ~дщА)щА) (где А — любая формула) — аксиома, полученная по скеме АЗ. 4.
Еднггственвыы правилом вывода формулы служит правило воды ролеы (сокращенно гл. р.). Пусть имеются трн формулы: Л, А щ В и В. Про формулу В будем говорить что оиа. 64 долучаежя ио правилу вывопа ж. р, нз формул А и А щ В. Это л. лов. дрзвило вывода записыва«тся сби зно в вите в Хотя для исчисления высказываний мы выбрали только даа логических симвала -! и гч с помощью след]чипах определений можно ввести и остальные операции: А ЛВ означает -! (Л» ю-]В]! А]г'В означает ~А~В! А В означает -!((Вщд) л -, (Л' В)!.
Докажем иескалька утверждений о выаодимастн формул в исчислении вмсказыеаний. Парпду со свойствами вызодимости 1 — Ч (см. с. 63) в асчз~слевизг вискааыеаннй выволняется также следующее свойства: Уй Вслп Г 1- А ю В н Г 1- А, то Г (-В. Пусть Аз,..., А вьюод формулы А из Г, где А совпадает с Л. Пусть Вь ...,  — вывоп формулы А ~ В иа Г, где В совпадает с А юВ. Тогда Л,..., А, Вь...,   — вивод формулы В иэ Г. Последняя фарыула в этом выводе аолучсн» применением правила ю. р. к формулам А п В .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
