Основы дискретной математики В.А. Осипова (Основы дискретной математики В.А.Осипова), страница 6

Третье утверскдение приходится считать ложным, ибо, исходя из истинного равенства, мы с помощью умозаключений не придем к ложному. Четвертое утверждение естественно считать истинным: прибавляя 1 к обеим частям равенства 0 = 1, получаем равенство 1 = 2. Таким образом, используя оборот «если Р, то Я» как логическую операцию (связку), определим ее следующим образом. Нмпликацией двух высказываний Р и Я называется высказывание, ложное тогда и только тогда, когда Р истинно, а Я ложно. Импликация высказываний Р и с, обозначается через Р Э Я (или Р ~ Я) н читается как «Р влечет Я» (или, иначе, «если Р, то Я», «из Р следует Я»). Высказывание Р называется посылкой импликации, а высказывание заключением импликации. Импликация определяется также таблицей истинности (см.

табл. 2.4). 2 — 2952 Осипова 35 2,1, Логика высказываний 34 Глава 2, ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ Таблица 2.4. Таблица 2.6. Эквиввленцией двух высказываний Р и Я называется высказывание, истинное тогда и только тогда, когда истинностные значения Р и Я совпадают. Эквиваленция высказываний Р и Я обозначается через Р Я и читается как «Р эквивалентно Я». Эквиваленция определяется также таблицей истинности (см. табл. 2.5). Определим понятие формулы логики высказываний. Алфавитом называется любое непустое множество.

Элементы этого множества называются символами данного алфавита. Словом в данном алфавите называется произвольная конечная последовательность символов (возможно, пустая). Слово а называется подсловом слова Ь, если Ь = Ь1аЬ«' для некоторых слов Ьг и Ь2. Алфавит логики высказываний содержит следующие символы: высказывательные переменные Хм Х«, Хз, ...; логические символы ее, Ч,, ~,; символы скобок (, ). Слово в алфавите логики высказываний называется формулой, если оно удовлетворяет следующему определению: 1) любая высказывательная переменная — формула; 2) если А и  — формулы, то (.

А), (А'мВ), (А «'В), (А ~ В), (А В) — формулы; 3) только те слова являются формулами, для которьгх это следует из 1) и 2). Подформулой формулы А называется любое подслово А, само являющееся формулой. Для упрощения записи будем в формуле опускать внешние скобки и те пары скобок, без которых можно восстановить эту формулу, если пользоваться следующим правилом: каждое вхождение знака .

относится к наикратчайшей подформуле, следующей за ним. Пример 2.1. Слово (ХгйХз) ~ Хз Х1 не является формулой, а слова ( Х1 з Х») ЧХМ (Х1 Х») з. Хз — формулы. Слова Х1 Х2, Хз, Х~., Хз, Хз — подформулы последней формулы. Принцип математической индукции, который будем использовать в рассухсдениях, формулируется следующим образом; если какое-то высказывание Р(г), зависящее от натурального параметра Ф, доказано для 1 = О и при произвольном 1 удается из истинности РЯ обосновать истинность Р(Ь+1), то РЯ истинно для всех 1. Будем применять также и другую формулировку этого принципа: если Р(1) истинно при 1 = О и для любого 1 из истинности Р(в) при всех в < ~ следует истинность Р(~ + 1), то Р(Ь) истинно для всех 1.

Применительно к высказывательным формулам принцип математической индукции можно сформулировать следующим образом: если какое-то утверждение Р(Р), зависящее от параметра Р, который пробегает все множество высказывательных формул, истинно для всех формул, не содержащих логических символов (т.

е. формул вида Х;), и при любом натуральном н из того, что Р(Р) истинно для всех формул Р с числом логических символов меньше и, следует, что Р(Р) истинно для всех формул с и логическими символами, то Р(Р) истинно для всех формул Р. Иногда параметр Р будет пробегать не все множество формул, а лишь часть его, скажем, все формулы, построенные с помощью фиксированного набора переменных. Если каждой высказывательной переменной, входящей в формулу, придавать истинностные значения И и Л, то формула будет определять истинностпную функцию, т, е, функцию, определенную на множестве (И, Л) со значениями в этом множестве. Истинностная функция мохсет быть представлена таблицей истинности.

Пример 2.2. Формулы (Х1 з Хз) г' (Х1 З (Х2йХ1)) и (Х1 ~ Х2) «' ~Хз имеют соответственно таблицы истинности 2.5 и 2.7. Таблица 2.6. 37 2Л. Логика высказывавий Таблица 2.7. 36 Глава 2. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ Опишем как определяется истинностная функция по данной формуле. Упорядоченный набор высказывательных переменньгх ( Х;„ Х;„..., Х;„> назовем списком переменных формулы А, если все переменные формулы А содержатся в этом наборе. В списке переменных формулы А часть переменных может быть фиктивной, т. е.

не входить явно в формулу А. Оценкой списка переменных назовем сопоставление каждой переменной списка некоторого истинностного значения. При этом, если список переменных формулы А содержит к переменных, то имеется 2" различных оценок, и, следовательно, таблица истинности этой формулы содержит 2" строк. Пример 2.3. Список переменных первой из формул, приведенных в примере 2.2, есть < Х1, Х2 > или < Х1, Х2, Хз >, < Х1, Х2, Хз, Х4 > и т. д. (здесь Хз, Х4 — фиктивные переменные). Оценка списка < Х1, Х2, Хз >, например, < И, Л, И >.

Для формул, зависящих от фиксированного списка ( Хгы Х;„..., Х;„>, определим индуктивно их значение на данной оценке списка (или, иначе, при данном распределении истинностных значений переменных): 1) формула есть одна из переменных Х;„Х,„..., Х,„, например, Х;,; тогда значение ее на данной оценке есть то истинностное значение, которое сопоставлено переменной Х;,; 2) формула имеет вид ( А), а значение А на данной оценке есть в; тогда значение ( А) на данной оценке определяется как - и, где . в вычисляется по табл. 2.1; 3) формула имеет вид (АагВ), или (А Ч В) или (А ~ В), или (А В), а значения А, В на данной оценке есть в, 1.

Тогда значение (АЙВ) будет вЫ, где в«с1 вычисляется по табл. 2.2, а значения остальных формул определяются аналогично. Теперь можно сформулировать основные понятия логики высказываний. 2.1.2. Равносильность формул Пусть А и  — две формулы, зависящие от одного и того же списка переменных < Х;„Х;„..., Х;, >. Будем называть их равносильными, если на любой оценке списка < Х;„Х;„..., Х«» > они принимают одинаковые значения. На первый взгляд, это определение кажется неоднозначным, так как А и В могут зависеть от бесконечного числа списков переменных. Однако эта неоднозначность только кажущаяся. Любой из возможных списков должен содержать все переменные А и В, причем значения А и В на любых оценках списка будут зависеть только от значений переменных, входящих в формулы А и В.

Равносильность формул имеет свой алгебраический аналог в тождественном равенстве алгебраических выражений. Равносильность формул А и В будем обозначать через А = В (так же, как в алгебре; например, а(б+ с) = ау+ ас). Нужно различать символы — и с—з . Так, является символом формального языка, с помощью которого строятся формулы, а символ: — заменяет слово «равносильно». Отношение равносильности есть отношение эквивалентности.

Действительно, оно рефлексивно, так как для любой формулы А А = А; симметрично, так как для любых формул А и В, если А = В, то В— : А; транзитивно, так как для любых формул А, В, С, если А = В и В = С, то А = С. Поскольку в определении равносильности формул А, В безразлично„какой список переменных берется (лишь бы он включал в себя переменные А и В), то в качестве < Х;„Х;„... ..., Х;„> возьмем список всех переменных формул А, В, С. На любой оценке этого списка формулы А, В, а равно и В, С принимают одни и те же значения.

Следовательно, и формулы А, С на всех оценках принимают одинаковые значения. Основные равносильности. Для любит формул А, В, С справедливы следующие равносильности: 1) АасВ = ВША (коммутативностпь й); 2) АйА = А (идсмпогаенгпносгпь й); 38 Глава 2. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ 3) Ай(ВйС) = (АйВ)йС (ассоциативность й); 4) А и'В = В ~/ А (коммутативностпь |~); 5) А и' А = А (идемпотпе~тпность |/); 6) А '4 (В Ъ' С):— (А Ъ' В) Ч С (ассоциативностпь ~/); 7) А ~l (ВйС) = (А Ч В)й(А ~l С) (дистрибутивностпь ~l отпноситель~о й); 8) Ай(В ~/ С) = (АйВ) ~l (АйС) (дистрибутивностпь й отпноситгльно ~l); 9) Ай(А Ч В) = А (первый закон поглощения); 10) А Ч (АйВ) = А (второй закон поглощеиия); 11) А = А (снятие двойного отрицания); 12) — (АйВ) = А Ч - В (первый закон де Моргана); 13) — (А и' В) = - Ай В (втпорой закон де Моргана); 14) А = (АйВ) ~l (Ай.

В) (первая формула расщепления); 15) А ив з (А ~/ В)й(А ~/. В) (втпорая формула расщепления). Л!обая из этих равносильностей легко может быть доказана с помощью таблиц истинности. Рассмотрим, например, равносильность 7). Пусть < Х;„Х;„..., Х;„> — какой-либо список переменных, от которого зависят А, В, С. Тогда имеется восемь вариантов значений формул А, В, С на любой оценке списка их переменных. Для каждого варианта по таблицам истинности нетрудно подсчитать значения левой и правой частей равносильности 7) и убедиться в том, что в любом из восьми случаев эти значения совпадают (см.

табл. 2.8). Таблица 2.8. 2.!. Логика высказываний списка переменных, от которого зависят А и В, левая часть равносильности 12) получает значение Л, то и правая ее часть получит значение Л, и, наоборот, если на какой-то оценке списка переменных правая часть равносильности принимает значение Л, то и левая часть примет значение Л. Это и будет означать равносильность. Итак, пусть на некоторой оценке списка переменных формула — (АйВ) принимает значение Л. Тогда формула АйВ принимает значение И, а поэтому обе формулы А, В принимают значение И. Но в этом случае, очевидно, и правая часть равносильности 12) примет значение Л. И наоборот, пусть формула ~А 'т' ~В принимает значение Л.