Основы дискретной математики В.А. Осипова (552659), страница 7
Текст из файла (страница 7)
Тогда формулы ~А, ~В принимают значение Л, а формулы А,  — значение И. Очевидно, что и левая часть равносильности 12) примет значение Л. Следующая группа равносильностей показывает, что одни логические операции могут быть выражены через другие: 16) А В = (А з В)й(В З А) г— н (АйВ) е ( Ай В); 17) Аз В= АЧВ=-(Ай- В); 18) АМ В = — А з В= — -(-Ай-.В); 19) АйВ= (Аз В) = ( Ач В). В силу транзитивности отношения равносильности, если А! = А2, А2 = Аз, ..., Ав ! = Аы то А! = Ав.
В таком случае для простоты будем записывать цепочку А! = Аа = эзАв !=Аь. Приведем правило, с помощью которого можно переходить от одних равносильностей к другим. Однако часто равносильность экономнее доказывать без составления полной таблицы, а лишь с помощью некоторого рассуждения. Рассмотрим, например, первый закон де Моргана (равносильность 12)). Докажем, что если на какой-то оценке Лемма 2.1. Пусть А = В и С вЂ” произвольная формула.
Тогда А = ~В, АйС = — ВйС, СйА = СйВ, А Ч С = В Ч С, СЧА = СМВ, А з С = В з С, С ! А = С з В, А С = В С, С А=С В. Докажем, например, равносильность А ~ С = В ~ С. На произвольной оценке списка переменных, от которого зависят А, В, С, формулы А и В принимают одинаковое значение (скажем, и). Пусть ! — значение С на этой оценке. Обе части рассматриваемой равносильности принимают одно и то же значение и З !.
Лемма 2.2. Пусть А = В и С вЂ” формула, в которой выделено одно вхождение переменной Х;. Пусть Сл полу !ается 40 Глава 2. ЭЛКМКНТЫ МАТКМАТИЧКСКОЙ ЛОГИКИ из С заменой этого вхождения Х; на А, а Сп — из С заменой того же вхождения Х; на В. Тогда Сл = Сн. Докажем это индукцией по числу п логических символов С. Если и = О, то формула С должна совпадать с Х; (так как в ней имеется вхождение переменной Х;). Б этом случае Сл есть А, Сп есть В, а Ся = Св — не что иное, как А в— е В. Пусть лемма доказана для числа логических символов меньше и и пусть С вЂ” формула с и логическими символами.
Она имеет вид Р, или РгсЕ, или Р '»' Е, или Р Э Е, или Р ~ Е, причем в первом случае выделенное вхождение Х, содержится в Р, а в остальных случаях — либо в Р, либо в Е, но не в Р и Е сразу. Рассмотрим, например, случай, когда С имеет вид Р ~ Е, а выделенное вхождение Х; содержится в Р. Заменяя Х; в этом вхождении в .0 на А и В, получаем соответственно формулы Рл и Рв. Ясно, что С,1 есть .0,1 Э Е, а Св есть .Рв .э Е.
Так как в формуле Р меньше логических символов чем в С, то Рл = — Ра. Применим теперь лемму 2.1 в случае А З С = В:> С, где в роли А выступаег Рл, в роли  — Ра, в роли С вЂ” Е. Б результате получаем Сл = Св. Другие случаи рассматриваются аналогично. 'Утверждение 2.1 (правило равносильных преобразований). Пусть Сл — формула, содержащая А в качестве своей подформулы. Пусгпь Св получается из Сл заменой А в этом вхоэкдении на В. Тогда, если А = В, то С,1 = Са. Рассмотрим произвольную переменную Х; и получим формулу С из Сл заменой А на Х;. Будем считать это вхождение Х; в С выделенным.
Тогда С, А, В, С,1, Сп удовлетворяют условиям леммы 2.2, а значит, Сл = Сп. Заметим, что алгебраический аналог этого правила достаточно очевиден (впрочем, как и само правила) и обычно применяется без особого обоснования. Например, пользуясь тождеством х + х = 2х, получают у(х + х) = у(2х). 'Утверждение 2.2 (правило устранения логических символов Э и ). Для каждой формулы можно указать равносильную ей формулу, не содерисащую логических символов и э. 2Л. Логика высказываний Б самом деле, опираясь на правило равносильных преобразований, можно в исходной формуле каждую подформулу вида А - В заменить на (АасВ) Ч ( Аъг В), а каждую подформулу вида А э  — на .
А Ч В (см, равносильности 16) и 17)). Можно дать и более строгое доказательство, применив индукцию по числу логических символов. Пример 2.4. Формула (Х1 Э (Х2 З Хз)) - -(Хз Э Х1) преобразуется следующим образом: (Х1 З (Хз ~ Хз)) — — (Хз ~ Х1) = =(Х, ~ (-Х,7Хз)) -(-(-Х2УХ1)) —= = (- Х1 У (- Ха У Хз)) — (- Хз ь' Х1) = = (( Х1 Ч ( Хз Ч Хз))вс ( Хз 17 Х1))У ~ (-+ Х1 У ( Хз Ч Хз)) Й-. (- Хз У Х1)). 2.1.3. Булевы алгебры Можно заметить, что законы, связанные с заданными в алгебре множеств и логике высказываний опрерациями, похожи друг на друга. Это вызвано тем, что обе эти теории являются интерпретацией одной и той же математической системы, а именно булевой алгебры. Булева алгебра названа по имени английского математика Джорджа Буля, который в 1854 году опубликовал труд «Исследование законов мышления», положивший основу современной математической логики.
Целью этой работы было «исследовать основные законы тех операций ума, посредством которых проводятсц рассуждения, выразить их на символическом языке». Математическая система является булевой алгеброй, если она удовлетворяет известному определенному набору требований или, иначе, аксиом. Из этих основных аксиом можно логически вывести остальные положения булевой алгебры. Существует несколько способов выбора системы аксиом для булевой алгебры. Мы рассмотрим не самый изящный, но более естественный из них. Множество В с заданными в нем двумя бинарными операциями О (называемой объединением) и О (называемой пересечением) называется булевой алгеброй, если выполняются следующие аксиомы: 2 1 Логика высказывании и 0 а' = 1, аПа' = 0 а0а=а, а П а = а. б) Для каждого а Е В а01= 1, а П 0 = О.
7) Длявсеха, ЬЕВ (а 0 Ь)' = а' П 66, (а П Ь)' = а' 0 Ь' иО=а,1=Ь,а'=Ь, Ь'=а. 42 Глава 2. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ 1. Каждая операция коммутативна: для всех а, Ь Е В а0Ь=Ь0а и иП6=ЬПа. 2. Каждая операция ассоциативна: для всех а, Ь, с Е В а 0 (Ь 0 с) = (а 0 6) 0 с и а П (6 П с) = (и П 6) П с, 3. Каждая операция дистрибутивна по отношению к другой: для всех а, Ь, с Е В а 0 (6 П с) = (а 0 6) П (а 0 с) и а П (6 0 с) = (а П 6) 0 (а П с).
4. В множестве В существуют отличные друг от друга элементы 0 и 1 такие, что а 0 0 = а и а П 1 = а для всех а Е В (О называется нулевым элементом, 1 — единичным). 5. Для каждого элемента а Е В и каждой пары элементов 0 и 1, определенный в п. 4 существует элемент и' такой, что (элемент а называется дополнением элемента а). / 3 а м е ч а н и е.
Аксиомы 1 — 5 не являются независимыми. Например, закон ассоциативности можно вывести из остальных. Для каждой булевой алгебры справедливы следующие утверждения. 1) Элементы 0 и 1 являются единственными. 2) Для каждого а Е В существует единственное дополнение а'. 3) Для каждого элемента и Е В (а ) = а. 4) О' = 1; (1)' = О, 5) Для каждого а Е В (законы де Моргана для булевой алгебры). Покажем выполнимость утверждения 1). Пусть 01 и 02— два нулевых элемента множества В, для которьгх выполняется аксиома 4, т.
е. для всех а Е В а 0 01 = а и а 0 02 = а. Тогда 02001 = 02 и 01002 = 01. На основании аксиомы 1 01002 = 02001. Отсюда 01 = 02. Следовательно, нулевой элемент единственен. Если под элементами множества В понимать множества, а операции 0 и П трактовать как теоретико-множественные объединение и пересечение, то аксиомы 1-5 выполняются в силу утверждения 1.1. Здесь роль нулевого элемента выполняет пустое множество, роль единичного элемента — универсальное множество, для каждого множества а множество а' — его дополнение. Это означает, что алгебра множеств является интерпретацией (или моделью) данной системы аксиом и, следовательно, булевой алгеброй. Другой интерпретацией булевой алгебры является алгебра логики.
Под элементами множества В подразумеваем множество составных высказываний, которое можно образовывать из истинных и ложных высказываний, используя многократно и всеми возможными способами операции —, й, Ч,, з . Правило образования составных высказываний задается понятием формулы логики высказываний.
При этом, как мы знаем, можно исключить операции и з. Каждому составному высказыванию соответствует элемент из множества (И, Л1, и два составных высказывания равносильны, если они принимают одинаковые истинностные значения. Тогда, если под операцией 0 подразумевать дизъюнкцию высказываний, под П вЂ” конъюнкцию высказываний, под дополнением — отрицание высказывания, под единичным элементом— истинное высказывание, под нулевым — ложное высказывание, и знак равенства понимать как равносильность, то все аксиомы булевой алгебры выполняются для такой интерпретации.
Приведем пример булевой алгебры, у которой множество В состоит из двух элементов В = (а, Ь), операции 0 и П заданы таблицами 44 Глава 2. ЭЛЕМЕНТЪ| МАТЕМАТИЧЕСКОЙ ЛОГИКИ Непосредственной проверкой можно убедиться в выполнимости аксиом 1 — 5. Какими свойствами обладают булевы алгебры, у которых число элементов множества В конечно? Оказывается, что если в булевой алгебре число элементов и множества В конечно, то и = 2™ для некоторого натурального т. 2.1.4. Тождественно-истинные формулы.
Проблема разрешимости Пусть формула А зависит от списка переменных < Хгы Х;„..., Х;„>. Формула А называется тождественно-истинной (или тавтологией), если на любых оценках списка переменных < Х;,, Х;„..., Х,, > она принимает значение И. Формула А называется выполнимой, если на некоторой оценке списка переменных < Х;„Х;„..., Х,, > она принимает значение И. Формула А называется тождественно-ложной, если на любых оценках списка переменных < Х,„Х;„..., Х;, > она принимает значение Л.
Формула А называется опровержимой, если на некоторой оценке списка переменных < Х;„Х;„..., Х;„> она принимает значение Л. Как и в определении равносильности, здесь не имеет значения, будут ли в списке фиктивные переменные. Приведем утверждения, которые являются очевидными следствиями данных определений: 1) А — тождественно-истинная тогда и только тогда, когда А не является опровержимой; 2) А тождественно-ложна тогда и только тогда, когда А не является выполнимой; 3) А — тождественно-истинная тогда и только тогда, когда - А тождественно-ложна; 4) А тождественно-ложна тогда и только тогда, когда -А— тавтология; 5) А  — тождественно-истинная тогда и только тогда, когда А и В равносильны.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
