Игошин Математическая логика и теория алгоритмов (1019110), страница 6
Текст из файла (страница 6)
Например, отрицание задает следующие правила действия с этими символами: О = 1, 1 = О, конъюнкция — следующие: О л О = О, О л1 = О, 1 л О = О, 1», 1 = 1, импликация — следующие: О -+ О =1, О -> 1 = 1, 1 -+ О = О, 1 -+ ! = 1 и т.д. Учитывая два правила действия с символами О и 1, определяемые отрицанием, можно записать равенство для вычисления логического значения высказывания — Р: Х(- Р) = — 2.(Р).
(1. 1) Указанные четыре правила действия с символами О и 1, определяемые конъюнкцией, позволяют записать равенство для вычисления логического значения высказывания Р л Д: (1.2) Х(Р л Д) = ЦР) л ХЯ). Аналогично, правила действия с символами О и 1, сформулированные в определениях 1.5, 1.7, 1.9, дают возможность записать равенства для вычисления логических значений высказываний Р ~ Ц, Р— » Д и Р ~-> 0 соответственно: ЦР ч 0) = ) (Р) ~ Х(Д); (1.3) Х(Р -+ Д) = Х(Р) -» Цо); (1.4) Х(Р <-» Ц) = ЦР) <-+ Х(0).
(1.5) Равенства (1.2) ... (1.5) можно записать в виде одного соотношения: Х(Р * Ц) = ЦР) * Х(Д), где значок «»» обозначает один из символов логических операций л, «, -», <-» . Равенства (1.1) — (1.5) фактически использовались при вычислениях логических значений высказываний А„А, », Ам А, ч А,, А, ч А„А, -+ -» Ац А1-» Аъ А, »» А„которые были проделаны выше в качестве примеров применения операций над высказываниями. 22 й 2. Формулы алгебры высказываний Конструирование сложных высказываний. С помощью логических операций, рассмотренных в з 1, из простейших высказываний можно строить высказывания более сложные.
Например, из высказываний Ан А,, А, можно построить такое высказывание: «Если Саратов находится на берегу Невы и все люди смертны, то А.С. Пушкин— великий русский математик>. Построенное высказывание символически записывается так: (Аз л Аз) -» Аъ Конечно, оно звучит несколько странно, поскольку соединяет в себе столь разнородные понятия, которые обычно существуют раздельно друг от друга. Но нас, еше раз подчеркиваем, интересует не содержание этого высказывания, а его логическое значение. Оно может быть определено, исходя из логических значений исходных высказываний А„Ам А, и той схемы, по которой из исходных высказываний построено сложное высказывание. Так как ЦА1) = О, ЦА,) = 1, Х(А,) = О, то, используя соотношения (1.4), (1.2) и определения 1.7, 1.3, находим: ) [(А~ л Аз) » А7[ = ЦА2 л Аз) -+ Х(А7) = ().(Аз) л ЦАз)) -+ ЦА7) = = (О л 1) -+ 0 = 0 -+ 0 = 1.
Итак, высказывание (Аз л Аз) -+ А7 истинно. Для конструирования данного сложного высказывания из простейших высказываний А„А, и А, нужно применить операцию конъюнкции к первым двум высказываниям, а затем к полученному высказыванию и к третьему исходному высказыванию применить операцию импликации. Это словесное описание схемы конструирования данного сложного высказывания можно заменить описанием символическим: (Х л 1') -» У, где Х, У, У— некоторые символы (переменные), вместо которых можно подставить любые конкретные высказывания. Такая схема конструирования составного высказывания может быть применена к различным конкретным высказываниям, а не только к высказываниям Аъ Аи Аъ Например, по этой схеме' из высказываний А«, Ам А5 построим высказывание «Если Сократ — человек и снег — белый, то 7 < 4».
Находим его логическое значение: ).[(А4 л А,) — » А5] = = 2(А«о Ав) — > ЦА5) = (Х(А4) о 1.(А«)) -+ ЦА5) = (1 о 1) — » 0 = 1 — » -«О = О. Таким образом, та же самая схема построения составного высказывания привела к ложному высказыванию. Однако ввиду разнородности понятий, которыми оперируют исходные высказывания Ао А,, А,, трудно на интуитивной основе судить об истинности высказывания (А4 л А,) » А,. По рассматриваемой схеме построено и следующее высказывание: «Если 100 делится на 5 и 100 делится на 2, то 100 делится на 10» Формальное вычисление логического значения данного высказывания показывает, что оно истинно, с чем вполне согласуются наши интуитивные представления об этом высказывании.
Итак, символическая запись (Хо 'г') » Уявляется своего рода формулой. Конечно, более привычны формулы типа Х= лг' (фор- 23 мула площади круга), Е = огай (формула потенциальной энергии тела) и им подобные. Тем не менее выражение (Хл У) — г Утакгке можно считать формулой — формулой схемы конструирования составных высказываний из более простых. Понятие формулы алгебры высказываний. В формулу (Хл У) — г У вместо переменных Х 1; У можно подставлять конкретные высказывания, после чего вся формула будет превращаться в некоторое составное высказывание. Переменные, вместо которых можно подставлять высказывания, т.е.
переменные, пробегающие множество высказываний, называют пропозициональными переменными, или высказывательными переменными, или переменными высказываниями. Будем обозначать пропозициональные переменные заглавными буквами латинского алфавита Р, Ц, Я, Ю, Х У, Хили такими же буквами с индексами Рь Рг, ..., Цг, Др, ..., Хь Хг, ..., 1'ь )г, .... Теперь дадим точное определение формулы алгебры высказываний. Определение 2.1 1. Каждая отдельно взятая пропозициональная переменная есть формула алгебры высказываний. 2. Если Г, и Рг — формулы алгебры высказываний, то выражения — Рн (Гг л Рг), (Р г Гг), (Г, -+ Гг), (Гг <-> Рг) также являются формулами алгебры высказываний.
3. Никаких других формул алгебры высказываний, кроме получающихся согласно п. ! и 2, нет. Определения такого типа называются индуктивными. В них имеются прямые пункты (в данном случае п. 1 и п. 2), где задаются объекты, которые в дальнейшем именуются определяемым термином (в данном случае — формулами алгебры высказываний), и косвенный пункт (в данном случае п. 3), в котором говорится, что такие объекты исчерпываются объектами, заданными в прямых пунктах. Среди прямых пунктов имеются базисные пункты (в данном случае п.
1), где указываются некоторые конкретные объекты, именуемые в дальнейшем определяемым термином, и индуктивные пункты (в данном случае п. 2), где даются правила получения определяемых объектов, в частности из объектов, перечисленных в базисных пунктах. В настоящей главе формулы алгебры высказываний будем называть просто формулами. Есть и другие названия для понятия формулы: правильно построенная формула или правильно построенное выражение, но они представляются менее предпочтительными.
Само определение формулы, носящее индуктивный характер, на первых порах кажется непривычным. Определения такого типа вам ранее не встречались. Лучшее понимание этого определения наступит, когда вы научитесь применять его для определения того, является или не является формулой последовательность символов (слово), составленная из пропозициональных переменных, символов логических операций и скобок. 24 К этому полезно добавить следующее. Для каждой формулы должна существовать конечная последовательность всех ее подформул, т.е. такая конечная последовательность, которая начинается с входящих в данную формулу пропозициональных переменных, заканчивается самой этой формулой, и каждый член этой последовательности, не являющийся пропозициональной переменной, есть либо отрицание уже имеющегося члена этой последовательности, либо получается из двух уже имеющихся членов этой последовательности их соединением с помощью одного из знаков п, и, -+, ~-> и заключением полученного выражения в скобки.
Такую последовательность всех подформул данной формулы иногда называют порождающей последовательностью для данной формулы. Наличие такой последовательности у логического выражения служит критерием того, что выражение является формулой. Это свойство отличает формулы. Приведем примеры формул. На основании п. 1 определения 2.1 формулами будут пропозициональные переменные: Р, Д, А, Х, 1; У; Рп Рп ..., Оп Дп ..., Хп Хп ....
Далее на основании п. 2 того же определения из этих формул построим следующие: —,Р, -зД~ 1Х «1, -1У, (Р '~ А) (Х и ) ) (Х -+ У), (О +"+ А), (У м У). Из построенных формул также на основании п. 2 строим еще более сложные формулы: (-Рл Д), (Р и Р), ((Хп г') -+ У), ((Х-+ У) п (У ч У)), ((Р м А) -+ (О е-» А)), ((Х вЂ” э У) -+ 1'). Ясно, что процесс построения все более сложных формул может продолжаться безгранично. Приведем примеры выражений, не являющихся формулами.
Это в каком-то смысле нелепые выражения. К примеру, выражение ((ХУ) — ь У) было бы формулой на основании п. 2 определения 2.1, если бы формулами были выражения (ХТ) и У. Выражение У есть пропозициональная переменная и потому на основании п. 1 определения 2.1 является формулой. Рассмотрим выражение (ХУ). Оно было бы формулой, если бы между формулами Хи Устоял один из знаков логических связок.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
