2015-10-22
1912
Алгебра логики задается двумя множествами: U и Р 2, где U – это множество всех высказываний, принимающих значения «истина» или «ложь», или любое другое множество, элементы которого могут принимать одно их двух значений или находиться в одном из двух состояний. Например, множество переключателей, каждый из которых может быть «включен» или «выключен», или множество электрических сигналов, поступающих на вход некоторого устройства, – «сигнал есть» или «сигнала нет» и т.п.. Сопоставим значению «истина» символ «1», а значению «ложь» – символ «0». Таким образом, алгебра логики оперирует на множестве всех высказываний со значениями из двухэлементного множества Е 2 ={0, 1}.
Множество Р 2 – это множество всех таких функций, которые принимают «истинностные» значения 0 или 1, если их аргументы пробегают те же значения. Т.е., если f (x 1, x 2,…, xn) – истинностная функция от n аргументов или f (x 1, x 2,…, xn)Î Р 2, то она определяет отображение f: 
® E 2. Алгебра логики занимается изучением свойств этих функций.
|
|
|
Истинностные функции называют также функциями алгебры логики, или булевыми функциями, или переключательными функциями.
Число всех функций алгебры логики от n переменных равно 22 n.
Функции алгебры логики могут быть заданы одним из следующих способов: 1) словесное описание;
2) табличное представление;
3) графическое изображение;
4) алгебраическое (в виде формулы).
Таблица значений функции алгебры логики называется таблицей истинности или комбинационной таблицей.
Ниже приведены таблицы истинности элементарных функций алгебры логики, к которым относятся функции от одной и от двух переменных.
| x | g 1(x) | g 2(x) | g 3(x) | g 4(x) | |
| Таблица 1 |
В таблице 1 функция g 1(x) – это константа ноль или «противоречие».
Функция g 2(x) – «тождественная функция x».
Функция g 3(x) – «отрицание x», обозначается «
» или «
».
Функция g 4(x) – константа единица или «тавтология».
| x | y | f 1 | f 2 | f 3 | f 4 | f 5 | f 6 | f 7 | f 8 | f 9 | f 10 | f 11 | f 12 | f 13 | f 14 | f 15 | f 16 |
| Обозначение | & | 
| x | 
| y | Å | Ú | ¯ | º | 
| y ® x |
| x ® y | | | |||
| Таблица 2 |
В таблице 2 приведены также обозначения элементарных функций. Эти обозначения (символы) принято называть пропозициональными связками или символами логических операций.
|
|
|
Функция f 1(x, y) – это так же, как и в таблице 1, константа ноль или «противоречие».
Функция f 2(x, y)= x & y – «конъюнкция» х и у или «логическое умножение». Читается: «х и у». Значения этой функции можно получить простым умножением значений её аргументов или как наименьшее из значений аргументов, т.е. f 2(x, y) = x & y = x×y = min (x, y).
Функции f 3(x, y)= и f 5(x, y)= – это «условное вычитание» у из х, и х из у,соответственно. Их значения можно получить по правилу: 
и 
.
Функции f 4(x, y)= х и f 6(x, y)= у – как и в таблице 1, «тождественная функция x» и «тождественная функция у» соответственно.
Функция f 7(x, y)= х Å у – «сложение по модулю 2» или «исключающее или». Значения этой функции равны остатку от деления на 2 суммы её аргументов.
Функция f 8(x, y)= х Ú у – «дизъюнкция» х и у или «логическое сложение». Читается: «х или у». Значения этой функции можно получить как наибольшее из значений аргументов, т.е. f 2(x, y) = x Ú y = max (x, y).
Функция f 9(x, y)= х ¯ у – «стрелка Пирса» или «отрицание дизъюнкции» или «конъюнкция отрицаний». Последние два названия обусловлены правилом, по которому получаются значения этой функции.
Функция f 10(x, y)= х º у – «эквиваленция». Читается: «х эквивалентно у». Значения этой функции получаются по правилу: 
.
Функции f 11(x, y)= и f 13(x, y)= – это так же, как и в таблице 2, «отрицание у» и «отрицание х» соответственно.
Функции f 12(x, y)= y ® x и f 14(x, y)= x ® y – это так называемая «импликация». Для чтения выражения x ® y можно использовать фразу «х влечет у» или «если х, то у». Значения x ® y получаются как ответ на вопрос «х меньше, либо равно у?». При этом положительный ответ записывается «1», а отрицательный – «0».
Функция f 15(x, y)= y | x – «штрих Шеффера» или «отрицание конъюнкции» или «дизъюнкция отрицаний». Последние два названия обусловлены правилом, по которому получаются значения этой функции.
Последняя функция в таблице 2 – это так же, как и в таблице 1, константа единица или тавтология.
Из пропозициональных переменных, элементарных функций и скобок строятся логические формулы.
Вычисление значений формулы выполняется путем подстановки различных наборов значений переменных, входящих в формулу. Результаты вычислений обычно оформляются в виде таблицы истинности формулы. Такие таблицы могут быть полными и сокращенными.
Для построения полной таблицы истинности исходную формулу разделяют на подформулы и затем вычисляют значение каждой подформулы. Таким образом, если n – это число переменных в формуле, а s – число выделенных подформул, то число столбцов в полной таблице истинности исходной формулы будет равно n + s, а число строк – 2 n. При этом последний столбец этой таблицы будет представлять значения формулы.
Для примера рассмотрим построение полной таблицы истинности формулы 
. Разделим её на подформулы: f 1=Ø x, f 2= f 1Ú y, f 3= f 2® z. Тем самым, таблица будет содержать 8 строк и 6 столбцов. См. таблицу 3.
| x | y | z | f 1 | f 2 | f 3 |
| Таблица 3 |
В последнем столбце таблицы 3 находятся значения исходной формулы.
Сокращенная таблица истинности строится непосредственно под формулой. Для этого выписывают саму формулу, затем под именами переменных записывают столбцы их значений, а под каждой логической связкой – столбец результатов соответствующей логической операции.
| ((Ø | x | Ú | y) | ® | z) | |
 0
| Таблица 4 |
Рассмотрим построение сокращенной таблицы истинности на примере той же формулы: . См. таблицу 4.
|
|
|
Внизу таблицы стрелками указаны участвующие в операции столбцы, номером в кружочке отмечен порядок выполняемых действий. Столбец результатов отмечен номером 3.
Из рассмотренных примеров видно, что значениями формулы могут быть только 0 или 1. Поэтому столбец результатов можно рассматривать, как некоторую истинностную функцию, принимающую те же значения, что и формула, на соответствующих «энках». Об этой функции говорят, что она реализуется формулой, про формулу, – что она реализует функцию.
Две формулы А и В называются эквивалентными, если функции fA и fB, соответствующие им, эквивалентны или равны, т.е. fA = fB. Для обозначения эквивалентных формул традиционно используется запись А = В, которую называют тождеством.
Следующие тождества характеризуют важнейшие свойства элементарных функций: {0, 1, Ø, &, Ú}. (Обозначим «∘» любую из функций: {&, Ú, Å}.)
1) ((x ∘ y)∘ z)=(x ∘(y ∘ z)) – свойство ассоциативности;
2) (x ∘ y)=(y ∘ х) – коммутативность;
3) конъюнкция и дизъюнкция дистрибутивны друг относительно друга: ((x Ú y) & z) = ((x & z) Ú (y & z))
((x & y) Ú z) = ((x Ú z) & (y Ú z));
4) 
– закон двойного отрицания;
5) 
– законы Де Моргана для конъюнкции и дизъюнкции;
6) (х & х) = x; (x Ú x) = x – законы идемпотентности;
7) 
– закон исключенного третьего;
8) 
– закон противоречия;
9) (х & 0) = 0, (x Ú 0) = x – умножение на ноль и сложение с нулем;
10) (х & 1) = х, (x Ú 1) = 1 – умножение на единицу и сложение с единицей;
11) ((х & y) Ú x) = x, ((х Ú y) & x) = x – законы поглощения.
Все тождества легко проверяются с помощью таблиц истинности.
Из свойств элементарных функций следует ряд простых правил преобразования формул:
а) если хотя бы один из сомножителей логического произведения равен нулю, то значение произведения также равно нулю;
б) если логическое произведение содержит не менее двух сомножителей, один из которых равен единице, то этот сомножитель можно сократить;
|
|
|
в) если логическая сумма содержит не менее двух слагаемых, одно из которых принимает значение ноль, то его можно сократить;
г) если хотя бы одно из слагаемых логической суммы принимает значение единица, то и вся логическая сумма равна единице;
д) пусть U1 – подформула формулы U; если в формуле U заменить любые вхождения подформулы U1 эквивалентной ей формулой В1, то в результате будет получена формула В, эквивалентная исходной формуле U.
Для упрощения записи формул вводятся следующие соглашения:
1) В формулах опускают внешнюю пару скобок, т.е. вместо формулы (х ® у) пишут выражение х ® у. Аналогично в выражениях со знаком отрицания вместо 
записывают 
.
2) По закону ассоциативности для операции «∘» вместо формулы ((x ∘ y) ∘ z) или (x ∘(y ∘ z)) используется выражение без скобок: x ∘ y ∘ z. Для восстановления формулы достаточно расставить скобки, порядок которых не является существенным для вычислений.
3) О старшинстве операций: если в выражении с помощью скобок специально не указан порядок выполнения операций, то одинаковые по старшинству операции выполняются последовательно слева направо. Если в выражении имеются различные операции, то сначала выполняется отрицание, затем конъюнкция, дизъюнкция, импликация и т.д., самой последней выполняется эквиваленция. Скобки восстанавливаются по тому же правилу.
Ввиду введенного старшинства операций не всякая формула может быть записана без скобок. Например, в выражениях х ®(у ® z) или х &(y Ú z) дальнейшее исключение скобок невозможно, т.к. это может повлиять на значение, вычисленное по формуле.
4) Для компактности вместо записи х 1& x 2&…& xs используется запись 
, а вместо х 1Ú x 2Ú…Ú xs – 
.
Перечисленные свойства и правила позволяют преобразовывать формулы, получая новые тождества.
Рассмотрим эквивалентные преобразования формулы: 
1= 
2= 
3= 
4= 
5= 
Тождество 1 записано по правилу сокращения единичного сомножителя, тождество 2 – по правилу замены подформулы эквивалентной формулой, а именно: здесь для замены использовался закон исключенного третьего. В тождестве 3 применен закон дистрибутивности. Тождество 4 получено по закону коммутативности. И, наконец, тождество 5 записано по закону поглощения, причем для наглядности «поглощающие элементы» подчеркнуты одинарной и двойной чертой.
