5.2 Логические переменные и логические функции. Алгебра логики

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

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

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

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

• функция Y₀(X) = 0 – функция «константа 0», принимающая значение 0, независимо от своего аргумента (т.е. от переменной X);

• функция Y₁(X) = X – функция «повторение аргумента», принимающая то же значение, что и ее аргумент (т.е. переменная X);

• функция Y₂(X) = – функция «отрицание», принимающая значение 1, еслиX=0, и значение 0, если X=1;

• функция Y₃(X) = 1 – функция «константа 1», принимающая значение 1, независимо от своего аргумента (т.е. от переменной X).

Пусть X1 и X2 – логические переменные. Можно задать 16 логических функций, принимающих значения 0 или 1 в зависимости от значений двух логических переменных. Эти логические функции (называемые также логическими операциями) описаны в таблице 5.2.

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

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

Таблица 5.2 – Логические функции двух переменных

Значения переменных	X1	0	0	1	1	Название функции	Описание функции
	X2	0	1	0	1
Функции	Y0(X1,X2) = = 0	0	0	0	0	Константа 0	Принимает значение 0, независимо от своих аргументов (т.е. от переменных X1иX2)
	Y1(X1,X2) = = X1 & X2	0	0	0	1	Конъюнкция	Принимает значение 1, только если оба аргумента (т.е. переменные X1иX2) принимают значение 1
	Y2(X1,X2) = = X1 ← X2	0	0	1	0	Запрет первого аргумента	Переменная X2«запрещает» переменнуюX1: когдаX2=1 (запрет действует), функция принимает значение 0, а когдаX2=0 (запрет не действует), функция принимает значениеX1
	Y3(X1,X2) = = X1	0	0	1	1	Повторение первого аргумента	Принимает значение X1, независимо от значенияX2
	Y4(X1,X2) = = X2 ← X1	0	1	0	0	Запрет второго аргумента	Аналогична функции Y2(X1,X2), но в данном случае переменнаяX1запрещает переменнуюX2
	Y5(X1,X2) = = X2	0	1	0	1	Повторение второго аргумента	Принимает значение X2, независимо от значенияX1
	Y6(X1,X2) = = X1  X2	0	1	1	0	Исключающее ИЛИ	Принимает значение 1, если аргументы принимают разные значения (один – 1, другой – 0)
	Y7(X1,X2) = = X1  X2	0	1	1	1	Дизъюнкция	Принимает значение 1, если хотя бы один из аргументов (т.е. переменных X1иX2) принимает значение 1
	Y8(X1,X2) = = X1 ↓ X2	1	0	0	0	Стрелка Пирса (НЕ-ИЛИ)	Принимает значение 1, только если оба аргумента принимают значение 0
	Y9(X1,X2) = = X1 ~ X2	1	0	0	1	Эквивалентность	Принимает значение 1, если аргументы принимают одинаковые значения
	Y10(X1,X2) = =	1	0	1	0	Отрицание второго аргумента	Принимает значение , независимо от значенияX1
	Y11(X1,X2) = = X2 → X1	1	0	1	1	Импликация	Принимает значение 0, только если X2= 1, аX1= 0
	Y12(X1,X2) = =	1	1	0	0	Отрицание первого аргумента	Принимает значение , независимо от значенияX1
	Y13(X1,X2) = = X1 → X2	1	1	0	1	Импликация	Принимает значение 0, только если X1= 1, аX2= 0
	Y14(X1,X2) = = X1 | X2	1	1	1	0	Штрих Шеффера (НЕ-И)	Принимает значение 0, только если оба аргумента принимают значение 1
	Y15(X1,X2) = = 1	1	1	1	1	Константа 1	Принимает значение 1, независимо от своих аргументов (т.е. от переменных X1иX2)

Пример 5.2 – Построить таблицу истинности для следующей логической функции: (A ↓ B)  (A ← B), где A, B – логические переменные.

Таблица истинности для рассматриваемой функции приведена в таблице 5.5.

Таблица 5.3 – Таблица истинности для примера 5.2

A	B	A ↓ B	A ← B	(A ↓ B)  (A | B)
0	0	1	0	1
0	1	0	0	0
1	0	0	1	1
1	1	0	0	0

Поясним построение таблицы истинности. В столбцах A и B указываются все возможные комбинации значений переменных A и B. Таких комбинаций четыре: A=0, B=0; A=0, B=1; A=1, B=0; A=1, B=1. Затем составляются таблицы истинности для функций A ↓ B (стрелка Пирса) и A ← B (запрет) согласно определениям этих функций, приведенным в таблице 5.2. Заполняются столбцы A ↓ B и A ← B. Затем определяются значения функции (A ↓ B)  (A ← B); для этого используются значения (A ↓ B) и (A ← B), найденные ранее, и для них определяются значения функции  (неравнозначность).

Из таблицы 5.2 видно, что значения функции (A ↓ B)  (A ← B) во всех случаях получились точно такими же, как величина . Другими словами, функции (A ↓ B) и (A ← B) и эквивалентны: (A ↓ B)  (A ← B) = .

Пример 5.3 – Построить таблицу истинности для следующей логической функции: X₁ ← (X₂ & X₃), где X₁, X₂, X₃ – логические переменные.

Таблица истинности для рассматриваемой функции приведена в таблице 5.4.

Таблица 5.4 – Таблица истинности для примера 5.3

X1	X2	X3	X2 & X3	X1 ← (X2 & X3)
0	0	0	0	0
0	0	1	0	0
0	1	0	0	0
0	1	1	1	0
1	0	0	0	1
1	0	1	0	1
1	1	0	0	1
1	1	1	1	0

Здесь в столбцах X₁, X₂, X₃ перечислены все возможные комбинации значений этих переменных (таких комбинаций - восемь). Затем составляется таблицы истинности для функции X₂ & X₃ (конъюнкция). Затем определяются значения функции X₁ ← (X₂ & X₃) согласно определению функции «запрет», причем для этого используются значения X₂ & X₃, найденные ранее.