Колмогоров, Драгалин - Введение в математическую логику (947386), страница 8
Текст из файла (страница 8)
С) (26) о=с, с =о. (> о = а П а ~ а Ц а = а Ц а = е. (.) (16) 64) (22) Определим разность двух элементов а~ Ь жаПб. У п р а ж н е н и е. Докажите, что а<Ь сч-а' Ь = о. 8. Укажем теперь на связь между булевыми кольцами и булевыми решетками. Если дано булево кольцо (В, +, ° ) то можно определит() булеву решетку (В, П, О, — ), положив аПЬ=аЬ, аЦЬ=а+Ь+аЬ, а=а+е. Следует, конечно, проверить, что 39 1(х„...,х„) = ~) 1(а„..., а„) П (ха+ ах+ 1), (1) е„а„...,а "'" л 4=! где суммирование ведется по всем наборам а!,...,а„из нулей и единиц, т е. по всем элементам кольца 0".
Для доказательства достаточно заметить, что произведение л 8„„„, (х„...,х„) = П (х4+ а„+ 1), ь=! (2) рассматриваемое как функция от хь...,х„, равно единице только при х!=а!, ха=ам ...,х =а . В остальных же случаях это произведение равно нулю. Положив х =х при а=1, х~=х=х+1 при а=О, 40 это действительно булева решетка, т.
е. что выпо.чняютс аксиомы А1 — Аб. Проверим, например А4: а() (ЬПс) =а+Ьс+аЬс; (аОЬ) П (а()с) = (а+Ь+а6) (а+с+ ас) = =а+аЬ+аЬ-+ас+Ьс+-аЬс+ас+аЬс+аЬс=а+Ьс+аЬс, Обратно, если дана булева решетка . (В, О, П, ), можно определить булево кольцо ( В, +, ° ), положивв а+Ь=(а()6)~ (аДЬ), аЬ аДЬ.
Например, аксиома Вк8 в п.1 следует из (2) п. 7. Проверка остальных аксиом предоставляется читателю. Важно отметить, что описанное соответствие между кольцами и решетками взаимно-обратно. Так, если по данной булевой решетке образовать кольцо, а затем по кольцу вновь образовать решетку, то мы получим не что иное, как первоначальную решетку. Таким образом, между булевыми, кольцами и булевыми решетками имеется каноническое взаимно-однозначное соответствие. Мы имеем, по сути дела, одну теорию — булеву алгебру.
9. Рассмотрим булево кольцо Г функций )(х!,...,х ) от а переменных х! ...,х,еи0 со значениями из В, так называемых булевых функций. уп р ажн ение. Сколько элементов в Г„у Пользуясь операциями сложения и умножения в коль- ~ це 11, можно представить такую функцию по формуле Лаг-, ранжа в виде 1 л запишем произведение (2) в виде б»„...,а (хы .
х») х~~хз ' х»"' На языке булевых решеток Ь»„...,»„есть конъюнкция, в которую каждое хд входит либо само, либо в виде хь ровно один раз, Так как различные произведения б и 6' таковы, что бб'=О, то в формуле (1) кольцевую сумму Х можно заменить на булево объединение Ц. Мы получаем представление произвольной булевой функции в так называемой совершенной дизъюнхтивной нормальной форме 1(хы...,х„) = (.) 1(а,, ..., а„)х ...
х„ »» ..» Если ~ не равна тождественно нулю, то это выражение можно записать в виде Г(х„...,х„) = () х', ... х„"», к»»"" »' где суммирование распространяется на все наборы аь ..., а„, для которых 1(аь ..., а„) =1. Имеет место и двойственное представление в булевой решетке произвольной булевой функции в.совершенной конъюнктивной нормальной форме. Если функция не равна тождественно единице, то ~(х," .)= П (4()" ()4). и»» "»»1=0 $7. ЛОГИКА ВЫСКАЗЫВАНИЙ 1, Будем считать, что большие латинские буквы обозначают высказывания. Нам уже знакомы операции, которые, будучи применены к одному или двум высказываниям, доставляют новые высказывания.
Из высказывания А можно образовать отрицание этого высказывания ) А. Из двух высказываний А и  — их конъюнкцию А/~В и их дизъюнкцию А~/В и т. д. Нас будут занимать только такие операции над высказываниями Р, для которых истинностнос значение Р(Аь ..., А») полностью определяется истинностными значениями Аь ..., А„: ~Р(Аь-. А )~=1(1А11 - ~А 1).
Операции Р с одной и той же булевой функцией ~ равносильны. Операции над высказываниями нас интересуют лишь 3 зе». Ив «с точностью до равносильности». Поэтому классификац операций над высказываниями «с точностью до равносиль ности» совпадает с классификацией соответствующих буле вых функций г(аь ..., ав), отображающих Р" в Р. Имеется четыре попарно не равносильных операции на одним высказыванием: Р1(А) «-:.АЛ 1А, Рв (А) «=»А, Рв(А)«=» 1А, Р,(А) с-е-А~/ ~ А и шестнадцать попарно не равносильных операций над двум высказываниями: Рв(А> В)с=»АЛ ~А Рв(А В)в:»АЛВ, Рв<=эАЛ ~В Рвв=» 1АЛВ, Рв<=» 1АЛ )В, Р„~=» А, Р„~=» В, Рвв в=» ~ А, Рвв в:» 1 В, Р,вс=»(АЛВ)~/( 1АЛ ~В), Рввс=~(АЛ ~ВИДАЛ ~В), Рввв»А~/В Ри в»АЧ 1В, Рввв-» ~А~~В, Рввв=» ~ А ~ 1В, Рвв<=» А~1 1А.
Все перечисленные операции мы выразили через три: от рицание, конъюнкцию и дизъюнкцию. Через эти три опера ции выражаются и все л-местные операции над высказыва пнями при любом л (например, в дизъюнктивной нормаль ' ной форме, которая соответствует указанной в 5 б форм записи булевых функций). Так как АЛВ«=» 1( ~А~ 1В), А~/Вв=» 1( 1АЛ 1В), можно было бы пользоваться только наборами операций ~/ или ), Л. Это примеры базисов для системы операций логики высказываний.
Любопытно, что существуют базисы состоящие только из одной двуместной операции. Для этог пригодны операция А)В= ) АЛ 1 В =- "Рв(А, В) или двойственная ей операция А~В= ) А~l ~ В = Рм(А, В). Например через Т отрицание,и конъюнкция выражаются так: 1Ас-." А)А АЛВ«~-(А~А) ) (В)В). Представляет интерес еще базис 1(, =», где известная вам операция ="- импликации есть (А=>-В) «=-( РАУВ)-4::.Рвв(А, В). В этом базисе конъюнкция и дизъюнкция выражаются так". А~/В»» ( ~А»В), АЛВ«=- ) (А=в- ) В), 2. Будем считать буквы Р, Я, И, ... переменными, область значений которых состоит из всевозможных высказываний. Такие переменные называются лроиозициональными, Формулы логики высказбвваний (пропозициональные фор- мулы) строятся из пропозициойальных переменных с по- мощью формальных символов — скобок и знаков, обозна- чающих операции над высказываниями.
Мы используем сле- дующие знаки: Л вЂ” «конъюнкцня», операция Рв, «и»; ~l — «дизъюнкция», Рвв, «или»; :э — «импликация», Рвв, «если..., то»; ) — «отрицание», одноместная операция Р„ «не». Пропозициональные формулы строятся начиная с про- позициональных переменных с помощью следующего порож- дающего правила: если А и В суть уже построенные форму- лы логики высказываний, то можно построить новые фор- мулы (АЛВ), (А~/В), (А:эВ), ) А, Применяя последовательно это правило, можно строить различные строчки символов — формулы. Например, формулами логики высказываний являются выражения ( (Р:эф:э ((Р:э (Я:эЯ) ) ~ (Р~К) ) ), (Р»ж (РЛ()))). Заметим, что в формулах знаки Ч:эЛ и т. п.
суть просто символы, а не обозначения результата действия соответствующих операций. Чтобы подчеркнуть это, мы используем формальный знак ~ вместо =». Знак ~ следует воспринимать как букву, символ, а А=~-В есть сокращенное обозначение для выражения на русском языке «если верно А, то В».
Остальные логические знаки мы используем и формально, и для содержательных сообщений, но это не должно вести к недоразумениям. Подобным образом, (А= — В) есть сокращенное обозначение для формулы ((А=эВ) Л(В~А)), в то время как А««В есть сокращение для высказывания на русскйм языке «А тогда и только тогда, когда В». 3» 4Э Сама по себе пропозициональная формула не истинна и не ложна, это просто строчка символов, но если вместо ее пропозициональных переменных подставить конкретные вы. сказывания, то естественно определяется конкретное выска- зывание, получающееся, если, выполнить над высказывания- ми указанные операции. Таким образом, каждой формуле логики высказываний Р(Р„..., Р„) от пропозициональных переменных ' Рп, Р„ соответствует булева функция ((хь...,х ) кольца Г .
Упражнение. Каким из двуместных операций Рь — Рть соответствуют формулы а) ((РЛФ~(РМТ), Ь) ((1РЧ®= 1а. Формула Р(Рь ...,'Р„). называется тавтологией (прологи. циональной тавтологией, оби(езначимой формулой, логиче- ским законом), если она становится истинной при подстановке любых конкретных высказываний вместо Р„..., Р„, т. е. если этой формуле соответствует булева функция из Г„, тождест- венно равная единице. Примеры тавтологий: А~/ 1А (закон исключенного третьего), 1 1А еа А (закон двойного отрицания), 1(АЛ 1А) (закон противоречия), ( )А~В)ЛДА:э )В):э А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
