2014-02-13
1097
С увеличением числа переменных число различных логических функций очень быстро растет, и изучить все их особенности невозможно. Однако нетрудно показать, что любую функцию, зависящую от n переменных (n > 2), можно выразить через функции, зависящие от одной или двух переменных. Поэтому логические функции, зависящие от одной или двух переменных, занимают особое место в алгебре логики. Их называют элементарными логическими функциями. Рассмотрим их кратко.
Функции одной переменной приведены в таблице 2.9. Их всего 
. Две из них – 
и 
– не зависят от x. Они называются соответственно нулевой функцией – константой 0 и единичной функцией – константой 1.
| Таблица 2.9 | ||||||||
| fi | Наборы x | Формула | Название функции | |||||
| Нулевая | |||||||
| x | Повторение | ||||||
| 
| Инверсия (функция НЕ) | ||||||
| Единичная |
Значение функции 
совпадает со значением переменной. Это – функция повторения.
Значение функции 
противоположно (инверсно) значению переменной x. Это – функция отрицания (инверсия, функция НЕ).
Отметим, что для каждой функции одной переменной существует инверсная ей функция
Логических функций от двух переменных всего 
Шесть из них являются вырожденными функциями, зависящими от одной переменной:
Остальные десять функций зависят от двух переменных.
Полный перечень всех функций от двух переменных приводится в таблице 2.10. Наиболее важные из них следующие.
Функция 
принимающая значение 1 на наборе 11, а на остальных наборах равная 0, носит название к о н ъ ю н к ц и и (логическое умножение, функция И). Для ее обозначения применяют символы 
&, точку или вообще опускают всякий символ между переменными, например:
Функция 
принимающая значение 1, когда либо x 1 = 1, либо x 2 = 1, носит название д и з ъ ю н к ц и и (логическое сложение, функция ИЛИ). Для ее обозначения применяют символы 
«+» между переменными x 1 и x 2, например:
Функция 
принимающая значение 1 на наборе 00, а на остальных наборах равная 0, носит название функции ИЛИ-НЕ (стрелка Пирса, функция Вебба) и обозначается так:
↓
Функция 
принимающая значение 0 на наборе 11, а на остальных наборах равная 1, носит название функции И-НЕ (функция Шеффера, штрих Шеффера) и обозначается следующим образом:
Кроме того, имеются функции:
~
– функция эквивалентности (равнозначности);
– сложение по модулю два (функция неэквивалентности, неравнозначности);
– импликация x 2 в x 1;
– импликация x 1 в x 2;
– запрет x 2;
– запрет x 1.
В таблице 2.10 номер функции соответствует весовому состоянию строки значений функции на различных наборах x 1 и x 2 при базе 20212223.
Значения рассмотренных функций одной и двух переменных состоит в том, что из них может быть построена произвольная логическая функция, зависящая более чем от двух переменных.
Элементарные логические функции позволяют получать (определять) сложные функции путем подстановки в данную функцию вместо ее переменных других функций. Такой метод называется методом с у п е р п о з и ц и и функции, а сложная функция, полученная таким методом, носит название суперпозиции использованных элементарных функций.
Например, имея элементарные функции
можно, пользуясь принципом суперпозиции, получить новые функции:
Функция f 3 получена путем подстановки в функцию f 1 вместо переменной x 2 функции f 2. Функция f 4 получена путем подстановки в функцию f 2 вместо переменной x 3 функции f 1.
При использовании принципа суперпозиции возникает вопрос, каким должен быть состав элементарных логических функций, которые позволяют с их помощью построить произвольную логическую функцию, зависящую от конечного числа переменных.
| Таблица 2.10 | |||||||||
| Наборы | Обозначение | Название функции | Формула | ||||||
| x 1 | |||||||||
| x 2 | |||||||||
|
|
| Константа 0 | 
| ||||||
|
|  ↓
| Функция Пирса, ИЛИ-НЕ | 
| ||||||
|
| 
| Запрет x 2 | 
| ||||||
|
| 
| Отрицание x 2 | 
| ||||||
| 
| Запрет x 1 | 
| ||||||
| 
| Отрицание x 1 | 
| ||||||
| 
| Сложение по мо- дулю 2 (неравнозначность) | 
| ||||||
| 
| Функция Шеффера, И-НЕ | 
| ||||||
| 
| Конъюнкция, И | 
| ||||||
|  ~
| Эквивалентность (равнозначность) | 
| ||||||
| 
| Повторение x 1 | 
| ||||||
| 
| Импликация x 2 в x 1 | 
| ||||||
| 
| Повторение x 2 | 
| ||||||
| 
| Импликация x 1 в x 2 | 
| ||||||
| 
| Дизъюнкция, ИЛИ | 
| ||||||
| 
| Константа 1 | 
|
В алгебре логики рассматриваются различные классы логических функций.
Основными из них являются:
1. Класс функций, сохраняющих константу 0. Это функции, которые на наборе переменных 00…0 имеют значение, равное 0, например функция f = x 1 x 2.
2. Класс функций, сохраняющих константу 1. Это функции, которые на наборе переменных 11…1 имеют значение, равное 1, например функция f = x 1 x 2.
3. Класс самодвойственных функций.
Предварительно укажем, что две функции алгебры логики – 
и 
– называются двойственными, если имеет место равенство
т.е. если одна функция получается из другой заменой всех операций конъюнкции на операции дизъюнкции и наоборот. Например, функции 
и 
двойственны, так как 
Логическая функция называется самодвойственной, если она двойственна по отношению к самой себе, т.е. имеет место соотношение
Например, функция 
является самодвойственной, так как
4. Класс линейных функций. Функция называется линейной, если возможно представление ее в виде
где k 0, k 1, k 2 – двоичные постоянные (0 или 1).
5. Класс монотонных функций. Функция называется монотонной, если имеет место равенство
при 
Система элементарных логических функций называется функционально полной, если любая логическая функция может быть представлена в виде суперпозиции функций этой системы.
Функционально полная система логических функций называется минимальной, если удаление из нее хотя бы одной функции превращает систему в неполную.
Критерий полноты системы функций алгебры логики устанавливает теорема Поста-Яблонского, по которой для полноты системы логических функций необходимо и достаточно, чтобы она содержала следующие функции: не сохраняющую константу «нуль», не сохраняющую константу «единица», не являющуюся самодвойственной, не являющуюся линейной, не являющуюся монотонной, т.е. каждое из перечисленных выше свойств не принадлежало бы какой-либо из функций в этой системе.
Наибольшее распространение в теории и практике дискретных устройств, особенно с точки зрения технической реализации, получили функционально полные системы, состоящие из двух функций:
- функции И и НЕ;
- функции ИЛИ и НЕ;
состоящие из одной функции:
- функции И-НЕ;
- функции ИЛИ-НЕ
и состоящие из трех функций:
- функции И, ИЛИ, НЕ.
Последняя полная система функций не является минимальной, но зачастую весьма удобная для представления сложных функций. Она иногда называется «основной».
