I.3. Функции и формулы алгебры логики

Алгебра логики задается двумя множествами: U и Р₂, где U – это множество всех высказываний, принимающих значения «истина» или «ложь», или любое другое множество, элементы которого могут принимать одно их двух значений или находиться в одном из двух состояний. Например, множество переключателей, каждый из которых может быть «включен» или «выключен», или множество электрических сигналов, поступающих на вход некоторого устройства, – «сигнал есть» или «сигнала нет» и т.п.. Сопоставим значению «истина» символ «1», а значению «ложь» – символ «0». Таким образом, алгебра логики оперирует на множестве всех высказываний со значениями из двухэлементного множества Е₂ ={0, 1}.

Множество Р₂ – это множество всех таких функций, которые принимают «истинностные» значения 0 или 1, если их аргументы пробегают те же значения. Т.е., если f(x₁,x₂,…,x_n) – истинностная функция от n аргументов или f(x₁,x₂,…,x_n)ÎР₂, то она определяет отображение f: ® E₂. Алгебра логики занимается изучением свойств этих функций.

Истинностные функции называют также функциями алгебры логики, или булевыми функциями, или переключательными функциями.

Число всех функций алгебры логики от n переменных равно 2²ⁿ.

Функции алгебры логики могут быть заданы одним из следующих способов: 1) словесное описание;

2) табличное представление;

3) графическое изображение;

4) алгебраическое (в виде формулы).

Таблица значений функции алгебры логики называется таблицей истинности или комбинационной таблицей.

Ниже приведены таблицы истинности элементарных функций алгебры логики, к которым относятся функции от одной и от двух переменных.

x	g1(x)	g2(x)	g3(x)	g4(x)
					Таблица 1

В таблице 1 функция g₁(x) – это константа ноль или «противоречие».

Функция g₂(x) – «тождественная функция x».

Функция g₃(x) – «отрицание x», обозначается « » или « ».

Функция g₄(x) – константа единица или «тавтология».

x

y

f1

f2

f3

f4

f5

f6

f7

f8

f9

f10

f11

f12

f13

f14

f15

f16

Обозначение

&

x

y

Å

Ú

¯

º

y®x

x®y

|

Таблица 2

В таблице 2 приведены также обозначения элементарных функций. Эти обозначения (символы) принято называть пропозициональными связками или символами логических операций.

Функция f₁(x,y) – это так же, как и в таблице 1, константа ноль или «противоречие».

Функция f₂(x,y)=x&y – «конъюнкция» х и у или «логическое умножение». Читается: «х и у». Значения этой функции можно получить простым умножением значений её аргументов или как наименьшее из значений аргументов, т.е. f₂(x,y) = x&y = x×y = min(x, y).

Функции f₃(x,y)= и f₅(x,y)= – это «условное вычитание» у из х, и х из у,соответственно. Их значения можно получить по правилу: и .

Функции f₄(x,y)=х и f₆(x,y)=у – как и в таблице 1, «тождественная функция x» и «тождественная функция у» соответственно.

Функция f₇(x,y)=хÅу – «сложение по модулю 2» или «исключающее или». Значения этой функции равны остатку от деления на 2 суммы её аргументов.

Функция f₈(x,y)=хÚу – «дизъюнкция» х и у или «логическое сложение». Читается: «х или у». Значения этой функции можно получить как наибольшее из значений аргументов, т.е. f₂(x,y) = xÚy = max(x, y).

Функция f₉(x,y)=х¯у – «стрелка Пирса» или «отрицание дизъюнкции» или «конъюнкция отрицаний». Последние два названия обусловлены правилом, по которому получаются значения этой функции.

Функция f₁₀(x,y)=хºу – «эквиваленция». Читается: «х эквивалентно у». Значения этой функции получаются по правилу: .

Функции f₁₁(x,y)= и f₁₃(x,y)= – это так же, как и в таблице 2, «отрицание у» и «отрицание х» соответственно.

Функции f₁₂(x,y)= y®x и f₁₄(x,y)= x®y – это так называемая «импликация». Для чтения выражения x®y можно использовать фразу «х влечет у» или «если х, то у». Значения x®y получаются как ответ на вопрос «х меньше, либо равно у?». При этом положительный ответ записывается «1», а отрицательный – «0».

Функция f₁₅(x,y)= y | x – «штрих Шеффера» или «отрицание конъюнкции» или «дизъюнкция отрицаний». Последние два названия обусловлены правилом, по которому получаются значения этой функции.

Последняя функция в таблице 2 – это так же, как и в таблице 1, константа единица или тавтология.

Из пропозициональных переменных, элементарных функций и скобок строятся логические формулы.

Вычисление значений формулы выполняется путем подстановки различных наборов значений переменных, входящих в формулу. Результаты вычислений обычно оформляются в виде таблицы истинности формулы. Такие таблицы могут быть полными и сокращенными.

Для построения полной таблицы истинности исходную формулу разделяют на подформулы и затем вычисляют значение каждой подформулы. Таким образом, если n – это число переменных в формуле, а s – число выделенных подформул, то число столбцов в полной таблице истинности исходной формулы будет равно n+s, а число строк – 2ⁿ. При этом последний столбец этой таблицы будет представлять значения формулы.

Для примера рассмотрим построение полной таблицы истинности формулы . Разделим её на подформулы: f₁=Øx, f₂=f₁Úy, f₃=f₂®z. Тем самым, таблица будет содержать 8 строк и 6 столбцов. См. таблицу 3.

x	y	z	f1	f2	f3
Таблица 3

В последнем столбце таблицы 3 находятся значения исходной формулы.

Сокращенная таблица истинности строится непосредственно под формулой. Для этого выписывают саму формулу, затем под именами переменных записывают столбцы их значений, а под каждой логической связкой – столбец результатов соответствующей логической операции.

((Ø	x	Ú	y)	®	z)
0						Таблица 4

Рассмотрим построение сокращенной таблицы истинности на примере той же формулы: . См. таблицу 4.

Внизу таблицы стрелками указаны участвующие в операции столбцы, номером в кружочке отмечен порядок выполняемых действий. Столбец результатов отмечен номером 3.

Из рассмотренных примеров видно, что значениями формулы могут быть только 0 или 1. Поэтому столбец результатов можно рассматривать, как некоторую истинностную функцию, принимающую те же значения, что и формула, на соответствующих «энках». Об этой функции говорят, что она реализуется формулой, про формулу, – что она реализует функцию.

Две формулы А и В называются эквивалентными, если функции f_A и f_B, соответствующие им, эквивалентны или равны, т.е. f_A=f_B. Для обозначения эквивалентных формул традиционно используется запись А=В, которую называют тождеством.

Следующие тождества характеризуют важнейшие свойства элементарных функций: {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 – законы поглощения.

Все тождества легко проверяются с помощью таблиц истинности.

Из свойств элементарных функций следует ряд простых правил преобразования формул:

а) если хотя бы один из сомножителей логического произведения равен нулю, то значение произведения также равно нулю;

б) если логическое произведение содержит не менее двух сомножителей, один из которых равен единице, то этот сомножитель можно сократить;

в) если логическая сумма содержит не менее двух слагаемых, одно из которых принимает значение ноль, то его можно сократить;

г) если хотя бы одно из слагаемых логической суммы принимает значение единица, то и вся логическая сумма равна единице;

д) пусть U¹ – подформула формулы U; если в формуле U заменить любые вхождения подформулы U¹ эквивалентной ей формулой В¹, то в результате будет получена формула В, эквивалентная исходной формуле U.

Для упрощения записи формул вводятся следующие соглашения:

1) В формулах опускают внешнюю пару скобок, т.е. вместо формулы (х®у) пишут выражение х®у. Аналогично в выражениях со знаком отрицания вместо записывают .

2) По закону ассоциативности для операции «∘» вместо формулы ((x ∘ y) ∘ z) или (x∘(y ∘ z)) используется выражение без скобок: x∘ y ∘ z. Для восстановления формулы достаточно расставить скобки, порядок которых не является существенным для вычислений.

3) О старшинстве операций: если в выражении с помощью скобок специально не указан порядок выполнения операций, то одинаковые по старшинству операции выполняются последовательно слева направо. Если в выражении имеются различные операции, то сначала выполняется отрицание, затем конъюнкция, дизъюнкция, импликация и т.д., самой последней выполняется эквиваленция. Скобки восстанавливаются по тому же правилу.

Ввиду введенного старшинства операций не всякая формула может быть записана без скобок. Например, в выражениях х®(у®z) или х&(yÚz) дальнейшее исключение скобок невозможно, т.к. это может повлиять на значение, вычисленное по формуле.

4) Для компактности вместо записи х₁&x₂&…&x_s используется запись , а вместо х₁Úx₂Ú…Úx_s – .

Перечисленные свойства и правила позволяют преобразовывать формулы, получая новые тождества.

Рассмотрим эквивалентные преобразования формулы: ¹= ²= ³= ⁴= ⁵=

Тождество 1 записано по правилу сокращения единичного сомножителя, тождество 2 – по правилу замены подформулы эквивалентной формулой, а именно: здесь для замены использовался закон исключенного третьего. В тождестве 3 применен закон дистрибутивности. Тождество 4 получено по закону коммутативности. И, наконец, тождество 5 записано по закону поглощения, причем для наглядности «поглощающие элементы» подчеркнуты одинарной и двойной чертой.