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

1.1 Логические операции

1.2 Булевы функции

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

1.1 Логические операции. Алгебра логики – самый простой раздел математической логики. Язык алгебры логики является одним из простейших языков математики. Основными объектами данного раздела являются высказывания. Понятие «высказывание» является первичным, оно не определяется, а поясняется. Под высказыванием понимают предложение, о котором можно сказать одно из двух: истинно оно или ложно. Например, высказывание «2+3=5» – истинное, высказывание «существует действительное число Х такое, что

Х2 = –1» ложное. Очевидно, не каждое предложение является высказыванием. Например, предложения: «Когда ты был дома?», «Пойдем со мной!» не являются высказываниями. Высказывания будем обозначать малыми латинскими буквами X, y, z,…, а их значения, т. е. истину и ложь, соответственно 1 и 0. Из двух данных высказываний с помощью связок «не», «и», «или», «если … то», «тогда и только тогда, когда …» можно образовать новые высказывания. Например, из высказываний «число 2 простое», «число 2 четное» с помощью указанных выше связок получаем высказывания «число два простое и четное», «число 2 непростое», «число 2 простое или четное». Высказывание «если π иррационально, то π2 тоже иррационально» получается связыванием двух высказываний связкой «если … то». Эти операции соответствуют упомянутым выше связками, употребляемым в обычной речи.

Рассмотрим примеры логических операций.

1. Логическая операция, соответствующая связке «и», называется Конъюнкцией и обозначается &. В некоторых книгах эту операцию обозначают символом . Пусть X и y – высказывания. Высказывание X×y назовем конъюнкцией X И Y. Данное высказывание истинно тогда и только тогда, когда истинны оба высказывания X и Y.

Соответствующее определение запишем в виде таблицы истинности

X	Y	Xy
0	0	0
0	1	0
1	0	0
1	1	1

Определение конъюнкции двух высказываний естественным образом распространяется на любое конечное число высказываний.

Конъюнкция X1x2…xn, которую мы кратко обозначим через , истинна тогда и только тогда, когда истинны все высказывания.

2. Логическая операция, соответствующая связке «или», называется Дизъюнкцией и обозначается .

Пусть X и Y – высказывания. Высказывание XÚY назовем дизъюнкцией X и Y. Данное высказывание истинно тогда и только тогда, когда хотя бы одно из высказываний X и Y истинно.

Данное определение запишем в таблицы истинности.

X	Y	XY
0	0	0
0	1	1
1	0	1
1	1	1

Определение дизъюнкции двух высказываний естественным образом распространяется на любое конечное число высказываний. Дизъюнкция X1Ú X2 Ú … Ú XN, которую мы кратко обозначим через , истинна тогда и только тогда, когда хотя бы одно из высказываний X1, X2, …, XN истинно.

3. Логическая операция, соответствующая связке «не», называется Отрицанием.

Отрицание высказывания X записывается так: и определяется следующей таблицей истинности:

X
0	1
1	0

4. Логическая операция, соответствующая связке «если … то», называется Импликацией. Эту операцию будем обозначать символом _. При этом высказывание «если X, то Y» записывается в виде x_Y. Высказывание X называется посылкой импликации, Y – ее заключением. Импликация двух высказываний X и Y задается следующей таблицей истинности:

X	Y	X_Y
0	0	1
0	1	1
1	0	0
1	1	1

Из определения импликации вытекает, что:

· импликация с ложной посылкой всегда истинна;

· импликация с истинным заключением всегда истинна;

· импликация ложна тогда и только тогда, когда посылка истинна, а заключение ложно.

5. Логическая операция, соответствующая связке «тогда и только тогда, когда …» называется Эквивалентностью и обозначается символом n.

Пусть X и Y – высказывания. Высказывание XNY назовем эквивалентностью X и Y. Данное высказывание истинно тогда и только тогда, когда оба высказывания X и Y или истинны или ложны.

Данное определение запишем в виде таблицы истинности:

X	Y	XNY
0	0	1
0	1	0
1	0	0
1	1	1

1.2 Булевы функции. Пусть исходный алфавит переменных.

Функцией алгебры логики От переменных называется функция, принимающая значения 1, 0 и аргументы которой также принимают значения 1, 0.

Обычно функции алгебры логики называют булевыми функциями. Название «булевы функции» возникло в связи с использованием функций рассматриваемого типа в алгебре логики, начало которой было положено трудами ирландского ученого 19 века Дж. Буля. Областью определения булевой функции от n переменных служат совокупность всевозможных n-мерных упорядоченных наборов , где .

Следует отметить, что любой такой набор можно рассматривать как представление некоторого целого неотрицательного числа в двоичной системе счисления. Например, набору (0,1,0,1) соответствует число , а набору (1,1,1) – число .

Все наборы размерности n нумеруются целыми числами от 0,2n-1. Отсюда нетрудно заметить, что число таких наборов равно 2n.

Всякая булева функция от n переменных может быть задана с помощью таблицы истинности:

Таблица 1

X1	X2	…	XN-1	XN	F(X1,X2,…,XN-1,XN)
0	0	…	0	0	F (0,0,…,0,0)
0	0	…	0	1	F (0,0,…,0,1)
0	0	…	1	0	F (0,0,…,1,0)
…	…	…	…	…	…
1	1	…	1	1	F (1,1,…,1,1)

Данная таблица состоит из 2n строк, причем в ней все наборы расположены в порядке возрастания их номеров.

Очевидно, что булевы функции от n переменных однозначно определяются своими последними столбцами из таблицы 1, т. е. наборами из 2n нулей и единиц. Следовательно, различных булевых функций от n переменных будет столько, сколько имеется различных наборов длины 2n, а их число равно . Итак, мы доказали следующую теорему:

Теорема 1. Имеется точно Булевых функций от Переменных.

В алгебре логики особое значение имеют следующие булевы функции, которые называют элементарными булевыми функциями.

- константа 0;

- константа 1;

- тождественная функция;

- отрицание х;

- конъюнкция X и y;

- дизъюнкция х и у;

- импликация х и у;

- эквивалентность х и у;

- сложение х и у по mod2;

- функция Шеффера;

- стрелка Пирса.

Последние три функции задаются следующими таблицами истинности:

0	0	0	1	1
0	1	1	1	0
1	0	1	1	0
1	1	0	0	0

Введенное понятие булевой функции несовершенно тем, что оно не позволяет рассматривать функцию от меньшего числа аргументов как функцию от большего числа аргументов. Для устранения этого недостатка введем понятие фиктивной переменной.

Переменная XI в функции называется Фиктивной, если = при любых значениях остальных переменных. В этом случае функция , по существу, зависит от (n-1) – переменной, т. е. представляет собой функцию от (n-1) переменной. Говорят, что функция g получается из функции f удалением фиктивной переменной, а функция f получается из g введение фиктивной переменной, причем эти функции являются равными.

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

< Предыдущая		Следующая >