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