f (x1,..., xn )

196 Информатика и математика

Из элементарных высказываний можно составить сложные высказывания с помощью логических операций. Все операции в логике высказываний описываются только таблицей истинности.

Функция называется n–местной булевой функцией, если

каждая переменная принимает только два значения 0 или 1 и функция принимает значения в этом же множестве {0;1}.

1. Отрицание

Для логической операции «отрицание» таблица истинности выглядит следующим образом:

А		А
0		1
1		0

Иллюстрацией отрицания в естественном языке служит частица «не» или слова «неверно, что».

Покажем, что А = А:

А		А			А
0		1			0
1		0			1

2. Конъюнкция

Введем еще одну логическую операцию, определив ее словесно следующим образом. Конъюнкция двух высказываний истинна тогда и только тогда, когда оба высказывания истинны. Эта логическая операция называется еще логическим умножением, или логическим минимумом. Выпишем таблицу истинности для конъюнкции:

А	В	А& В
0	0	0
0	1	0
1	0	0
1	1	1

Свойства конъюнкции:

А&1 = А;	А&	А	= 0 ;
А& 0 = 0 ;	А& А= А.

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

3. Дизъюнкция

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

2. План-конспект лекционного курса	197

значается эта операция знаком и иногда называется логическим сложением или логическим максимумом. Таблица истинности дизъюнкции выглядит так:

	А	B		А B
	0	0		0
	0	1		1
	1	0		1
	1	1		1
Укажем свойства этой операции:
А 1 =1;				А			=1 ;
						А
А 0 = A ;				А А= А.
4. Импликация
A1 A2 ... An истинна,		если	Ai −истинно

Следующая логическая операция, которую мы рассмотрим, – это операция импликации. Импликация ложна тогда и только тогда, когда А – истинно, а B – ложно.

А	B	A → B
0	0	1
0	1	0
1	0	1
1	1	1

Это выражение читается так: если А, то B . В таком виде часто формулируются математические теоремы. Если теорема сформулирована какнибудь иначе, то ее можно перефразировать в указанном виде, не теряя сущности.

В математических терминах импликация еще обозначается фразами:

B– следствие А;

А– достаточное условие B .

Импликацию тоже можно выразить через &, ,¬

A → B = A & B = A B .

5. Эквивалентность

Она истинна только тогда, когда значения А и B совпадают. Эту операцию еще иногда называют логическим равенством:

А	B	А↔ B
0	0	1

198			Информатика и математика
	0	1	0
	1	0	0
	1	1	1

В математических терминах эта операция интерпретируется в качестве фраз «тогда и только тогда», «необходимо и достаточно». Такая форма тоже очень часто используется в формулировке теорем. Эквивалентность представляется в виде:

А↔ B = (А→ В)& (B → A) ,

т.е. из А следует B и из B следует А.

Алфавитом называется любой непустой набор символов. Элементы этого набора называются символами алфавита.

Словом в алфавите G называется произвольная конечная (возможно пустая) последовательность символов из G . Фиксируем некоторый конечный или счетный алфавит переменных X = (x1, x2 ,...) .

Формула алгебры логики определяется следующим образом (индуктивное определение):

•любая логическая переменная есть формула;

•если А – формула, то (А) – формула (допустимы технические сим-

волы);

•если А и B – формулы, то А, B, A & B, A B, A → B, A ↔ B, A B, A/ B – тоже формулы (допустимы все логические связки);

•других формул нет.

Подформулой формулы А называется любое подслово слова А, которое само является формулой.

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

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

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

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

•отрицание;

•конъюнкция;

•дизъюнкция;

•импликация и эквивалентность в порядке их записи.

Формула называется тождественно истинной или тавтологией, если она реализует функцию «тождественная единица», и тождественно ложной, если 0.

2. План-конспект лекционного курса	199

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

Пример. Составим таблицу истинности следующей формулы:

(X →Y )& (Y → Z ):

																													(X →Y )& (Y → Z )
				X																			Y		Z	(X →Y )		(Y → Z )
																													1
	0																						0		0	1		1
	0																						0		1	1		1	1
	0																						1		0	1		0	0
	0																						1		1	1		1	1
	1																						0		0	0		1	0
	1																						0		1	0		1	0
	1																						1		0	1		0	0
	1																						1		1	1		1	1
	Всякий раз, вводя логическую операцию, учитываем их свойства:
		A&								= 0 – закон исключенного противоречия;
					A
		A								=1– закон исключенного третьего;
				A
	законы идемпотентности:
		A& A = A ,
		A A = A ;
	законы отрицания:
										=											,
		A& B										A							B
							=							&						;
		A B									A							B
	закон навешивания двойного отрицания:
		A =						;
				A
	закон контрапозиции:
		A → B =														→							.
													B									A
Теперь выпишем законы Булевой алгебры:
Коммутативный закон																												Ассоциативный закон
X Y =Y X																										(X Y ) Z = X (Y Z )
X &Y =Y & X																										(X &Y )& Z = X & (Y & Z )
Дистрибутивный закон																												Законы поглощения
X & (Y Z )= (X &Y ) (X & Z )																										X & (Y X )= X
X (Y & Z )= (X Y )& (X Z )																										X (Y & X )= X

Выпишем приведенные ранее выражения операций через &, ,¬

A ↔ B = (A → B)& (B → A)= (A & B) (A & B) A → B == A & B = A B