Высказывание - это фрагмент текста, для которого можно выяснить его истинность (хотя бы приблизительно).
В булевой алгебре рассматриваются только те высказывания, для которых истинность может принимать два значения: либо истина (true), либо ложь (false). Другие значения - нельзя. Оба значения сразу - нельзя. Ни одного значения вообще - тоже нельзя. Подобные высказывания называются булевыми высказываниями.
Булево высказывание - это такое высказывание, для которого рассматриваются только два значения истинности: истина и ложь.
Всякая буква, обозначающая некоторое высказывание,—это переменная величина, принимающая одно из двух значений — либо 0, либо 1. Такую переменную называют двоичной.
В булевой алгебре операции выполняются не над чис- лами, а над высказываниями, представленными двоич- ными переменными. В результате получаются сложные высказывания. Эти сложные высказывания записываются в виде формул, также носящих двоичный характер. Двоичная переменная в булевой алгебре определяется следующими аксиомами [23, c. 50]: A AA A = ≠= ≠ 1 00 1,;,. если если В обычной алгебре (школьной) над переменными вы- полняются операции сложения, вычитания, умножения, деления, возведения в степень и т. д. В булевой же алгеб- ре основными являются только три операции. Их назы- вают дизъюнкция, конъюнкция, инверсия. Операция дизъюнкции обозначается знаком ∨, кото- рый ставится между двумя переменными: A ∨ B. Однако, если учесть некоторое сходство операции дизъюнкции с арифметическим сложением, то вместо знака ∨ можно писать знак обычного арифметического сложения, не забывая, разумеется, что знак плюс обозначает дизъюнк- цию: A + B. Этим знаком мы будем пользоваться и в дальнейшем. Операция дизъюнкции, называемая иногда логи- ческим сложением, определена следующими аксиомами [23, c. 51]: 00 0 011 10 1 111 + = += + = +=;;;. Первые три аксиомы согласуются с обычной арифме- тикой. А вот четвёртая может вызвать недоумение. Здесь необходимо иметь в виду, что единица обозначает не количество, а тот факт, что некоторое утверждение явля- ется истинным. Например, пусть A обозначает: «На улице тепло»; B — «Светит солнце». Что будет обозначать A + B? Это сложное высказывание: «На улице тепло или светит солнце». Оно истинно, если A = 1, или B = 1, или A = B = 1. В связи с тем, что в сложном высказывании два простых высказывания соединены союзом ИЛИ, дизъ- юнкцию иногда называют операцией ИЛИ. Рассмотрим вторую операцию — конъюнкцию. Она обозначается знаками ∧, &. Но, как и в случае дизъюнк- ции, этими знаками лучше не пользоваться. Конъюнк- ция— «родня» арифметическому умножению, поэтому вместо знака ∧ будем использовать точку: A⋅ B либо вообще не указывать никакого знака. При этом надо пом- нить, что если две буквы записаны рядом без какого-либо знака, то это значит, что они соединены знаком конъ- юнкции: A ∧=⋅= B A B AB. Операция конъюнкции (логическое умножение) опре- деляется следующими аксиомами [23, c. 51]: 00 0 01 0 10 0 11 1 ⋅ = ⋅= ⋅ = ⋅=;;;. Вернёмся к предыдущему примеру и рассмотрим сложное высказывание AB. Что оно обозначает? В отли- чие от дизъюнкции конъюнкция AB читается так: «На улице тепло и светит солнце». Два простых высказы- вания соединены союзом И, поэтому конъюнкцию неред- ко называют операцией И. Третья операция—инверсия, или отрицание. Она обо- значается чертой над буквой: A. Например, если A —это «На улице темно», то A —«На улице не темно». Инверсия определяется следующими аксиомами: 0110 = =;. т. е. отрицание лжи есть истина, отрицание исТаким образом, полный список аксиом, которыми бу- дем пользоваться в дальнейшем, имеет вид:
0+0=0; 0+1=1; 1+0=1; 1+1=1;
0*0=0, 0*1=0; 1*0=0; 1*1=1;
0=1; 1=0
Определение
1. Непустое множество S с определенной на нем (бинарной) операцией называется полугруппой, если эта операция ассоциативна, т.е (a b) c = a (b c)
для любых элементов a,b,c из S. Обозначение: (S,).
Определение 2. Полугруппа M с нейтральным элементом e, т.е. таким элементом, что
a e=e a=a для любого элемента a из M называется моноидом.
Примерами моноидов являются числовые множества N, Z, Q, R относительно обычного умножения и Z, Q, R относительно обычного сложения. Важнейшими примерами моноидов
являются свободные моноиды, которые широко применяются в теориях формальных языков, кодов и криптографии.
Легко понять, что относительно так определенной операции умножения множество A* является моноидом (его называют свободным моноидом над алфавитом А). а множество А+ всех непустых слов – полугруппой (её называют свободной полугруппой над алфавитом А).
Главным свойством, характеризующим свободные моноиды и полугруппы, является однозначное представление их непустых слов в виде произведения букв алфавита А.
Свободные моноиды и полугруппы
Свободные моноиды широко используются в теории алфавитного кодирования. Подмножество С свободного моноида А* называется кодом над А, если любое слово
в алфавите С имеет только одно представление в виде произведения элементов из С.
Например, если А = {a,b}, то подмножество С = {a2, a3} моноида А* не является кодом над А*, так как a 6 = a 2 · a3 = a 3 · a2 и однозначность представления нарушается, а подмножество Сn= {abk | k =1,2,..,n } при любом натуральном n, как нетрудно понять, является кодом
над С.
Свободные моноиды и полугруппы
Последнее позволяет с помощью двухбуквенного алфавита закодировать любой конечный алфавит, следовательно, и любое сообщение в нем. Однозначность представления слов через элементы кода обеспечивают безошибочное восстановление исходной информации, т.е. декодирование. Это обстоятельство широко используется при передаче информации по каналам связи. Обычно используется алфавит {0,1}. Это объясняется удобством интерпретации этого алфавита при передачи двоичной информации по каналам связи, напр., разной частотой для передачи 1 и 0.
11. Свободные моноиды и полугруппы
Для кодирования русского алфавита можно использовать код: А – 01, Б – 011, В – 0111, Г – 01111, Д – 011111 и т.д. Например, слово ГАД будет закодировано при этом следующим образом: 0111101011111. Для декодирования надо найти цифру 0 и все единицы правее ее до следующего нуля и восстановить соответствующую букву.
