Полная версия

Главная arrow Математика, химия, физика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Функции алгебры логики

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

Определение 3.4Функцией алгебры логики от п переменных (или булевой функцией) называется произвольная п-местная функция f(x],x2,...,жте), определенная на двухэлементном множестве В = {0,1} со значениями в этом же множестве В.

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

До сих пор мы предусматривали логическую интерпретацию двоичных символов «0» и «1», однако она не является обязательной, поэтому будем рассматривать их как формальные символы, не имеющие арифметического смысла. Отметим, что булева функция является п-местной операцией по определению 3.4. Обозначим через Ро множество всех логических функций, а через А(п) - множество всех логических функций от п переменных. Тогда алгебра 93= (В: А), образованная множеством ? = {0,1} со всеми возможными операциями на нем, называется алгеброй логики. Всякая логическая функция (другое, более распространенное название функция алгебры логики) п переменных может быть задана таблицей, в левой части которой перечислены все 2п наборов значений переменных, а в правой части - значение функции на этих наборах.

Пример 3.7. Задать таблицей функцию принятия решения «кабинетом трех» при условии, что каждый голосующий говорит либо «да», либо «пет», а решение принимается большинством голосов.

Хх

х2

Хг

f(x 123)

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

1

1

1

1

1

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

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

Переменная хи функции /(зц,..., Xk-u %k-> %k+u •••, ж») называется фиктивной, если

при любых значениях остальных переменных. В этом случае ясно, что, удалив фиктивную переменную, получим функцию, которая зависит от (п— 1) переменной. Смысл удаления фиктивных переменных очевиден. Однако иногда бывает полезно вводить фиктивные переменные, так как это позволяет любую конечную совокупность функций считать зависящей от одного и того же множества переменных. В частности, равенство (3.1) имеет место при условии, что А(^) содержит все возможные функции п переменных, в том числе и функции с фиктивными переменными.

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

Таблица 7

X

Ч>

<Рз

0

0

0

1

1

1

0

1

0

1

Функции (/?() и if:з представляют собой константы 0 и 1, соответственно. Их значения не зависят от значения переменной, т. е. х - фиктивная переменная. Функция р(х) = х, а функция (fo{x) совпадает с операцией отрицания, т. е. аналитически может быть представлена формулой (fo(x) = ^X.

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

Таблица 8

Х

х2

Ро

Pi

Р2

Рз

Ра

Ръ

Рб

(fj

р8

<Р9

Рю

Рп

Р2

Рз

Ри

Pl5

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

Функции (fo(x, Х2) = 0 и (f 15(^1, ^2) = ! ~ константы, т. е. функции с двумя фиктивными переменными. Функции ps(xi,X2) = Xi, совпадают с одной из переменных, a рю(хi,X2) = ~^xo и fn{xi, Хо) = — ~Х с отрицанием одной переменной, имея в качестве фиктивной другую переменную. Сравнивая значения функций в табл. 8 с таблицами истинности для логических операций, заключаем, что вполне естественно функцию (f (х, Х2) назвать конъюнкцией и обозначить (fi(xi, Х2) = = Х&Х2, функцию (fl{X,X2)=X V Х2 ~ ДИЗЪЮНКЦИвЙ, (fg(Xi,X2) = = Х=Х2 - эквивалентностью, рг(х,Х2) = Х ~^Х2 - импликацией. Еще три функции имеют свои обозначения: р^{х) #2) = Х 0 Х2 - сложение по модулю два (неравнозначность), tp&(x,X2) = Xlx2 ~ стрелка Пирса, fu(x, х2) = Хх2 ~ штрих Шеффера, Остальные функции специальных названий не имеют, однако легко выражаются через перечисленные ранее функции.

Упражнение 4• Проверить справедливость следующих равенств: (f2{Xl,X2) = -'{X]^X2), ip4{Xi,X2) = -'(X2—>Xi), (fs{X, Х2) = V Ж2),

, X2)X2 —* X, (fu{xi, X2) = ~'{x-lkx2) -

Заметим, что ifn(x, X2) = <^1з(ж2> #i), т. e. функция <f получена из импликации переименованием переменных, а функция if 14 является результатом подстановки в функцию pn(xi,X2) функции р{х,Х2), вместо аргумента х, т. е. р 14(х, Хо) = -^(хУхо) = fi2{х, Хо), Хо)- Таким образом, приходим к очень важному понятию.

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

Пусть E = {/i, /2,/w,...} - некоторое множество функций алгебры логики, т. е. подмножество множества Р2- Каждая функция f% G Е есть формула над Е. Пусть f(x^x2, ...,жта) - функция п переменных из Е и Пр Л2,- либо формулы над Е, либо символы переменных, тогда /(ЛЬЛ2п) - формула над Е. Других формул над Е нет.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>