назад

2.1 Представление логических функций

В базовом курсе содержались элементы математической логики: истинные и ложные высказывания и операции над ними. Теперь рассмотрим те же и другие понятия и соотношения, используя функциональный язык. Будем считать простые высказывания независимыми переменными, сопоставив истинным высказываниям значение 1, а ложным - значение 0. Тогда операции над высказываниями представляют собой функции этих переменных. Введем необходимые понятия.

Логические переменные - это переменные, принимающие значения из двухэлементного множества В{0;1}. Они называются также булевыми, или двоичными переменными.

Булева функция (логическая функция, функция алгебры логики) - это функция одной или нескольких переменных Z=ƒ(X1, X2, ...Xn), где X1, X2, ...Xn, Z - логические переменные, т. е. и значения аргументов, и значение функции - ноль или единица. Тем самым, булева функция n переменных есть функция на Bn - множестве n - мерных векторов σ =(σ1, σ2, ..., σn), компоненты которых равны 0 или 1: σi≤ B. Можно применять векторные обозначения ~X,ƒ(~X) для сокращения записи. Пользуясь другими терминами, можно считать областью определения булевой функции множество вершин n - мерного единичного куба En.

На рисунке 1 изображена функция 3 переменных ƒ(X, Y, Z), принимающая значение 1 на наборах (001), (011), (100). Обратите внимание на допустимую форму записи: можно не разделять запятыми значения аргументов - все они однозначные числа.

Рисунок 1
Рисунок 1

Если число переменных равно n и любая из них может независимо от других принимать 2 значения, то число различных n - векторов равно 2n. Относительно каждой функции Z = ƒ{X1, X2,...,Хn) все множество Bn разбивается на два класса n -векторов: прообраз значения 0 и прообраз значения 1 функции Z . Мы будем рассматривать только всюду определенные функции.

Если считать, что переменные X1, X2,...,Хn обозначают истинность (значение 1) или ложность (значение 0) высказываний-аргументов, то функция Z выражает истинность или ложность определенного сложного высказывания при различных сочетаниях значений аргументов. Например, конъюнкция двух высказываний - это сложное высказывание, истинное тогда и только тогда, когда истинны оба составляющих простых высказывания. С функциональной точки зрения конъюнкцию можно рассматривать как булеву функцию двух логических переменных, принимающую значение 1 тогда и только тогда, когда оба аргумента равны 1.

Для задания логической функции нужно указать каким-либо образом, какое значение принимает функция на тех или иных наборах значений аргументов. Поэтому естественным является табличное представление булевых функций - для функции Z = ƒ( X1, X2,...,Хn) - таблица из 2n строк - n -мерных булевых векторов в алфавитном порядке, каждому из которых сопоставлено значение функции Z, равное 0 или 1. Заметим, что булева функция Z является на Вn характеристической функцией того множества точек Вn, для которых Z = 1 .

В таблице 1 представлены все функции одной переменной - их 4. В 1-м столбце - значения переменной Х; в каждом из последующих - значения соответствующей функции, обозначение функции - в 1-й строке. Во 2-м столбце - функция-константа Z 0, в 5-м - функция-константа Z 1. В 3-м столбце тождественная функция Z = Х , в 4-м - функция Z = ┐Х, которую называют отрицанием. Второй способ обозначения подчеркивает, что отрицание - одноместная функция аргумента Х.

Аналогично могут быть заданы функции нескольких переменных. Некоторые из них - для двух переменных - в таблице 2. Сравните их (столбцы 3-5) с таблицами истинности основных логических операций: конъюнкции, дизъюнкции, импликации, эквивалентности, для которых значения аргументов и результатов операций обозначались буквами И, Л. Отметим также, что с арифметической точки зрения, т.е. если рассматривать 0 и 1 как натуральные числа с обычными операциями арифметики, выполнены равенства:

┐X = 1\Х ; Х Y = Х × Y = min(X,Y);

 X Y = X + Y - XY = max(X,Y)

Поэтому конъюнкцию ХY называют умножением и записывают со знаком произведения: X × Y или вообще - как в алгебре - без знака: XY. Дизъюнкцию иногда удобно называть логическим сложением, а связываемые ею члены - логическими, или дизъюнктивными слагаемыми. Однако следует иметь в виду, что, во-первых, на наборе (1, 1) значение дизъюнкции не совпадает с арифметической суммой, а, во-вторых, термин "сумма" для логических переменных употребляется и в другом значении, представленном в той же таблице 2. В двух последних столбцах таблицы 2 представлены функции, которые не встречались раньше, а именно:

Сумма по модулю 2 - функция двух переменных, равная 0, если значения аргументов совпадают, и 1 в противном случае; ее обозначение - Х Y. Арифметическое значение (ХY) - остаток от деления числа (Х+Y) на 2, - отсюда название. Другое название - неэквивалентность, поскольку выполнено тождество: ХY = ┐(ХY) .

Сумма по модулю 2 как бинарная операция обладает свойствами коммутативности и ассоциативности
b) с = а (b с), и поэтому ее можно записывать без скобок а b с и переставлять слагаемые.

Штрих Шеффера - функция двух переменных, равная 0 тогда и только тогда, когда оба аргумента равны 1. Обозначение: Х | Y, условное название " Х несовместно с Y". Выполнены тождества:

Х | Y = ┐(Х Y) = ┐Х ┐Y .

Если принять, что всевозможные наборы значений двух аргументов (как легко видеть, их 4) расположены в таблице в алфавитном порядке, то каждая функция двух переменных полностью задается столбцом значений длины 4. Так же, булевым вектором длины 2n задается логическая функция n переменных. Для удобства записи можно транспонировать столбец значений в строку и таким сокращенным способом задавать булевы функции. Например, (0001)T представляет конъюнкцию, (0111)T - дизъюнкцию, (1101)T-импликацию; (11001100)T представляет функцию трех переменных g2 , заданную в последнем столбце таблицы 3. Для получения таблицы нужно приписать слева к столбцу значений стандартный (для каждого n ) перечень всех n -наборов, расположенных в алфавитном порядке.

Для задания булевой функции наряду с транспонированным столбцом значений функции можно использовать сокращенную запись: кортеж номеров тех строк таблицы, где функция равна 1 (номера могут быть записаны в десятичной системе в возрастающем порядке). Например, функцию m3 из таблицы 3 можно задать кортежем: [3,5,6,7], а функцию g2 из той же таблицы - [0,1, 4, 5]. Это особенно удобно, если функция принимает значение 1 на небольшом числе наборов, по сравнению с их общим количеством.

Важный пример применения булевых функций дают арифметические действия над двоичными числами: поскольку возможные знаки в двоичной системе суть 0 и 1, то зависимости знаков результата от знаков слагаемых/сомножителей выражаются булевыми функциями. При сложении двух однозначных двоичных чисел А и В знак суммы в младшем разряде равен (AB), а знак переносаσ возникает только если оба слагаемых равны 1, т.е. σ= АВ. Умножение однозначных двоичных чисел тождественно конъюнкции, что фактически отмечено выше.


Таблица 1
X 0 X ┐X 1
0 0 0 1 1
1 0 1 0 1

Таблица 2
X Y XY XY XY XY XY X | Y
0 0 0 0 1 1 0 1
0 1 0 1 1 0 1 1
1 0 0 1 0 0 1 1
1 1 1 1 1 1 0 0

Таблица 3
X Y Z m3 g1 g2
0 0 0 0 0 1
0 0 1 0 1 1
0 1 0 0 0 0
0 1 1 1 1 0
1 0 0 0 1 1
1 0 1 1 1 1
1 1 0 1 1 0
1 1 1 1 1 0

В таблице 3 представлены 3 функции трех переменных. Первую из них - m3 (X,Y,Z) называют иногда функцией большинства - ее значение равно значению, которое принимает большинство аргументов (т.е. два или три): если в наборе больше единиц, чем нулей, то и значение функции равно 1. Заметим, что при сложении двух многозначных двоичных чисел в каждом разряде, кроме самого младшего, складываются 3 однозначных числа: знаки двух слагаемых в этом разряде и знак переноса из предыдущего разряда. Таким образом, знак суммы как логическая функция есть сумма по модулю 2 трех булевых переменных. Знак переноса 1 возникает, если при таком сложении знаков число единиц равно 2 или 3, т.е. он равняется значению функции большинства от тех же 3 переменных.

В той же таблице заданы две другие функции, обозначенные g1 и g2 . По форме - это функции трех переменных, однако нетрудно убедиться, что g1 = Х Z, g2=┐Y. Как видим, функция g1 не зависит от аргумента Y, а функция g2 от аргументов Х, Z . Действительно, если, например, Х=0, Z=1, то и при Y=0 (набор 001), и при Y = 1 (набор 011) выполнено равенство g1 =1. Таким же образом проверяются остальные 3 сочетания переменных Х и Z. Введем определение.

Несущественные (фиктивные) переменные: для функции Z = ƒ (X1, X2 ,..., Xk-1, Xk, Xk+1,..., Xn) переменная Xk называется несущественной, если выполнено ƒ(X1, X2 ,..., Xk-1, 0, Xk+1,..., Xn) =ƒ (X1, X2,..., Xk-1, 1, Xk+1,..., Xn) при всех значениях X1, X2 ,..., Xk-1, Xk+1,..., Xn.

Таким образом, для функции g1 - несущественной переменной является Y, а для функции g1 - несущественные переменные X и Z. Если относить к функциям n переменных и функции, существенно зависящие не от всех своих переменных (т.е. являющиеся по существу функциями меньшего числа переменных), то общее число функций n переменных равно числу булевых векторов длины 2n, т.е. 22n. Для одной переменной это число равно 4 (таблица 1); для двух переменных - 24 = 16 ; для трех переменных - 28 = 256; четырех переменных -216 = 65536 и т.д.

Множество всех логических функций, от любого конечного числа переменных обозначается Р2.

Если X1 - фиктивная переменная функции Z =ƒ( X1, X2,...,Хn), то первая половина задающего ее столбца значений совпадает со второй, и если отбросить вторую половину таблицы этой функции и затем удалить 1-й столбец (состоящий из нулей), то останется таблица некоторой функции (n-1) переменных X2,...,Хn. Аналогично, если Xk - фиктивная переменная функции Z = ƒ( X1, X2,...,Хn) и вычеркнуть из таблицы столбец переменной Xk и все строки с единичным значением Хk (т.е. строки, в которых Хk=1), то останется таблица функции g ( X1, X2 ,..., Xk-1, Xk+1,..., Xn ). Будем говорить, что g получается из ƒ удалением, а ƒ из g - введением фиктивной переменной Хk .

Функции, которые могут быть получены друг из друга удалением и введением фиктивных переменных, считаются равными. Очевидно, равенство функций есть отношение эквивалентности на Р2, поэтому множество всех булевых функций разбивается на классы равных функций. В этом смысле, использованные выше записи g1 =X Z, g2 = ┐Y - правильны, т.е. функция g1 равна функции двух переменных Х Z , имеющей столбец значений (0111)Т, а функция g2 равна функции одной переменной Y , имеющей столбец значений (10)Т.

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

Высказывания и предикаты

Основным понятием математической логики является понятие высказывания.

Высказыванием называется повествовательное предложение, которое может быть либо истинным, либо ложным.

Пример

х+3=7 - не является высказыванием, так как истинность этого равенства зависит от значения х.

  1. х=4, 4+3=7 - истинное высказывание;
  2. х=9, 9+3=7 - ложное высказывание.

Предложения, в которые входят переменные и которые при замене этих переменных их значениями становятся высказываниями, называют высказывательными формами или предикатами. При этом должно быть задано множество X, которое может принимать переменная х, если предикат с одной переменной (одноместный предикат).

Множество Т значений переменной при подстановке которых в предикат получается истинное высказывание, называют множеством истинности предиката.

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

Если в предикат входят переменные x1, x2, :, xn, пробегающие соответственно множества X1, X2, :, Xn, то декартово произведение X1 X2 ... Xn является областью определения этого предиката, а множество Т кортежей (a1, a2 , :, an) таких, что при замене x1 на а1, x2 на a2, ...xn на an получается истинное высказывание - называют областью истинности предиката.

Будем обозначать:
А, В, ... - высказывания;
А(x), х Х - одноместный предикат;
B(x,y), x X,y Y - двуместным предикатом и т.д.,
А(а) - высказывание, получающиеся при замене в предикате А(х) переменной х на её значение а.

Кванторы

В формулировках различных математических предложений часто встречаются слова "некоторые", "все", "каждый" и их синонимы.

Рассматривая понятие высказательной формы (предиката), мы указали один из способов получения высказываний. Для этого достаточно в высказывательную форму F(x) подставить какое-нибудь значение переменной. Например, если дана высказывательная форма F(x): "х - четное число", то подставив в неё х=6 получим высказывание F(6): "6 - четное число", которое является истинным высказыванием, а высказывание F(5): "5 - четное число" -ложное высказывание.

Однако существуют и другие способы получения высказывательных форм (предикатов). Рассмотрим их.

  1. Пусть имеем предикат F(x), х Х. Тогда предложение "Для всех хХ истинно F(x)" - является высказыванием. Это высказывание обозначается (хХ) F(x).
    Замечание: Если заранее оговорено, для элементов какого множества Х рассматривают предикат F(x), то обозначение этого множества опускают и пишут (х) F(x).

    Символ (его обозначение связано с перевернутой первой буквой английского слова All - "все") называют квантором всеобщности, а присоединение этого символа к предикату F(x) - "навешиванием квантора всеобщности (или общности)". Квантор общности выражается с помощью слов "каждый", "всякий", "любой", "ни один".

  2. Из предиката F(x), xX можно получить другое высказывание. В множестве Х существует такой элемент а, что F(a) - истинное высказывание. Это высказывание обозначают:(хХ) F(x) или (x) F(x).

    Символ - называют квантором существования (такое обозначение происходит от перевернутой первой буквы английского слова Exist - "существовать"). Квантор существования выражается словами "некоторые", "найдется", "существует", "хотя бы один" и др.

Если воспользоваться принятыми обозначениями, то высказывание"Все целые числа кратны 3" можно записать так: (хZ) F(x), где F(x) - "число кратное 3", а высказывание "некоторые целые числа кратны 3" будет иметь вид: (хZ) F(x).

  1. На переменную х "навесили существования" или переменную х "связали квантором существования".
  2. Можно составить и такое высказывание "В множестве Х есть один и только один элемент а, такой что F(a) - истинное высказывание". Это высказывание обозначают: (Х) F(x).

Символ ! - называют квантором единственности.

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

При "навешивании" кванторов на переменные многоместных предикатов каждая переменная может быть связана своим квантором. При этом два квантора одного наименования:(х) (y) F(x,y) или (х) (y) F(x,y) - можно менять местами, при этом не меняется истинность высказывания. При "навешивании" разноименных кванторов нельзя менять их порядок, так как может измениться истинность высказывания.

Пример

F(x,y) - "человек х родился в году у".

Тогда (х) (y) F(x,y) - истинное высказывание, так как для каждого человека х есть год у, в котором он родился.

А высказывание (х) (у) F(x,y) - ложное, так как оно означает, что существует год у, в котором родился любой человек х.

Уже говорилось, что в математике одной из важнейших задач является установление значения истинности высказываний. Выясним, как устанавливают значения истинности высказываний с кванторами.

В высказывании (хХ) F(x) утверждается, что для любого х из множества Х истинно F(x), поэтому чтобы убедиться в истинности этого высказывания, надо показать, что множество Т истинности высказывательной формы F(x) совпадает с множеством X. Чтобы убедиться в ложности высказывания (хХ) F(x) достаточно показать, что ТХ, то есть доказать, что существует такое значение х, при котором высказывательная форма обращается в желаемое высказывание.

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

Выясним, как устанавливается значение истинности высказываний с квантором существования.

В высказывании (х) F(x) утверждается, что в множестве Х есть такой элемент х, который обладает свойством F. Поэтому оно будет истинно, если множество истинности высказывательной формы F(x) не пусто. Для того чтобы показать это, достаточно найти такое значение переменной х, при котором высказывательная форма F(x) обращается в истинное высказывание, то есть привести пример. Так, высказывание "некоторые натуральные числа двузначные" можно считать истинным, так как 36 действительно двузначное число.

Высказывание (х) F(x) ложно в том случае, когда Т=ø убедиться в этом можно лишь путем доказательства.

Таким образом, истинность высказывания с квантором существования устанавливается при помощи конкретного приема. Чтобы убедиться в ложности такого высказывания, необходимо провести доказательство.

 

Вопросы для самоконтроля

Основы алгебры логики
  1. Дайте определение истинного и ложного высказывания.
    Пpиведите примеры.
  2. Сформулируйте определение дизъюнкции, конъюнкции.
  3. Перечислите 16 логических функций, запишите их обозначения и истинность на различных наборах значений.
  4. Объясните в чём различие действительной и фиктивной функций.
Свойства элементарных функций алгебры логики
  1. Сформулируйте и запишите 8 основных аксиом.
  2. Запишите законы: Де Моргана и следствие из него, закон склеивания, закон поглощения.
  3. Воспризведите основные свойства функции сложения по модулю 2, функции импликации, функции Шеффера, функции Пирса.
Представление логических функций
  1. Дайте определение булевой функции.
  2. Сформулируйте принцип табличного представления функций.
  3. Дайте определение функций: Сумма по модулю 2, штрих Шеффера.

Практические задания

Tест для самоконтроля