1. Методические указания

1.1. Логические функции

Пусть имеется функция, заданная на некотором множестве М. Функция называется логической, если она принимает значения в конечном множестве N. Если множество N содержит п элементов, то логическая функция называется п-значной. Перечень всех символов, соответствующих области значений логической функции, называется алфавитом, а сами элементы множества N – буквами этого алфавита. Логическая функция называется однородной, если её аргументы принадлежат тому же множеству, что и значение функции. Однородная функция двух переменных может быть задана таблицей соответствия (матрицей), строки и столбцы которой соответствуют буквам алфавита. Таким образом можно определять функции одной и двух переменных.

Наиболее простым и в то же время важнейшим классом однородных функций являются двузначные (булевы) функции. Областью определения булевых функций от п переменных слу­жит множество слов длины п. Они представляют собой всевозмож­ные наборы из п двоичных цифр и их общее количество равно .

Число всевозможных булевых функций п переменных быстро возрастает с увеличением п (при п = 3 оно равно 256, а при п = 5 превышает 4 миллиарда). Но функции одной и двух перемен­ных еще можно перечислить и подробно исследовать, так как их количество сравнительно невелико (v = 4 при п = 1 и v = 16 при п = 2).

Общая таблица соответ­ствия для булевых функций одной переменной имеет следующий вид (справа указаны обозначения функций):

Таблица 1 – Булевы функции одной переменной

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

Единственной нетривиальной функцией является , назы­ваемая отрицанием или инверсией. Она равна 1, когда аргумент принимает значение 0, и равна 0 при аргументе 1.

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

Таблица 2 - Булевы функции двух переменных

	0	0	1	1	Обозначение	Название
	0	1	0	1
	0	0	0	0	0	Константа 0 (тождественный 0)
	0	0	0	1		Конъюнкция (логическое «и», произведение)
	0	0	1	0		Отрицание импликации
	0	0	1	1		Повторение первого аргумента
	0	1	0	0		Отрицание обратной импликации
	0	1	0	1		Повторение второго аргумента
	0	1	1	0		Сумма по модулю два (антиэквивалентность, неравнозначность)
	0	1	1	1		Дизъюнкция (логическое «или», логическая сумма)
	1	0	0	0		Стрелка Пирса (отрицание дизъюнкции, логическое «не-или»)
	1	0	0	1		Эквиваленция (равнозначность)
	1	0	1	0		Отрицание (инверсия) второго аргумента
	1	0	1	1		Обратная импликация
	1	1	0	0		Отрицание (инверсия) первого аргумента
	1	1	0	1		Импликация (следование)
	1	1	1	0		Штрих Шеффера (отрицание конъюнкции, логическое «не-и»)
	1	1	1	1	1	Константа 1 (тождественная 1)

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

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

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

- коммутативность
- ассоциативность
- дистрибутивность
- свойства констант
- свойства отрицания
-закон двойного отрицания
- законы де Моргана
- законы идемпотентности
- законы поглошения

Использование тождеств существенно упрощает запись логических формул.

Из свойств, при­веденных выше видно, что в булевой алгебре имеет место, принцип двойственности. Взаимно двой­ственными операциями являются дизъюнкция и конъюнкция. За­меняя в некоторой формуле каждую операцию на двойственную ей, получаем двойственную формулу. Например, из формулы имеем .

На основе законов де Моргана выводится следующее положение: если и - двойственные формулы, то равносильна . Отсюда следует, что

=

т. е. двойственная формула выражается как отрицание формулы, полученной из исходной замещением каждой переменной ее отри­цанием. Таблица соответствия двойственной функции получается заменой аргументов и значений в исходной функции на противополож­ные, т. е. 0 заменяется на 1, а 1 - на 0. Если формулы и равносильны, то и двойственные им формулы и также равносильны.

Формула или функция, равносильная своей двойственной, называется самодвойственной. Самодвойственная функция на инверсных наборах принимает инверсные значения.