-
Способы задания функций алгебры логики
Укажем следующие 4 способа задания функций алгебры логики:
словесное описание;
табличное представление;
графическое изображение;
алгебраическое (в виде формулы).
Рассмотрим пример задания одной и той же функции от двух переменных каждым из перечисленных способов.
– это словесное описание функции.
-
x
y
f(x,y)
0
0
0
– табличное представление.
0
1
1
1
0
1
1
1
0
В графическом изображении единичные значения функции отмечаются некоторым способом, например «*», как на рисунке 1, а нулевые значения представляются неотмеченными вершинами единичного «куба» (в данном случае – квадрата).
Та же функция задается
формулой:
-
Таблицы истинности и элементарные функции
Рассмотрим таблицу значений функции от n переменных. Число строк в такой таблице будет равно числу всевозможных «энок», т.е. равно 2n. А число столбцов – числу переменных плюс единица, т.е. (n+1). При построении таблицы учтем, что каждую «энку» можно рассматривать как двоичное число, и выпишем их в порядке возрастания от 0 до 2n–1.
|
x1 |
x2 |
x3 |
… |
xn-1 |
xn |
f(x1, x2, x3,…, xn-1, xn) |
|
|
0 |
0 |
0 |
… |
0 |
0 |
f(0,0,0,…,0,0) |
|
|
0 |
0 |
0 |
… |
0 |
1 |
f(0,0,0,…,0,1) |
|
|
0 |
0 |
0 |
… |
1 |
0 |
f(0,0,0,…,1,0) |
|
|
… |
… |
… |
… |
… |
… |
…………… |
|
|
1 |
1 |
1 |
… |
1 |
1 |
f(1,1,1,…,1,1) |
Таблица 1 |
В правом столбце таблицы 1 выпишем значения функции на соответствующих «энках». Такая таблица называется таблицей истинности или комбинационной таблицей. Последнее название объясняется тем, что с помощью неё можно описывать поведение логических схем, называемых также комбинационными схемами или схемами без внутренней памяти, на вход которых подается n сигналов, а выход является функцией входного набора сигналов и полностью определяется этим набором.
Приведем примеры таблиц истинности для элементарных функций алгебры логики, к которым относятся функции от одной и от двух переменных.
Заметим, что число функций от одной переменной равно 4 (см. таблицу 2), а от двух переменных – 16 (см. таблицу 3).
|
x |
g1(x) |
g2(x) |
g3(x) |
g4(x) |
|
|
0 |
0 |
0 |
1 |
1 |
|
|
1 |
0 |
1 |
0 |
1 |
Таблица 2 |
В таблице 2 функция g1(x) – это константа ноль или «противоречие».
Функция g2(x) – «тождественная функция x».
Функция g3(x)
– «отрицание x»,
обозначается «
»
или «
».
Функция g4(x) – константа единица или «тавтология».
|
x |
y |
f1 |
f2 |
f3 |
f4 |
f5 |
f6 |
f7 |
f8 |
f9 |
f10 |
f11 |
f12 |
f13 |
f14 |
f15 |
f16 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
Обозначение |
0 |
& |
|
x |
|
y |
|
|
|
|
|
yx |
|
xy |
| |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 3 |
||
В таблице 3 приведены обозначения элементарных функций. Эти обозначения (символы) принято называть пропозициональными связками или символами логических операций. Укажем также их названия, способы вычисления и прочтения.
Функция f1(x,y) – это так же, как и в таблице 2, константа ноль или «противоречие».
Функция f2(x,y)=x&y – «конъюнкция» х и у или «логическое умножение». Читается: «х и у». Значения этой функции можно получить простым умножением значений её аргументов или как наименьшее из значений аргументов, т.е. f2(x,y) = x&y = xy = min(x, y).
Функции f3(x,y)=
и f5(x,y)=
–
это «условное вычитание» у из
х, и х из у, соответственно.
Их значения можно получить по правилу:
и
.
Функции f4(x,y)=х и f6(x,y)=у – как и в таблице 2, «тождественная функция x» и «тождественная функция у» соответственно.
Функция f7(x,y)=ху – «сложение по модулю 2» или «исключающее или». Значения этой функции равны остатку от деления на 2 суммы её аргументов.
Функция f8(x,y)=ху – «дизъюнкция» х и у или «логическое сложение». Читается: «х или у». Значения этой функции можно получить как наибольшее из значений аргументов, т.е. f2(x,y) = xy = max(x, y).
Функция f9(x,y)=ху – «стрелка Пирса» или «отрицание дизъюнкции» или «конъюнкция отрицаний». Последние два названия обусловлены правилом, по которому получаются значения этой функции.
Функция f10(x,y)=ху
– «эквиваленция». Читается: «х
эквивалентно у». Значения этой
функции получаются по правилу:
.
Функции f11(x,y)=
и f13(x,y)=
– это так же, как и в таблице 2, «отрицание
у» и «отрицание х» соответственно.
Функции f12(x,y)= yx и f14(x,y)= xy – это так называемая «импликация». Для чтения выражения xy можно использовать фразу «х влечет у» или «если х, то у». Значения xy получаются как ответ на вопрос «х меньше, либо равно у?». При этом положительный ответ записывается «1», а отрицательный – «0».
Функция f15(x,y)= y | x – «штрих Шеффера» или «отрицание конъюнкции» или «дизъюнкция отрицаний». Последние два названия обусловлены правилом, по которому получаются значения этой функции.
Последняя функция в таблице 3 – это так же, как и в таблице 2, константа единица или тавтология.